Proving a Fibonacci relation by induction

Question

Let $n\ge1$ be an integer. Prove that there exists an integer $k\ge1$ and a sequence of positive integers $a_1,a_2,a_3......a_k$ such that $a_{i+1}\ge2 + a_i$ for all $i=1,2,3,4......k-1$ and $n=F_{a_1} + F_{a_2} + F_{a_3} + F_{a_4}.........+F_{a_k}$. The numbers $F_0=0, F_1=1, F_2=1, F_3=2 $ etc are all the Fibonacci numbers.

My work: Let $a_1=F_4=3$ and $a_2=F_5=5$ and $a_{i+2}=a_{i+1} + a_i$ for $i\ge1$. I will prove the inequality by induction.
Claim: $a_{i+1}-a_i\ge2$, $\forall i\ge1$

Base case: $i=1$ We have $a_2 - a_1=2\ge2$

Induction hypothesis: Suppose $a_{i+1}-a_i\ge2$ is true for some $i=k, k\lt r, r∈ \mathbb{N}$.

Then we have $a_{k+1}-a_k\ge2$

Now let us consider $i=k-1$.

We get $a_{k} - a_{k-1}= (a_{k} + a_{k-1}) - 2a_{k-1}= a_{k-2}$

I don't know how to proceed at this point. I've tried to manipulate the expression that I get after plugging in $k-1$ in a few different ways but non of them seem to pan out

Answer 1

Note that the $a_i$ are the indices of the Fibonacci numbers in the statement of the theorem you have, not the Fibonacci numbers themselves. Also, for example, we have $5=3+2$ as a Fibonacci decomposition which does not satisfy the restriction on indices, though $5=5$ obviously does, so you need some control over the indices, and this is obtained by using the Fibonacci relation.

For the inductive step, try this as an alternative.

Suppose the theorem is true for positive integers $\le n$.

Let $F_r$ be the greatest Fibonacci number $\le n+1$. If $n+1=F_r$ we are done. Otherwise $n+1=F_r+m$ and $m$ has a decomposition of the form we require.

Let $m=F_s+F_t+\dots$ where $F_t\gt F_s\gt \dots$ is the decomposition we can take from the inductive hypothesis. We may have $m=F_t$ if $m$ is a Fibonacci number, but where it is not we have $t\ge s+2$ and the condition on indices is satisfied for any remaining components of $m$.

Then $n+1=F_r+F_s+F_t+\dots$

You might want to see whether you can proceed yourself from here - you will get some control over the indices using the Fibonacci relation $F_m=F_{m-1}+F_{m-2}$ so if two indices are consecutive, you can potentially change that.

We have either $r\ge s+2$, which you should be able to conclude; or $r=s+1$, when the leading terms are $n+1=F_{s+1}+F_s+F_t+\dots$ which you should be able to complete using the Fibonacci relation, which leads to a contradiction with the previous assumption (that $F_r$ is the greatest Fibonacci number $\le n+1$); or $r=s$ when the leading terms are $F_r+F_r+F_t+\dots$ and you should be able to show that $F_{r+1}\lt 2F_r$ for a similar contradiction.

I've left a little for you to fill in.