Difference Tables: Finding Polynomial & Exponential Functions

[Nimz]

It's well known that difference tables can be used to find polynomial functions that go with a sequence of numbers. E.g:
0 1 4 9 16 25 ...
1 3 5 7 9 ...
2 2 2 2 ...
0 0 0 ...
The polynomial can be recovered by taking 0*1 + 1*x + 2*x(x-1)/2! + 0*x(x-1)(x-2)/3! + 0 ... = x + x^2 - x = x^2

If the function is not polynomial, though, the difference table never terminates. I have been looking at when the function is an exponential and have found some curious properties. First, the sequence going down the first diagonal, which would normally be used to reconstruct the polynomial, is also an exponential, with the base reduced by 1.

1 3 9 27 81 243 ...
2 6 18 54 162 ...
4 12 36 108 ...
8 24 72 ...
16 48 ...
32 ...

This is easily proven in general. I think I've found a method of taking a sequence and iteratively make difference tables for it to determine its function. If the function is a sum of exponentials, all with whole number bases, it's fairly easy. The product of a polynomial with an exponential is a bit less trivial, but still fairly easy to do. I've figured out how to do a few special cases of a sum of these products, but I'm having trouble generalizing those special cases. For instance, the sequence 0, 7, 68, 435, 2320, 11195, 50820, 221851, ... can be found to be x^2 * 3^x + x * 4^x, but I'm having a terrible time getting that 1, 6, 32, 136, 512, 1824, 6400, 22656, 81920, ... is x^2 * 2^x + 4^x from the difference tables.

I'm not sure whether what I'm doing is novel, so if any of you know of something like this being done before, I'd love to find out. And if any of you are interested in the methods I've used to determine the functions, I'll be happy to expound.

Btw, sorry about the formatting - I haven't had the chance to figure out how to make this look pretty yet.

 

[Nimz]

Let's see. I looked at the first 400 or so posts on the LaTex tutorial page. Maybe I can make this look prettier. Here's the first difference table, hopefully formatted how I wanted it:
$$\begin{gather*} 0 \, 1 \, 4 \, 9 \, 16 \, 25\, \dots \\ 1 \, 3 \, 5 \, 7 \, 9 \, \dots \\ 2 \, 2 \, 2 \, 2 \, \dots \\ 0 \, 0 \, 0 \, \dots \end{gather*}$$

- edit -
well, not quite a complete success, but not a complete failure, either. The original function can be recovered by adding $0 \cdot \binom{x}{0} + 1 \cdot \binom{x}{1} + 2 \cdot \binom{x}{2} + 0 \cdot \dots = x^2$. Let's see about the other difference table:

$$\begin{array}{c c c c c c c c c c c c} 1 && 3 && 9 && 27 && 81 && 243 & \dots \\ & 2 && 6 && 18 && 54 && 162 & \dots \\ & & 4 && 12 && 36 && 108 & \dots \\ & & & 8 && 24 && 72 & \dots \\ & & & & 16 && 48 & \dots \\ & & & & & 32 & \dots \end{array}$$

Much better! So, is anyone interested in how I determined $x^2 3^x + x4^x$ or where my woes with $x^2 2^x + 4^x$ appeared?

 

[0rthodontist]

Yes, this is interesting. How much calculation do you have to do to find x^2 * 3^x + x * 4^x?

 

[Nimz]

I had a response written out, describing how I culled $x^2 3^x + x4^x$ out of 0, 7, 68, 435, 2320, 11195, 50820, 221851, ..., but I lost the post when I got logged out
I'm a bit frustrated at the moment, so I'll come back to it in a few hours.

For the moment, though, I'll at least give some of my motivation for trying this. First of all, I noticed that the difference table for 2^x looks the same, regardless of what row you start with. I wondered if 3^x might do the same, and found I was wrong. No big surprise, in retrospect.

Euler found an interesting family of rational functions that were generating functions for sums of powers. The denominator is arrived at easily enough, but the numerator is a bit trickier. As homework, I found a way to determine the coefficients in the numerator, but it was iterative. It would be really nice to find a closed form. The first non-obvious sequence of coefficients is 1, 11, 66, 302, 1191, 4293, 14608, 47840, 452637, ..., which I finally determined to follow the formula: $3^{x+3} - 2^{x+3}(x+4) + \frac{(x+3)(x+4)}{2}$, by using my method of multiple difference tables. I haven't had time to prove it yet, but I'm pretty confident in that result. With that result, I also have a conjecture for all the sequences of coefficients now.

I know there are other methods of determining the closed form for exponential functions that can be applied to iterative forms. I don't remember how to use them off hand, though. Rather than look up the other methods, I figured I'd work out how to do it with difference tables, possibly paving some new ground

 

[Nimz]

I wrote this whole thing out in Notepad before logging in this time. That ought to prevent the earlier mishap :grumpy:

I tested $x^2 3^x + x 4^x$ see how far my ideas for determining the function for a sequence could go. As I knew the answer a priori, this was a test to see if I could identify the answer in the tables. To start with, I wrote the sequence with its difference table. I figured eight terms should be enough to find the pattern:

$$\begin{array}{ccc ccc ccc ccc ccc} 0 && 7 && 68 && 435 && 2320 && 11195 && 50820 && 221851 \\ & 7 && 61 && 367 && 1885 && 8875 && 39625 && 171031 \\ && 54 && 306 && 1518 && 6990 && 30750 && 131406 \\ &&& 252 && 1212 && 5472 && 23760 && 100656 \\ &&&& 960 && 4260 && 18288 && 76896 \\ &&&&& 3300 && 14028 && 58608 \\ &&&&&& 10728 && 44580 \\ &&&&&&& 33852 \end{array}$$

There is no obvious pattern that I could see in the \ oriented diagonals, so I made a new difference table, taking the first diagonal of this table to be the first row of the new table:

$$\begin{array}{ccc ccc ccc ccc ccc} 0 && 7 && 54 && 252 && 960 && 3300 && 10728 && 33852 \\ & 7 && 47 && 198 && 708 && 2340 && 7428 && 23124 \\ && 40 && 151 && 510 && 1632 && 5088 && 15696 \\ &&& 111 && 359 && 1122 && 3456 && 10608 \\ &&&& 248 && 763 && 2334 && 7152 \\ &&&&& 515 && 1571 && 4818 \\ &&&&&& 1056 && 3247 \\ &&&&&&& 2191 \end{array}$$

Nothing seems to be standing out, so I repeated the process:

$$\begin{array}{ccc ccc ccc ccc ccc} 0 && 7 && 40 && 111 && 248 && 515 && 1056 && 2191 \\ & 7 && 33 && 71 && 137 && 267 && 541 && 1135 \\ && 26 && 38 && 66 && 130 && 274 && 594 \\ &&& 12 && 28 && 64 && 144 && 320 \\ &&&& 16 && 36 && 80 && 176 \\ &&&&& 20 && 44 && 96 \\ &&&&&& 24 && 52 \\ &&&&&&& 28 \end{array}$$

The first diagonal is starting to have spots where it decreases, which is behavior that hasn't been seen so far. I started the next difference table, but stopped at the third row, since an infinite sequence of zeros appeared at that point:

$$\begin{array}{ccc ccc ccc ccc ccc} 0 && 7 && 26 && 12 && 16 && 20 && 24 && 28 \\ & 7 && 19 && -14 && 4 && 4 && 4 && 4 \\ && 12 && -33 && 18 && 0 && 0 && 0 \end{array}$$

If the row was entirely zeros, the first few numbers in the top row would have to change. The amount each of those numbers must change is important: 0-0, 7-3, 26-18, 12-0, 16-0, ..., and the change is 0, 3, 18. The first diagonal would then be 0, 4. These finite sequences are the key to the polynomials that multiply the exponentials. Namely, since 0, 3, 18 comes from the diagonal of the third difference table, it will contribute:

$$3^x \left( 0 \times \frac{ \binom{x}{0} }{3^0} + 3 \times \frac{ \binom{x}{1} }{3^1} + 18 \times \frac{ \binom{x}{2} }{3^2} \right) = x^2 3^x$$

Likewise, since 0, 4 comes from the diagonal of the fourth difference table, it will contribute:

$$4^x \left( 0 \times \frac{ \binom{x}{0} }{4^0} + 4 \times \frac{ \binom{x}{1} }{4^1} \right) = x 4^x$$

Thus, the whole function is revealed: $x^2 3^x + x 4^x$.

A table of the first diagonals can be an abbreviated way of expressing much of the above difference tables. Although I did not complete the last difference table in this description, I include the complet first diagonal here. It alternates, indicating that a polynomial was present at some stage, as we already know:

$$\begin{array}{cccc cccc} 0 & 7 & 68 & 435 & 2320 & 11195 & 50820 & 221851 \\ 0 & 7 & 54 & 252 & 960 & 3300 & 10728 & 33852 \\ 0 & 7 & 40 & 111 & 248 & 515 & 1056 & 2191 \\ 0 & 7 & 26 & 12 & 16 & 20 & 24 & 28 \\ 0 & 7 & 12 & -45 & 96 & -165 & 252 & -357 \end{array}$$

 

[Nimz]

The first non-obvious sequence of coefficients is 1, 11, 66, 302, 1191, 4293, 14608, 47840, 452637, ..., which I finally determined to follow the formula: $3^{x+3} - 2^{x+3}(x+4) + \frac{(x+3)(x+4)}{2}$, by using my method of multiple difference tables. I haven't had time to prove it yet, but I'm pretty confident in that result. With that result, I also have a conjecture for all the sequences of coefficients now.

I have proven that formula now. Along with several of the formulas of my conjecture. The conjecture is that
$$(-1)^{n+1} \sum_{i=0}^{n} i^{x+n} \binom{x+n+1}{n-i} (-1)^{n-i}$$
is the x^th number in the n^th sequence of coefficients. The only thing I need to prove the general case is that the above sum (ignoring the (-1)ⁿ⁺¹ in front) is 1 as long as x = 0. In another form, the condition I need is:
$$\sum_{i=0}^{n} \binom{n}{i} (n-i-1)^{n-1} (-1)^{i} = 0$$
for all n.

 

[Nimz]

$$\sum_{i=0}^{n} \binom{n}{i} (n-i-1)^{n-1} (-1)^{i} = 0$$

and

$$\sum_{i=0}^{n} i^{n} \binom{n+1}{n-i} (-1)^{n-i} = 1$$

If one of these is true, the other immediately follows from symmetry. I'm still stumped on how to prove either of these equations. Induction on n is just too messy. I have verified that these equations are true for a small number of n's, but I'm looking for a general proof. Any help would be appreciated.

Btw, the class has been over for a couple weeks now. This is just for my own curiosity.

 

[shmoe]

$$\sum_{i=0}^{n} \binom{n}{i} (n-i-1)^{n-1} (-1)^{i} = 0$$

Defining $$\Delta f(n)=f(n+1)-f(n)$$ and $$\Delta^k f(n)=\Delta(\Delta^{k-1} f(n))$$, the usual forward difference, we have:

$$\Delta^n f(x)=\sum_{i=0}^{n}\binom{n}{i}(-1)^{n-i}f(x+i)$$

This is pretty easy to prove by induction on n. Take $$f(x)=(-x)^{n-1}$$ and your sum is (up to sign) $$\Delta^n f(1-n)$$. But f is a degree n-1 polynomial, so the nth forward difference will be zero.

 

[Nimz]

Thanks alot. I think I understand now (after spending a few minutes verifying it all). Not that I don't trust you. I'm not completely comfortable with the forward and backward difference operators yet. The notation, that is. I've seen the notation once before, and just skimmed thru the section dealing with it :P Now that I've taken a look at it, I see that I've been using them all along, but without any real notation.

It would only be off by a sign if n was odd. But since the nth difference of a degree n-1 polynomial is zero, it doesn't matter. The induction argument for
$$\Delta^n f(x)=\sum_{i=0}^{n}\binom{n}{i}(-1)^{n-i}f(x+i)$$
is pretty easy, even on n. I feel silly now.

 

[Rudakil]

using a difference table i have the rule 1/6ncubed why is it 1/6

 

[Chamalama]

We have just started the course, I will find you as we go deep