Add Me!Close Menu Navigation

Super Fibonacci

Show that k|a_k where a_k defined as

     \begin{align*} a_0 &= 0 \hspace{4mm} a_1 = 1 \\ a_2 &= 2 \hspace{4mm} a_3 = 6 \\ a_{n+4} &= 2a_{n+3} + a_{n+2} - 2a_{n+1} - a_n \end{align*}

1. Guess at a solution

Let’s start off by enumerating these terms

    \[\begin{tabular}{c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6  \\ \hline $a_n$&1&2&6&12&25&48 \end{tabular}\]

Since the problem asks us to prove that n|a_n, let’s just see what we get left over after dividing out n

    \[\begin{tabular}{c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6  \\ \hline $a_n$& \underbrace{1}_{\mathclamp{\frac{a_n}{n} = 1}}&\underbrace{2}_{1}&\underbrace{6}_{2}&\underbrace{12}_{3}&\underbrace{25}_{5}&\underbrace{48}_{8} \end{tabular}\]

Oh my god! That’s the fibonacci sequence defined by

    \begin{align*} f_1 &= 1 \\ f_2 &= 2 \\ f_{n+2} &= f_{n+1} + f_n \end{align*}

This naturally suggests that a_n = n f_n

2. Show that a_n = n f_n

We can prove this inductive on consecutive naturals n. Informally, We form the inductive steps through the regrouping of the terms of a_n as

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

Proof by induction

We need to prove the proposition P_n \equiv a_n = n f_n holds for all n.

As the base cases, we observe that a_1 = 1 \underbrace{f_1}_{1} = 1, a_2 = 2 \underbrace{f_2}_{1} = 2, a_3 = 3 \underbrace{f_3}_{2} = 6, a_4 = 4 \underbrace{f_4}_{3} = 12 and hence P_1, P_2, P_3, P_4.

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

    \begin{align*} a_{n+4} &= 2(a_{n+3} + a_{n+2}) - (a_{n+2} + a_{n+1}) - (a_{n+1} + a_n) & \mbox{\tiny{discharge $P_n, P_{n+1}, P_{n+2}, P_{n+3}$}} \\ &= n\left( 2(f_{n+3} + f_{n+2}) - \underbrace{(f_{n+2} + f_{n+1})}_{f_{n+3}} - \underbrace{(f_{n+1} + f_n)}_{f_{n+2}} \right) + \underbrace{6f_{n+3}}_{{4f_{n+3} + 2f_{n+3}}} + 2f_{n+2} - 2f_{n+1} - 0f_n  \\ &= n\left( 2(f_{n+3} + f_{n+2}) - (f_{n+3} + f_{n+2})\right) + 4f_{n+3} + 2f_{n+2} + 2f_{n+2} + 2f_{n+1} - 2f_{n+1} \\ &= n\left(\underbrace{f_{n+3} + f_{n+2}}_{f_{n+4}}\right) + 4f_{n+3} + 4f_{n+2} \\ &= (n+4) f_{n+4} \\ & \implies P_{n+4} \end{align*}

This concludes our proof that a_n = n f_n. \blacksquare

3. Show that k|a_k

Since f_n is successively defined in terms of addition on the naturals, which closes the naturals, then it must be the case that for any n, f_n \in \mathbb N. Because a_n = n f_n, then trivially n|(n f_n). This concludes the proof that k|a_k \fa k \in \mathbb N. \blacksquare

Posted By Lee

Woosh