<s>[INST] Solution to a linear recurrence What is the general solution to the recurrence: $x(n + 2) = 6x(n + 1) - 9x(n)$ for $n \geq 0$;
with $x(0) = 0; x(1) = 1$?
Solution. The first few values of $x(n)$ are $0,1,6,27,...$ The auxiliary equation for the
recurrence is $r^2-6r+9$ which factors as $(r-3)^2$. Thus, we have repeated roots so that the general solution to the recurrence will have the form $x(n) = c_13^n + c_2n3^n$. Substituting the values $n = 0$ and $n = 1$ gives us $x(0) = 0 = c_1$ and $x(1) = 1 = 0 + c_2\cdot3$. Thus, $c_1=1/3$ and $x(n) = nc^{n-1}$.

What doesn't make sense to me is why they added the additional $n$ in $c_2n3^n$ to get $x(n) = c_13^n + c_2n3^n$. When I did it myself I only got $x(n) = c_13^n$. Also why is the answer $x(n) = nc^{n-1}$, when I got $x(n)=(1/3)n3^n$ or $x(n)=n3^{n-1}$ ?
 [/INST] The best technique for solving recurrences I've seen is given in Wilf's "generatingfunctionology".
Define the ordinary generating function:
$$
X(z) = \sum_{n \ge 0} x_n z^n
$$
From the recurrence, by the properties of ordinary generating functions (see section 2.2 in the cited book):
$$
\begin{align*}
\frac{X(z) - x_0 - x_1 z}{z^2} &= 6 \frac{X(z) - x_0}{z} - 9 X(z) \\
X(z) &= \frac{1}{3} \cdot \frac{1}{(1 - 3 z)^2}
           - \frac{1}{3} \cdot \frac{1}{1 - 3 z}
\end{align*}
$$
The solution is thus (see the table of series in section 2 of the book):
$$
\begin{align*}
x_n &= \frac{1}{3} \binom{-2}{n} (-3)^n - \frac{1}{3} \cdot 3^n \\
    &= \left( \binom{n + 2 - 1}{2 - 1} - 1 \right) 3^{n - 1} \\
    &= n 3^{n - 1}
\end{align*}
$$
</s>