Comp.145  January 1997  Dr A.J. Mestel

Examples on Recurrence Relations

1. For each of the parts, find all sequences {x_{n}} satisfying the given recurrence relation. (a) x_{n} − 2x_{n−1} = 0 ,

(b) x_{n} − 3x_{n−1} + 2x_{n−2} = 0 ,

(c) x_{n} − 4x_{n−1} + 4x_{n−2} = 0 ,

(d) x_{n} − 3x_{n−1} + 3x_{n−2} − x_{n−3} = 0 .

2. For each of the parts, find all sequences {x_{n}} satisfying the given recurrence relation. (a) x_{n} − 2x_{n−1} = 3n ,

(b) x_{n} − 3x_{n−1} + 2x_{n−2} = −1 ,

(c) x_{n} − 3x_{n−1} + 2x_{n−2} = (−2)^{n} ,

(d) x_{n} − 4x_{n−1} + 4x_{n−2} = (−1)^{n} ,

(e) x_{n} − 4x_{n−1} + 4x_{n−2} = 2^{n} .

3. For each of the parts, find all sequences {x_{n}} satisfying the given relations. (a) x_{n} − 2x_{n−1} = 0 subject to x_{0} = 1,

(b) x_{n} − 4x_{n−1} + 4x_{n−2} = 0 subject to x_{0} = 1 and x_{1} = 0 ,

(c) x_{n} − 3x_{n−1} + 2x_{n−2} = −1 subject to x_{1} = 1 and x_{0} = 0.

4. For each of the parts, find all sequences {x_{n}} satisfying the given recurrence relation. Hint: what recurrence relation is the sequence {y_{n}} = {nx_{n}} forced to satisfy if {x_{n}} satisfies the given recurrence relation?

(a) nx_{n} − 2(n − 1)x_{n−1} + (n − 2)x_{n−2} = 0 ,

(b) nx_{n} − 2(n − 1)x_{n−1} + (n − 2)x_{n−2} = 2^{n} .

5. Solve the problem Y_{n+1} − Y_{n} = h^{2}n with Y_{0} = 1 where h is a given constant. Assuming 0 < h << 1, compare the solution for Y_{n} with the values y_{n} ≡ y(nh), where y(x) obeys the differential equation y′ = x, with y(0) = 1.

6. At each turn of a certain game a coin is tossed, landing heads or tails with equal probability. If it lands heads the player gains one point, if it lands tails she loses a point. The game continues in this way until either the player has twenty points, in which case she wins, or zero points, in which case she loses. If the player starts with 0 ⩽ r ⩽ 20 points what is the probability of her winning? Hint: let p_{t} be her probability of winning when she has t points and explain why p_{t} = \frac{1}{2}p_{t+1} + \frac{1}{2}p_{t−1}. Solve this recurrence relation for suitable values of p_{0} and p_{20}.