Solve recurring sequence using a generating function I have the sequence $a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$, $\forall\ n \ge 3$, with $a_0=2$, $a_1=2$, $a_2=4$ being the known terms, and I want to find a non-recursive equation for $a_n$ using a generating function.
What I have done:
$$
\begin{align}
A(x)
& = \sum_{n\ge0}{a_nx^n}
  = a_0+a_1x+a_2x^2+\sum_{n\ge 3}\left({3a_{n-1}-3a_{n-2}+a_{n-3}}\right)x^n\\
& = 2+2x+4x^2+3x\sum_{n\ge 3}{a_{n-1}x^{n-1}}
  -3x^2\sum_{n\ge 3}{a_{n-2}x^{n-2}}
  +x^3\sum_{n\ge 3}{a_{n-3}x^{n-3}}\\
& = 2+2x+4x^2+3xA(x)-3x^2A(x)+x^3A(x)\\
& = \frac{2+2x+4x^2}{1-3x+3x^2-x^3}\\
& = \frac{4x^2+2x+2}{(1-x)^3}
\end{align}
$$
As shown above, I have reached a solution for $A(x)$, but I'm not sure how to use it to find a solution for $a_n$. Any tips pointing me in the right direction would be greatly appreciated.
 A: $A(x)=2+2x+4x^2+3x\sum_{n\geq3}a_{n-1}x^{n-1}-3x^2\sum_{n\geq3}a_{n-2}x^{n-2}+x^3\sum_{n\geq3}a_{n-3}x^{n-3}$
$\Rightarrow A(x)=2-4x+4x^2+3x\sum_{n\geq1}a_{n-1}x^{n-1}-3x^2\sum_{n\geq2}a_{n-2}x^{n-2}+x^3A(x)$
$\Rightarrow A(x)=2-4x+4x^2+3xA(x)-3x^2A(x)+x^3A(x)$
$\Rightarrow (-x^3+3x^2-3x+1)A(x)=2-4x+4x^2$
$\Rightarrow A(x)=\frac{2-4x+4x^2}{-x^3+3x^2-3x+1}=\frac{2(2x^2-2x+1)}{(1-x)^3}=\frac{4}{1-x}-\frac{4}{(1-x)^2}+\frac{2}{(1-x)^3}$
I will use $\sum_{n\geq 0}x^n=\frac{1}{1-x}$
claim: $\frac{1}{(1-x)^k}=\sum_{n\geq 0}\binom{n+k-1}{n}x^n$
So, $\frac{1}{(1-x)^k}=(\sum_{n\geq 0}x^n)^k=\sum_{n\geq0}x^n(\sum_{{i_1}+{i_2}+...+{i_k}=n}1)=\sum_{n\geq0}x^n\binom{n+k-1}{n}$
So, now you need to find $a_n$ which is the coefficient of $x^n$ in the generating function
For your problem, it is $4\cdot\binom{n+1-1}{n}-4\cdot\binom{n+2-1}{n}+2\cdot\binom{n+3-1}{n}=4-4(n+1)+\frac{2(n+1)(n+2)}{2}=n^2+3n+2-4n\\=n^2-n+2$ 
A: Your calculation is correct up to
$$
\begin{align}
A(x)
& = \sum_{n\ge0}{a_nx^n}
  = a_0+a_1x+a_2x^2+\sum_{n\ge 3}\left({3a_{n-1}-3a_{n-2}+a_{n-3}}\right)x^n\\
& = 2+2x+4x^2+3x\sum_{n\ge 3}{a_{n-1}x^{n-1}}
  -3x^2\sum_{n\ge 3}{a_{n-2}x^{n-2}}
  +x^3\sum_{n\ge 3}{a_{n-3}x^{n-3}}
\end{align}
$$
But then
$$
\begin{align}
 \sum_{n\ge 3}{a_{n-1}x^{n-1}} &= \sum_{n\ge 2}{a_{n}x^{n}} = A(x) - 2 - 2x \\
 \sum_{n\ge 3}{a_{n-2}x^{n-2}} &= \sum_{n\ge 1}{a_{n}x^{n}} = A(x) - 2
\end{align}
$$
so that
$$
 A(x) = 2+2x+4x^2 + 3x(A(a) - 2-2x) -3x^2(A(x) - 2) + x^3A(x)
$$
which gives
$$
 A(x) = \frac{2-4x + 4x^2}{(1-x)^3} \, .
$$
Differentiating the geometric series $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$
twice gives
$$
 \frac{2}{(1-x)^3} = \sum_{n=2}^\infty n(n-1) x^{n-2} = \sum_{n=0}^\infty (n+1)(n+2)x^n \, ,
$$
therefore
$$
\begin{align}
 A(x) &= (1-2x + 2 x^2) \sum_{n=0}^\infty (n+1)(n+2)x^n \\
 &= \sum_{n=0}^\infty (n+1)(n+2)x^n - 2\sum_{n=0}^\infty (n+1)(n+2)x^{n+1} +2\sum_{n=0}^\infty (n+1)(n+2)x^{n+2}  \\
 &= \sum_{n=0}^\infty (n+1)(n+2)x^n - 2\sum_{n=1}^\infty n(n+1)x^n +2\sum_{n=2}^\infty (n-1)nx^n  \\
 &= \sum_{n=0}^\infty (n+1)(n+2)x^n - 2\sum_{n=0}^\infty n(n+1)x^n +2\sum_{n=0}^\infty (n-1)nx^n  \\
 &= \sum_{n=0}^\infty \bigl( (n+1)(n+2) - 2n(n+1) +2(n-1)n\bigr) x^n \\
 &= \sum_{n=0}^\infty (n^2 -n+2) x^n 
\end{align}
$$
and $a_n = n^2-n+2$.
A: Using Martin's hint, recall that $$ \frac{d^2}{dx^2} \left( \frac{1}{1-x} \right ) = \frac{2}{(1-x)^3}. $$
From a table (erm, Wikipedia), we see that the generating function for the sequence $a_n = \binom{n+2}{2}$ is the function $g(x) = \frac{1}{(1-x)^3}$. Doing some rearrangements we see that the intended solution is just $\frac{1}{4}\binom{n+2}{2}.$
A: $a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$, $\forall\ n \ge 3$, with $a_0=2$, $a_1=2$, $a_2=4$ being the known
There is a theorem that said the following: 
Let $q$ be a non zero number then $a_n = q^n$ is a solution of the linear homogeneous recurrence relation $a_n -c_1 a_{n-1} - a_2 a_{n-2} -\cdots - a_k a_{n-k} = 0$ with constant coefficients iff $q$ is a root of the polynomial equation $x^n - c_1 x^{n-1} - \cdots a_k = 0$ From "Introductory Combinatorics, 5th edition by Richard Brualdi". It is similar to differential equations you will find the roots if a root $r$  has a multiplicity say $k$ then the general solution $a_n = c_1 r^n + c_2 n r^n + c_3 n^2 r^n + \cdots + c_k n^k r^n $ 
Check the link "Roots of the characteristic polynomial"
https://en.wikipedia.org/wiki/Recurrence_relation
You can try this let 
$a_n = p^n$ 
then 
$$p^n -3p^{n-1} +3p^{n-2}-p^{n-3}=0$$ Factor $p^{n-3}$
$$p^{n-3} ( p^3 - 2p^2 + 2p - 1) = 0$$
$$p^3 -3p^2 +3p-1=0$$ Factor 
$$(p-1)(p^2-2p+1)=(p-1)(p-1)^2 =0$$
$(p-1)^3=0$ hence the solution is $1$ with multiplicity $3$ so 
$a_n = c_1 1^n +c_2 1^n n + c_3 1^n  n^2$  But we know that $1^n =1 $ then using the given initials to find the constants $a_0 = c_1 = 2 $ etc.. 
$$a_n = 2 - n + n^2$$ checking $a_3=8, a_4=14$
