<s>[INST] Recurrence Relations with single roots I have the following recurrence: $a_{n+3}=3a_{n+2}-3a_{n+1}+a_n$
with initial values $a_1 = 1, a_2 = 4, a_3 = 9$
I have found the characteristic equation to be $x^3-3x^2+3x-1$ and the root to be 1.
My text book is not helpful in how I should go about solving this when I have a single root and don't have the $a_0$ value given. 
Any tips on how I could move forward to solve this?
 [/INST] Use Wilf's "generatingfunctionology". Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$ to get:
$$
\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3}
  = 3 \frac{A(z) - a_0 - a_1 z}{z^2} - 3 \frac{A(z) - a_0}{z} + A(z)
$$
Using the recurrence "backwards" gives $a_0 = 0$. Solving for $A(z)$ and expanding into partial fractions:
$$ 
A(z) = \frac{1}{1 - z} - \frac{3}{(1 - z)^2} + \frac{2}{(1 - z)^3}
$$
By the expansions:
$$
(1 - u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} (-u)^k
             = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} u^k
$$
(the binomial coeffiecients are just $m - 1$ degree polynomials in $k$) you get:
$$
a_n = 1 - 3 \binom{n + 1}{1} + 2 \binom{n + 2}{2}
    = 1 - 3 \frac{(n + 1)}{1} + 2 \frac{(n + 1) (n + 2)}{2}
    = n^2
$$
</s>