Recurrence Relations

(Difference Equations)

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 538
Pure mathematics is the subject in which
we do not know what we are talking about,
or whether what we are saying is true.
— Bertrand Russell (1872–1970)

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 539
Recurrence Relations Arise Naturally
• When a problem has a recursive nature, recurrence
relations often arise.
– A problem can be solved by solving 2 subproblems of
the same nature.
• When an algorithm is of the divide-and-conquer type, a
recurrence relation describes its running time.
– Sorting, fast Fourier transform, etc.
• Certain combinatorial objects are constructed
recursively such as hypercubes (p. 662).

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 540
First-Order Linear Homogeneous Recurrence Relations
• Consider the recurrence relation

an+1 = dan ,

where n ≥ 0 and d is a constant.

• The general solution is given by

an = Cdn (79)

for any constant C.

– It satisfies the relation: Cdn+1 = dCdn .
• There are infinitely many solutions, one for each choice
of C.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 541
First-Order Linear Homogeneous Recurrence Relations
(concluded)
• Now suppose we impose the initial condition a0 = A.
• Then the (unique) particular solution is an = Adn .
– Because A = a0 = Cd0 = C.
• Note that
an = nan−1
is not a first-order linear homogeneous recurrence
relation.
– Its solution is n! when a0 = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 542
First-Order Linear Nonhomogeneous Recurrence
Relations
• Consider the recurrence relation

an+1 + dan = f (n).

– n ≥ 0.
– d is a constant.
– f (n) : N → R.
• A general solution no longer exists.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 543
kth-Order Linear Homogeneous Recurrence Relations
with Constant Coefficients
• Consider the kth-order recurrence relation

Cn an + Cn−1 an−1 + · · · + Cn−k an−k = 0, (80)

where Cn , Cn−1 , . . . , Cn−k ∈ R, Cn = 0, and Cn−k = 0.

• Add k initial conditions for a0 , a1 , . . . , ak−1 .
• Clearly,
ak , ak+1 , . . .
are well-defined.
• Indeed, an can be calculated with O(kn) operations.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 544
,Q−N ,Q−N , Q− ,Q

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 545
kth-Order Linear Homogeneous Recurrence Relations
with Constant Coefficients (concluded)
• A solution y for an is general if for any particular
solution y ∗ , the undetermined coefficients of y can be
found so that y is identical to y ∗ .
• Any general solution for an that satisfies the k initial
conditions and Eq. (80) is a particular solution.
• In fact, it is the unique particular solution because any
solution agreeing at n = 0, 1, . . . , k − 1 must agree for all
n ≥ 0.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 546
Conditions for the General Solutiona
(1) (2) (k)
Theorem 70 Let an , an , . . . , an be k particular solutions
of Eq. (80). If

(1) (2) (k)
a0 a0 ··· a0

a(1) (2)
a1 ···
(k)
a1
1
= 0, (81)
.. .. .. ..
. . . .

(1) (2) (k)
ak−1 ak−1 ··· ak−1

(1) (2) (k)

then an = c1 an + c2 an + · · · + ck an is the general
solution, where c1 , c2 , . . . , ck are arbitrary constants.
a Samuel Goldberg (1986), Introduction to Difference Equations.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 547
Fundamental Sets
• The particular solutions of Eq. (80) on p. 544,

a(1) (2) (k)

n , an , . . . , an ,

that also satisfy inequality (81) in Theorem 70 (p. 547)

are said to form a fundamental set of solutions.
• Solving a linear homogeneous recurrence equation thus
reduces to finding a fundamental set!

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 548
kth-Order Linear Homogeneous Recurrence Relations
with Constant Coefficients: Distinct Roots
• Let r1 , r2 , . . . , rk be the (characteristic) roots of the
characteristic equation

Cn xk + Cn−1 xk−1 + · · · + Cn−k = 0. (82)

• If r1 , r2 , . . . , rk are distinct, then the general solution has

the form
an = c1 r1n + c2 r2n + · · · + ck rkn ,
for constants c1 , c2 , . . . , ck determined by the initial
conditions.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 549
The Proof
• Assume an has the form cr n for nonzero c and r.
• After substitution into recurrence equation (80) on
p. 544, r satisfies characteristic equation (82).
• Let r1 , r2 , . . . , rk be the k distinct (nonzero) roots.
• Hence an = rin is a solution for 1 ≤ i ≤ k.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 550
The Proof (continued)
• Solutions rin form a fundamental set because


1 1 ··· 1


r1 r2 ··· rk

.. .. .. .. = 0.
. . . .

k−1
r1 r2k−1 · · · rkk−1
• The k × k matrix is called a Vandermonde matrix,
which is nonsingular whenever r1 , r2 , . . . , rk are distinct.a
a This is a standard result in linear algebra.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 551
The Proof (concluded)
• Hence
an = c1 r1n + c2 r2n + · · · + ck rkn
is the general solution.
• The k coefficients c1 , c2 , . . . , ck are determined uniquely
by the k initial conditions a0 , a1 , . . . , ak−1 :
⎡ ⎤ ⎡ ⎤⎡ ⎤
a0 1 1 ··· 1 c
⎢ ⎥ ⎢ ⎥⎢ 1 ⎥
⎢ ⎥ ⎢ ⎥⎢ ⎥
⎢ a1 ⎥ ⎢ r 1 r2 ··· rk ⎥ ⎢ c 2 ⎥
⎢ ⎥=⎢ ⎥⎢ ⎥ . (83)
⎢ . ⎥ ⎢ .
. . . .. .. ⎥
. ⎢ . ⎥
⎢ . ⎥ ⎢ . .. . ⎥ ⎢ .. ⎥
⎣ ⎦ ⎣ ⎦⎣ ⎦
ak−1 r1k−1 r2k−1 · · · rkk−1 ck

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 552
The Fibonacci Relation
• Consider
an+2 = an+1 + an .

• The initial conditions are a0 = 0 and a1 = 1 for

Fibonacci numbers (p. 221).a
• The characteristic equation is

r 2 − r − 1 = 0.
√
• Its two roots are (1 ± 5 )/2.b
a Clearly
an can be calculated with O(n) operations.
√
b The golden ratio (1 + 5 )/2 has fascinated mathematicians since

Pythagoras (570 B.C.–495 B.C.).

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 553
The Fibonacci Relation (continued)
• Because the roots are distinct, the fundamental set is

√ n
√ n
1+ 5 1− 5
, .
2 2

• The general solution is hence

√ n
√ n
1+ 5 1− 5
an = c 1 + c2 . (84)
2 2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 554
The Fibonacci Relation (continued)
• For example,

√ n
1+ 5
an =
2
satisfies the Fibonacci relation, as

√ n+2
√ n+1
√ n
1+ 5 1+ 5 1+ 5
= + .
2 2 2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 555
The Fibonacci Relation (concluded)
• Finally, solve

0 =
a0 = c 1 + c 2
√ √
1+ 5 1− 5
1 = a1 = c 1 + c2
2 2
√ √
for c1 = 1/ 5 and c2 = −1/ 5 .
• The particular solution is thus

√ n
√ n
1 1+ 5 1 1− 5
an = √ −√ , (85)
5 2 5 2

known as the Binet formula.a

a So
an can now be calculated with O(log n) operations. There is no
√
need to expand 5 !

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 556
Don’t Believe It?

√ 2
√ 2
1 1+ 5 1 1− 5
a2 = √ −√
5 2 5 2
√ √
1 1+2 5+5 1 1−2 5+5
= √ −√ = 1.
5 4 5 4

√ 3
√ 3
1 1+ 5 1 1− 5
a3 = √ −√
5 2 5 2
√ √ √ √
1 1 + 3 5 + 15 + 5 5 1 1 − 3 5 + 15 − 5 5
= √ −√
5 8 5 8
= 2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 557
Back to Inequality (81) (p. 547)
• Let us test the criterion for the general solution in
inequality (81):
√ 0
1 1+√5 0
√ − √1 1− 5
5 2 5 2
√ 1 √ 1
√1 1+ 5 − √1 1− 5
5 2 5 2

√
√
1 1− 5 1 1+ 5
= − +
5 2 5 2
1
= √
5
= 0,

indeed.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 558
Growth of the Binet Formula
• Recall the Binet formula (85) on p. 556:

√ n
√ n
1 1+ 5 1 1− 5
an = √ −√ .
5 2 5 2
√
• Note (1 − 5)/2 ≈ −0.618.
• So clearly,

√ n
1 1+ 5
an < √ + 1.
5 2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 559
Growth of the Binet Formula (concluded)
• On the other hand,

√ n
√ 0
1 1+ 5 1 1− 5
an ≥ √ − √
5 2 5 2

√ n
1 1+ 5 1
= √ − √ .
5 2 5

• So
√ n
1 1+ 5
an ∼ √ .
5 2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 560
Impacts of the Initial Conditions
• Different initial conditions give rise to different solutions.
• Suppose a0 = 1 and a1 = 2.
• Then solve

1 = a0 = c 1 + c 2 ,
√ √
1+ 5 1− 5
2 = a1 = c 1 + c2 ,
2 2
for
√ √ 2
c1 = [ (1 + 5 )/2 ] / 5 ,
√ 2
√
c2 = −[ (1 − 5 )/2 ] / 5 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 561
Impacts of the Initial Conditions (continued)
• Finally,

√ n+2
√ n+2
1 1+ 5 1 1− 5
an = √ −√ . (86)
5 2 5 2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 562
Impacts of the Initial Conditions (continued)
• Suppose a0 = a1 = 1 instead.
• Then solve

1 = a0 = c 1 + c 2 ,
√ √
1+ 5 1− 5
1 = a1 = c 1 + c2 ,
2 2
for
√ √
c1 = [ (1 + 5 )/2 ]/ 5 ,
√ √
c2 = −[ (1 − 5 )/2 ]/ 5 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 563
Impacts of the Initial Conditions (concluded)
• Finally,

√ n+1
√ n+1
1 1+ 5 1 1− 5
an = √ −√ . (87)
5 2 5 2

• This formula differs from Eq. (86) on p. 562.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 564
Generating Function for the Fibonacci Relation
• From an+2 = an+1 + an , we obtain
∞
∞

n+2
n+2 n+2

an+2 x = an+1 x + an x .
n=0 n=0

• Let f (x) be the generating function for { an }n=0,1,2,... .

• Then

f (x) − a0 − a1 x = x[ f (x) − a0 ] + x2 f (x).

• Hence
−a0 x + a0 + a1 x
f (x) = . (88)
1 − x − x2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 565
A Formula for the Fibonacci Numbers an

√ n
√ n n/2−1
1 1+ 5 1 1− 5 n−m−1
√ −√ = .
5 2 5 2 m=0
m

• The generating function (88) on p. 565 givesa

−a0 x + a0 + a1 x
1 − x − x2
x
=
1 − x(1 + x)
= x + x2 (1 + x) + x3 (1 + x)2 + · · ·
+xn−1 (1 + x)n−2 + xn (1 + x)n−1 + · · ·
n − 2 n − 1
n − n/2
= ··· + + ··· + + xn + · · · .
n/2 − 1 1 0

a Recall that a0 = 0 and a1 = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 566
Binary Sequences without Consecutive 0s
• Let an denote the number of binary sequences of length
n without consecutive 0s.
• There are an−1 valid sequences with the nth symbol
being 1.
• There are an−2 valid sequences with the nth symbol
being 0 because any such sequence must end with 10.
• Hence an = an−1 + an−2 , a Fibonacci sequence.
• Because a1 = 2 and a2 = 3, we must have a0 = 1 to
retrofit the Fibonacci sequence.
• The formula is Eq. (86) on p. 562.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 567
Number of Subsets without Consecutive Numbers
• How many subsets of { 1, 2, . . . , n } contain no 2
consecutive integers?
• A binary sequences b1 b2 · · · bn of length n can be
interpreted as the set { i : bi = 0 } ⊆ { 1, 2, . . . , n }.
• So a subset of { 1, 2, . . . , n } without consecutive integers
implies a binary sequence without consecutive 0s, and
vice versa.
• Hence there are an subsets of { 1, 2, . . . , n } that contain
no 2 consecutive integers, where an is the Fibonacci
number with a0 = 1 and a1 = 2.a
a Recall p. 567.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 568
Number of Subsets without Consecutive Numbers
(continued)
• From formula (86) on p. 562,

√ n+2
√ n+2
1 1+ 5 1 1− 5
an = √ −√
5 2 5 2

is the Fibonacci number with a0 = 1 and a1 = 2.

n−m+1
• We knew there are m m-element subsets of
{ 1, 2, . . . , n } that contain no consecutive integers.a
a Recall Eq. (15) on p. 93.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 569
Number of Subsets without Consecutive Numbers
(concluded)
• Hence an also equals
n/2
n−m+1
.
m=0
m
• In summary,
√ n+2 √ n+2 n/2
1 1+ 5 1 1− 5 n−m+1
√ −√ = .
5 2 5 2 m=0
m

• We could have used the identity on p. 566 to derive it.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 570
Number of Subsets without Cyclically Consecutive
Numbers
• How many subsets of { 1, 2, . . . , n } contain no 2
consecutive integers when 1 and n are considered
consecutive?
• Let an be the solution for the problem on p. 568.
• So an is the Fibonacci number with a0 = 1 and a1 = 2
(formula appeared in Eq. (86) on p. 562).
• Now assume n ≥ 3 first.
• There are an−1 acceptable subsets that do not contain n.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 571
Number of Subsets without Cyclically Consecutive
Numbers (continued)
• If n is included, an acceptable subset cannot contain 1
or n − 1.
• Hence there are an−3 such subsets.
Δ
• The total is therefore Ln = an−1 + an−3 , the Lucas
number.a
• It can be easily checked that
Ln = an−1 + an−3
= an−2 + an−3 + an−4 + an−5
= Ln−1 + Ln−2 .
a Corrected by Mr. Gong-Ching Lin (B00703082) on May 19, 2012.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 572
Number of Subsets without Cyclically Consecutive
Numbers (continued)
• Furthermore, L0 = 2 and L1 = 1.
– L3 = a2 + a0 = 3 + 1 = 4 and
L4 = a3 + a1 = 5 + 2 = 7.
– So

L2 = L4 − L3 = 3,
L1 = L3 − L2 = 1,
L0 = L2 − L1 = 2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 573
Number of Subsets without Cyclically Consecutive
Numbers (continued)
• The general solution is

√ n
√ n
1+ 5 1− 5
Ln = c1 + c2
2 2

by Eq. (84) on p. 554.

• Solve

2 = L0 = c1 + c2 ,
√ √
1+ 5 1− 5
1 = L1 = c1 + c2 ,
2 2
for c1 = 1 and c2 = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 574
Number of Subsets without Cyclically Consecutive
Numbers (concluded)
• The solution is finally

√ n
√ n
1+ 5 1− 5
Ln = + .
2 2

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 575
Number of Palindromes Revisited
• A palindrome is a composition for n ∈ Z+ that reads the
same left to right as right to left (p. 108).
• Let an denote the number of palindromes for n.
• Clearly, a1 = 1 and a2 = 2.
• Given each palindrome for n, we can do two things to
obtain a palindrome for n + 2.
– Add 1 to the first and last summands.
∗ So 1 + 3 + 1 becomes 2 + 3 + 2.
– Insert summand 1 to the start and end.
∗ So 1 + 3 + 1 becomes 1 + 1 + 3 + 1 + 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 576
The Proof (continued)
• This mapping is a one-to-two correspondence (why?).
• Hence
an+2 = 2an , n ≥ 1.

• The characteristic equation

r2 − 2 = 0
√
has two roots ± 2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 577
The Proof (continued)
• The general solution is hence
√ n √ n
an = c 1 2 + c2 − 2 .

• Solvea
√
1 = a1 = 2 (c1 − c2 ),
2 = a2 = 2(c1 + c2 ),

for c1 = (1 + √1 )/2 and c2 = (1 − √1 )/2.

2 2
a This time, we are not retrofitting.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 578
The Proof (concluded)
• The number of palindromes for n therefore equals
1+ √1 √ n 1 − √1 √ n
2 2
an = 2 + − 2
2 2
⎧ 1+ √1 1− √1
⎨ 2 2 n/2
+ 2
2n/2 , if n is even,
2 2
=
⎩ 1+ √2 √ √ (n−1)/2
1 1− √1
(n−1)/2
2
22 − 2
2
22 , if n is odd,
⎧
⎨ 2n/2 , if n is even,
=
⎩ 2(n−1)/2 , if n is odd,

= 2n/2 .

• It matches Theorem 20 (p. 110).

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 579
An Example: A Third-Order Relation
• Consider
2an+3 = an+2 + 2an+1 − an
with a0 = 0, a1 = 1, and a2 = 2.
• The characteristic equation

2r 3 − r 2 − 2r + 1 = 0

has three distinct real roots: 1, −1, and 0.5.

• The general solution is

an = c1 1n + c2 (−1)n + c3 (1/2)n
= c1 + c2 (−1)n + c3 (1/2)n .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 580
An Example: A Third-Order Relation (concluded)
• Solving the three initial conditions, we havea
⎡ ⎤ ⎡ ⎤⎡ ⎤
0 1 1 1 c1
⎢ ⎥ ⎢ ⎥⎢ ⎥
⎢ 1 ⎥=⎢ 1 −1 0.5 ⎥ ⎢ c2 ⎥.
⎣ ⎦ ⎣ ⎦⎣ ⎦
2 12 (−1)2 0.52 c3

• The solutions are

c1 = 2.5,
c2 = 1/6,
c3 = −8/3.
a Or see Eq. (83) on p. 552.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 581
The Case of Complex Roots
• Consider
an = 2(an−1 − an−2 )
with a0 = 1 and a1 = 2.
• The characteristic equation

r 2 − 2r + 2 = 0

has two distinct complex roots 1 ± i.

• The general solution is

an = c1 (1 + i)n + c2 (1 − i)n .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 582
The Case of Complex Roots (concluded)
• Solve the two initial conditions for c1 = (1 − i)/2 and
c2 = (1 + i)/2.
• The particular solution becomesa

an = (1 + i)n−1 + (1 − i)n−1
√ n
= ( 2 ) [ cos(nπ/4) + sin(nπ/4) ].

a An
√
equivalent one is an = ( 2 )n+1 cos((n − 1)π/4) by Mr. Tunglin
Wu (B00902040) on May 17, 2012.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 583
kth-Order Linear Homogeneous Recurrence Relations
with Constant Coefficients: Repeated Real Roots
• Consider the recurrence relation

Cn an + Cn−1 an−1 + · · · + Cn−k an−k = 0,

where Cn , Cn−1 , . . . are real constants, Cn = 0, Cn−k = 0.

• Let r be a characteristic root of multiplicity m, where

2 ≤ m ≤ k, of the characteristic equation

f (x) = Cn xk + Cn−1 xk−1 + · · · + Cn−k = 0.

• The general solution that involves r has the form

(A0 + A1 n + A2 n2 + · · · + Am−1 nm−1 ) rn , (89)

with A0 , A1 , . . . , Am−1 are constants to be determined.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 584
The Proof
• If f (x) has a root r of multiplicity m, then

f (r) = f (r) = · · · = f (m−1) (r) = 0.

• Because r = 0 is a root of multiplicity m, it is easy to

check that

0 = r n−k f (r),
0 = r(r n−k f (r)) ,
0 = r(r(r n−k f (r)) ) ,
..
.
m−1 m−1

0 = r(· · · r(r( r n−k f (r) ) ) · · · ) .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 585
The Proof (continued)
• Note that we differentiate and then multiply by r before
iterating.
• These give
n n−1 n−k
0 = Cn r + Cn−1 r + · · · + Cn−k r ,
0 = Cn nr n + Cn−1 (n − 1) r n−1 + · · · + Cn−k (n − k) r n−k ,
2 n 2 n−1 2 n−k
0 = Cn n r + Cn−1 (n − 1) r + · · · + Cn−k (n − k) r ,
.
.
.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 586
The Proof (continued)
• Now, an = nk r n , 0 ≤ k ≤ m − 1, is indeed a solution
because the kth row above says

0
= Cn nk r n + Cn−1 (n − 1)k r n−1 + · · · + Cn−k (n − k)k r n−k
= Cn an + Cn−1 an−1 + · · · + Cn−k an−k .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 587
The Proof (continued)
• From Eq. (81) on p. 547, r n , nr n , n2 r n , . . . , nm−1 r n form
a fundamental set ifa

1 ···
0 0

r r ··· r


r2 2r 2
··· 2m−1 r 2 = 0.

. .. .. ..
.. .
. .

r m−1 (m − 1) r m−1 · · · (m − 1)m−1 r m−1

• But it is a Vandermonde matrix in disguise.

a The ith row sets n = i − 1, i = 1, 2, . . . , m.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 588
The Proof (concluded)
• In fact, after deleting the first row and column, the
determinant equals

(m − 1)! r 1+2+···+(m−1)


1 1 ··· 1


1 2 ··· 2m−2
× .. .. .. ..
= 0.

. . . .

m−2
1 (m − 1) · · · (m − 1)

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 589
Nonhomogeneous Recurrence Relations
• Consider

Cn an + Cn−1 an−1 + · · · + Cn−k an−k = f (n). (90)

• Suppose an = an−1 + f (n).

• Then the solution is
n

an = a0 + f (i).
i=1
n
• A closed-form formula exists if one for i=1 f (i) does.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 590
Nonhomogeneous Recurrence Relations (concluded)
• In general, no failure-free methods exist except for
special f (n)s.
– See pp. 441–2 of the textbook (4th ed.).
– See p. 532 of Rosen (2012) when f (n) is the product
of a polynomial in n and the nth power of a constant.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 591
Examples (c, c1 , c2 , . . . Are Arbitrary Constants)
an+1 − an = 0 an = c
an+1 − an = 1 an = n + c
an+1 − an = n an = n(n − 1)/2 + c
an+2 − 3an+1 + 2an = 0 an = c1 + c2 2n
an+2 − 3an+1 + 2an = 1 an = c1 + c2 2n − n
an+2 − an = 0 an = c1 + c2 (−1)n
an+1 = an /(1 + an ) an = c/(1 + cn)

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 592
Trial and Error
• Consider an+1 = 2an + 2n with a1 = 1.
• Calculations show that a2 = 4 and a3 = 12.
• Conjecture:
an = n2n−1 . (91)

• Verify that, indeed,

(n + 1) 2n = 2(n2n−1 ) + 2n ,

and a1 = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 593
Application: Number of Edges of a Hasse Diagram
• Let an be the number of edges of the Hasse diagram for
the partial order (2{ 1,2,...,n } , ⊆).
• Consider the Hasse diagrams H1 for (2{ 1,2,...,n } , ⊆) and
H2 for ({ T ∪ { n + 1 } : T ⊆ { 1, 2, . . . , n } }, ⊆).
– H1 and H2 are “isomorphic.”
• The Hasse diagram for (2{ 1,2,...,n+1 } , ⊆) is constructed
by adding an edge from each node T of H1 to node
T ∪ { n + 1 } of H2 .
• Hence an+1 = 2an + 2n with a1 = 1.
• The desired number has been solved in Eq. (91) on
p. 593.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 594
Illustration with (2{ 1,2,3 } , ⊆)

{1,2,3}
{1,2}
{1,3} {2,3}
{1}
{2}
{3}
{}

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 595
Trial and Error Again
• Consider an+1 − Aan = B.
• Calculations show that

a1 = Aa0 + B,
a2 = Aa1 + B = A2 a0 + B(A + 1),
a3 = Aa2 + B = A3 a0 + B(A2 + A + 1).

• Conjecture (easily verified by substitution):

⎧
⎨ An a + B An −1 , if A = 1,
0 A−1
an = (92)
⎩ a0 + Bn, if A = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 596
Will the Number of Students Explode?
• A professor teaches a required course that N new
students take every year.
• He flunks 0 < f < 1 of the students taking his course.
• Assume students who fail take the course until he passes.
• Does the number of students in the classroom have a
limit?
• With a0 = 0, B = N , and A = f in Eq. (92) on p. 596,
the number of students in year n is
fn − 1 N
N → .
f −1 1−f

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 597
Financial Application: Compound Interesta
• Consider an+1 = (1 + r) an .
– Deposit grows at a period interest rate of r > 0.
– The initial deposit is a0 dollars.
• The solution is obviously

an = (1 + r)n a0 .

• The deposit therefore grows exponentially with time.

a “In
the fifteenth century mathematics was mainly concerned with
questions of commercial arithmetic and the problems of the architect,”
wrote Joseph Alois Schumpeter (1883–1950) in Capitalism, Socialism
and Democracy (1942).

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 598
Financial Application: Amortization
• Consider an+1 = (1 + r) an − M .
– The initial loan amount is a0 dollars.
– The monthly payment is M dollars.
– The outstanding loan principal after the nth
payment is an .
• By Eq. (92) on p. 596, the solution is
n
n (1 + r) −1
an = (1 + r) a0 − M .
r

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 599
The Proof (concluded)
• What is the unique monthly payment M for the loan to
be closed after k monthly payments?
• Set ak = 0 to obtain

k (1 + r)k − 1
ak = (1 + r) a0 − M = 0.
r
• Hence
(1 + r)k a0 r
M= k
.
(1 + r) − 1
• This is a standard formula for home mortgages and
annuities.a
a Lyuu (2002).

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 600
Trial and Error a Third Time
• Consider the more general an+1 − Aan = BC n .
• Calculations show that

a1 = Aa0 + B,
a2 = Aa1 + BC = A2 a0 + B(A + C),
a3 = Aa2 + BC 2 = A3 a0 + B(A2 + AC + C 2 ).

• Conjecture (easily verified by substitution):

⎧
⎨ An a + B An −C n , if A = C
0 A−C
an = . (93)
⎩ An a0 + BAn−1 n, if A = C

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 601
Application: Runs of Binary Strings
• A run is a maximal consecutive list of identical objects
(p. 112).
– Binary string “0 0 1 1 1 0” has 3 runs.
• Let rn denote the total number of runs determined by
the 2n binary strings of length n.
• First, r1 = 2.
– Each of “0” and “1” has 1 run.
• Next, r2 = 6.
– “00” and “11” each has 1 run, while “01” and “10”
each has 2 runs.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 602
The Proof (continued)
• In general, suppose we append a bit to every (n − 1)-bit
string b1 b2 · · · bn−1 to make b1 b2 · · · bn−1 bn .
• First, suppose bn−1 = bn (i.e., the last 2 bits are
identical).
• Then the total number of runs does not change.
– The total number of runs remains rn−1 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 603
The Proof (continued)
• Next, suppose bn−1 = bn (i.e., the last 2 bits are
distinct).
• Then the total number of runs increases by 1 for each
(n − 1)-bit string.
– There are 2n−1 of them.
– So the total number of runs becomes rn−1 + 2n−1 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 604
The Proof (continued)
• Hence
rn = 2rn−1 + 2n−1 , n ≥ 2. (94)

• By Eq. (93) on p. 601,

rn = 2n r0 + 2n−1 n.

• To make sure that r1 = 2, it is easy to see that r0 = 1/2.

• Hence
rn = 2n−1 + 2n−1 n = 2n−1 (n + 1).

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 605
The Proof (concluded)
• The recurrence (94) is identical to that for the number
of edges of a Hasse diagram (p. 594).
• But the initial condition was different: a1 = 1.
• Its slightly different solution appeared in Eq. (91) on
p. 593: an = n2n−1 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 606
Method of Undetermined Coefficients
• Recall Eq. (90) on p. 590, repeated below:

Cn an + Cn−1 an−1 + · · · + Cn−k an−k = f (n). (95)

(h)
• Let an denote the general solution of the associated
homogeneous relation (with f (n) = 0).
(p)
• Let an denote a particular solution of the
nonhomogeneous relation.
• Then
an = a(h)
n + a (p)
n .

• All the entries in the table on p. 592 fit the claim.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 607
Conditions for the General Solution
Similar to Theorem 70 (p. 547), we have the following
theorem.
(p)
Theorem 71 Let an be any particular solution of the
nonhomogeneous recurrence relation Eq. (95) on p. 607. Let

a(h)
n = C 1 a (1)
n + C 2 a (2)
n + · · · + C k a (k)
n

be the general solution of its homogeneous version as

(h) (p)
specified in Theorem 70. Then an + an is the general
solution of Eq. (95) on p. 607.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 608
Solution Techniques
• Typically, one finds the general solution of its
(h)
homogeneous version an first.
(p)
• Then one finds a particular solution an of the
nonhomogeneous recurrence relation Eq. (95) on p. 607.
(p) (h)
• Make sure an is “independent” of an .
• Finally, use the initial conditions to nail down the
(h)
coefficients of an .
(h) (p)
• Output an + an .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 609
an+1 − Aan = B Revisited
(h)
• Recall that the general solution is an = cAn by Eq.
(79) on p. 541.
• A particular solution is (verify it)
⎧
⎨ B/(1 − A), if A = 1,
a(p)
n =
⎩ Bn, if A = 1.

(p)
• So an = cAn + an .
• In particular,
⎧
⎨ a − B/(1 − A), if A = 1,
(p) 0
c = a0 − a0 =
⎩ a0 , if A = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 610
an+1 − Aan = B Revisited (concluded)
• The solution matches Eq. (92) on p. 596.
• We can rewrite the solution as
⎧
⎨ An [ a − a(p) ] + a(p) , if A = 1,
0 n n
an = (96)
⎩ a0 + a(p)
n , if A = 1.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 611
Nonhomogeneous an − 3an−1 = 5 × 7n with a0 = 2
(h)
• an = c × 3n , because the characteristic equation has
the nonzero root 3.
(p)
• We propose an = a × 7n .
• Place a × 7n into the relation to obtain
a × 7n − 3a × 7n−1 = 5 × 7n .
(p)
• Hence a = 35/4 and an = (35/4) × 7n = (5/4) × 7n+1 .
• The general solution is an = c × 3n + (5/4) × 7n+1 .
• Now, c = −27/4 because a0 = 2 = c + (5/4) × 7.
• So the solution is an = −(27/4) × 3n + (5/4) × 7n+1 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 612
Nonhomogeneous an − 3an−1 = 5 × 3n with a0 = 2
(h)
• As before, an = c × 3n .
(h)
• But this time an and f (n) = 5 × 3n are not
“independent.”
(p)
• So propose an = an × 3n .
• Plug an × 3n into the relation to obtain
an × 3n − 3a(n − 1) × 3n−1 = 5 × 3n .
(p)
• Hence a = 5 and an = 5n × 3n .
• The general solution is an = c × 3n + 5n × 3n .
• Finally, c = 2 with use of a0 = 2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 613
Nonhomogeneous an+1 − 2an = n + 1 with a0 = 4
(h)
• From Eq. (92) on p. 596, an = c × 2n .
(p)
• Guess an = an + b.
• Substitute this particular solution into the relation to
yield
a(n + 1) + b − 2(an + b) = n + 1.

• Rearrange the above to obtain

(−a − 1) n + (a − b − 1) = 0.

• This holds for all n if a = −1 and b = −2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 614
The Proof (concluded)
(p)
• Hence an = −n − 2.
• The general solution is

an = c × 2n − n − 2.

• Use the initial condition

4 = a0 = c − 2

to obtain c = 6.
• The solution to the complete relation is

an = 6 × 2n − n − 2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 615
Nonhomogeneous an+1 − an = 2n + 3 with a0 = 1
• This equation is very similar to the previous one:

an+1 − 2an = n + 1.
(h)
• First, an = d × 1n = d.
(p)
• If one guesses an = an + b as before, then

an+1 − an = a(n + 1) + b − an − b = a,

which cannot be right.a

(p)
• So we guess an = an2 + bn + c.
a Contributed by Mr. Yen-Chieh Sung (B01902011) on June 17, 2013.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 616
The Proof (continued)
• Substitute this particular solution into the relation to
yield

a(n + 1)2 + b(n + 1) + c − (an2 + bn + c) = 2n + 3.

• Simplify the above to obtain

2an + (a + b) = 2n + 3.

• The solutions are a = 1 and b = 2.

(p)
• Hence an = n2 + 2n + c.
• The general solution is an = n2 + 2n + c.a
a We merge d into c.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 617
The Proof (concluded)
• Use the initial condition

1 = a0 = c

to obtain c = 1.
• The solution to the complete relation is

an = n2 + 2n + 1 = (n + 1)2 .

• It is very different from the solution to the previous

example:
an = 6 × 2n − n − 2.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 618
Nonhomogeneous an+2 − 3an+1 + 2an = 2 with
a0 = 0 and a1 = 2
• The characteristic equation r 2 − 3r + 2 = 0 has roots 2
and 1.
(h)
• So an = c1 1n + c2 2n = c1 + c2 2n .
(p)
• Guess an = an + b.
(p)
• Substitute an into the relation to yield

a(n + 2) + b − 3[ a(n + 1) + b ] + 2(an + b) = 2.

• Rearrange the above to obtain a = −2.

(p)
• Hence an = −2n + b.

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 619
The Proof (concluded)
• The general solution is now an = c1 + c2 2n − 2n.a
• Use the initial conditions

0 = a0 = c1 + c2 ,
2 = a1 = c1 + 2c2 − 2.

to obtain c1 = −4 and c2 = 4.
• The solution to the complete relation is

an = −4 + 2n+2 − 2n.
a We merge b into c1 .

c
2018 Prof. Yuh-Dauh Lyuu, National Taiwan University Page 620