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

[John Keith]

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 (Delta-LIST) 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:


\<< DUP DUP SIZE \-> n
  \<< 2. n
    START \GDLIST DUP
    NEXT DROP n \->LIST
  \>>
\>>

A simple modification of the program above will return the inverse binomial transform of the list on level 1:

Code:


\<< DUP SIZE \-> n
  \<< 2. n
    START DUP HEAD NEWOB SWAP \GDLIST
    NEXT EVAL n \->LIST
  \>>
\>>

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:


\<< DUP HEAD SWAP DUP SIZE \-> n
  \<< 2. n
    START :: + DOSUBS DUP HEAD NEWOB SWAP
    NEXT DROP n \->LIST
  \>>
\>>

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.



...And one more useful variation, called "inverse summation" in this paper.

Code:


\<< DUP HEAD NEWOB SWAP \GDLIST +
\>>

This is the exact inverse of the cumulative or partial sum, and does not shorten the list.

Edited 9/20/2019 to add NEWOB to binomial transform, inverse binomial transform, and inverse summation programs. This simple addition allows the programs to process much larger lists and makes the programs run somewhat faster.

[Thomas Klemm]

(01-17-2019 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

[Thomas Klemm]

(01-17-2019 09:56 PM)John Keith Wrote:  

Code:

  \<< 1. s 1. -

With START and NEXT you could instead use:

Code:

  \<< 2. s

Cheers
Thomas

[John Keith]

(01-18-2019 08:14 AM)Thomas Klemm Wrote:  

(01-17-2019 09:56 PM)John Keith Wrote:  

Code:

  \<< 1. s 1. -

With START and NEXT you could instead use:

Code:

  \<< 2. s

Cheers
Thomas

You are correct of course. I have pointed that out to others at times myself. I shall correct the oversight.

[John Keith]

(01-18-2019 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.
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

Thanks, Thomas. I know there is a connection here to polynomials and generating functions but this is mostly above my current level of knowledge.

[Thomas Klemm]

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(n-1)}{2}+1\frac{n(n-1)(n-2)}{6}\\
&=n+ n(n-1)+\frac{n(n-1)(n-2)}{6}\\
&=\frac{n(n+1)(n+2)}{6}
\end{align*}\)

This is in accordance with A000292.

Cheers
Thomas

[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 ListExt library it can be implemented as
:: + LSCAN

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.

[John Keith]

Following on from the last two posts, a much faster binomial transform program for sequences defined by simple polynomials. Sequences defined by an nth degree polynomial are binomial transforms of a sequence beginning with n+1 terms followed by an arbitrary number of zeros. For instance, A000292, the tetrahedral numbers, is the binomial transform of { 1 3 3 1 0 0 0... }.

The following program requires a list of the non-zero terms on level 2 and a number on level 1 which is the number of terms to return. The list on level 2 must have at least two terms. For example, with { 1 3 3 1 } on level 2 and 12 on level 1, the program will return a list of the first 12 tetrahedral numbers.

Code:


\<< OVER SIZE 2. - \-> n s
  \<< EVAL n LASEQ
    IF s
    THEN 1. s
      START SWAP :: + LSCAN
      NEXT
    END
  \>>
\>>

This program is HP 50g only since it uses commands from the ListExt Library

The following version is compatible with the HP-48G. It is longer and slower than the HP 50 version but still reasonably fast. The list on level 2 must have at least two terms.

Code:


\<< OVER SIZE 2 - ROT OBJ\->
  2 + ROLL LASTARG ROLL \-> m n s
  \<< n m * OVER + 1 -
    FOR j j m
    STEP n \->LIST
    IF s
    THEN 1 s
      START 1
        \<< OVER +
        \>> DOSUBS +
      NEXT
    END
  \>>

Edited to remove reference to GoferLists and replace GoferLists functions with those from ListExt.
Edited to improve the above programs.