This semester, I’m a teaching assistant for MAT102, UTM’s introduction to mathematical proofs and reasoning.

A topic discussed in that course, is induction. This is sometimes explained using dominos or ladders. Suppose you have some sort of statement (something that is true or false), that depends on some positive integer $n$.

An example of this, would be the statement “if $n \geq 12$, I can make $n$ cents out of a pile of $4$ and $5$ cent coins” or “$n$ can be written as a sum of powers of two”.

Induction

Induction is the idea that if you show the statement for $n = 1$ (or the lowest $n$ the statement is meant for, like twelve), and you show that for any $n$, if it holds for $n$, it must hold for $n+1$, then it is true for every value.

The “domino” effect looks like this: \(S(1) \implies S(2) \implies S(3) \implies S(4) \implies \dots\)

A related concept that students struggle a lot on, is strong induction. I’m not going to explain it in this blog, but you can read about it here.

The problem

This past week, students were shown the following problem: “For any (natural) number $n$, it can be written as the sum of distinct, non-consecutive, Fibonacci numbers, uniquely”. This is where we consider the Fibonacci numbers as \(1, 2, 3, 5, 8, 13, 21, \dots\)

Let’s prove this. We will denote $F_n$ for the $n$th Fibonacci number, with $F_1 = 1, F_2 = 2$.

Before you read the proof, I recommend seeing if you can observe some facts about Fibonacci numbers and try some numbers yourself. Convince yourself of this statement!

First, here are some facts.

  1. ${F_{\square}}$ is a strictly increasing sequence.
  2. For any $k \in \mathbb{N}$, $\sum_{i = 1}^k F_{2i} < F_{2k + 1}$
  3. For any $k \in \mathbb{N}$, $\sum_{i = 1}^{k} F_{2i - 1} < F_{2k}$

The last two facts fall out of trying to see how big you can get with trying to add non-consecutive Fibonacci numbers. You can prove both of them using induction themselves, and we will omit the proofs for them here.

To see a couple examples, notice that

\[\begin{align*} 2 &<3\\ 2 + 5 &< 8\\ 2 + 5 + 13&< 21\\ 1 &< 2\\ 1 + 3 &< 5\\ 1 + 3 + 8 &< 13\\ \end{align*}\]

The proof

For the base case, $1 = 1$, and can definitely not be written in any other way with Fibonacci numbers (as they are all bigger than $1$), so we’ve proven the statement for $1$.

If you’d like, you can also check this fairly elementarily for $2$ and $3$ as well. $2$ can only be written as $2$ or $1+1$, and similarly for $3$.

The induction step

For the induction step, suppose for some $n$, this is true for $1, 2, 3, \dots, n$, which is the strong induction hypothesis. We wish to show the statement is true for $n+1$.

If $n+1$ is a Fibonacci number, we’re done. Why? Well, $n+1 = n+1$, so we can definitely write it using distinct, non-consecutive Fibonacci numbers. Per the second and third facts, we cannot express it using smaller Fibonacci numbers, which gets us uniqueness!

If not, since the Fibonacci numbers are an increasing sequence, we know that for some $m \in \mathbb{N}$, it is true that $F_m < n + 1 < F_{m+1}$.

Suppose that $F_m$ was not used in the sum for $n+1$. If $m$ is even, then we can write $m = 2k$, and \(\sum_{i = 1}^{k} F_{2i - 1} < F_{2k} < n+1\)

Using the even ones (not including $F_m$) would also result in less than $n+1$:

\[\sum_{i = 1}^{k-1} F_{2i} < F_{2k-1} < F_{2k} < n+1\]

The logic, when $m$ is odd, is very similar. This shows that if there is a sum that works, $F_m$ must be in it. Denote $r = (n+1) - F_m$, the “remainder”.

Note that $F_{m-1} = F_{m+1} - F_{m} > n+1 - F_m = r$. By the induction hypothesis, since $r < n+1$, there must be some way to write $r$ as the sum of non-consecutive Fibonacci numbers, and that too uniquely.

Note that $r$ won’t be written with $F_m$ or $F_{m-1}$ because they are too big. So the list that $r$ is written with, is not consecutive with $F_m$, and is distinct from it.

For uniqueness, suppose there were natural numbers $i_1, \dots, i_\alpha$ and $j_1, \dots, j_\beta$ (in increasing order) such that

\[\sum_{\ell = 1}^\alpha F_{i_\ell} = n+1 = \sum_{\ell = 1}^\beta F_{j_\ell}\]

That is, there are two different ways to write $n+1$ as a sum of distinct, non-consecutive Fibonacci numbers. Then, we know that $F_{i_\alpha} = F_m = F_{j_\beta}$, as we showed before. However, it must be that \(\sum_{\ell = 1}^{\alpha - 1} F_{i_\ell} = (n+1) - F_m = \sum_{\ell = 1}^{\beta - 1} F_{j_\ell}\) but that contradicts the fact that $r = (n+1) - F_m$ is writeable uniquely!

So there is only one way to write $n+1$ as a sum of distinct, non-consecutive Fibonacci numbers, which concludes the induction step.

With the induction step and the base case, by induction, we get the desired statement, that any number $n$ is writeable uniquely in this way.