6.042/18.062J Mathematics for Computer Science March 18,2005
Srini Devadas and Eric Lehman
Notes for Recitation 12
1 Solving linear recurrences
Guessing a particular solution,Recall that a general linear recurrence has the form,
f (n) = a
1
f (n?1) + a
2
f ( + a
d
f (n?d) + g(n)n?2) +···
As explained in lecture,one step in solving this recurrence is?nding a particular solu-
tion; i.e.,a function f (n) that satis?es the recurrence,but may not be consistent with the
boundary conditions,Here’s a recipe to help you guess a particular solution,
If g(n) is a constant,guess that f (n) is some constant c,Plug this into the recurrence
and see if any constant actually works,If not,try f (n) = bn + c,then f (n) = an
2
+
bn + c,etc,
More generally,if g(n) is a polynomial,try a polynomial of the same degree,If that
fails,try a polynomial of degree one higher,then two higher,etc,For example,if
2
g(n) = n,then try f (n) = bn + c and then f (n) = an + bn + c,
If g(n) is an exponential,such as 3
n
,then?rst guess that f (n) = c3
n
,Failing that,try
f (n) = bn3
n
+ c3
n
and then an
2
3
n
+ bn3
n
+ c3
n
,etc,
In practice,your?rst or second guess will almost always work,
Dealing with repeated roots,In lecture we saw that the solutions to a linear recurrence
are determined by the roots of the characteristic equation,For each root r of the equation,
the function r
n
is a solution to the recurrence,
Taking a linear combination of these solutions,we can move on to?nd the coef?cients,
The situation is a little more complicated when r is a repeated root of the characteristic
equation,if its multiplicity is k,then (not only r
n
,but)
n n 2 n
each of the functions r,nr,n r,.,,,n
k?1
r
n
is a solution to the recurrence,
so that our linear combination must use all of them,
Recitation 12 2
2 Mini-Tetris (again)
Remember Mini-Tetris from Recitation 4? Here is an overview,A winning con?guration in
the game is a complete tiling of a 2× n board using only the three shapes shown below,
For example,the several possible winning con?gurations on a 2× 5 board include,
In that past recitation,we had de?ned T
n
to be the number of different winning con?g-
urations on a 2 × n board,Then we had to inductively prove T
n
equals some particular
closed form expression,Remember that expression? Probably not,But no damage,now
you can?nd it on your own,
(a) Determine the values of T
1
,T
2
,and T
3
.
Solution,T
1
= 1,T
2
= 3,and T
3
= 5.
(b) Find a recurrence equation that expresses T
n
in terms of T
n?1
and T
n?2
,
Solution,Every winning con?guration on a 2× n board is of one three types,dis-
tinguished by the arrangment of pieces at the top of the board,
n? 1
n? 2 n? 2
There are T
n?1
winning con?gurations of the?rst type,and there are T
n?2
winning
con?gurations of each of the second and third types,Overall,the number of win-
ning con?gurations on a 2× n board is,
T
n
= T
n?1
+ 2T
n?2
Recitation 12 3
(c) Find a closed-form expression for T
n
,
Solution,The characteristic polynomial is r
2
r?2 = (r?2)(r +1),so the solution
n
is of the form A2
n
+ B(?1), Setting n = 1,we have 1 = T
1
= 2A? B,Setting
2
n = 2,we have 3 = T
2
= A2
2
+ B(?1) = 4A + B,Solving these two equations,we
conclude A = 2/3 and B = 1/3,That is,the closed form expression for T
n
is
n
2 1
T
n
= 2
n
+ (?1)
n
=
2
n+1
+ (?1)
,
3 3 3
Remember it now?
3 Inhomogeneous linear recurrences
Find a closed-form solution to the following linear recurrence,
T
0
= 0
T
1
= 1
T
n
= T
n?1
+ T
n?2
+ 1 (*)
(a) First?nd the general solution to the corresponding homogenous recurrence,
2
Solution,The characteristic equation is r? r? 1 = 0,The roots of this equation
are,
1 +
√
5
r
1
=
2
1?
√
5
r
2
=
2
Therefore,the solution to the homogenous recurrence is of the form

1?
√
5
n n
1 +
√
5
T
n
= A + B,
2 2
(b) Now?nd a particular solution to the inhomogenous recurrence,
Solution,Since the inhomogenous term is constant,we guess a constant solution,c,
So replacing the T terms in (*) by c,we require
c = c + c + 1,
namely,c =?1,That is,T
n
≡?1 is a particular solution to (*),
Recitation 12 4
(c) The complete solution to the recurrence is the homogenous solution plus the partic-
ular solution,Use the initial conditions to?nd the coef?cients,
Solution,

1?
√
5
n n
1 +
√
5
T
n
= A + B?1
2 2
All that remains is to?nd the constants A and B,Substituting the initial conditions
gives a system of linear equations,
0 = A + B?1

1?
√
5
1 +
√
5
1 = A + B?1
2 2
The solution to this linear system is,
5 + 3
√
5
A =
10
5?3
√
5
B =
10
(d) Therefore,the complete solution to the recurrence is,
Solution,

5?3
√
5

1?
√
5
n n
5 + 3
√
5

1 +
√
5
T
n
= +?1,
10
·
2 10
·
2
4 Back to homogeneous ones
Let’s get back to homogeneous linear recurrences,Find a closed-form solution to this one,
S
0
= 0
S
1
= 1
S
n
= 6S
n?1
9S
n?2
Anything strange?
2
Solution,The characteristic polynomial is r?6r +9 = (r?3)
2
,so we have a repeated
root,r = 3,with multiplicity 2,The solution is of the form A3
n
+Bn3
n
for some constants
A and B,Setting n = 0,we have 0 = S
0
= A3
0
+ B · 3
0
= A,Setting n = 1,we have 0 ·
1 = S
1
= A3
1
+ B · 3
1
= 3B,so B = 1/3,That is,1·
1
n3
n
S
n
= 0·3
n
+ = n3
n?1
,
3
·
5 Recitation 12
Short Guide to Solving Linear Recurrences
A linear recurrence is an equation
f(n) = a
1
f(n? 1) + a
2
f(n? 2) +,.,+ a
d
f(n? d) +g(n)

homogeneous part inhomogeneous part
together with boundary conditions such as f(0) = b
0
,f(1) = b
1
,etc,
1,Find the roots of the characteristic equation,
n
x = a
1
x
n?1
+ a
2
x
n?2
+,.,+ a
k
2,Write down the homogeneous solution,Each root generates one term and the homoge-
n
neous solution is the sum of these terms,A nonrepeated root r generates the term c
r
r,
where c
r
is a constant to be determined later,A root r with multiplicity k generates the
terms,
n n 2 n n
c
r
1
r,c
r
2
nr,c
r
3
n r,...,c
r
k
n
k?1
r
where c
r
1
,...,c are constants to be determined later,
r
k
3,Find a particular solution,This is a solution to the full recurrence that need not be con-
sistent with the boundary conditions,Use guess and verify,If g(n) is a polynomial,
try a polynomial of the same degree,then a polynomial of degree one higher,then two
higher,etc,For example,if g(n) = n,then try f(n) = bn+c and then f(n) = an
2
+bn+c,
If g(n) is an exponential,such as 3
n
,then?rst guess that f(n) = c3
n
,Failing that,try
f(n) = bn3
n
+ c3
n
and then an
2
3
n
+ bn3
n
+ c3
n
,etc,
4,Form the general solution,which is the sum of the homogeneous solution and the partic-
ular solution,Here is a typical general solution,
n
+f(n) = c2
n
+ d(?1) 3n + 1

homogeneous solution
particular solution
5,Substitute the boundary conditions into the general solution,Each boundary condition
gives a linear equation in the unknown constants,For example,substituting f(1) = 2
into the general solution above gives,
2 = c· 2
1
+ d· (?1)
1
+ 3· 1 + 1
2 = 2c? d
Determine the values of these constants by solving the resulting system of linear equa-
tions,