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?
Best Answer
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$$