Suppose I have the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2} -n +6,$ and I am given initial conditions $a_0 = 0; a_1 = 1$. I understand that without using initial conditions, the general solution $g(n,\alpha,\beta) = \alpha(4)^n +\beta(-1)^n + \frac{1}{6}n – \frac{25}{36} $ gives us a vector space for the $a_n$ solution, and so any $g(n,\alpha_1,\beta_1) + g(n,\alpha_2,\beta_2)$ is also a solution.
But after making use of the initial conditions, I'm not sure how to prove (in a non-hand-waving way) that $a_n = \frac{4^{n+1}}{9} + \frac{(-1)^n}{4} + \frac{1}{6}n – \frac{25}{36}$ is the unique solution for the recurrence relation.
Best Answer
Suppose that $a'_n$ is another solution. Let $n$ be the smallest index for which $a_n \neq a'_n$. Clearly $n \neq 0,1$, since $a_0=a'_0=0$ and $a_1=a'_1=1$ by the initial condition. Thus $n \ge 2$. But now,
$$a_n= 3a_{n-1}+4a_{n-2}-n+6= 3a'_{n-1}+4a'_{n-2}-n+6= a_n'$$ a contradiction.
This means that $a_n=a'_n$ for all $n$.