Simplest way to prove uniqueness of solution to recurrence relation

Question

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.

Answer 1

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

Answer 2

Suppose there exist two different solutions, $\{a_n\}$ and $\{b_n\}$. Then for all n, $a_{n}- b_{n}= 3a_{n-1}+ 4a_{n-2}- n+ 6- b_{n-1}- b_{n-2}+ n- 6= 3(a_{n-1}- b_{n-1})+ 4(a_{n-2}- b_{n-2})$. Also $a_0- b_0= 0$ and $a_1- b_1= 0$. Letting $c_n= a_n- b_n$, Show that $c_n= 0$ for all n is the unique solution to $c_n= 2c_{n-1}+ 4c_{n-2}$, $c_0= c_1= 0$.