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.


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

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.

  • $\begingroup$ This is a really awesome solution, because $y_n$ is the Fibonacci sequence (and one can use Binet's formula--with an offset--for this). Then $x_n$ is at hand. $\endgroup$ – apnorton Dec 12 '14 at 4:36

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

  • $\begingroup$ I did this initially, actually. After plugging in everything I set A = -1 and plugged it in, giving me B = 0. Thus, x(p) = - n, but this solution is incorrect (probably because it really is incorrect). $\endgroup$ – Math Dude Needs Help Dec 12 '14 at 3:42

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.


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.