 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/discrete-mathematics-continuous-mathematics-and-probability/8/b/iii/solution

The initial values are

p_{0} = 1

and

p_{1} = 1/2

16 r^{2} - 8 r - 3 = (4 r - 3) (4 r + 1),

3/4

and

- 1/4

. Hence

p_{n} = a (3/4)^{n} + b (- 1/4)^{n}

a + b = 1

3 a - b = 2

, so

a = 3/4

b = 1/4

. Therefore

p_{n} = \frac{3}{4} (\frac{3}{4})^{n} + \frac{1}{4} (- \frac{1}{4})^{n} = \frac{3 ^{n + 1} + ( - 1 ) ^{n}}{4 ^{n + 1}}, n \geq 0.

 New to topics? Read the docs here!