Let $a$ be a sequence where $a_0 = 21$, $a_1 = 35$, and $a_{n+2} = 4a_{n+1} − 4a_n + n^2$ for $n ≥ 2$. Compute $a_{2006} \pmod {100}$

Question

Problem

Let $a_0, a_1, a_2, ...$ be a sequence of real numbers defined by $a_0 = 21, a_1 = 35$, and $a_{n+2} = 4a_{n+1}-4a_n+n^2$ for $n ≥ 2$. Compute the remainder obtained when $a_{2006}$ is divided by > $100$. (From HMMT Feb 2006 Guts Round, #23)

I've tried reading the official solution, which i get up to this point:

No pattern is evident in the first few terms, so we look for a formula for $a_n$. If we write $a_n = An^2 + Bn + C + b_n$ and put $b_{n+2} = 4b_{n+1} − 4b_n$. Rewriting the original recurrence, we find $n^2 + 8An + (4A + 4B) + 4b_{n+1} − 4b_n$. Solving, A = 1, B = 4, C = 8. With this information, we can solve for $b_0 = 1$ and $b_1 = 6$. ...

Specifically, I'm not understanding why it's possible that $b_0 = 1$ and $b_1 = 6$, since using the original equation for $a_{n+2}$ and the new equation with $A$, $B$ and $C$ plugged in gives $b_2=36$. Can someone please explain?

Answer 1

Consider the basics of the problem in a general way. Let $$ a_{n+2} = 4 \, a_{n+1} - 4 \, a_{n} + n^2 $$ then the generating function can be found to be $$ \sum_{n=0}^{\infty} a_{n} \, t^{n} = \frac{a_{0} + (a_{1} - 4 \, a_{0}) \, t}{(1 - 2 \, t)^2} + \frac{t^3 \, (1+t)}{(1-t)^3 \, (1-2 \, t)^2}. $$ Decomposing the fractions leads to $$ a_{n} = 2^{n-1} \, ((a_{1} - 2 \, a_{0} + 3) \, n + 2 \, a_{0} - 16 ) + n^2 + 4 \, n + 8. $$ The solution defines $b_{n}$ by $b_{n+2} = 4 \, b_{n+1} - 4 \, b_{n}$ with the generating function $$ \sum_{n=0}^{\infty} b_{n} \, t^n = \frac{b_{0} + (b_{1} - 4 \, b_{0}) \, t}{(1 - 2 \, t)^2} $$ and has the form $b_{n} = 2^{n-1} \, ((b_{1} - 2 \, b_{0}) \, n + 2 \, b_{0})$. Now, \begin{align} a_{n} &= 2^{n-1} \, ((a_{1} - 2 \, a_{0} + 3) \, n + 2 \, a_{0} - 16 ) + n^2 + 4 \, n + 8 \\ b_{n} &= 2^{n-1} \, ((b_{1} - 2 \, b_{0}) \, n + 2 \, b_{0}), \end{align} it is seen that $a_{n} = b_{n} + t_{n} + 2^{n-1} \, (3 \, n -16)$, where $t_{n} = n^2 + 4 \, n + 8$ is the transformation defined. The portion the solution does not appear to account for is $2^{n-1} \, (3 \, n - 16)$. Also notice that if the transformation of the problem, $a_{n} = b_{n} + n^2 + 4 \, n + 8$, is to be true then $b_{0} = a_{0} - 8$ and $b_{1} = a_{1} - 13$. If this is not the case then the method of the solution is then only partly true, but does provide a method to solve the difference equation by reducing the complexity.

With the given $a_{0} = 21$ and $a_{1} = 35$ then $a_{n} = 2^n \, (13 - 2 \, n) + n^2 + 4 \, n + 8$. By considering $a_{n} \, (\text{mod} \, 100)$ then it can be found that $a_{n+100} \equiv a_{n} \, (\text{mod} \, 100)$ for $n \geq 2$. It would then seem that $a_{2006} = a_{6 + 20 \cdot 100} \equiv a_{6} = 32 \, (\text{mod} \, 100)$.