Fibonacci expansion
Task number: 3319
Prove that every natural number \(n\) can be uniquely written as the sum of various Fibonacci numbers such that the sum contains no two consecutive Fibonacci numbers.
Formally: \(n\) can be uniquely written in the form \(\displaystyle n=\sum_{j=1}^{k}F_{i_j},\) where \(i_1\ge 2\) and for every \(j \in \{1, 2, …, k-1\}\) we have \(i_{j+1}\ge i_j + 2\).
Solution
We proceed by induction on \(n\). For \(n=1\) we have \(1=F_2\).
Induction step \(n \to n+1\): By the induction hypothesis for \(n\) there exist \(i_1,…,i_k\) such that \(\displaystyle n=\sum_{j=1}^{k}F_{i_j},\). Then \(\displaystyle n+1=1+\sum_{j=1}^{k}F_{i_j}\).
- If \(i_1\ge 4\), we write 1 as \(F_2=F_{i_0}\), and then simply shift index numbers by 1
- If \(i_1=3\), we write 1 as \(F_2=F_{i_0}\), and then adjust the sequence as described below
- If \(i_1=2\), we write 1 as \(F_1=F_{i_0}\), and also adjust the sequence
At the beginning of our adjustments, the sequence contains only one pair of consecutive Fibonacci numbers. If this pair is \(F_{i_j}\), \(F_{i_{j+1}}\), where \(i_{j+1}=i_j+1\), we replace these two terms with \(F_{i_j+2}\). In this way we eliminate one pair of consecutive Fibonacci numbers and at most one more such pair arises, i.e. if \(i_{j+2}=i_j+3\).
Because the sequence is finite and the consecutive pairs are formed from greater and greater Fibonacci numbers, this process of adjustments must end after a finite number of steps.
