Finite Differences and Recurrence Relations

Solutions.

1. Make an argument to show that the third differences for cubic data is actually 6a.

X Y +1 +2 +3
x-2 a ( x − 2) + b ( x − 2)
3 2

+ c( x − 1) + d
a ( 3x 2 + 9 x + 7 ) +
b ( 2 x + 3) + c
x-1 a ( x − 1) + b ( x − 1)
3 2
a ( 6 x + 6 ) + 2b
+ c( x − 1) + d
a ( 3x 2 + 3x + 1) + 6a

b ( 2 x + 1) + c
x a ( x) + b ( x)
3 2
a ( 6 x ) + 2b
+ cx + d
a ( 3x 2 − 3x + 1) + 6a

b ( 2 x − 1) + c
x+1 a ( x + 1) + b ( x + 1)
3 2
a ( 6 x − 6 ) + 2b
+ c( x + 1) + d
a ( 3x 2 − 9 x + 7 ) +
b ( 2 x − 3) + c
x+2 a ( x + 2) + b ( x + 2)
3 2

+ c( x + 2) + d

2. Find the sum of the squares of the first 100 positive integers.

Of course this is arithmetic, so we all know the quick formula for this, that is
100
S100 = (1 + 100 ) = (101)(50) = 5050 , but let’s do it with the finite differences.
2
X 1 2 3 4 5
Y 1 3 6 10 15
+1 2 3 4 5
+2 1 1 1

1
Written & Compiled by John Goebel, NCSSM Problem Solving Course, 2006
 It looks like the second finite differences are all one, so the function for the partial
1
sums is quadratic with leading coefficient ½. So we get S (n) = n 2 + bn + c and
2
1 2 1 1
see that S (1) = (1) + b + c = 1 and S (2) = ( 2 ) + 2b + c = 3 , so b + c = , and
2

2 2 2
1
2b + c = 1 . Solving this system of equations gives us b = , c = 0 , so
2
1 1 1
S (n) = n 2 + n = ⋅ n ( n + 1) .
2 2 2

3. Find the sum of the cubes of the first 50 positive integers.

X 1 2 3 4 5 6 7
Y 1 9 36 100 225 441 784
+1 8 27 64 125 216 343
+2 19 37 61 91 127
+3 18 24 30 36
+4 6 6 6

Since the fourth differrences are constant, we know that this is a fourth-degree
6
polynomial of the form S (n) = n 4 + bn3 + cn 2 + dn + f . There are several
4!
approaches to finding the remaining coefficients. The most efficient way may be
2
⎛1 ⎞
to notice that the desired sums are all perfect squares, so S (n) = ⎜ n 2 + bn + c ⎟ ,
⎝2 ⎠
2
⎛1 ⎞ 1
and S (1) = ⎜ ⋅12 + b + c ⎟ = 1 ⇒ b + c = and
⎝2 ⎠ 2
2
⎛1 ⎞ 1
S (2) = ⎜ ⋅ 22 + 2b + c ⎟ = 9 ⇒ 2 + 2b + c = 3 . This system yields b = , c = 0 , so
⎝2 ⎠ 2
2
⎛1 1 ⎞ 1
our desired sum is S (n) = ⎜ n 2 + n ⎟ = n 2 ( n + 1) ,
2

⎝2 2 ⎠ 4

4. Find the sum 1 − 4 + 9 − 16 + " − 1002 .

Notice that the partial sums for the triangular numbers with the added fact that
every other one is negative. So if we find the formula for the triangular numbers,
we are nearly done.
n 1 2 3 4 5 6
S(n) 1 -3 6 -10 15 -21

2
Written & Compiled by John Goebel, NCSSM Problem Solving Course, 2006
 n 1 2 3 4 5
S(n) 1 3 6 10 15
+1 2 3 4 5
+2 1 1 1

⎛1 ⎞
So we see that the sum is quadratic of the form S (n) = ⎜ ⋅ n 2 + bn + c ⎟ .
⎝2 ⎠
⎛ 1 ⎞ ⎛ 1 ⎞
Substituting we find that S (1) = ⎜ ⋅12 + b + c ⎟ = 1 and S (2) = ⎜ ⋅ 22 + 2b + c ⎟ = 3 ,
⎝2 ⎠ ⎝2 ⎠
1 1
So b + c = , 2b + c = 1 ⇒ b = , c = 0 . So the desired sum is
2 2
n +1 ⎛ 1 ⎞
S (n) = ( −1) ⎜ ⎟ ( n 2 + n ) .
⎝2⎠

5. The Lucas sequence begins with 2, then 1, and then the remaining terms are found
as in the Fibonacci sequence. Write the recursive and closed forms for the terms
of this sequence.

The recursive form for the Lucas sequence is simply

t0 = 2, t1 = 1, tn = tn −1 + tn − 2 , n ≥ 2 , so the terms are 2, 1, 3, 4, 7, 11, 18, 29, 47, ….
To find the closed formula, rewrite the recursive equation as tn − tn −1 − tn − 2 = 0
and notice that this is exactly like the Fibonacci solution above, so
n n
⎛ 1+ 5 ⎞ ⎛ 1− 5 ⎞
tn = c1 ⋅ r1 + c2 ⋅ r2 = c1 ⎜⎜
n n
⎟⎟ + c2 ⎜⎜ ⎟⎟ , but since the initial values are
⎝ 2 ⎠ ⎝ 2 ⎠
0 0
⎛ 1+ 5 ⎞ ⎛ 1− 5 ⎞
different, we have t0 = c1 ⎜⎜ ⎟⎟ + c2 ⎜⎜ ⎟⎟ = c1 + c2 = 2 and
⎝ 2 ⎠ ⎝ 2 ⎠
1 1
⎛ 1+ 5 ⎞ ⎛ 1− 5 ⎞
t1 = c1 ⎜⎜ ⎟⎟ + c2 ⎜⎜ ⎟⎟ = c1 + c2 = 1
⎝ 2 ⎠ ⎝ 2 ⎠

6. The first term of a sequence is 0 and the second is 1. For all

n ≥ 2, tn = 3 ⋅ tn −1 − 2 ⋅ tn − 2 . Find the first 5 terms of the sequence, the recursive, and
the closed form for the terms of this sequence.

The first five terms are 0, 1, 3, 7, and 15, so it looks like the function is simply
tn = 2n − 1. Let’s use the method above to rewrite the recursive equation as
tn − 3 ⋅ tn −1 + 2 ⋅ tn − 2 = 0 and proceed. We will have cr n − 3cr n −1 + 2cr n − 2 = 0 , so
cr n − 2 ( r 2 − 3r + 2 ) = 0 . The solutions to the second factor are r1 = 1, r2 = 2 . Now

3
Written & Compiled by John Goebel, NCSSM Problem Solving Course, 2006
 we have tn = c1 ⋅ r1n + c2 ⋅ r2 n = c1 (1) + c2 ( 2 ) . Now take the first two given values
n n

to find the values for c1 , c2 . We get the system of equations:

0 = c1 (1) + c2 ( 2 ) = c1 + c2 ⇒ c2 = −c1
0 0

.
1 = c1 (1) − c1 ( 2 ) = c1 − 2c2 ⇒ −1 = c1 , ⇒ c2 = 1
1 1

(
This means then that tn = −1 (1) − ( 2 )
n n
)=2 n
−1 .

7. Sequence ( a1 , a2 , a3 ,...) is defined recursively by a1 = 0, a2 = 100 and

an = 2an −1 − an − 2 − 3 . Find the greatest term in the sequence ( a1 , a2 , a3 ,...) . {Duke
Math Meet 1998 Team Problem #9)

Since an − 2an −1 + an − 2 = −3 , this is a non-homogenous recurrence relation,

so the above method does not work. However, finite difference will work. First,
generate several values:

n 0 1 2 3 4
f(n) 0 100 197 291 382
+1 100 97 94 91
+2 -3 -3 -3

3
We see now that the function is quadratic, and in the form f (n) = − n 2 + bn + c .
2
We also know that f (0) = 0 ⇒ c = 0 . Similarly we also know that
3 2 3
f (1) = 100 = − (1) + b(1) ⇒ b = 101.5. So we have f (n) = − n 2 + 101.5n and
2 2
b 101.5
the maximum value of this function occurs when x = − = = 33.83 . Since
2a 3
our function is a sequence (whose domain is the Whole Numbers), we need to
check the values 33 and 34 to find the maximum. Since 34 is closer to the real-
valued vertex, it yields 1717, which is the maximum value.

⎧ f (0) = k
8. Find k given that ⎨ and f (−50) = 4000.
⎩ f (n) = f (n + 1) − 3n − 2
SMC 2003 Integer # 11

This problem can be done, among other ways, by using finite differences. First, it
might help to rewrite the recursive equation as f (n + 1) = f (n) + 3n + 2 . Now
generate a table of the first several values.

4
Written & Compiled by John Goebel, NCSSM Problem Solving Course, 2006
 x 0 1 2 3 4
y k k+ k+7 k + 15 k + 26
2
+1 2 5 8 11
+2 3 3 3

3 2
We see now that the function is quadratic, and in the form f (n) = n + bn + k .
2
3 1
We also know that f (1) = k + 2 = ⋅12 + b ⋅1 + k ⇒ b = . Finally we are told that
2 2
3
f (−50) = 4000 = ( −50 ) + (−50) + k ⇒ k = 275.
2

5
Written & Compiled by John Goebel, NCSSM Problem Solving Course, 2006