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

  • $\begingroup$ What is the initial condition? $\endgroup$ – Math1000 Mar 6 '15 at 0:21
  • $\begingroup$ Sorry, let me edit that in! $\endgroup$ – Belphegor Mar 6 '15 at 0:23
  • $\begingroup$ Is the approach I used correct in anyway? $\endgroup$ – Belphegor 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$.

  • $\begingroup$ How did you go from 1+x/(1-x)^3 to the next step? $\endgroup$ – Belphegor Mar 6 '15 at 0:49
  • $\begingroup$ $\frac{1+x}{(1-x)^3}=\frac1{(1-x)^3} + \frac x{(1-x)^3}$ and the series expansion for $\frac1{(1-x)^3}$. $\endgroup$ – Math1000 Mar 6 '15 at 0:51
  • 1
    $\begingroup$ 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? $\endgroup$ – Belphegor Mar 6 '15 at 0:58
  • $\begingroup$ 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 $\endgroup$ – Math1000 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.

  • $\begingroup$ So my original approach cannot be used? $\endgroup$ – Belphegor Mar 6 '15 at 0:28
  • $\begingroup$ 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. $\endgroup$ – user2566092 Mar 6 '15 at 0:32
  • $\begingroup$ 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 $\endgroup$ – Belphegor Mar 6 '15 at 0:36
  • $\begingroup$ Actually, I might have interpreted the table wrong, but how would I solve for the particular solution if my logic was wrong? $\endgroup$ – Belphegor Mar 6 '15 at 0:39
  • $\begingroup$ 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. $\endgroup$ – user2566092 Mar 6 '15 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.