3

Solve $$ x_{n+1} - x_n = 2n + 3, x_0 = 1, n \ge 0$$

I would try to find a homogen solution and used $$ r^2 - r = 0$$ and got $$x^h_n = A1^n$$ but this seems wrong and I'm stuck on how to continue.

=== Edit ===

Homogen solution: $r^2 - r = 0 $ has the solutions $r=0, r=1 $ So we have $$x_n^h = C1^n$$

Particulair solution: $x_n^p = B(2n+3)$. Inserting this in the original equation gives:

$$ B(2(n+1)+3) - B(2n + 3) = 2n + 3$$ $$ B = \frac{2n + 3}{8}$$

Solution: $$ x_n = C 1^n + \frac{2n + 3}{8}(2n + 3)$$

Using $x_0 = 1$ to find $C$ gives $C = - \frac{1}{8}$

So the answer is $$ x_n = x_n^h + x_n^p = - \frac{1}{8}1^n + \frac{2n + 3}{8}(2n + 3)$$

However I know that the answer should be $x_n = (n+1)^2$ so my answer seems to be really off.

=== Edit 2 ===

Okay, so I realise that I should guess a polynom of the same size as my right hand part of the original equation. Since this doesn't work for this particulair problem, I'll try with size + 1. So:

$$ x_n^p = an^2 + bn + c $$

Insert this in the original equation: $$a(n+1)^2 + b(n+1) + c - an^2 -bn -c = 2n +3$$ And this gives $a = 1, b = 2$.

Then I got $$ x_n = 1^n + n^2 +2n$$ Still not the answer I'm looking for. Specially not the $1^n$ part which will still be there no matter what particulair solution I find.

iveqy
  • 1,327
  • I suggest you write the first numbers $x_0$,$x_1$,$x_2$,$x_3$,$x_4$,$x_5$. This could give you some ideas. – Claude Leibovici Sep 13 '14 at 14:32
  • I think I should use it by first finding a homogenous solution and then guess a particulair solution and combine these. If I don't do it this way I will fail with later exercises. – iveqy Sep 13 '14 at 14:33
  • There are two ways to do this. One is to use a summation: $x_n = x_1 + (x_2 - x_1) + \dots (x_n - x_{n-1})$. The other is to use a theorem on the form of a particular solution of your non-homogeneous equation. (For example,see p. 523 of Discrete Math and its Applications, 7th ed. by Rosen.) It will tell you that here there must be a solution of the form $n(an + b)$, where $a$ and $b$ are constants. – Dave Sep 13 '14 at 14:39
  • @Dave it's just that later solution I try to use, but I fail to apply it. Would you be able to show me an example on how to use this method in the case with a = 1 and a polynom on the right side. – iveqy Sep 13 '14 at 14:43

5 Answers5

3

Do the sum on both sides, which gives you $x_n-x_0 = \sum_{k=0}^{n-1} (2k +3)$

That should be easy to finish it from there.

Matt B.
  • 1,246
  • for you $x_1-x_0=0$ but accordingto original equation it is 3 – avz2611 Sep 13 '14 at 14:59
  • @user142634 No, my equation is correct and gives 3. – Matt B. Sep 13 '14 at 15:03
  • That's a nice method – Jonathan Sep 13 '14 at 15:05
  • @Jonathan I have to respectfully disagree. While in this case the equation happens to telescope, that's simply a result of the question being fabricated to make this true. Almost all recursions of this sort will grow exponentially, only the marginal cases where they don't will have telescoping solutions. This corresponds to eigenvalues of $0$ or $\pm 1$ in the corresponding affine equation. – DanielV Sep 13 '14 at 15:10
  • @DanielV it may not be of great general use, but it still exploits a feature of the recurrence relation in a clever way. I am just now working through your solution and learning from it, too. I've never spent much time on recurrence relations before, so these are all new tricks to me. – Jonathan Sep 13 '14 at 15:15
  • @Jonathan Ah I skipped a few steps in mine. If you are learning, I will add clarification if you ask. – DanielV Sep 13 '14 at 15:17
  • @DanielV thanks, it's more than clear for me (I'm not the poster of the question FWIW). – Jonathan Sep 13 '14 at 15:17
1

$$x_{n+1} - x_n = 2n + 3 \tag A$$ $$n = \frac 12 x_{n+1} - \frac 12 x_n - \frac 32 \tag B$$ $$n-1 = \frac 12 x_{n} - \frac 12 x_{n-1} - \frac 32 \tag C$$ Subtract previous two: $$1 = \frac 12 x_{n+1} + \left(-\frac 12 - \frac 12\right)x_n + \frac 12 x_{n-1} \tag D$$ $$x_{n+1} = x_{n} - x_{n-1} + 2 \tag E$$ Now it is a regular affine equation.

$$\begin{bmatrix} x_{n+1} \\ x_{n} \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & -1 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n \begin{bmatrix} x_1 \\ x_0 \\ 1 \end{bmatrix} \tag F$$

DanielV
  • 23,556
  • Finally got back to this. It's a great method, but you have an arithmetic mistake in equation C. The top-left entry in the matrix should be a $2$; powers of the matrix are considerably nicer after the correction :). – Jonathan Sep 14 '14 at 00:18
1

Since you're interested in general methods of solving linear recurrences, here is the fact you need:

Consider the recurrence relation $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} + F(n),$$ where $F(n)$ is of the form $f(n)s^n$ for some polynomial $f(x)$ of degree $t$ and some constant $s$. Then there is a particular solution of the form $a_n = n^m g(n) s^n$, where $g(x)$ is a polynomial of degree at most $t$ and $m$ is the multiplicity of the root $s$ in the characteristic equation $x^k - c_1 x^{k-1} - c_2 x^{k-2} - \dots - c_{k-1}x - c_k = 0$. We agree that $m$ is zero when $s$ is not a root.

In your situation, you have $F(n) = (2n + 3)1^n$, so you apply the foregoing with $f(x) = 2x + 3$ and $s = 1$. $1$ is a root of multiplicity one of the characteristic equation $x - 1 = 0$, so here $m = 1$. Furthermore, $f$ has degree $1$. Thus there is a particular solution of the form $a_n = n(cn + d)$.

This should be enough to get you started, but if you need more help, please edit your question to say what you've tried with this.

EDIT: No, the particular solution won't be $B(2n + 3)$. $c$ and $d$ are not necessarily $2$ and $3$. They are constants that you'll have to solve equations to find. Also, why are you using $B$? As I said, $m=1$ in this case, so you need to multiply by $n$. Set $x_n = cn^2 + dn$.

EDIT: The fact that you'd have to have degree $2$ was predictable from the rule I stated. $g$ can have degree as large as $1$, and $m=1$.

Once you've found the particular solution $x_n = n^2 + 2n$, then to get the general solution, you add the general homogeneous solution, which is $k \cdot 1^n$ = $k$, so is constant. Thus the general solution to the recurrence $x_{n+1} - x_n = 2n + 3$ is $x_n = n^2 + 2n + k$.

This doesn't take into account that $x_0 = 1$. Pick $k$ so that the initial condition is satisfied.

Dave
  • 2,087
0

Substitute $n=n+1$ we have system of equations $$x_{n+1}-x_n=2n+3\\x_{n+2}-x_{n+1}=2n+5\\x_{n+2}-2x_{n+1}+x_n=2$$ Than doing the same again $$x_{n+2}-2x_{n+1}+x_n=2\\x_{n+3}-2x_{n+2}+x_{n+1}=2\\x_{n+3}-3x_{n+2}+3x_{n+1}-x_n=0$$ So now you can solve the homogeneous equation which gives $a_n=n^2+n+1$

kingW3
  • 13,496
0

This telescopes conveniently.

Summing from $n=0$ to $n=m-1$ gives

$$\begin{align}\require{cancel} \sum_{n=0}^{m-1}x_{n+1}-x_n&=\sum_{n=0}^{m-1}\left(2n+3\right)\\ x_m-\cancelto{1}{x_0}&=2\sum_{n=0}^{m-1}n+3m\\ x_m-1&=m(m-1)+3m\\ x_m&=m^2+2m+1\\ x_m&=(m+1)^2\\ x_n&=(n+1)^2\qquad \blacksquare \end{align}$$

Check:

$$x_{n+1}-x_n=(n+2)^2-(n+1)^2=(2n+3)(1)=2n+3$$

Hypergeometricx
  • 22,657