# Proving a Fibonacci relation by induction

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

• Look up: Zeckendorf's theorem – Robert Israel Mar 5 '19 at 22:19
• Just to make sure, I am correct in using induction the downward direction i.e first assume true for n=k and then try to prove it is true for n=k-1, for this particular question? The induction proofs for Zeckendorf's theorem differ slightly in that the first assume true for n=k, and then prove true for n=k+1 – user140161 Mar 5 '19 at 23:35
• am i correct in using* – user140161 Mar 6 '19 at 0:42
• No, you can't use induction "downward". – Robert Israel Mar 6 '19 at 1:53
• Why? And if that's the case, then can I use it with having n=k for the inductive step and prove n=k+1 for this particular question? – user140161 Mar 6 '19 at 3:29

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.