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$. The characteristic polynomial of the linear recurrence iswith roots $3/4$ and $-1/4$. Hence $p_n=a(3/4{)}^n+b(-1/4{)}^n$. The initial conditions give $a+b=1$, $3a-b=2$, so $a=3/4$, $b=1/4$. Therefore