# Alternating Fibonacci-like sequences are periodic?

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

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