Mathematrec

I guess it's just finite differences, right? If you have numbers generated by a polynomial of degree \(n\) then the \(n^{th}\) order differences are constant. For instance, take \(g(n)=n^3+6n^2-4n-3\). Plugging in 0, 1, 2... you get

-3, 0, 21, 66, 141, 252, 405, 606...

Take differences between successive numbers and you get

3, 21, 45, 75, 111, 153, 201...

And repeat

18, 24, 30, 36, 42, 48...

And repeat

6, 6, 6, 6, 6...

Looking at it the other way, if you start with a constant sequence and repeatedly construct sequences that have the previous sequence as their differences, then each sequence (which is generated by a successively higher degree polynomial) depends only on the starting values of the sequences and the number of sequences. In the above case we know the first sequence if we know it's the fourth sequence and the four sequences start with -3, 3, 18, and 6.

Now, if you have a sequence that begins with \(m\) powers of 2, then its differences start with \(m-1\) powers of 2, the second order differences start with \(m-2\) powers of 2, and so on. So each sequence starts with a 1. The earliest possible constant sequence eventually arrived at must be

1, 1, 1, 1, 1...

The prior one is (starting with 1, then adding 1, then adding 1 again, then adding 1 again...)

1, 2, 3, 4, 5, 6...

then (start with 1, add 2, add 3...)

1, 2, 4, 7, 11, 16, 22...

then

1, 2, 4, 8, 15, 26, 42, 64...

then

1, 2, 4, 8, 16, 31, 57, 99, 163...

and so on. It's easy to show by induction each sequence starts with \(m\) powers of 2 followed by \(2^m-1\).

So the simplest polynomial that starts by generating powers of 2 will then generate 1 less than the next power of 2. You could have a polynomial that for instance generates 1, 2, 4, 8, 16, 242251… but it would be a higher degree polynomial because the fourth order differences would not be constant.