Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 7 / c

A particular solution of the linear recurrence is $-n-1$, while its homogeneous solution is $C{2}^n$. The initial value gives $C-1=1$, soSubstitution verifies $u_{n+1}-2u_n=n$, and the recurrence plus $u_0$ determines all later terms uniquely.

The characteristic polynomial is $r^2-3r+2=(r-1)(r-2)$. Therefore $u_n=A+B{2}^n$. The initial values give $A+B=1$ and $A+2B=0$, yielding $A=2$, $B=-1$. HenceThe two constants are fixed by the two initial conditions of this second-order linear recurrence.

The characteristic polynomial of the homogeneous linear recurrence is $(r-2{)}^2$, so its repeated-root solutions are $(A+Bn)2^n$. A constant particular solution is one. Thus $u_n=1+(A+Bn)2^n$. The initial conditions give $A=-1$ and $B=1$, henceThe factor $n$ is required by the repeated root of a polynomial; omitting it would lose one independent solution.