Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 2 / 8B (Differential Equations)

For the homogeneous linear recurrence relation, a trial $u_k=r^k$ gives the characteristic equation of a linear recurrence $r^2+5r+6=(r+2)(r+3)=0$. Thus the two homogeneous sequences are $(-2{)}^k$ and $(-3{)}^k$. Seek a particular solution $u_k=ak+b$; substitution gives $12ak+12b-5a=12k+1$, so $a=1$ and $b=1/2$. HenceThe two independent constants supply arbitrary initial values for this second-order linear recurrence relation.

The homogeneous sequences are again $(-2{)}^k$ and $(-3{)}^k$. A particular solution $D{2}^k$ has left-hand side $10D{2}^k$, so $D=1/10$. Consequently $y_k=A(-2{)}^k+B(-3{)}^k+2^k/10$. The two initial conditions require $A+B=9/10$ and $-2A-3B=4/5$, giving $A=7/2$ and $B=-13/5$. ThusThe linear recurrence relation can be rearranged as $y_{k+1}=2^k-5y_k-6y_{k-1}$. Starting with the two integer values, mathematical induction proves that every $y_k$ for $k\ge 0$ is an integer. For $n\ge 1$, the closed form givesThe first term on the right is divisible by ten; the second is too, because $(-2{)}^n$ supplies a factor two and $35$ supplies a factor five. Therefore $10$ divides $2^n-26(-3{)}^n$ for every positive integer $n$. The positivity condition matters: at $n=0$ the expression is $-25$.