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

• What is the initial condition? Mar 6 '15 at 0:21
• Sorry, let me edit that in! Mar 6 '15 at 0:23
• Is the approach I used correct in anyway? Mar 6 '15 at 0:32

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

• How did you go from 1+x/(1-x)^3 to the next step? Mar 6 '15 at 0:49
• $\frac{1+x}{(1-x)^3}=\frac1{(1-x)^3} + \frac x{(1-x)^3}$ and the series expansion for $\frac1{(1-x)^3}$. Mar 6 '15 at 0:51
• Your technique makes sense, but I don't understand why i didn't see your way of doing it in my textbook o.o..What is this technique called? Mar 6 '15 at 0:58
• Generating functions. They're really nifty and you can do all sorts of things with them. Here's a great introduction: math.upenn.edu/~wilf/DownldGF.html Mar 6 '15 at 1:08

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.

• So my original approach cannot be used? Mar 6 '15 at 0:28
• Something went wrong when you attempted to solve for the non-homogeneous part of the solution. You should have gotten $an^2 + bn + c$ for the general form, which is also what is stipulated in the theorem I quoted. Mar 6 '15 at 0:32
• Ah yes, I had a feeling that it was there, but the reason why I wrote what you see now is because according to my chart, if the right side has 'n' on it then the particular solution of the non homogenous relation is A_1(n) + A_0 Mar 6 '15 at 0:36
• Actually, I might have interpreted the table wrong, but how would I solve for the particular solution if my logic was wrong? Mar 6 '15 at 0:39
• One way to see that it must be a quadratic polynomial is to note that a sum of constant terms is a linear polynomial, and if you take a sum of pure linear terms $n$ then you can arrange them in a triangle that makes up half a rectangle by cutting the rectangle down the diagonal, and thus see that a sum of linear terms is a quadratic polynomial. Mar 6 '15 at 0:48

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