4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.