## A Fibonacci-like sequence

What’s the pattern of the following sequence?

$\displaystyle 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, \cdots$

Can you guess the next term?

The answer is 60. (Honestly, I don’t think I can if I haven’t worked on this problem.) The pattern is:

$\displaystyle \begin{cases} a_1=1, \\ a_2=1,\\ a_3=1, \\ a_{n+3}=a_{n}+a_{n+2}. \end{cases} \ \ \ \ \ (1)$

This sequence looks artificial. But I will show that it has an interesting “geometric” property. The sequence ${\{a_n\}}$ is very similar to the Fibonacci sequence ${\{F_n\}}$. Recall that ${\{F_n\}}$ is defined by

$\displaystyle \begin{cases} F_1=1,\\ F_2=1,\\ F_{n+2}=F_n+F_{n+1}. \end{cases}$

So the first few terms of ${F_n}$ are:

$\displaystyle 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,\cdots$

Recently I learned the following amazing property of ${\{F_n\}}$ (while teaching calculus):

 Theorem 1 $\displaystyle F_1^2 +F_2^2 +\cdots +F_n^2 = F_{n}F_{n+1}.$

For example,

$\displaystyle \begin{array}{rl} 1^2+1^2=2=1\cdot 2, \\ 1^2+1^2+2^2=6=2\cdot 3, \\ 1^2+1^2+2^2+3^2=15=3\cdot 5. \end{array}$

The proof of this result can be found in this video. In fact the identity is proved by computing the areas of the “Fibonacci rectangles” in two ways.

Inspired by this result, I tried to look for a sequence with a similar property. After playing with sequences for a while, I found:

 Theorem 2 For the sequence ${\{a_n\}}$ defined in (1), $\displaystyle \sum_{n=1}^m a_n \cdot a_{n+1}^2= a_m a_{m+1}a_{m+2}.$

(Unfortunately, it is not as beautiful as Theorem 1.) For example,

$\displaystyle \begin{array}{rl} 1\cdot 1^2 +1\cdot 1^2 +1\cdot 2^2 =6=1\cdot 2\cdot 3,\\ 1\cdot 1^2 +1\cdot 1^2 +1\cdot 2^2+2\cdot3^2 =24= 2\cdot 3\cdot 4,\\ 1\cdot 1^2 +1\cdot 1^2 +1\cdot 2^2+2\cdot3^2 +3\cdot 4^2=72= 3\cdot 4\cdot6,\\ 1\cdot 1^2 +1\cdot 1^2 +1\cdot 2^2+2\cdot3^2 +3\cdot 4^2+4\cdot 6^2=216= 4\cdot6\cdot9. \end{array}$

Proof: For a rectangular block ${B}$ of width ${w}$, depth ${d}$ and height ${h}$, we record this information as

$\displaystyle \mathrm{dim}(B)=w\cdot d\cdot h,$

here ${\mathrm{dim}}$ stands for dimension. (Of course, its volume is also ${w\cdot d\cdot h}$.)

In the following figure, there is a single cube ${R_1}$ of dimension

$\displaystyle \mathrm{dim}(R_1)=a_1\cdot a_2 \cdot a_3=1\cdot 1\cdot 1.$

Now, we “thicken” this cube ${R_1}$ in the positive ${x}$-direction by ${a_3}$ units. This just means appending a (red) cube of dimension ${a_3\cdot a_2\cdot a_3}$ to the right hand side of the original cube (assuming that the positive ${x}$ direction is pointing to the right):

So now the new rectangular block ${R_2}$ is of dimension

$\displaystyle \mathrm{dim}(R_2)=(a_1+a_3)\cdot a_2\cdot a_3=a_4\cdot a_2\cdot a_3,$

by the definition of ${a_4}$. Let’s denote this “thickening” (or appending) process by “${+(a_3, 0, 0)}$“.

Now, we do a “${+(0, a_4, 0)}$” process to ${R_2}$. More precisely, we thicken this block (${R_2}$) in the positive ${y}$-direction by ${a_4=a_1+a_3}$ units. Equivalently, this amounts to appending a (red) rectangular block of dimension ${a_4\cdot a_4\cdot a_3}$ just beside ${R_2}$ in the positive ${y}$-direction:

Let’s call the resulting block by ${R_3}$. Then by the definition of ${a_5}$,

$\displaystyle \mathrm{dim}(R_3)=a_4\cdot (a_2+a_4)\cdot a_3=a_4\cdot a_5\cdot a_3.$

To go on, we do a ${+(0, 0, a_5)}$ process to ${R_3}$ to obtain ${R_4}$, which amounts to appending a block of dimension ${a_4\cdot a_5\cdot a_5}$ to ${R_3}$ (in the positive ${z}$-direction). Note that in each process, after appending a new block to ${R_i}$, the resulting block ${R_{i+1}}$ is still a rectangular blocks, since the dimension fits each other.

We recursively do these processes to obtain ${R_i}'s$. i.e. ${R_{5}}$ is obtained from ${R_4}$ by doing a “${+(a_6, 0, 0)=+(a_3+a_5, 0, 0)}$” to ${R_4}$, etc. In short:

$\displaystyle \begin{array}{rl} R_4&\stackrel{+(a_6, 0, 0)}\longrightarrow R_5\\ R_5&\stackrel{+(0, a_7, 0)}\longrightarrow R_6\\ R_6&\stackrel{+(0, 0, a_8)}\longrightarrow R_7\\ R_7&\stackrel{+(a_9, 0, 0)}\longrightarrow R_8\\ &\vdots \end{array}$

It’s now easy to verify our claim. For simplicity, let’s look at ${R_4}$. On the one hand, its volume is clearly

$\displaystyle \mathrm{Vol}(R_4)= a_4\cdot a_5\cdot a_6.$

On the other hand, since ${R_4}$ is obtained by successively appending rectangular blocks starting from ${R_1}$, it is easy to see that

$\displaystyle \begin{array}{rl} \mathrm{Vol}(R_4) =& \mathrm{Vol}(R_1)+ a_2\cdot a_3^2 +a_3\cdot a_4^2 +a_4\cdot a_5^2\\ =& a_1\cdot a_2^2+ a_2\cdot a_3^2 +a_3\cdot a_4^2 +a_4\cdot a_5^2. \end{array}$

Therefore

$\displaystyle a_4\cdot a_5\cdot a_6=a_1\cdot a_2^2+ a_2\cdot a_3^2 +a_3\cdot a_4^2 +a_4\cdot a_5^2..$

The general case can be similarly proven. $\Box$

Question: Can you generalize this to “higher dimensions”?

Advertisements
This entry was posted in Algebra, Combinatorics. Bookmark the permalink.