Formula involving polynomial sequences + recursive reps

[Mr Davis 97]

Say that we have a sequence defined by the m^th degree polynomial, $a_n=\displaystyle \sum_{k=0}^{m}c_kn^k$. I found the following formula which is a recursive representation of the same sequence: $\displaystyle a_n =\sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1}a_{n-k}$.

I'm curious as to why this formula involves binomial coefficients. Any ideas? Also. How could I prove this formula? With induction?

 

[mfb]

This formula leads to a specific set of c_k. So what? As far as I can see other sets of c_k will lead to different recursive formulas, or don't allow reasonable recursive formulas at all.

 

[Stephen Tashi]

Any ideas?

If the formula holds true for an arbitrary sequence of coefficients ${c_i}$ then I we can imagine the symbols "$c_i$" as representing independent unit vectors and imagine each member of the sequence ${a_i}$ as representing a vector expressed as a linear combination of those unit vectors. For example, in the case $m = 3$ we have $a_5 = 5^0 c_0 + 5^1 c_1 + 5^2 c_2 + 5^3 c_3$.

The recursion claims to express the vector $a_n$ as a linear combination of the previous vectors $a_{n-1}, a_{n-2},..a_{n-(m+1)}$. If such a linear combination exists then the coefficient of each $c_i$ in the vector $a_n$ would have to be expressed as a sum of the coefficients of the same $c_i$ in the previous vectors.

For example in the case of $m= 3$ and $a_5$ we have the questions:

Is the coefficient of $c_0$ in $a5$ correctly expressed?
Does the recursion correctly express $5^0$ as a linear combination of the numbers $4^0, 3^0, 2^0, 1^0$. ?

Is the coefficient of $c_1$ in $a5$ correctly expressed?
Does the recursion correctly express $5^1$ as a linear combination of the numbers $4^1, 3^1, 2^1, 1^1$. ?

Is the coefficient of $c_2$ in $a5$ correctly expressed?
Does the recursion correctly express $5^2$ as a linear combination of the numbers $4^2, 3^2, 2^2, 1^2$ ?

Is the coefficient of $c_3$ in $a5$ correctly expressed?
Does the recursion correctly express $5^3$ as a linear combination of the numbers $4^3, 3^3, 2^3, 1^3$ ?

So the problem seems purely arithmetical. What general formula does the recursion claim is correct for expressing positive integer $r^s$ as a sum involving the integers $(r-1)^s, (r-2)^s,... (r-(m+1))^s$? And can we prove that formula ?

 

[andrewkirk]

I tested the recursion formula with a bit of code and it failed for the first set of $c_i$ coefficients I tried, which was 1,7,3,-5,0,2,-90.

I then tried a shorter set: 1,1, and it failed again.

So it looks like the recursion formula is not valid.

 

[mfb]

Did some steps of expanding the formula:
$$a_n =\sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1}a_{n-k} = \sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1} \sum_{j=0}^{m}c_j (n-k)^j = \sum_{j=0}^{m}c_j \left(\sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1} (n-k)^j \right)$$
For a general formula to hold, the large bracket has to equal n^j. And I don't see how this is supposed to work.

 

[Mr Davis 97]

I actually posted this question on Math stack exchange also, and I got a few answers which were purported proofs. http://math.stackexchange.com/quest...es-and-their-recursive-repres/2006692#2006692

How do you guys reconcile this?

 

[Stephen Tashi]

Did you understand the answer on stackexchange that used the finite difference operator $\nabla$ ? We could rehash that answer in greater detail.

 

[mfb]

Let's check m=1:
$a_n = c_0 + c_1 n$
$$\sum_{k=1}^{2}\binom{2}{k} (-1)^{k-1}a_{n-k} = 2a_{n-1} - a_{n-2} = 2(c_0 + c_1 (n-1))-(c_0 + c_1 (n-2)) = c_0 + c_1 n = a_n$$
Works for m=1. The simple counterexample given by @andrewkirk is not a counterexample.

Looking back at my previous post:
With m=1, $\sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1} (n-k)^j = 2(n-1)^j - (n-2)^j = n^j$ for j=0 and j=1.
With m=2, $\sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1} (n-k)^j = 3(n-1)^j - 3(n-2)^j + (n-3)^j = n^j$ for j=0 and j=1 and j=2.

I start seeing a pattern. And induction over m gives the same for all m.

Interesting formula.

 

[andrewkirk]

The simple counterexample given by @andrewkirk is not a counterexample.

Yes, I checked back and found I made a coding error. Having fixed that and run it over a bunch of polynomials at each degree from 1 to 10, the recursion formula gives the correct result.

 

[Mr Davis 97]

Yes, I checked back and found I made a coding error. Having fixed that and run it over a bunch of polynomials at each degree from 1 to 10, the recursion formula gives the correct result.

If I may ask, what programming language did you use to compute the recursion formula? Since I have been doing it by hand, it has been kind of a pain...

 

[Mr Davis 97]

Did you understand the answer on stackexchange that used the finite difference operator $\nabla$ ? We could rehash that answer in greater detail.

Not completely. The induction makes sense, but the use of finite difference operators confuses me.

 

[andrewkirk]

If I may ask, what programming language did you use to compute the recursion formula?

I wrote it in R, which is a high-level interpreted language aimed at mathematical number crunching, statistics and graphics. It has similarities to Matlab and SAS. Here's my code, after correcting the error.

# define a function to calc the value of the polynomial for input n
polyval<-function(n){
  if (length(n)>1){
    # vector input, so split into elements and do one at a time
    vapply(n,polyval,1)
  } else {
    # scalar input, so apply the polynomial formula
    sum(coeff*(n^(0:m)))
  }
}

# define a function to calculate the value of the recursion formula for input n
recursval<-function(n){
  x<-1:(m+1)  
  if (length(n)>1){
    # vector input, so split into elements and do one at a time
    vapply(n,recursval,1)
  } else {  
    # scalar input, so apply the polynomial formula
    sum(choose(m+1,x)*ifelse(x %% 2==1,1,-1)*polyval(n-x))
  }
}

# set up vector of inputs n to use for testing discrepancies between poly value and recursion formula
n<-(-10):10
# try a poly of degree 6 with leading coefficient -90
coeff<-c(1,7,3,-5,0,2,-90)
m<-length(coeff)-1
# display diff between poly formula and recursion formula for integer inputs from -10 to 10
recursval(n)-polyval(n)
# try a poly x+1
coeff<-c(1,1)
m<-length(coeff)-1
# display diff between poly formula and recursion formula for integer inputs from -10 to 10
recursval(n)-polyval(n)

# Now look at diffs between polyval and recursval for 5 polynomials with random coefficients
# at each order from 1 to 12
maxorder<-12
numpolys<-5
rang<-20
nmin<-20
# create array to store results
res<-array(0,c(maxorder,numpolys))
for (m in 1:maxorder){
  for (s in 1:numpolys){
    # look at discrepancies for one poly
    # first randomly generate a set of poly coeffs of order m
    coeff<-floor(runif(m+1)*(2*rang+1)-rang)
    # create vector of inputs n to consider
    y<-(-nmin):nmin
    # now calc the highest discrepancy for this poly for all integer inputs n from -nmin to +nmin
    res[m,s]<-max(recursval(y)-polyval(y))
  }
}
# display table of discrepancies. If it's all zeros, the recursion formula has always been correct
res

The discrepancies became nonzero for polynomials of degree 10 and higher. But on investigation that turned out to be an artefact of rounding, because the values were so enormous.

 

[Stephen Tashi]

Before doing proofs, let's start with some examples.

Given a sequence {a_i}, we can form a new sequence of "first differences" that consists of the differences between consecutive terms of {a_i}. We can perform the same process on the sequence of "first differences" to get a sequence of "second differences", etc.

Using the convention that first differences of a sequence {s_i} are the sequence given by t_i = s{i+1} - s{i] , we have, for example:

Sequence ---------------{a_i}: 4 ,6 , 9 , 10 , 11 , 15, 14 , 12
First differences: -------- {b_i}: 2, 3, 1, 1, 4, -1, -2
Second differences:--------{c_i}: 1, -2, 0, 3, -5, -1
Third differences:------------{d_i}: -3, 2, 3, -8, 4

A term of a k-th difference of the sequence {a_i} can be expressed as a linear combination of terms of the sequence {a_i}. In that linear combination, the coefficients of the {a_i} are binomial coefficients.

For example, using the above sequences:
d[1] = -3 = c[2] - c[1]
= (b[3] - b[2]) - (b[2] - b[1])
= ((a[4]- a[3] ) - (a[3] - a[2])) - ((a[3] - a[2]) - (a[2] - a[1]) )
= a[4] - 3a[3] + 3 a[2] - a[1]

The coefficients 1, -3, 3, -1 correspond to the binomial coefficients in the expansion of $(x-1)^3$.
Sequences of the form {a_n} = n^k have the property that their (k+1)-th differences are zero. For example, if k = 3 then we have:
Sequence--------------{a_i}: 1, 8, 27, 64, 125, 216,...
First differences-------{b_i}: 7, 19, 37, 61, 91,...
Second differences-----{c_i}: 12, 18, 24, 30,...
Third differences------- {d_i}: 6, 6, 6, ...
Fourth differences--------{e_i} 0, 0, ...

In the above example, the first term $e[1]$ in the sequence of fourth differences can be expressed as:
$e_1 = 0 = \binom{4}{0} a_5 - \binom{4}{1} a_4 + \binom{4}{2}a_3 - \binom{4}{3}a_2 + \binom{4}{4}a_1$

which implies $\binom{4}{0}a_5 = a_5 = \binom{4}{1} a_4 - \binom{4}{2}a_3 + \binom{4}{3}a_2 - \binom{4}{4}a_1$

$a_5 = \sum_{k=1}^4 \binom{4}{k}(-1)^{k-1} a_{(5 - k)}$

which is an example of the recursion in your original post:
$a_n =\sum_{k=1}^{m+1}\binom{m+1}{k} (-1)^{k-1}a_{n-k}$.

using $n = 5,\ m = 3$.

 

[Stephen Tashi]

The answer on stackexchange uses the backward difference operator $\nabla$. I prefer to think in terms of the forward difference operator "$\triangle$" which is defined by $\triangle f(x) = f(x+1) - f(x)$.

Having a made mathematical statement, its always a good idea to figure out what we meant. An "operator" can be defined as function whose domain is a set of functions and whose co-domain is a set of functions. I have in mind using the operator $\triangle$ on sequences of real numbers. Technically, a sequence is a type of function; it is a function from a set of integers (the indices) into the set of real numbers. If a sequence is the function named "$a$", we traditionally use the notation $a_j$ to mean $a(j)$.

If we denoted the operator $\triangle$ in the way we usually write functions, we'd denote it as $\triangle(f)$ and we would have equations like $g = \triangle(f)$ where $g$ is a function. Since the function $\triangle(f)$ is defined by its "operation" on specific values "$x$" of "$f$" , its more practical to use equations that describe this operation.

In summary, the usual notation for the forward difference operator applied to sequences involves two departures from the $f(x)$ type of notation for functions. For sequences, we use the $a_j$ notation instead of $a(j)$. For the operator, we rarely deal with the notation $\triangle(f)$. Instead, we deal with the particular formula for $\triangle f(x)$ which involves both a function $f$ and a real number $x$.

Using the examples in my previous post, we could say that $\triangle(a) = b$, but it is more informative to write $\triangle a_i = a_{i+1} - a_i = b_i$

By analogy to way we can take second and third derivatives of functions, we can apply the $\triangle$ operator several times to a function. Technically, "to apply" means "to compose" in the sense of composing functions. The interpretation of $\triangle ( \triangle f(x) )$ as a composition of functions follows from the definition of $\triangle$ and the definition of what it means to compose two functions. Specifically:
$\triangle( \triangle f(x)) = \triangle( f(x+1) - f(x) ) = ( (f(x+2) - f(x+1)) - (f(x+1) - f(x)) ) = f(x+2) - 2(x+1) + f(x)$.

We denote the operator $\triangle (\triangle f(x))$ by $\triangle^2 f(x)$. More generally, n nested compositions of the operator $\triangle$ are denoted by $\triangle^n$.

One theorem we need is to prove is:
$\triangle^n f(x) = \sum_{i=0}^n{ \binom{n}{i} f(x+i) (-1)^{n-i} }$.
If the function $f$ is sequence, we can write the theorem using the notation:
$\triangle^n f_k = \sum_{i=0}^n{ \binom{n}{i} f_{k+i}) (-1)^{n-i}}$.

The theorem can be proven by induction, but its more interesting to establish it using magic - meaning algebraic manipulations that would take a lot of exposition to justify rigorously.

Define the "increment operator" $E$ by $Ef(x) = f(x+1)$. Denote $E(E f(x))$ by $E^2 f(x)$ and, in general, denote the nested composition of $n$ applications of $E$ by $E^n f(x)$.

Trivially, $E^2 f(x) = E E(f(x)) = E (f(x+1)) = f(x+2)$ and $E^n f(x) = f(x+n)$.

What I want to say now is that "$\triangle = E - 1$" and I can offer a demonstration of that by the manipulations:
$(E-1) f(x) = E f(x) - f(x) = f(x+1) - f(x) = \triangle f(x)$.
If the audience is half asleep, that sort of magic works. If the audience is awake, someone will spoil the fun by asking what these manipulations mean. For example, I haven't defined the notation "$E-1$" as an operator. Some people might prefer a notation like $E - I$ where "$I$" is "the identity operator".

The show continues with:
$\triangle^n f(x) = (E - 1)^n f(x)$

$= ( \sum_{i=0}^n {\binom{n}{i} (E^{i}) (-1)^{n-i}}) f(x)$. (Instead of saying "shazam", we say "expanding $(E-1)^n$ by the binomial theorem".)

$= \sum_{i=0}^n { \binom{n}{i} (E^{i}) (-1)^{n-i} f(x)}$ (Putting $f(x)$ within the summation and hoping people take that for granted)

$= \sum_{i=0}^n { \binom{n}{i} (E^{i} f(x)) (-1)^{n-i} }$ ( Let's not ask whether (-1)^{n-i} is an operator or a number)

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

 

[Mr Davis 97]

The answer on stackexchange uses the backward difference operator $\nabla$. I prefer to think in terms of the forward difference operator "$\triangle$" which is defined by $\triangle f(x) = f(x+1) - f(x)$.

Having a made mathematical statement, its always a good idea to figure out what we meant. An "operator" can be defined as function whose domain is a set of functions and whose co-domain is a set of functions. I have in mind using the operator $\triangle$ on sequences of real numbers. Technically, a sequence is a type of function; it is a function from a set of integers (the indices) into the set of real numbers. If a sequence is the function named "$a$", we traditionally use the notation $a_j$ to mean $a(j)$.

If we denoted the operator $\triangle$ in the way we usually write functions, we'd denote it as $\triangle(f)$ and we would have equations like $g = \triangle(f)$ where $g$ is a function. Since the function $\triangle(f)$ is defined by its "operation" on specific values "$x$" of "$f$" , its more practical to use equations that describe this operation.

In summary, the usual notation for the forward difference operator applied to sequences involves two departures from the $f(x)$ type of notation for functions. For sequences, we use the $a_j$ notation instead of $a(j)$. For the operator, we rarely deal with the notation $\triangle(f)$. Instead, we deal with the particular formula for $\triangle f(x)$ which involves both a function $f$ and a real number $x$.

Using the examples in my previous post, we could say that $\triangle(a) = b$, but it is more informative to write $\triangle a_i = a_{i+1} - a_i = b_i$

By analogy to way we can take second and third derivatives of functions, we can apply the $\triangle$ operator several times to a function. Technically, "to apply" means "to compose" in the sense of composing functions. The interpretation of $\triangle ( \triangle f(x) )$ as a composition of functions follows from the definition of $\triangle$ and the definition of what it means to compose two functions. Specifically:
$\triangle( \triangle f(x)) = \triangle( f(x+1) - f(x) ) = ( (f(x+2) - f(x+1)) - (f(x+1) - f(x)) ) = f(x+2) - 2(x+1) + f(x)$.

We denote the operator $\triangle (\triangle f(x))$ by $\triangle^2 f(x)$. More generally, n nested compositions of the operator $\triangle$ are denoted by $\triangle^n$.

One theorem we need is to prove is:
$\triangle^n f(x) = \sum_{i=0}^n{ \binom{n}{i} f(x+i) (-1)^{n-i} }$.
If the function $f$ is sequence, we can write the theorem using the notation:
$\triangle^n f_k = \sum_{i=0}^n{ \binom{n}{i} f_{k+i}) (-1)^{n-i}}$.

The theorem can be proven by induction, but its more interesting to establish it using magic - meaning algebraic manipulations that would take a lot of exposition to justify rigorously.

Define the "increment operator" $E$ by $Ef(x) = f(x+1)$. Denote $E(E f(x))$ by $E^2 f(x)$ and, in general, denote the nested composition of $n$ applications of $E$ by $E^n f(x)$.

Trivially, $E^2 f(x) = E E(f(x)) = E (f(x+1)) = f(x+2)$ and $E^n f(x) = f(x+n)$.

What I want to say now is that "$\triangle = E - 1$" and I can offer a demonstration of that by the manipulations:
$(E-1) f(x) = E f(x) - f(x) = f(x+1) - f(x) = \triangle f(x)$.
If the audience is half asleep, that sort of magic works. If the audience is awake, someone will spoil the fun by asking what these manipulations mean. For example, I haven't defined the notation "$E-1$" as an operator. Some people might prefer a notation like $E - I$ where "$I$" is "the identity operator".

The show continues with:
$\triangle^n f(x) = (E - 1)^n f(x)$

$= ( \sum_{i=0}^n {\binom{n}{i} (E^{i}) (-1)^{n-i}}) f(x)$. (Instead of saying "shazam", we say "expanding $(E-1)^n$ by the binomial theorem".)

$= \sum_{i=0}^n { \binom{n}{i} (E^{i}) (-1)^{n-i} f(x)}$ (Putting $f(x)$ within the summation and hoping people take that for granted)

$= \sum_{i=0}^n { \binom{n}{i} (E^{i} f(x)) (-1)^{n-i} }$ ( Let's not ask whether (-1)^{n-i} is an operator or a number)

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

That's a very clever way of doing things, and the way you describe it makes perfect sense. But how would I have thought to do that? In my case, I would have just tried to plunge headfirst in doing some messy induction proof without any notion of backward or forward difference, probably ending up nowhere.

 

[Stephen Tashi]

That's a very clever way of doing things, and the way you describe it makes perfect sense. But how would I have thought to do that?

That method isn't my invention. I've seen it in books on "The Calculus of Finite Differences".