Periodicity of recursive sequence

Question

It's known that recursive sequence

$x_{n+2} = x_{n+1} - x_n$

has a period 6 (independent of initial values)

The young lady(12) asked me: "Why is this so?"
The "simple" straight answer would contain references to an eigenvalues, complex numbers and trigonometric functions. I don't think she is capable to understand it clearly.

But she is smart enough to understand e.g. conception of geometrical transformations. Obviously our recursion can be written as:

$(x,y)\mapsto(y,y-x)$

With Mathematica I've found that this transformation contain rotation on $\pi/3$ and maybe some scaling. But Jordan matrix doesn't look like rotation. So I'm confused but hope that there is simple enough demonstration for nature of periodicity.

Answer 1

Geometric transformation is a matrix. This is one of my favorite videos on linear algebra.

The given recurrence relation can be expressed in matrix form as follows: $$\begin{cases}F_n=F_{n-1}-F_{n-2}\\ F_{n-1}=F_{n-1}\end{cases}\Rightarrow \begin{pmatrix}F_n\\ F_{n-1}\end{pmatrix}=F_{n-1}{\color{red}{1\choose 1}}+F_{n-2}{\color{blue}{-1\choose 0}}=\begin{pmatrix}\color{red}1&\color{blue}{-1}\\ \color{red}1&\color{blue}0\end{pmatrix}\begin{pmatrix}F_{n-1}\\ F_{n-2}\end{pmatrix}$$ Note that the transition matrix $\begin{pmatrix}\color{red}1&\color{blue}{-1}\\ \color{red}1&\color{blue}0\end{pmatrix}$ transforms the identity matrix (or bases vectors) $\begin{pmatrix}\color{red}1&\color{blue}0\\ \color{red}0&\color{blue}1\end{pmatrix}$ so that the base vector ${\color{red}{1\choose 0}}$ moves to ${\color{red}{1\choose 1}}$ and ${\color{blue}{0\choose 1}}$ to ${\color{blue}{-1\choose 0}}$. Indeed: $$\begin{pmatrix}\color{red}1&\color{blue}{-1}\\ \color{red}1&\color{blue}0\end{pmatrix}\begin{pmatrix}\color{red}1&\color{blue}0\\ \color{red}0&\color{blue}1\end{pmatrix}=\begin{pmatrix}\color{red}1&\color{blue}{-1}\\ \color{red}1&\color{blue}0\end{pmatrix}.$$ So, the $x$ and $y$ base vectors rotate counterclockwise for $45^\circ$ and $90^\circ$, respectively. See the graphs below, where the red base vectors were transformed to green vectors.

Let's see how a chosen vector, for example ${2\choose 0}$ (initial values of the above difference equation problem), rotates and returns back.

Step 1: The transition matrix $\begin{pmatrix}1&-1\\ 1&0\end{pmatrix}$ makes the vector ${2\choose 0}$ rotate by $45^\circ$ and land on $y=x$ line. Indeed:

$\hspace{7cm}$

$$\begin{pmatrix}1&-1\\ 1&0\end{pmatrix}{2\choose 0}={2\choose 2}$$ Note: The red base vectors were transformed to green vectors. The chosen vector stayed on the transformed $x$-axis.

Step 2: The transition matrix $\begin{pmatrix}1&-1\\ 1&0\end{pmatrix}$ makes the vector ${2\choose 2}$ rotate by $45^\circ$ and land on $y$ axis. Indeed:

$\hspace{7cm}$

$$\begin{pmatrix}1&-1\\ 1&0\end{pmatrix}{2\choose 2}={0\choose 2}$$

Step 3: The transition matrix $\begin{pmatrix}1&-1\\ 1&0\end{pmatrix}$ makes the vector ${0\choose 2}$ rotate by $90^\circ$ and land on $x$ axis. Indeed:

$\hspace{7cm}$

$$\begin{pmatrix}1&-1\\ 1&0\end{pmatrix}{0\choose 2}={-2\choose 0}$$ Note: $y$ base red vector rotates counterclockwise by $90^\circ$ and arrives at the green vector. So does the vector ${0\choose 2}$, that is, it rotates counterclockwise by $90^\circ$.

Can you continue and guess after how many rotations and by how many degrees each time the vector will return to the initial state ${2\choose 0}$?

Answer:

Step 4: Rotate by $45^\circ$ to get to ${-2\choose -2}$. Step 5: Rotate by $45^\circ$ to get to ${0\choose -2}$. Step 6: Rotate by $90^\circ$ to get to ${2\choose 0}$.

Answer 2

Here's a simple though non-geometric demonstration of period $6$:

$x_{n+6}=x_{n+5}-x_{n+4}=x_{n+4}-x_{n+3}-x_{n+4}$

$=-x_{n+3}=-x_{n+2}+x_{n+1}=-x_{n+1}+x_{n}+x_{n+1}=x_n$

Answer 3

"Why" is a really good question (particularly from a 12 year old). Here's a piece of the geometry that follows easily from the algebra.

• The $x$-axis maps to the $y$-axis with a clockwise quarter turn.

• The $y$-axis maps to the line $y=x$ with a clockwise turn through an eighth of a circle.

• The line $y=x$ maps back to the $x$-axis with another eighth.

Those three turns through half a circle reverse the $x$-axis. Repeat for period $6$.

That gives you periodicity for both axes and for the line $y=x$.

Tracing what happens starting at $(1,0)$ shows a nice hexagon with parallel sides.

For the periodicity everywhere, which follows algebraically from linearity, the hexagons aren't quite as easy to see. But this might be a good start.