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

01172019, 09:56 PM
(This post was last modified: 04032019 05:51 PM by John Keith.)
Post: #1




(48G/50g) Binomial Transform, Difference Table
Difference tables and the binomial transform are powerful methods for analyzing integer sequences and their underlying logic. See also Conway and Guy, "The Book of Numbers", chapter 3.
Difference tables can be easily created using the \GDLIST (DeltaLIST) command on many HP calculators. Given a list of integers on level 1, the following program returns a difference table as a list of lists: Code:
A simple modification of the program above will return the inverse binomial transform of the list on level 1: Code:
Modifying the above program by inserting NEG after \GDLIST will produce the variation described by Thomas Klemm in this post. And finally another modification returns the binomial transform, the inverse of the function of the program above: Code:
Unlike \GDLIST, the two programs above do not shorten the list. If a list of integers is transformed by one program followed by the other, the original list will return unchanged. 

01182019, 05:53 AM
Post: #2




RE: (48G/50g) Binomial Transform, Difference Table
(01172019 09:56 PM)John Keith Wrote: A simple modification of the program above will return the inverse binomial transform of the list on level 1: This can be used to find an explicit formula for a polynomial sequence given only the first couple of values. From the older thread Solving a Recursive Sequence in Sequence App: { 0 1 4 10 20 35 56 } → { 0 1 2 1 0 0 0 } Thus: \(a_n=0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+1\binom{n}{3}\) Cheers Thomas 

01182019, 08:14 AM
Post: #3




RE: (48G/50g) Binomial Transform, Difference Table  
01182019, 07:39 PM
Post: #4




RE: (48G/50g) Binomial Transform, Difference Table  
01182019, 08:01 PM
Post: #5




RE: (48G/50g) Binomial Transform, Difference Table
(01182019 05:53 AM)Thomas Klemm Wrote: This can be used to find an explicit formula for a polynomial sequence given only the first couple of values. Thanks, Thomas. I know there is a connection here to polynomials and generating functions but this is mostly above my current level of knowledge. 

01182019, 08:50 PM
Post: #6




RE: (48G/50g) Binomial Transform, Difference Table
That's just this formula for the inverse binomial transform from the linked Wikipedia article:
\(a_n=\sum_{k=0}^n {n\choose k} t_k\) In the given example it leads to: \(\begin{align*} a_n&=0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+1\binom{n}{3}\\ &= 0+1\frac{n}{1}+2\frac{n(n1)}{2}+1\frac{n(n1)(n2)}{6}\\ &=n+ n(n1)+\frac{n(n1)(n2)}{6}\\ &=\frac{n(n+1)(n+2)}{6} \end{align*}\) This is in accordance with A000292. Cheers Thomas 

01182019, 09:44 PM
Post: #7




RE: (48G/50g) Binomial Transform, Difference Table
Thanks again for the explanation.
The difference table from your post in the other thread (11212014 10:52 PM)Thomas Klemm Wrote: For polynomial sequences you can apply the forward difference operator \(\Delta\) consecutively until you get just 0s. 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 builtin command on the HP 50 but using the GoferLists library it can be implemented as such: Code:
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. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)