A while ago a friend of mine texted me asking the continuation of the following sequence:

1, 9, 16, 23, ...

I scribbled the following on my scratch paper:

1 9 16 23 ...
 8 7  7 ...

So, I thought the continuation would be 29, 35, 40, 45, and so on since:

1 9 16 23 29 35 40 45 41 37...
 8 7  7  6  6  5  5  4  4...

But, my friend told me that the difference should be:

8,
7, 7,
6, 6, 6,
5, 5, 5, 5, ...

to which I agreed since it had a good pattern.

Next, she asked me whether 9 should be removed from the following sequence:

1, 8, 9, 27, 64, 125 ...

So, I tried to figure out the difference between having 9 and not:

1  8  27  64  125 ...
 7  19  37  61 ...
  12  18  24 ...
    6   6 ...

vs.

1  8  9  27  64  125 ...
 7  1  18  61 ...
  13  18  24 ...
    5   6 ...
      1 ...

Since I saw that the one without 9 had a good pattern of repeating 6s, I answered that 9 should be removed.
But, I asked her about the function that generated the sequence since I was sure that there was one.
After some minutes waiting for her response, I realized that it was f(x) = x^3 where x is an integer greater than zero.

At this point, I recalled that I had ever had read an article on Charles Babbage's difference engine on http://en.wikipedia.org.
An interesting point from the engine that I remembered was that it could calculate the results of a polynomial function just by moving different sizes of gears because the results of a polynomial function had a constant difference.

Since I would like to see that interesting point at work, I experimented with it a bit.

f(x) = x where x is an integer greater than zero:

1 2 3 4 5 ...
 1 1 1 1 ...

f(x) = x^2 where x is an integer greater than zero:

1  4  9  16  25  36  ...
 3  5  7   9   11  ...
  2  2  2   2    ...

f(x) = x^3 where x is an integer greater than zero:

1  8  27  64  125 ...
 7  19  37  61 ...
  12  18  24 ...
    6   6 ...

From those three experiments, I concluded the following interesting properties for x^n:
1. n signifies the depth at which the difference will be constant.
2. the repeating constant at that particular depth is the fingerprint of function f(x) = x^n.

With those two properties, I could find the generating function of any integer sequence resulting from a polynomial function as far as enough numbers are given.

For example, given a sequence: 16, 49, 126, 265, ..., the generating function can be found as follows:

16   49   126   265   484   ...
  33   77    139   219   ...
    44   62     80    ...
      18   18     ...

Since the repeating depth is 3, it can be concluded that the degree of the generating function is 3.
The fingerprint of a 3rd-degree polynomial function is 6.
Since the repeating constant is 18, the coefficient for the cubed term is 18 / 6 = 3.
IOW, the first term of the generating function is 3x^3.

To get the other terms, we subtract the value of 3x^3 from the sequence as follows:

16   49   126   265   484   ...
 3   24    81   192   375   ...
------------------------------- -
13   25    45    73   109

We need to subtract because of the following relationship:

3(1)^3 + g(1) = 16   =>   g(1) = 16 - 3(1)^3

Continuing the search:

13   25    45    73   109
  12   20    28    36
    8    8     8

The next term is 4x^2. f(x) = 3x^3 + 4x^2 + g(x).

13   25    45    73   109
 4   16    36    64   100   ...
------------------------------- -
 9    9     9     9     9

Because it has no repetition depth, the last term is a constant of value 9.

Therefore, the generating function is f(x) = 3x^3 + 4x^2 + 9.

It can be seen that each sequence uniquely corresponds to a certain generating function.