Fibonacci Sequence and Difference Equations (Recurrence relations)

Created by Mr. Francis Hung on 20081104 Last updated: 2022-09-03

1. Fibonacci Sequence
Define the sequence: F1 = F2 = 1, when n ≥ 1, Fn+2 = Fn+1 + Fn
Let α > β be the roots of x2 – x – 1 = 0, then α + β = 1, α β = –1
Fn+2 = Fn+1 + Fn  Fn+2 – (α + β )Fn+1 + α β Fn = 0
 Fn+2 – α Fn+1 = β(Fn+1 – α Fn) ………(*)
Let Vn = Fn+1 – αFn, for n = 1, 2, …, n – 1
By (*) Vn+1 = β Vn
n = 1, V2 = βV1
n = 2, V3 = βV2 = β2V1
…………………….....
n → n – 1, Vn = βVn–1 = … = βn–1V1
Fn+1 – αFn = βn–1V1 …….(1)
On the other hand (*) may be rewritten as Fn+2 – β Fn+1 = α (Fn+1 – β Fn) ………(**)
Let Wn = Fn+1 – βFn, for n = 1, 2, …, n – 1
By (**) Wn+1 = α Wn
n = 1, W2 = αW1
n = 2, W3 = αW2 = α2W1
……………………........
n → n – 1, Wn = αWn–1 = … = αn–1W1
Fn+1 – βFn = αn–1W1 …….(2)
(2) – (1) (α –β)Fn = αn–1(F2 – βF1) – βn–1(F2 – αF1)
α n−1 (1 − β ) − β n−1 (1 − α )
Fn =
α −β

=
(
α n−1 − β n−1 − αβ α n −2 − β n −2 )
α −β

=
(
α n−1 − β n−1 + α n− 2 − β n− 2 ) (∵α β = –1)
α −β

=
(
α n−1 + α n− 2 − β n −1 + β n −2 ) (∵α – β = (α − β)2 − 4αβ = 5)
5
α (1 + α ) − β n− 2 (1 + β )
n−2
=
5

=
α n−2
( )
α − β n−2 β 2
2
( ) (∵α > β are roots of x2 – x – 1 = 0, α2 = α + 1, β2 = β + 1)
5

1  1 + 5   1 − 5  
n n

=   − 
5  2   2  
 

http://www.hkedcity.net/ihouse/fh7878/ Page 1
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

Fn
1
(α n
− βn )
5
Define Rn = =
Fn +1 1
(α n +1
− β n +1 )
5

α n − βn
=
α n+1 − β n +1

  β n    β n 
α 1 −   
n
1 −   
  α     α  
= = 
  β  n+1    β  n+1 
α n+1 1 −    α 1 −   
  α     α  

  β n 
1 −   
  α  
n
1 β β
lim Rn = lim = (∵ − 1 < < 1, lim   = 0 )
β  α α n →∞ α 
n →∞ n →∞  n +1
α 1 −   
  α  
2 5 −1
= =
1+ 5 2

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 2
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

The Fibonacci sequence is defined inductively as follows:

a1 = a2 = 1, an = an–1 + an–2 for n > 2.

 a n+2  a  1 1 
(a) Show that   = A n +1  , where A =   .
 a n +1   an  1 0 

 a n+2  a 
Hence prove that for all positive integral values of n,   = A n  2  .
 a n +1   a1 

(b) Show that A satisfies the matrix equation A2 – A – I = 0.

(c) Suppose when xn is divided by x2 – x – 1, the remainder is r1x + r2, where r1, r2 are real numbers,

1  1 + 5 
n
1 − 5  
n
1  1 + 5  n −1  1 − 5  n −1 
  −       
show that: r1 =
5  2   2   , r2 = 5  2  −  2   .
        

(d) Show that An = r1A + r2I. (where I is the identity matrix.)

n +1 n +1
1  1 + 5  1 − 5  
Deduce that an+1 =   −  
5  2   2  .
   

a an 
(e) Show that An =  n+1 2 n
 for n > 1 and hence deduce that an+1an–1 – an = (–1) .
 n a a n −1 

a n + 2 = a n +1 + a n  a n + 2  1 1  a n +1 
(a)     =   
 a n +1 = a n +1  a n +1  1 0  a n 
 a n+2  a 
To prove   = A n  2  , induction on n.
 a n +1   a1 
n = 1, done above.
 ak +2  a 
Suppose   = A k  2  .
 a k +1   a1 
 a k +3  a  a 
  = A k + 2  = A k +1  2  . By MI, it is true for all positive integer n.
 ak +2   a k +1   a1 
1 1  1 1  1 1  1 0
(b) A2 – A – I =     –   –  
1 0  1 0  1 0  0 1
 2 1 1 1  1 0  0 0
=   –   –   =   = 0
 1 1 1 0  0 1  0 0
(c) Let xn = (x2 – x – 1)Q(x) + r1x + r2
1+ 5 1− 5
= (x – )(x – ) Q(x) + r1x + r2
2 2
n
1+ 5 1 + 5  1+ 5
Put x =   
 = r1 + r2 ⋯⋯ (1)
2  2  2
n
1− 5 1 − 5  1− 5
Put x =   
 = r1 + r2 ⋯⋯ (2)
2  2  2

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 3
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

n n
1 + 5  1 − 5 
(1) – (2) 5 r1 =   – 
  2 

 2   
1  1 + 5  1 − 5  
n n

r1 =   −  
5  2   2  
  

n −1 n −1
(1) − (2)  1
r2  −
1 
=
1 + 5 
 
1 − 5 
–  
1 + 5  1 − 5   1+ 5 1− 5   2  
     2 2     2 
 2   2 
   
n −1 n −1
2r2
1− 5
(
1 − 5 − 1 − 5 =  ) 1 + 5 
2
 –

1 − 5 

 2 

   
− −1
1  1 + 5  1 − 5  
n 1 n

r2 =   −  
5  2   2  
  

(d) An = (A2 – A – I)Q(A) + r1A + r2I = r1A + r2I
 a2   a2   a2 
An   = r1A   + r2  
 a1   a1   a1 
 a n+2  1 1   a 2  a 
  = r1     + r2  2 
 a n +1  1 0   a1   a1 
 an+1 = r1a2 + r2 a1 = r1 + r2
n −1 n −1
1  1 + 5   1 − 5   1  1 + 5  1 − 5  
n n
  −       
an+1 =
5  2   2   + 5  2  −  2  
        
n −1 n −1
1  1 + 5   3 + 5   1 − 5   3 − 5 
an+1 =    −   
5  2   2   2   2 
 
+ +
1  1 + 5  1 − 5  
n 1 n 1

=   −   
5  2   2  
 

2
1 1   2 1  a3 a2 
(e) Induction on n. n = 2, A2 =   =  = 
1 0   1 1  a2 a1 
 2 1 1 1   3 2   a4 a3 
n = 3, A3 =     =  = 
 1 1 1 0   2 1   a3 a2 
a ak  a ak +1 
Suppose Ak =  k +1  and Ak+1 =  k +2
ak 
for k > 1.
 ak ak −1   ak +1
2
By (b), A – A – I = 0
a ak +1   ak +1 a k   ak + 3 ak + 2 
∴ Ak+2 – Ak+1 – Ak = 0  Ak+2 = Ak+1 + Ak =  k +2
ak   ak ak −1   ak + 2 ak +1 
+ =
 ak +1
By induction, the result is true for all n > 1.
det(An) = det(A)n
= (− 1)
an+1 an n
an an−1
an+1an–1 – an2 = (–1)n

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 4
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

In particular, put n = 6, a7a5 – a62 = 13×5 – 82 = (–1)6 = 1.

We can draw two rectangles whose dimensions are 13×5 and 8×8 respectively so that:

If we dissect the two rectangles into small parts A, B, C, D and P, Q, R, S as shown:

S Q

B
A
R
D P
C

It seems that A = P, B = Q, C = R, D = S and the areas of the two rectangles appeared to be equal.
65 = 64?
Can you see that there is a white gap between the regions A, B C and D?

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 5
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

Exercise
Let a1 = 3, a2 = 2, an = 2an–1 – an–2 for n > 2.
Express an in terms of n only.
 2 − 1 a  a 
Let A =   . To prove  n + 2  = A n  2  , induction on n.
1 0   a n +1   a1 
 a3   2a2 − a1   2 − 1 a2 
n = 1,   =   =   
 a2   a2   1 0  a1 
 ak +2  a 
Suppose   = A k  2  .
 a k +1   a1 
 ak +3   2ak +2 − ak +1   2 − 1 ak +2  a  a 
  =   =    = A ⋅ Ak  2  = Ak +1  2  .
 ak + 2   ak +2   1 0  ak +1   a1   a1 
By MI, it is true for all positive integer n.
Next, A satisfies the matrix equation: A2 – 2A + I = 0
 2 − 1 2 − 1  2 − 1  1 0   3 − 2   4 − 2   1 0 
L.H.S. = A2 – 2A + I =    − 2  +   =   −   +   = 0
 1 0  1 0   1 0   0 1   2 − 1   2 0   0 1 
Thirdly, we find the remainder when xn is divided by x2 – 2x + 1 for n > 2.
Let xn = (x2 – 2x + 1)Q(x) + r1x + r2
Put x = 1: 1 = r1 + r2 ⋯⋯ (1)
Differentiate w.r.t. x: nxn–1 = (x – 1)2Q’(x) + 2(x – 1)Q(x) + r1
Put x = 1: n = r1 ⋯⋯ (2)
Sub. (2) into (1): r2 = 1 – n
∴ The remainder is nx + 1 – n
An = (A2 – 2A + I)Q(A) + nA + (1 – n)I
 a2   a2   a2 
An   = r1A   + r2  
 a1   a1   a1 
 a n+2  1 1   a 2  a 
  = n     + (1 – n)  2 
 a n +1  1 0   a1   a1 
an+1 = na2 + (1 – n)a1
 an = (n – 1)⋅2 + (1 – n + 1)⋅3 = 4 – n

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 6
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

Example Given a1 and a2, an+2 = an + an+1 for n ≥ 1.

Prove that a1 + a2 + a3 + … + an = an+2 – a2 for n ≥ 1
Proof: Induction on n.
n = 1, L.H.S. = a1 = (a1 + a2) – a2 = a3 – a2 = R.H.S.
∴ It is true for n = 1.
Suppose a1 + a2 + a3 + … + ak = ak+2 – a2 for some k ≥ 1
a1 + a2 + a3 + … + ak + ak+1 = (ak+1 + ak+2) – a2 (by induction assumption)
= ak+3 – a2
If it is true for n = k, then it is also true for n = k + 1.
By the principal of mathematical induction,
a1 + a2 + a3 + … + an = an+2 – a2 for all integers n ≥ 1
In particular, evaluate the following expression:
4 + 5 + 9 + 14 + 23 + 37 + 60 + 97 + 157 + 254 + 411 + 665 + 1076 + 1741 + 2817 + 4558.

a1 = 4, a2 = 5, a3 = 9 = 4 + 5 = a1 + a2, a4 = 14 = 5 + 9 = a2 + a3, … , an+2 = an + an+1 for n ≥ 1

a16 = 4558
a17 = 2817 + 4558 = 7375
a18 = 4558 + 7375 = 11933
a1 + a2 + a3 + … + a16 = a18 – a2 = 11933 – 5 = 11928

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 7
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

2. Difference Equation (Recurrence relation)

2.1 Types of difference equations.
The general form of difference equation is ar,n un+r + ar,n–1 un+r–1 + ... + ar,1 ur+1 + ar,0 ur = br.
It is called a linear difference equation of order n (ar,n ≠ 0, ar,0 ≠ 0).
e.g.1 ur+2 – ur+1 + ur = r is a linear difference equation of order 2.
Some example of difference equation which is non-linear.
e.g.2 ur ur–1 – aur – bur–1 + c = 0
If br = 0, the equation is said to be homogeneous.
e.g.3 ur – 2r ur–1 + k2 ur–2 = 0. This is a linear homogeneous difference equation of order 2.
(e.g.1 is non-homogeneous.)
If ar,n, ar,n–1, ... , ar,1, ar,0 are constants and independent of r, the equation is called a linear
difference equation with constant coefficients of order n.
e.g.4 ur – A ur–1 + B = 0.
This is a linear non-homogeneous difference equation with constant coefficients of order 1.
e.g.5 ur = 3 ur–1 – 2 ur–2
This is a linear homogeneous difference equation with constant coefficients of order 2.

2.2 First order linear homogeneous difference equations.

un+1 – a un = 0
un = a un–1 = a2 un–2 = a3 un–3 = ....... = an–1 u1
Let u1 = Aa, where A is a constant and independent of n.
∴ un = A an

2.3 First order linear non-homogeneous difference equation.

un+1 – a un = bn
un = a un–1 + bn–1
= a (a un–2 + bn–2) + bn–1
= ...................................
= an–1 u1 + bn–1 + a bn–2 + ....... + an–2 b1
= A an + bn–1 + a bn–2 + ....... + an–2 b1
In particular, if bn is independent of n, let bn = b.
 n n−1
 Aa + b ⋅ a − 1 , if a ≠ 1
un =  a −1
 A + (n − 1) b , if a = 1

 A a n + B , if a ≠ 1
un =  1 .
 A1 + Bn , if a = 1

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 8
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

2.4 Second order linear homogeneous difference equation un+2 – a un+1 + b un = 0

Define the characteristic equation to be t2 – at + b = 0
Let α, β be the roots of the characteristics equation.
∴ un+2 – (α + β) un+1 + αβ un = 0 ............(*)
(un+2 – α un+1) + β (un+1 – α un) = 0 .............(1)
Let vn = un+1 – α un
then vn+1 = un+2 – α un+1
∴ (1) becomes vn+1 – β vn = 0, which is of type in section 2.
By the result in section 2, vn = A βn ........ (2)
(*) can also be written as (un+2 – β un+1) + α (un+1 – β un) = 0 ........... (3)
Let wn = un+1 – β un
(3) becomes wn+1 – α wn = 0
By the result of section 2, wn = B αn ............ (4)

u n+1 − αu n = Aβ n
Rewrite (2) and (4): 
u n+1 − β u n = Bα
n

Case 1: α ≠ β, solving (2) and (4), un = A1αn + B1βn for some constants A1, B1.
Case 2: α = β, (2) becomes un+1 – α un = A αn, which is of type in section (3)
un = A' αn + A(αn–1 + α⋅αn–2 + ..... + αn–2⋅α)
=(A1n + B1) αn for some constant A1, B1.

2.5 mth order linear homogeneous difference equation with constant coefficients.
am um+r + am–1 um+r–1 + ... + a1 ur+1 + a0 ur = 0
The characteristic equation is am tm + am–1tm–1 + ... + a1 t + a0 = 0 ...... (*), where am ≠ 0, a0 ≠ 0
Suppose α1, α2, ..... , αm are the roots of (*)
Case 1: All roots are distinct, then un = A1α1n + A2α2n + ..... + Amαmn
Case 2: α1, α2, ..... , αk are distinct (k < m)

β1 of multiplicity ℓ 1 > 1, β2 of multiplicity ℓ 2 > 1, ...... , βj of multiplicity ℓ j > 1

k + ℓ 1 + ℓ 2 + ...... + ℓ j = m, then

un = A1α1n + A2α2n + ..... + Akαkn

( ) (
+ B1,ℓ1 −1n ℓ1 −1 + ⋯ + B1,1n + B1,0 β1n + ⋯ + B j ,ℓ j −1n
ℓ j −1
)
+ ⋯ + B j ,1n + B j ,0 β nj

where all letters except α1, α2, ..... , αk, β1, β2, ...... , βj are constant.
The proof are outside the scope of text.

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 9
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

2.6 The solution for non-homogeneous difference equation are much difficult and so is omitted.
We give an example to solve a non-linear one.
Advanced Level Pure Mathematics by S.L. Green p.408 Q16
(Reference: Techniques of Mathematics Analysis by C.J. Tranter p.33 ex.12)
Show that if un un+1 – a un+1 – b un + c = 0, for all positive integral values of n, the constants a,
b, c being independent of n, then
v
vn+2 + (a – b) vn+1 + (c – ab) vn = 0, where un = n+1 + a.
vn
Hence find un if a = 4, b = 1, c = 6, u1 = 1. Show that un → 2 as n → ∞.
v
Solution un = n+1 + a. The difference equation becomes
vn
vn+1 v v v
( + a)( n+ 2 + a) – a( n+ 2 + a) – b( n+1 + a) + c = 0
vn vn+1 vn+1 vn
vn + 2 v v v v
+ a n+ 2 + a n+1 + a2 – a n+ 2 – a2 – b n+1 – ab + c = 0
vn vn+1 vn vn+1 vn
vn + 2 v v
+ a n+1 – b n+1 – ab + c = 0
vn vn vn
vn+2 + (a – b) vn+1 + (c – ab) vn = 0 Q.E.D.
a = 4, b = 1, c = 6
vn+2 + 3 vn+1 + 2 vn = 0
Characteristic equation (t + 2)(t + 1) = 0
vn = A(–1)n + B(–2)n

A(− 1)n+1 + B(− 2)n+1

un = +4
A(− 1)n + B(− 2)n

B(− 2)n
un = 3 –
A(− 1)n + B(− 2)n

1
=3– , where C is a constant.
1 + C ⋅ 2 −n
1
u1 = 1  1 = 3 –
1+ C 2
1 C
= 1+
2 2
C = –1
1 1
un = 3 – −n
=2– n
1− 2 2 −1
as n → ∞, un → 3 – 1 = 2

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 10
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

Exercise
1. Find the general solution of Un+2 – 3 Un+1 + 2 Un = 0.
2. Find the general solution of Un+3 + 3 Un+2 + 3 Un+1 + 2 Un = 0.
(This is a third order difference equation where all the roots of the characteristic equation are
different.)
3. Find the general solution of Vn+1 – Vn = 5.
4. Find the general solution of Wn+1 – 2 Wn = 5.
5. Using Q.1, Q.3 and Q.4, solve Un+2 – 3 Un+1 + 2 Un = 5.
(This is second order non-homogeneous difference equation.)
6. Find the general solution of 4 Un+2 + 4 Un+1 + Un = 0
(In this case, the roots of the characteristic equation are equal.)
7. Using the method in Q.5, solve 4 Un+2 + 4 Un+1 + Un = –1.
(Can you solve Un+2 + b Un+1 + c Un = a ? Just memorizes the formulae you have derived, you
need not to do it all again.)
8. Solve Un+2 – 7 Un+1 + 12 Un = 2 n.
(This is a second order difference equation, but the coefficients are not similar, use a method
similar to Q.5)
9. Prove that the general solution of Un+2 + Un+1 + Un = 0 is
Un = A cos 120n° + B sin 120n°, where A and B may be complex.
(In this case, the roots are complex, use De-Movrie's Theorem)
10. Solve Un+2 + Un = n2 + n
(This is a second order non-homogeneous difference equation, and the roots of the characteristic
equation are complex.)
11. Solve Un+3 + Un+2 – Un+1 – Un = 0
(2 equal roots.)
12. Do Q.2 again, with the aids of Q.9.
(3 different roots.)
13. Solve Un+3 – 6 Un+2 + 12 Un+1 – 8 Un = 0
(3 equal roots, now can you guess a formula for an nth order linear homogeneous difference
equation?)

The above questions have no initial conditions. Now we come with initial conditions and the recurring
series. The solutions are called particular solutions.

14. Solve Un+3 – 3 Un+2 + 2 Un+1 = 0, U1 = 3, U2 = 4.

(This is a 'second' order difference equation.)
15. Solve Un+2 – 4 Un+1 – 5 Un = 2n, U1 = 0, U2 = 1.
(Complex roots, non-homogeneous.)
16. Solve Un+2 – Un = 0, U1 = 1, U2 = 0.
17. Solve Un+2 – 6 Un+1 + 9 Un = 1, U1 = 0, U2 = 0

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 11
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

18. Suppose Un satisfies the second order recurrence relation and is the coefficient of xn in the series:
1 + 5x + 9x2 + 13x3 + ...
(a) Find the recurrence relation Un+2 + a Un+1 + b Un = 0.
(b) Find the particular solution Un.
A + Bx
(c) Prove that the series converges to .
1 + ax + bx 2
Find the restriction on x.
19. Do Q.18 again with the series: 1 + x + 2x2 + 3x3 + ...
20. Advanced Level Pure Mathematics by S.L. Green p.408 Q14(i)
Find the nth term of the recurring series, and the sum to infinity of the series:
1 + 5x + 9x2 + 13x2 + ........
21. Advanced Level Pure Mathematics by S.L. Green p.408 Q15
The sequence u1, u2, u3, ....... is such that each term after the second is the sum of the two
preceding terms. Find un, given u1 = 1, u2 = –1.
22. Advanced Level Pure Mathematics by S.L. Green p.408 Q17
In the series u1 + u2 + u3 + ..... + un + ......, un = x un–1 + 2x2 un–2
If u1 = 4, u2 = 5x, find the general term un and the sum of the first n terms of the series.
23. Techniques of Mathematics Analysis by C.J. Tranter p.35 Q1
Find the general solution of the difference equation ur+2 + 3 ur+1 – 4 ur = 0, r ≥ 0.
Find also the values of the constants in the general solution if u0 = 21 and u1 = 1.
24. Techniques of Mathematics Analysis by C.J. Tranter p.37 Q17
1
The numbers xn satisfy the recurrence formula xn+3 = (xn + xn+1 + xn+2 ) .
3
Prove that if yn = xn + 2xn+1 + 3xn+2 then yn+1 = yn = y1 = 6x (say).
1
Prove also that if zn = (xn – x)2 + 2(xn – x) (xn+1 – x) + 3(xn+1 – x)2, then zn+1 = z n = 3–n z1.
3
25. Algebra by J.W. Archbold p.41 Q11
n
n(n + 1)⋯(n + k )
Show that  r (r + 1)⋯(r − k + 1) = k +1
.
r =0
ar
Deduce that, if ar+1 = , then
1 + rar

n +1 n +1 2
( )
n
1 1
a a = 2
+ n + 2n + 3 + (n − 1)(n )(n + 1)(n + 2 )(n + 3) .
r =0 r r +2 a0 3a0 20

26. Algebra by J.W. Archbold p.41 Q12

a n
1 n n(n + 1) n(n + 1)(2n + 1)
If ar+1 = r , then
ar + 1
 a 2 = a2 + a0
+
6
.
r =1 r 0

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 12
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

27. Algebra by J.W. Archbold p.41 Q13

1 1 1 1
If f (r) = + + + ⋯ + , where r is a positive integer, prove that
1 2 3 r
n
1
 (2r + 1) f (r ) = (n + 1)2 f (n) − 2 n(n + 1) .
r =1
28. Algebra by J.W. Archbold p.41 Q14.
The Fibonacci sequence u1, .... , un, .... is defined by u1 = 1, u2 = 2 and un = un–1 + un–2 for n >2

Prove that (i) un =

(1 + 5 ) n +1
(
− 1− 5 )
n +1

,
n +1
2 5

(ii) u1 + .... + un = un+2 – 2,

(iii) u1 + .... + u2n–1 = u2n – 1,
(iv) u2 + u4 + .... + u2n = u2n+1 – 1,

(v) u2n = un2 + u n2−1 ,

(vi) u2n+1 = u n2+1 – u n2−1 .

Supplementary exercises: Techniques of Mathematics Analysis by C.J. Tranter p.37 Q13 – Q18
End of Exercise
Answers
1. Un = A + B 2n

2. Un = A(− 2)
n
+B
(− 1 + 3i ) n

+C
(− 1 − 3i ) n

2n 2n

3. Vn = A + 5 n
4. Wn = B 2n – 5
5. Un = A + B 2n – 5 n
n
 1
6. Un =  −  ( A + Bn )
 2

n
 1 1
7. Un =  −  ( A + Bn ) −
 2 9

General solution of Un+2 + b Un+1 + c Un = a :

Let r and s be the roots of the characteristic equation.
Case 1 r ≠ s, r ≠ 1, s ≠ 1
a
Un = A rn + B sn +
1+ b + c
Case 2 r ≠ s, r ≠ 1, s = 1 then r = c

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 13
Fibonacci Sequence and Difference Equations (Recurrence relations) Created by Mr. Francis Hung

an
Un = A + B cn +
1− c
Case 3 r=s≠1
a
Un = rn(A + B n) +
1+ b + c
Case 4 r=s=1
an 2
Un = A + B n +
2
Note that in all cases, all the solutions have the general solution of the homogeneous equation.
So you need to just memories the non-homogeneous part.
n 5
8. Un = A 4n + B 3n + +
3 18
General solution of Un+2 + b Un+1 + c Un = 2 n.
Let r and s be the roots of the characteristic equation.
Suppose r ≠ s, r ≠ 1, s ≠ 1
2n 4 + 2b
Un = A rn + B sn + –
1+ b + c 1+ b + c
n 2 − n −1
10. Un = A cos 90n° + B sin 90n° +
2
n
11. Un = A + (–1) (B + Cn)
12. Un = A(–2)n + B cos 120n° + C sin 120n°
13. Un = 2n(A + B n + C n2)
14. Un = 2 + 2n–1

15. Using the result of Q.8, r = –1, s = 5, then Un =

( − 1) 13 × 5 n n 1
n
+ − +
12 240 4 16
1 (− 1)
n
16. Un = −
2 2
 5 n 1
17. Un = 3n  − +  +
 36 18  4
18. (a) Un+2 – 2 Un+1 + Un = 0
(b) Un = –3 + 4n
1 + 3x
(c) ; |x| < 1
1− 2x + x2
19. (a) Un+2 – Un+1 – Un = 0
1  1 + 5   1 − 5  
n n

(b) Un =   − 
5  2   2  
 
1 5 −1
(c) ; |x| <
1− x − x 2
2
1 + 3 x
20. (4n – 3)xn–1, , –1 < x < 1.
(1 − x )2
21.
1
10
( )(
5 − 3 5 1+ 5 )n−1
⋅ 2 −n+1 + (
1
10
)(
5 + 3 5 1− 5 )
n−1
⋅ 2 −n+1 .

22. [3⋅2n–1 + (–1)n–1]xn–1; 3[1 – (2x)n](1 – 2x)–1 + [1 – (–x)n](1 + x)–1.

23. ur = A + B(–4)r, A = 17, B = 4.

C:\Users\孔德偉\Dropbox\Data\MathsData\Pure_Maths\Sequence&Series\notes\Difference_Equation.docx Page 14