Solve the recurrence relation (a^2)n+2 - 5(a^2)n+1 -4(a^2)n= 0, given a0 = 4 and a1= 13. .
Answers
Answer:
1. • Find a recurrence relation for the number of n-digit numbers whose decimal representation does not
contain “55”.
an = 9an−1 + 9an−2 (the sum of the number of such n-digit numbers that end in ∗ and ∗5 respectively,
where ∗ is anything that’s not a 5.)
• What are the initial conditions?
a0 = 1, a1 = 10.
Alternately, you could start at n = 1 with initial conditions a1 = 10, a2 = 99.
2. Write the closed form of the generating function for the sequence an = 6n+2
G(x) = X∞
n=0
anx
n =
X∞
n=0
6
n+2x
n = 36X∞
n=0
6
nx
n =
36
1 − 6x
.
3. Use generating functions to solve the recurrence an = 2an−1 + 5n where a0 = 1.
Let G(x) = X∞
n=0
anx
n
. Then since a0 = 1,
G(x) − 1 = X∞
n=1
anx
n =
X∞
n=1
(2an−1 + 5n
)x
n
=
X∞
n=1
2an−1x
n +
X∞
n=1
5
nx
n
= 2x
X∞
n=1
an−1x
n−1 +
X∞
n=1
5
nx
n
= 2x
X∞
n=0
anx
n +
X∞
n=0
5
nx
n − 5
0x
0
= 2xG(x) + 1
1 − 5x
− 1
So
G(x) − 2xG(x) = 1
1 − 5x
So
(1 − 2x)G(x) = 1
1 − 5x
Now
G(x) = 1
(1 − 2x)(1 − 5x)
and we need to find A and B such that
G(x) = A
1 − 2x
+
B
1 − 5x
We get A − 5Ax + B − 2Bx = 1 and thus A + B = 1 and 5A + 2B = 0. This solves to A = −2/3 and
B = 5/3. Thus an =
5
3
5
n −
2
3
2
n =
1
3
(5n+1 − 2
n+1).