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.

Difficulty level: Moderate task
Solution require uncommon idea
Cs translation
Send comment on task by email