<s>[INST] How do I solve the recurrence relation without manually counting? Given the recurrence relation : $a_{n+1} - a_n = 2n + 3$ , how would I solve this?
I have attempted this question, but I did not get the answer given in the answer key.
First I found the general homogenous solution which is $C(r)^n$ where the root is 1 so we get $C(1)^n$. Then I found the particular non homogenous solution which was $A_1(n) + A_0$. 
I then plugged the particular solution into the given recurrence relation and solved for $A_0$ and $A_1$. I got $A_0 = -1$ and $A_1 = 5$. After further steps I got 
$a_n = 5n-1 + 2(1)^n$
That answer is however completely off, in the answer key they have 
$a_n = (n+1)^2$. Can someone explain to me how to arrive at this answer?
EDIT: Initial condition is that $n\ge 0$ and $a_0 = 1$.
 [/INST] Let $$f(x) = \sum_{n=0}^\infty a_n x^n.$$
Multiplying both sides of the given recurrence equation by $x^n$ and summing over $n\geqslant0$, the left-hand side becomes
$$\sum_{n=0}^\infty a_{n+1}x^n-\sum_{n=0}^\infty a_nx^n = \frac1x\sum_{n=0}^\infty a_{n+1}x^{n+1} - f(x) = \frac1x\left(f(x)-1\right)+f(x).$$
The right-hand side becomes
$$\sum_{n=0}^\infty (2n+3)x^n = 2\sum_{n=0}^\infty(n+1)x^n + \sum_{n=0}^\infty x^n=\frac2{(1-x)^2}+\frac1{1-x}. $$
Equating the two we have
$$\frac1x\left(f(x)-1\right)+f(x) = \frac2{(1-x)^2}+\frac1{1-x},$$
and solving for $f(x)$,
$$f(x) = \frac{1+x}{(1-x)^3}.  $$
Now
$$\frac1{(1-x)^3}=\sum_{n=0}^\infty\frac12(n+1)(n+2)x^n = 1 + \sum_{n=1}^\infty\frac12(n+1)(n+2)x^n, $$
and
$$\frac x{(1-x)^3}=\sum_{n=0}^\infty\frac12(n+1)(n+2)x^{n+1} = \sum_{n=1}^\infty \frac12n(n+1)x^n. $$
Hence
$$
\begin{align*}
\frac{1+x}{(1-x)^3} &= 1 + \sum_{n=1}^\infty\frac12(n+1)(n+2)x^n + \sum_{n=1}^\infty\frac12n(n+1)x^n\\
&= 1 + \sum_{n=1}^\infty\frac12(n+1)(n+n+2)x^n\\
&= 1 + \sum_{n=1}^\infty(n+1)^2x^n\\
&= \sum_{n=0}(n+1)^2x^n.
\end{align*}
$$
It follows that $a_n=(n+1)^2$ for $n\geqslant0$.
</s>