Add Me!Close Menu Navigation

The Fib-Fib-Fib Sequence

Consider the sequences (a_n)_n, (b_n)_n, defined recursively by

     $$ \begin{tabular}{l l l l} $a_0 = 0$, & $a_1 = 2$, & $a_{n+1} = 4a_n + a_{n-1}$ & $n \ge 0$ \\ $b_0 = 0$, & $b_1 = 1$, & $b_{n+1} = a_n - b_n + b_{n-1}$ & $n \ge 0$ \end{tabular} $$

Show that (a_n)^3 = b_{3n} \fa n

Table Of Content

1. Show that

Show that

Show that

Yeah, I’m getting a bit sick of these sequence problems too…

1. Show that (a_n)^3 = b_{3n}

Let’s start with the (b_n)_n sequence first. We use the following code to generate b_n.

b_ = {}
def b(n):
   if n in b_:
       return b_[n]
   x = a(n-1) - b(n-1) + b(n-2)
   b_[n] = x
   return x

    \[\begin{tabular}{c|c|c|c|c|c|c|c|c|c} n& 1&2&3&4&5&6&7&8&9 \\ \hline b_n& 1&1&8&27&125&512&2197&9261&39304 \\ \hline b_n^{\frac{1}{3}}& 1&1&2&3&5&8&13&21&34 \end{tabular}\]

Are you even still surprised that the fibonacci sequence is popping up here? Anyways, this seems to suggest that b_n = f_n^3. However, in order to prove this, we first need to unravel the behavior of (a_n)_n. Using a similar method as above, we generate the following values for a_n

    \[\begin{tabular}{c|c|c|c|c|c|c|c|c|c} n& 1&2&3&4&5&6&7&8&9 \\ \hline a_n& 2&8&34&144&610&2584&10946&46368&196418 \end{tabular}\]

Hmm, it looks like b_1 = f_3, b_2 = f_6, b_3 = f_9. This suggests that a_n = f_{3n}. We show this inductively on consecutive naturals n.

Show that a_n = f_{3n}

We start off with the proposition P_n \equiv a_n = f_{3n}. As we’ve observed previously that P_1,P_2, we now outline the inductive step.

Show that P_{n-1},P_{n} \implies P_{n+1}

    \begin{align*} a_{n+1} &= 4a_n + a_{n-1} & \mbox{\tiny{discharging $P_n, P_{n-1}$}} \\ &= 4f_{3n} + f_{3n-3} \\ &= 3f_{3n} + f_{3n-1} + f_{3n-2} + f_{3n-3} \\ &= 3f_{3n} + 2f_{3n-1} \\ &= 2f_{3n+1} + f_{3n} \\ &= f_{3n+2} + f_{3n+1} \\ &= f_{3n+3} \\ &\imples P_{n+1} \end{align*}

This concludes our proof that a_n = f_{3n}. \blacksquare

Show that b_n = f_n^3

We also prove the proposition P_n \equiv b_n = f_n^3 inductive on the naturals. Informally, we make the substitution of a_n = b_{n+1} + b_{n} - b_{n-1} into the definition of a_n in order to get b_n closed in terms of b.

(1)   \begin{align*} a_{n+1} &= 4a_n + a_{n-1} \\ b_{n+2} + b_{n+1} - b_n &= 4b_{n+1} + 4b_n - 4b_{n-1} + b_n + b_{n-1} - b_{n-2} \\ b_{n+2} &= 3b_{n+1} + 6b_n - 3b_{n-1} - b_{n-2} \end{align*}

As we’ve observed previously that P_1,P_2,P_3,P_4, we now outline the inductive step.

Show that P_{n-3},P_{n-2},P_{n-1},P_n \implies P_{n+1}

    \begin{align*} b_{n+1} &= 3b_{n} + 6b_{n-1} - 3b_{n-2} - b_{n-3} &\mbox{\tiny{discharging $P_{n-3},P_{n-2},P_{n-1},P_n$}} \\ &= 3f_n^3 + 6f_{n-1}^3 - 3f_{n-2}^3 - f_{n-3}^3 \\ \intertext{We observe that $f_{n-1} = f_{n+1} - f_n$} &= 3(f_{n-1} + f_{n-2})^3 + 6f_{n-1}^3 -3f_{n-2}^3 - (f_{n-1} - f_{n-2})^3 \\ &= 8f_{n-1}^3 + 12f_{n-1}^2f_{n-2} + 6f_{n-1}f_{n-2}^2 + f_{n-2}^3 \\ &= (2f_{n-1} + f_{n-2})^3 \\ &=(f_{n-1} + f_{n})^3 \\ &= f_{n+1}^3 \\ &\implies P_{n+1} \end{align*}

It’s alright, it’s okay to yell out what the fuck. Anyways, this concludes our proof that b_n = f_n^3. \blacksquare

Therefore, it follows naturally that b_{3n} = f_{3n}^3 = a_n^3 from the above. \blacksquare

Posted By Lee

Woosh