General Solution for a non-Homogeneous Recurrence

Question

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$?

It's a question on a practice exam I'm reviewing and I'm not quite sure why my solution is incorrect.

So I went through the characteristic equation and found the constants, and the solution to the homogeneous part of this question is:

$$x(n) = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{\sqrt{5}}$$

This is the Fibonacci expression, right? So, what do I do with the non-homogeneous part of the expression? My professor mentioned something about solving them separately but I'm not sure what to do with it now.

Answer 1

Solution Using Method of Annihilators

Let $E$ denote the "shift" operator, and let $\langle x_n \rangle$ denote the sequence $x_1, x_2, x_3, \ldots$

Then our recurrence can be re-written as: $$x_{n+2} - x_{n+1} - x_n = n - 1 \iff (E^2-E-1)\langle x_n\rangle = \langle n-1\rangle$$

The annihilator for $n-1$ is $(E-1)^2$, we have:

$$(E-1)^2(E^2-E-1)\langle x_n\rangle = (E-1)^2\langle n-1\rangle=\langle 0\rangle$$

So, we've now converted our problem from a non-homogenous problem to a homogeneous problem; the only difficulty is that we have also changed the recurrence from a $2$nd order recurrence to a $4$th order recurrence. Thus, we need to compute two more initial conditions: \begin{align} x_2 &= 1\\ x_3 &= 3 \end{align}

We can easily move from the annihilator operator form to the characteristic of this fourth-order recurrence: $$(r-1)^2(r^2-r-1) \implies r=1, 1, \frac{1+\sqrt 5}{2}, \frac{1-\sqrt 5}{2}$$

Thus, our general solution has the form: $$x_n = A + Bn + C\left(\frac{1+\sqrt 5}{2}\right)^n + D\left(\frac{1-\sqrt 5}{2}\right)^n$$ Using our four initial conditions, we find:

\begin{align} x_1 &= 0 = A + B + \left(\frac{1+\sqrt 5}{2}\right)C + \left(\frac{1-\sqrt 5}{2}\right)D\\ x_2 &= 1 = A + 2B + \left(\frac{1+\sqrt 5}{2}\right)^2C + \left(\frac{1-\sqrt 5}{2}\right)^2D\\ x_3 &= 1 = A + 3B + \left(\frac{1+\sqrt 5}{2}\right)^3C + \left(\frac{1-\sqrt 5}{2}\right)^3D\\ x_4 &= 3 = A + 4B + \left(\frac{1+\sqrt 5}{2}\right)^4C + \left(\frac{1-\sqrt 5}{2}\right)^4D\\ \end{align}

This is a system of linear equations; using any method, we arrive at the solution $A = 0, B=-1, C=1, D = 1$.

Thus, the solution is:

$$x_n =\left(\frac{1+\sqrt 5}{2}\right)^n + \left(\frac{1-\sqrt 5}{2}\right)^n - n$$

For what it's worth, the first several values of the sequence are:

1 |  0
2 |  1
3 |  1
4 |  3
5 |  6
6 | 12
7 | 22
8 | 39
9 | 67

Answer 2

Hint: $x^2 - x - 1 = 0 \to x = \dfrac{1\pm \sqrt{5}}{2}$. Let $x_h = A\left(\dfrac{1+\sqrt{5}}{2}\right)^n + B\left(\dfrac{1-\sqrt{5}}{2}\right)^n$ be the homogeneous solution, and $x_p = Cn + D$ be the particular solution, then the general solution is:

$x_n = x_h + x_p$.

Answer 3

Let $y_n = x_n + n$. Then the equation becomes $y_{n+2} = y_{n+1}+y_n$. Now, solve for $y_n$ using usual method.

Answer 4

Generating Function Approach

The below recurrence is equivalent to the recurrence in the OP, but has been extended to allow $n=0$:

$$a_{n+2} = a_{n+1} + a_n + n - 1\tag{$\star$}$$ for $n\geq 2$, and $a_0=2, a_1=0$.

Define $A(x) = \sum_{n=0}^\infty a_n x^n$. Then, multiplying $(\star)$ by $x^n$ and summing over $n$, we have: (note: all sums are to be taken as $\sum_{n=0}^\infty$, but I'm leaving off the limits for ease of typing.)

$$\sum_n a_{n+2}x^n = \sum_na_{n+1}x^n+\sum_n a_n x^n + \sum_n(n-1)x^n\tag{$\star\star$}$$

We can rewrite $(\star\star)$ as:

$$\frac{A(x)-2}{x^2}-\frac{A(x)-2}{x} -A(x) = \sum_n (n-1)x^n = \frac{2x-1}{(1-x)^2}$$

Rearranging the above, we have: $$A(x)\frac{1-x-x^2}{x^2}=\frac{2-2x}{x^2}+\frac{2x-1}{(1-x)^2}$$

Thus, \begin{align}A(x) &= \frac{2(1-x)}{1-x-x^2} + \frac{2x^3-x^2}{(1-x-x^2)(1-x)^2} \\ &= \frac{5 x^2-6 x+2}{(1-x-x^2)(1-x)^2} \\ &= \frac{x-2}{x^2 + x - 1} -\frac{1}{(x-1)^2} - \frac{1}{x-1} \end{align}

The Taylor Series for each of the above can be found (albeit the first term takes some work), then the coefficient of $x^n$ is the $n$th term.