Method of Differences

Suppose we are given several consecutive integer points at which a polynomial is evaluated. What information does this tell us about the polynomial? To answer this question, we create the following table, known as the Difference Table:

nf(n)D1(n)D2(n)D3(n)123 \begin{array} {l l l l l l l} n & f(n) & D_1(n) & D_2(n) & D_3(n) & \ldots \\ 1 & \\ 2 & \\ 3 & \\ \vdots \\ \end{array}

In the first column, we fill out the points at which the polynomial is evaluated (which I will assume is 1,2,31, 2, 3\ldots.
In the second column, we fill out the corresponding values of the polynomial at those points.
In the third column, we calculate the difference between two entries in the previous column. This is known as the first difference and is given by D1(n)=f(n+1)f(n) D_1 (n) = f(n+1) - f(n) .
In the fourth column, we calculate the difference between two entries in the previous column. This is known as the second difference and is given by D2(n)=D1(n+1)D1(n) D_2 (n) = D_1 (n+1) - D_1 (n) .
We continue building out subsequent columns of the table in this way, with Dk+1(n)=Dk(n+1)Dk(n) D_{k+1} (n) = D_k (n+1) - D_k (n) .

For example, if we are given that f(n) f(n) is a quadratic polynomial satisfying

f(1)=4,f(2)=3,f(3)=4,f(4)=7 and f(5)=12, f(1) = 4, f(2) = 3 , f(3) = 4, f(4) = 7 \mbox{ and } f(5) = 12,

then the difference table is as follows:

nf(n)D1(n)D2(n)D3(n)14120231203432475512 \begin{array} {l l l l l l l} n & f(n) & D_1(n) & D_2(n) & D_3(n) & \ldots \\ 1 & 4 & -1 & 2 & 0 \\ 2 & 3 & 1 & 2 & 0\\ 3 & 4 & 3 & 2\\ 4 & 7 & 5 \\ 5 & 12 & \\ \vdots \\ \end{array}

Note that since we are not given f(6)f(6) , we are unable to calculate D1(5),D2(4),D3(3)D_1(5), D_2(4), D_3(3) or D4(2)D_4(2). Now, there isn't (yet) any reason why this table would ever end; if we are given infinitely many values, we can always calculate the differences of terms. However, here is an interesting fact.

If a polynomial f(x)f(x) has degree kk, then the kkth difference is constant.
Furthermore, the kkth difference is equal to k!k! times the leading coefficient of f(x)f(x) .

In the above example, we see that D2(1)=D2(2)=D2(3)=2 D_2 (1) = D_2(2) = D_2( 3) = 2 . Since f(x)f(x) is a quadratic polynomial, the above fact tells us that D2(n)=2 D_2(n) = 2 for all nn, and this allows us to fill in other entries in the table. We get that D2(4)=2 D_2(4) = 2 so D1(5)=7 D_1 (5) = 7 and hence f(6)=19f(6) = 19 ! These values are previously unknown to us, but the difference table allows us to calculate them without knowing the polynomial f(x)f(x)!

How do we prove this interesting fact? Let's consider a general polynomial of degree kk. We have

f(n)=aknk+ak1nk1++a1n+a0. f(n) = a_k n^k + a_{k-1} n^{k-1} + \ldots + a_1 n + a_0.

What is the value of D1(n) D_1(n) ? By definition, we have

D1(n)=f(n+1)f(n)=i=1kai[(n+1)ini] D_1(n) = f(n+1) - f(n) = \sum_{i=1}^k a_i [(n+1)^i - n^i]

By the binomial theorem, we have

(n+1)ini=(i1)ni1+(i2)ni2++(ii)n1+(ii)n0, (n+1)^{i} - n^i = {i \choose 1} n^{i-1} + {i \choose 2} n^{i-2} + \ldots + {i \choose i} n^1 + {i \choose i } n^0,

implying that there are no terms of degree nkn^k in D1(n)D_1(n) . Furthermore, the coefficient of nk1 n^{k-1} comes solely from the term ak[(n+1)knk]a_k [(n+1)^k - n^k] , and is equal to kak k a_k .

We may likewise continue by induction to consider the second difference, third difference, etc. Each time, we see that the degree of the polynomial decreases by 1. Hence, by the time we get to the kkth difference, it is a polynomial of degree 0. Since the only polynomials of degree 0 are the constants, this implies Dk(n)D_k(n) is a constant polynomial.

What happens to the leading coefficient at each step? We see that it gets multiplied by the degree of the (current) polynomial. Since the degree decreases by 1 at each step, we see that it gets multiplied by k×(k1)××2×1=k! k \times (k-1) \times \ldots \times 2 \times 1 = k! . Hence, we have Dk=ak×k! D_k = a_k \times k! , or that ak=Dkk! a_k = \frac{D_k} { k!} .

Worked Examples

1. Construct the difference table for the function fk(n)=(n1)×(n2)××(nk) f_k(n) = (n-1) \times (n-2) \times \ldots \times (n-k) for n=1 n =1 to k+1 k+1 . Note that fk(n)f_k(n) is a polynomial of degree kk.

Solution: This is a specially chosen function. We easily see that:

f(i)={0i=1 to kk!i=k+1. f(i) = \begin{cases} 0 & i = 1 \mbox{ to } k \\ k! & i = k+1 \\ \end{cases} .

This allows us to easily calculate the first difference column as:

D1(i)={0i=1 to k1k!i=k. D_1(i) = \begin{cases} 0 & i = 1 \mbox{ to } k-1 \\ k! & i = k \\ \end{cases} .

Similarly, for the jjth difference column, we have that

Dj(i)={0i=1 to kjk!i=kj+1. D_j (i) = \begin{cases} 0 & i = 1 \mbox{ to } k-j \\ k! & i = k-j+1 \\ \end{cases} .

(*) Show that if f(n)f(n) is a polynomial of degree kk, then f(n)=f(1)+i=1kDi(1)i!×fi(n). f(n) = f(1) + \sum_{i=1}^k \frac{D_i (1)}{i!} \times f_i (n) .

In particular, the quadratic polynomial ff in the write up above satisfying f(1)=4,f(2)=3,f(3)=4,f(4)=7 f(1) = 4, f(2) = 3 , f(3) = 4, f(4) = 7 and f(5)=12f(5) = 12 is given by f(n)=n24n+7f(n) = n^2 - 4n +7.

 

2. Prove that there is no polynomial (of finite degree) which satisfies f(n)=2n f(n) = 2^n for all positive integers.

Solution: Construct the difference table for f(n)=2n f(n) = 2^n . Since D1(n)=f(n+1)f(n)=2n+12n=2n=f(n) D_1(n) = f(n+1) - f(n) = 2^{n+1} - 2^{n} = 2^{n}=f(n) , we see that D1D_1 is exactly equal to ff . This remains true for each kkth difference column, and hence there is no polynomial of degree kk that satisfies f(n)=2nf(n) = 2^n .

Note by Calvin Lin
5 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

@Calvin Lin Is this technique also called 'Synthetic Division'? Or is it different from it?

Satvik Golechha - 5 years, 3 months ago

Log in to reply

@Satvik Golechha - Nope. Its different I guess. But unfortunately I'm not good at that one too :(

Krishna Ar - 5 years, 3 months ago

Log in to reply

Nope. Synthetic Division is just "Lazy man's long division for linear polynomials". The only thing that you save is writing out all the terms. If you don't understand Synthetic division, then just do long division.

Calvin Lin Staff - 5 years, 3 months ago

Log in to reply

Is there a typo in example 1? Should it be f(n)=f(1)+i=1kDi(1)i!×fi(n)f(n) = f(1) + \sum_{i=1}^k \frac{D_i(1)}{i!}\times f_i(n)

Raymond Tat - 4 years, 8 months ago

Log in to reply

Thanks! I've fixed it :)

Calvin Lin Staff - 4 years, 8 months ago

Log in to reply

in the first since this information is provided that the polynomial is quadratic we can assume a general quadratic plug in the given values and solve for three variables.

Rishi Sharma - 4 years, 8 months ago

Log in to reply

Yes, that is certainly one possible approach. But what happens when there are many more equations? See Worked example 2, how would you prove that there is no polynomial which is equal to 2n 2^n on the positive integers?

Calvin Lin Staff - 4 years, 7 months ago

Log in to reply

Can you help me? Cos It seems that I don't understand. please

Mark Anthony Seraspe - 4 years, 7 months ago

Log in to reply

What do you not understand? Which problem are you stuck at?

Calvin Lin Staff - 4 years, 7 months ago

Log in to reply

@Calvin Lin I tried this method in solving This problem , but something went wrong. Any help please?

Hasan Kassim - 5 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...