# I Formula involving polynomial sequences + recursive reps

1. Nov 8, 2016

### Mr Davis 97

Say that we have a sequence defined by the mth 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?

Last edited: Nov 8, 2016
2. Nov 9, 2016

### Staff: Mentor

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

3. Nov 9, 2016

### Stephen Tashi

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 ?

Last edited: Nov 9, 2016
4. Nov 9, 2016

### 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.

5. Nov 9, 2016

### Staff: Mentor

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 nj. And I don't see how this is supposed to work.

6. Nov 11, 2016

### Mr Davis 97

7. Nov 11, 2016

### Stephen Tashi

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

8. Nov 11, 2016

### Staff: Mentor

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.

9. Nov 11, 2016

### andrewkirk

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.

10. Nov 11, 2016

### Mr Davis 97

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...

11. Nov 11, 2016

### Mr Davis 97

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

12. Nov 11, 2016

### andrewkirk

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.
Code (Text):

# 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.

13. Nov 12, 2016

### Stephen Tashi

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$.

14. Nov 13, 2016

### 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)$.

Last edited: Nov 13, 2016
15. Nov 14, 2016

### Mr Davis 97

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.

16. Nov 14, 2016

### Stephen Tashi

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