How do I solve the recurrence relation without manually counting?

Question

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$.

Answer 1

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$.

Answer 2

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.