(48G/50g) Binomial Transform, Difference Table

[John Keith]

Thanks again for the explanation.

The difference table from your post in the other thread

(11-21-2014 10:52 PM)Thomas Klemm Wrote:  For polynomial sequences you can apply the forward difference operator \(\Delta\) consecutively until you get just 0s.
For the tetrahedral numbers we get:
\[
\begin{matrix}
U &: & {\color{Red} 0} & & 1 & & 4 & & 10 & & 20 & & 35 & & 56 & & \cdots \\
\Delta U &: & & {\color{Red} 1} & & 3 & & 6 & & 10 & & 15 & & 21 & & \cdots & \\
\Delta^2 U &: & & & {\color{Red} 2} & & 3 & & 4 & & 5 & & 6 & & \cdots & & \\
\Delta^3 U &: & & & & {\color{Red} 1} & & 1 & & 1 & & 1 & & \cdots & & & \\
\Delta^4 U &: & & & & & {\color{Red} 0} & & 0 & & 0 & & \cdots & & & & \\
\cdots &: & & & & & & & \cdots
\end{matrix}
\]

Then use Newton's forward difference formula to write the sequence as a sum of binomial coefficients:

\(U(n)=0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+1\binom{n}{3}\)

Cheers
Thomas

illustrates another analytic method and another useful list processing function. As one can see, each row above the fourth row is the cumulative sum of the row below. In a sense, the cumulative sum is the "inverse" of the forward difference which transforms each row into the row below.

The cumulative sum (sometimes called the partial sums) is available in several programming languages- cumSum on the Prime, accumulate in Python, etc. There is no such built-in command on the HP 50 but using the GoferLists library it can be implemented as such:

Code:


\<<
   \<< +
   \>> Scanl1
\>>

It is also worth noting that the methods under discussion here are most effective for sequences based on polynomials. There are many other types of sequences for which these methods have little or no use.