Find a closed form of $x_{n+2} = x_{n+1}+2x_n +2$ where $x_1 = x_2 = 1$, $n \in \mathbb N$

Question

Find a closed form $x_n$ for the following recurrence relation: $$ x_{n+2} = x_{n+1} + 2x_n + 2 \\ x_1 = x_2 = 1,\;\;n\in \mathbb N $$

I'm trying to understand why I get different results for different guesses of a solution for particular part of the recurrence relation.

I've started by splitting the solution into two parts: homogenous and particular ones. It's known that $$x_n = x_n^{(h)} + x_n^{(p)}$$

Having the above in mind lets solve for homogenous. I've done this with the help of characteristic polynomial:

$$ \lambda^2 - \lambda - 2 = (\lambda + 1)(\lambda - 2) = 0 $$

By this we obtain the form of the homogenous solution:

$$ x_n^{(h)} = C_1\cdot(-1)^n + C_2 \cdot2^n $$

Here is where things get vague for me. Let's try to guess the form of the non-homogenous solution. I've started with $B\cdot n$, then

$$ B\cdot(n+2) = B\cdot(n+1) + 2Bn + 2 \\ B = \frac{2}{1-2n} $$

Therefore:

$$ x_n = C_1 \cdot (-1)^n + C_2\cdot2^n + \frac{2}{1-2n} $$

Using the initial conditions one may find $C_1 = -{13 \over 9}$ and $C_2 = {7\over 9}$. Obtain the final form:

$$ x_n = -{13 \over 9} \cdot (-1)^n + {7 \over 9} \cdot 2^n + \frac{2}{1-2n} $$

And that result doesn't match the answer in the book. However if I assume that the solution for non-homogenous part is in the form $B$, then $C_1 = -{2\over 3}$ and $C_2 = {2 \over 3}$, which by the steps above results in:

$$ x_n = {1\over 3} \cdot (2^{n+1} - 2\cdot(-1)^n) - 1 $$

being a match with the answer from the book.

I'm trying to understand where it got wrong and why the answers are different. I could have assumed non-homogenous solution to be in various forms which I believe would still lead to some form of solution. Have I made a mistake in my first assumption?

Answer 1

Let's try to guess the form of the non-homogenous solution. I've started with $B\cdot n$

Where of course $\,B\,$ would be a constant for the particular solution to be linear.

then $\quad\ldots\quad B = \dfrac{2}{1-2n}$

But this $\,B\,$ depends on $\,n\,$ i.e. is not a constant. This proves that no linear solutions $\,x_n=B\cdot n\,$ exist.

However if I assume that the solution for non-homogenous part is in the form $B$

Then $\,B\,$ calculates to $\,-1\,$ i.e. does not depend on $\,n\,$. This proves that a constant solution $\,x_n=-1\,$ does in fact exist, then calculating the respective $\,C_1,C_2\,$ from the initial conditions provides the final, correct answer.

Answer 2

If you put $x_n = y_n+c$ so that $y_n$ is a solution to homogenus equation we get $c=-1$.

Since $y_1=y_2= 2$ and $$y_n = a(-1)^n+b2^n$$ we get $$y_n = {2\over 3}(2^n-(-1)^n)$$

or $$x_n = {2\over 3}(2^n-(-1)^n)-1$$

Answer 3

Go up one level: \begin{align} x_{n+2} &= x_{n+1}+2x_n +2 \\ x_{n+3} &= x_{n+2}+2x_{n+1}+2 \end{align} Therefore $$ x_{n+3}-x_{n+2}=x_{n+2}+x_{n+1}-2x_n $$ and the characteristic polynomial is $$ t^3-2t^2-t+2=(t^2-1)(t-2)=(t-1)(t+1)(t-2) $$ with the added condition that $x_3=5$. Note that you always get the original roots among the roots for the new recurrence.

Thus $$ x_n=\alpha+\beta(-1)^n+\gamma\,2^n $$ The linear system becomes \begin{cases} \alpha-\beta+2\gamma=1 \\[4px] \alpha+\beta+4\gamma=1 \\[4px] \alpha-\beta+8\gamma=5 \end{cases} and, easily, $\alpha=-1$, $\beta=-2/3$, $\gamma=2/3$.

Thus $$ x_n=-1-\frac{2}{3}(-1)^n+\frac{2}{3}\,2^n $$

Answer 4

An extended note:

The Jacobstahl numbers satisfy the difference equation $$J_{n+2} = J_{n+1} + 2 \, J_{n} \, \hspace{5mm} J_{n} \in \{0,1,1,3,5,11,21,43, \cdots \}_{n \geq 0}.$$ By comparison of the difference equations one may see a shifted form of the Jacobsthal equation by seeking $\phi_{n} = \alpha \, J_{n} + \beta$ for which $\phi_{n}$ satisfies $$\phi_{n+2} = \phi_{n+1} + 2 \, \phi_{n} - 2 \beta.$$ By comparison $\beta = -1$ and $\phi_{n} = \alpha \, J_{n} -1$. Now $\phi_{1} = 1 = \alpha \, 1 - 1$ and leads to $\alpha =2$. From this it is now determined that $$\phi_{n+2} = \phi_{n+1} + 2 \, \phi_{n} + 2 \, \hspace{5mm} \, \phi_{n} \in \{1,1,5,9, \cdots \}_{n \geq 1}$$ is satisfied by $\phi_{n} = 2 \, J_{n} - 1$.