Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 2 / 8B / ii

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$.