## Fibonacci expansion

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.