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$.
 A: 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$.
A: There is a theorem which is somewhat intuitive that says that if you take $\sum_{j=0}^n P(j)$ where $P$ is a polynomial of degree $d$, then the answer will be a polynomial in $n$ of degree $d + 1$. If you know this, then you can just plug in the values for $n = 0,1,2$ and then solve the arising linear system of equations to find the coefficients of your quadratic polynomial solution.
For a more direct solution for your case, note that adding up $3$ exactly $N$ times will result in a term of $3N$. So it only remains to see what happens when you add up $2n$ for $n=1 \ldots, N$. To see what this equals, note that you can double the sequence $1,2, \ldots N$ and write the duplicate copy in reverse order $N,N-1,\ldots,1$. lining up with the original sequence. Then you have twice the sum if you add all the terms , but every pair of lined up terms adds up to $N+1$ and you have $N$ pairs of terms. Thus the sum is $N(N+1)/2$. This is all you need to show that your solution must be a quadratic polynomial.
A: Denote by $s_n$ the difference $a_{n+1}-a_n$. It is easy to see that $a_n=a_0+ \left (s_{n-1}+s_{n-2}+ ... +s_0 \right)$; from $s_j=2j+3$ we get 
$$a_n=a_0+\sum_{j=0}^{n-1}s_j=a_0+\sum_{j=0}^{n-1}(2j+3)=1+2 \cdot \frac{(n-1)n}{2} + 3n =1+n^2-n+3n=n^2+2n+1 = (n+1)^2.$$ In the above calculations we have used the Gauss formula: $\sum_{j=1}^{m} j = \frac{m(m+1)}{2}$.  
