Explicit form of recursive formula So I was asked to give some background on the problem so here it goes. I was working on creating a problem with functions and series and at one point I ended up creating a bunch of these recurrence relation problems. So this one in particular seemed to me it was solvable, and I was pretty sure I saw something very similar in the past, however standard techniques failed to me and I could not even guess the answer to use induction, so that's why I posted the question, and the answers were extremely helpful to be honest, so thanks :).
What is the explicit form of the following recursive sequence:
$a_0 = 0 \\
a_1=2 \\
a_{n+1}=2a_n-a_{n-1}+2(n+1)
$
How can one solve this without guessing the answer, which btw I could not.
 A: Hint
Call $b_n=a_{n}-a_{n-1}$ and get
$$b_{n+1}-b_n=2(n+1)$$
Now use a telescoping sum.
A: Arnaldo has suggested a very nice elementary approach. It can also be done using generating functions. The recurrence
$$a_n=2a_{n-1}-a_{n-2}+2n$$
is valid for all $n\in\Bbb Z$ if we assume that $a_n=0$ for $n<0$. The generating function for the sequence $\langle a_n:n\ge 0\rangle$ is $g(x)=\sum_na_nx^n$, so multiply through by $x^n$ and sum over $n$:
$$\begin{align*}
g(x)&=2\sum_na_{n-1}x^n-\sum_na_{n-2}x^n+2\sum_nnx^n\\
&=2x\sum_na_{n-1}x^{n-1}-x^2\sum_na_{n-2}x^{n-2}+2\sum_nnx^n\\
&=2xg(x)-x^2g(x)+2x\sum_nnx^{n-1}\\
&=\left(2x-x^2\right)g(x)+2x\left(\frac1{1-x}\right)'\\
&=\left(2x-x^2\right)g(x)+\frac{2x}{(1-x)^2}\,,
\end{align*}$$
so
$$g(x)=\frac{2x}{(1-x)^2(1-2x+x^2)}=\frac{2x}{(1-x)^4}\,.$$
Now it helps to know some basic power series, in this case that
$$\frac1{(1-x)^4}=\sum_n\binom{n+3}3x^n\,,$$
so that
$$\begin{align*}
\frac{2x}{(1-x)^4}&=2x\sum_n\binom{n+3}3x^n\\
&=2\sum_n\binom{n+3}3x^{n+1}\\
&=\sum_n2\binom{n+2}3x^n\,,
\end{align*}$$
and
$$a_n=2\binom{n+2}3\,.$$
