Solve $ x_{n+1} - x_n = 2n + 3$

Question

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.

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

Answer 2

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.

Answer 3

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

Answer 4

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$

Answer 5

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