I’m trying to get the closed form for the following sequence:
$x_1=1$, $x_2=x$
\begin{align*}
x_n=x_{n-2}+x^{n-1} \quad\text{if } n\geq3.
\end{align*}
After some calculations the only thing I get is:
\begin{align*}
x_n=\sum_{k=0}^{\frac{n-1}{2}} x^{2k} \quad\text{if $n$ is odd,}
\end{align*}
and
\begin{align*}
x_n=\sum_{k=0}^{\frac{n}{2}} x^{2k+1} \quad\text{if $n$ is even.}
\end{align*}
But I'd like to get a closed form that doesn’t depend on the parity of $n$.
Note that in the summation form, there is a problem when it is the empty sum, since by "convention" it is zero.
Is there a way to get $1$ or $x$ with an empty sum or another way I could fix it?
Best Answer
Try with characteristic polynomial technique. From: $$x_n=x_{n-2}+x^{n-1}$$ $$x_{n+1}=x_{n-1}+x^{n}$$ then $$x\cdot x_n=x\cdot x_{n-2}+x^{n}$$ $$x_{n+1}=x_{n-1}+x^{n}$$ and $$x_{n+1}-x\cdot x_n-x_{n-1}+x\cdot x_{n-2}=0$$ with the characteristic polynomial: $$t^{3}-x\cdot t^{2}-t+x=0 \iff (t - 1) (t + 1) (t - x)=0$$ with the roots $-1, 1$ and $x$, leading to the: $$x_n=A\cdot (-1)^n + B\cdot (1)^n + C\cdot x^n=\\ A\cdot (-1)^n + B + C\cdot x^n$$ What is left is to find $A, B$ and $C$ from: $$x_1=1=-A + B + C\cdot x$$ $$x_2=x=A + B + C\cdot x^2$$ $$x_3=1+x^2=-A + B + C\cdot x^3$$ a system of linear equations, leading to: $$C=\frac{x}{x^2-1}, B=-\frac{1}{2\cdot(x-1)}, A=-\frac{1}{2\cdot(x+1)}$$
or $$x_n=-\frac{(-1)^n}{2\cdot(x+1)} -\frac{1}{2\cdot(x-1)} + \frac{x^{n+1}}{x^2-1}$$