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?
 A: If the characteristic equation has roots $x_1,x_2,\ldots,x_k$, where ($x_i \neq x_j, \, \forall i \neq j$) the root $x_j$ has multiplicity $m_j$, then the solution is of the form
$$a_n = \sum_{j=1}^k P_j(n)x_j^n$$
where $P_{j}(n)$ is a polynomial in $n$ of degree $m_j-1$. Hence, in your case,
$$a_n = (c_0 + c_1 n + c_2 n^2) 1^n, \text{i.e., } a_n = c_0 + c_1 n + c_2 n^2$$ With the initial conditions, we get that
$$a_n = n^2$$
A: 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
$$
