Closed form for a look-alike Fibonacci sequence

Question

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?

Answer 1

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

Answer 2

First, both of those finite sums have easily calculable closed formed solutions (they're geometric series). Second, the initial difference equation implies that the two subsequences $(x_1, x_3, x_5,...)$ or $(x_2, x_4, x_6, ...)$ are independent of one another. The presence of the $n-1$ term in the exponent of $x$ may be misleading.

Admittedly, I am not an expert in difference equations, but since the two subsequences are independent, I would not expect a single closed-formed equation to necessarily and "nicely" describe the entire sequence $(x_n)$, unless $x_1$ and $x_2$ are purposely chosen so that this is the case.

There is, however, a way to "cheat" and force a single solution. You can piece together your two solutions (after you've used known formulas for geometric series to simplify them) by using:

$$x_n = \frac{1}{2}[1-(-1)^n]a_n^{(odd)}+\frac{1}{2}[1-(-1)^{n+1}]a_n^{(even)}$$

I personally don't find this particularly more elegant than using a piecewise function that depends on the parity of $n$, but I digress.

Answer 3

I assume that the empty sum you mentioned, is the case when $x=0$ because in the summation form, it has a misleading term, $0^0$. Well, the simple way of dealing with this is to express the sum as a single fraction. Here's how I did it, let $G(t)= \displaystyle\sum_{n=0}^{\infty} a_n t^n,$ $$\sum_{n=3}^{\infty} x_nt^n = \sum_{n=3}^{\infty} x_{n-2}t^n +\sum_{n=3}^{\infty}x^{n-1}t^n$$ gives $$G(t)-t-xt^2=t^2G(t)+\sum_{n=3}^{\infty}x^{n-1}t^n.$$ Solving for $G(t),$ $$\begin{align*} G(t)&= \frac{1}{1-t^2}\left(t+xt^2 + \sum_{n=3}^{\infty}x^{n-1}t^n\right) \\ &= \left(\sum_{n=1}^{\infty} x^{n-1}t^n\right)\left(\sum_{k=0}^{\infty} t^{2k}\right).\end{align*}$$ Now, extracting the coefficient of $t^n,$ we get that when $n$ is odd, $$a_n=x^{n-1}+x^{n-3}+\cdots + 1 =\frac{x^{n+1}-1}{x^2-1}$$ and when $n$ is even, $$a_n = x^{n-1}+x^{n-3}+\cdots +x = \frac{x^{n+1}-x}{x^2-1}.$$ If you want a single expression for $a_n,$ what I can come up with is $$a_n = \frac{x^{n+1}+\frac{1}{2}((-1)^n-1)-\frac{1}{2}((-1)^n+1)x}{x^2-1}.$$