Alternating Fibonacci-like sequences are periodic

fibonacci-numbersrecurrence-relationssequences-and-series

Define a Fibonacci-like sequence that depends on a
parameter $k \in \mathbb{N}$,
and alternates $\pm$:
\begin{eqnarray}
k=1 \;:\; f_1(n) &=& f_1(n-1)\\
k=2 \;:\; f_2(n) &=& f_2(n-1)-f_2(n-2)\\
k=3 \;:\; f_3(n) &=& f_3(n-1)-f_3(n-2)+f_3(n-3)\\
k=4 \;:\; f_4(n) &=& f_4(n-1)-f_4(n-2)+f_4(n-3)-f_4(n-4)\\
&\cdots&\\
k=k \;:\; f_k(n) &=& \Sigma_{i=1}^k (-1)^{i+1} f_k(n-i)
\end{eqnarray}
For any initial data specifying the values of
$f_k(n)$ for $n=0,1,2,\ldots,k{-}1$,
I claim the sequence becomes periodic, with period $(k+1)$ if $k$ is odd, and $2(k+1)$ if $k$ is even.
For example, for $k=4$, and initial values
$$
\left(\; f_4(0),f_4(1),f_4(2),f_4(3) \;\right) = (1,2,3,4) \;,
$$
then $f_4(n)$, for $n=0,\ldots,20$ is:
$$
1, 2, 3, 4, 5, 2, -2, -3, -4, -5, -2, 2, 3, 4, 5, 2, -2, -3, -4, -5, -2 \;,
$$
with period $2(k+1)=10$.
For example,
\begin{eqnarray}
f_4(5) &=& f_4(4)-f_4(3)+f_4(2)-f_4(1)\\
f_4(5) &=& 5-4+3-2\\
f_4(5) &=& 2 \;.
\end{eqnarray}
If instead we pin all initial values to $1$, so that
$$
\left( \; f_4(0),f_4(1),f_4(2),f_4(3) \; \right) = (1,1,1,1) \;,
$$
the resulting sequence is:
$$
1, 1, 1, 1, 1, 0, -1, -1, -1, -1, 0, 1, 1, 1, 1, 0, -1, -1, -1, -1, 0 \;,
$$
also period $10$.

My question:

Q. What is a proof of the claim that such alternating
Fibonacci sequences $f_k(n)$ are periodic for any initial values?

I can prove that, e.g., $f_4(n)$ is periodic with period $10$, but only via induction for that specific $k{=}4$,
and initial conditions.
But if my claim is true, there should be a way to see that
all $f_k(n)$, regardless of initial values, are periodic with those odd/even periods $(k+1)$/$2(k+1)$.

Best Answer

You can express $k=4$ for example using matrices

$$ \left( \begin{array}{c } a_{n+1} \\ a_{n+2} \\ a_{n+3} \\ a_{n+4} \end{array} \right) = \left( \begin{array}{cccc} 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0\\ 0 & 0 & 0 & 1\\ -1& 1& -1& 1\end{array} \right) \left( \begin{array}{c } a_n \\ a_{n+1} \\ a_{n+2} \\ a_{n+3} \end{array} \right)$$

If you plug the matrix into Wolfram Alpha it says the eigenvalues $\lambda_1, \lambda_2,\lambda_3,\lambda_4$ are distinct and satisfy $\lambda_i^5 = \pm 1$. Prove it! Any sensible proof should work equally well for all even $k$.

Hence the matrix $A$ above has Jordan form $J$ and $A = S^{-1}J S$ for $$J = \text{diag}(\lambda_1, \lambda_2,\lambda_3,\lambda_4).$$

Then $$J^{10} = \text{diag}(\lambda_1^{10}, \lambda_2^{10},\lambda_3^{10},\lambda_4^{10}) = I$$ and so $$A^{10} = S^{-1}J^{10} S= S^{-1} S=I.$$ That means $$A^{10}(a_n,a_{n+1},a_{n+2},a_{n+3}) = (a_n,a_{n+1},a_{n+2},a_{n+3}).$$ But by definition $$A^{10}(a_n,a_{n+1},a_{n+2},a_{n+3}) = (a_{n+10},a_{n+11},a_{n+12},a_{n+13}).$$ Thus the period is $10$.

For $k=5$ the eigenvalues are sixth roots of $6$. Prove it! Then do the same thing with $10$ replaced by $6$.

Bonus! One useful fact might be that if $\omega_0, \ldots, \omega_{k-1} $ are the $k$ distinct roots of unity then

$$\omega_0+ \omega_1 \ldots+ \omega_{k-1} =0.$$

To prove this recall $\omega_m = e^{m(2 \pi i/k)}$ so we can define

$$X = \omega_0+ \ldots+ \omega_{k-1} = e^{0(2 \pi i/k)}+ e^{(2 \pi i/k)}+ \ldots+ e^{(k-1)(2 \pi i/k)}.$$

We claim $\omega_1 X = X$. Since $\omega_1 \ne 1$ this implies $X=0$. To prove it write

$$\omega_1 X = e^{(2 \pi i/k)}(e^{0(2 \pi i/k)}+ e^{(2 \pi i/k)}+ \ldots+ e^{(k-1)(2 \pi i/k)}) $$ $$ = e^{(2 \pi i/k)}+ e^{2(2 \pi i/k)}+ \ldots+ e^{(k-1)(2 \pi i/k)} + e^{k(2 \pi i/k)} $$ $$= \omega_1 +\omega_2 + \ldots + \omega_{k-1} + \omega_0 =X$$

Related Solutions

Sequences and Series – Interesting Properties of Fibonacci-like Sequences

In any general recurrence of the form:

$$x_n = \sum_{i=1}^k {a_i x_{n-i}}$$

you can determine an explicit formula in terms of the roots of the polynomial of degree k:

$$z^k - a_1{z^{k-1}} - a_2{z^{k-2}} - a_{k-1}z - a_k$$

If the polynomial has no repeated roots, then the form of the explicit formula will be:

$$x_n = b_1 r_1^n + b_2 r_2^n + ... + b_k r_k^n$$

Where the $b_i$ can be any numbers, and the $r_i$ are the distinct roots of the polynomial.

This means that "most of the time," $\lim\limits_{n\to \infty}{x_{n+1}/x_n}$ will be equal to the root $r_i$ with the largest absolute value such that $b_i\neq 0$. If two $r_i$ have the same largest absolute value, the convergent behavior might be odd - it possibly might never converge.

There is a lot of linear algebra involved in this - the $r_i$s are eigenvalues of a matrix which sends $(x_i,x_{i+1},...,x_{i+k-1})$ to $(x_{i+1},...,x_{i+k})$

In the case of what you call the k-nacci numbers, your polynomial is:

$$x^k-x^{k-1}-x^{k-2}-..-1 = x^k -\frac{x^k-1}{x-1}$$

I'm not sure what you can say about the roots of this polynomial when $k>2$. It's easy to show it has no repeated roots (a polynomial has no repeated roots of it is relatively prime to its derivative.)

[Math] Sum of product of Fibonacci numbers

Let's use $$ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - (-1)^n \phi^{-n} \right) $$ where $\phi$ is a Golden ratio constant $\phi = \frac{\sqrt{5}+1}{2}$. Now the sum reduces to the combination of geometric sums: $$ \begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^k - (-1)^k \phi^{-k}\right)\left(\phi^{n-k} - (-1)^{n-k} \phi^{k-n}\right) \\ &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^n - (-1)^k \phi^{n-2k} - (-1)^{n-k} \phi^{2k-n} + (-1)^n \phi^{-n} \right) \\ &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) - \frac{\phi^{n}}{5} \sum_{k=1}^{n-1} \left( -\phi^{-2}\right)^{k} - \frac{(-1)^{n}}{5} \phi^{-n} \sum_{k=1}^{n-1} \left(-\phi^2\right)^k \end{eqnarray} $$ Using the geometric sum $\sum_{k=1}^{n-1} x^k = \frac{x-x^n}{1-x}$ we get: $$\begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) + \frac{2}{5} \frac{\phi^{n-1} + (-1)^n \phi^{1-n}}{\phi + \phi^{-1}} \\ &=& \frac{n-1}{5} L_n + \frac{2}{5} F_{n-1} \end{eqnarray} $$ where $L_n$ denotes $n$-th Lucas number.

Quick sanity check in Mathematica:

In[84]:= Table[
 Sum[Fibonacci[k] Fibonacci[n - k], {k, 1, n - 1}] == (n - 1)/
    5 LucasL[n] + 2/5 Fibonacci[n - 1], {n, 1, 6}]

Out[84]= {True, True, True, True, True, True}

The sum stated in the edited question is obtained by replacing $n$ with $n+1$ in the sum evaluated above: $$ \sum_{k=1}^{n} F_k F_{n+1-k} = \frac{n}{5} L_{n+1} + \frac{2}{5} F_n $$

Best Answer

Related Solutions

Sequences and Series – Interesting Properties of Fibonacci-like Sequences

[Math] Sum of product of Fibonacci numbers

Related Question