# Does my rearrangement of the sequence to prove that - any $n\in\mathbb N$ can be written as the sum of Fibonacci numbers - look fine?

I have this problem in my textbook. I spent many days to come up with the solution. While I'm quite sure about the first part of my proof, I'm unable to verify the second part (which is related to the REARRANGEMENT of the sequence and is the most important). Some users have left comments and I responded to every of these comments, but they seem to stop interact with me.

Any $n\in\mathbb N$ can be written as the sum of a strictly increasing sequence of Fibonacci numbers.

My attempt:

Let $(f_n\mid n\in\mathbb N^*)$ be the Fibonacci sequence such that $f_1=1,f_2=2,$ and $f_{n+2}=f_{n+1}+f_n$.

Assume the contrary, then set $T$ consisting of positive integers that can NOT be expressed as the sum of a strictly increasing sequence of Fibonacci numbers is non-empty.

Let $m_0=\min T$, then $m_0=m+2$ for some $m$. As a result, $m,m+1\notin T$ and therefore can be expressed as the sum of a strictly increasing sequence of Fibonacci numbers.

We define: $E_n$ is an F-expression of $n\iff\begin{cases} \ t\in E_n\implies t\text{ is a Fibonacci number} \\ \sum_{t\in E_n}t=n \\ \end{cases}$

It' clear that $k\notin T\implies$ there exists an F-expression of $k$.

Since $m\notin T$, then there exists an F-expression of $m$ and, for any $E_m$, $2\in E_m$ (If not, $\{2\}\cup E_m$ will be an F-expression of $m+2$, and consequently $m+2\notin F$, which is a contradiction). Similarly, $1\in E_{m+1}$, then $E_{m+1}\setminus\{1\}$ is an F-expression of $m$, then $2\in E_{m+1}\setminus\{1\}$, then $2\in E_{m+1}$. Hence $1,2\in E_{m+1}$ for any $E_{m+1}$.

Let $m_1=\min\{n\in\mathbb N\mid f_{n+1}\notin E_{m+1}\}$, then $(n\leq m_1\implies f_n\in E_{m+1})$ and $f_{m_1+1}\notin E_{m+1}$. We have two cases in total:

1. $m_1=2k$

As a result, $m+1=f_1+f_2+...+f_{m_1}+...=(f_1+f_2)+(f_3+f_4)+...+(f_{2k-1}+f_{2k})+...=f_3+f_5+...+f_{2k+1}+...=f_3+f_5+...+f_{m_1+1}+...$

Thus $m+2=1+(f_3+f_5+...+f_{m_1+1}+...)=f_1+f_3+f_5+...+f_{m_1+1}+...$, then $m+2$ can be expressed as the sum of a strictly increasing sequence of Fibonacci numbers, and consequently $m+2\notin T$, which is a contradiction.

1. $m_1=2k+1$

As a result, $m+1=f_1+f_2+...+f_{m_1}+...=f_1+f_2+...+f_{2k}+f_{2k+1}+...=f_1+(f_2+f_3)+...+(f_{2k}+f_{2k+1})+...=f_1+f_4+...+f_{2k+2}+...\implies m=f_4+...+f_{2k+2}+...$ $\implies m+2=2+f_4+...+f_{2k+2}+...=f_2+f_4+...+f_{2k+2}+...$ Then $m+2$ can be expressed as the sum of a strictly increasing sequence of Fibonacci numbers, and consequently $m+2\notin T$, which is a contradiction.

Thus $T=\emptyset$. This completes the proof.

• Are there one or more typos in the following? Let m1=min{n∈N∣fn∈Em+1∧fn+1∉Em+1}, then (n≤m⟹fn∈Em+1) and fm1+1∉Em+1. – Steve B Aug 10 '18 at 6:24
• Thank you @SteveB, there is actually a typo. It should be $n\leq m_1\implies f_n\in E_{m+1}$ rather than $n\leq m\implies f_n\in E_{m+1}$. – MadnessFor MATH Aug 10 '18 at 6:31
• 1) How does n < $m_1$ imply that $f_n\in E_{m+1})$? 2) $m+1=f_1+f_2+...+f_{m_1}+...$? Surely m+1 is not the sum of an infinite series of Fibonacci numbers. – Steve B Aug 10 '18 at 6:46
• Simpler proof: consider the Fibonacci numbers $1,2,3,5,\ldots$ (that is, leave out the initial $0,1$). Suppose $f_k\le n<f_{k+1}$. Since $f_{k+1}\le2f_k$ we have $n=(n-f_k)+f_k$ with $n-f_k<f_k$. If $n-f_k=0$ we are finished, otherwise by induction we may assume $n-f_k$ is a sum of increasing Fibonacci numbers. – David Aug 10 '18 at 6:53
• @SteveB For 1: In order to have that property, I have changed $m_1=\min\{n\in\mathbb N\mid f_{n+1}\notin E_{m+1}\}$. For 2: since $(n\leq m_1\implies f_n\in E_{m+1})$, then $\{f_n\mid 1\leq n\leq m_1\}\subseteq E_{m+1}$, and consequently $m+1=f_1+f_2+...+f_{m_1}+...$ – MadnessFor MATH Aug 10 '18 at 9:00

Let $(f_n\mid n\in\mathbb N^*)$ be the Fibonacci sequence such that $f_1=1,f_2=2$, and $f_{n+2}=f_{n+1}+f_n$. I will prove this theorem by strong induction on $n$. Assume that the theorem is true for all $k<n$.
It's clear that there exists $t$ such that $f_t\leq n<f_{t+1}$. We have $f_{t+1}=f_t+f_{t-1}$, then $f_{t+1}-f_t=f_{t-1}<f_t$. We also have $n=(n-f_t)+f_t$ where $n-f_t<f_{t+1}-f_t<f_t\leq n$. Thus $n-f_t<n$.
If $n-f_t=0$, we are done.
If $n-f_t>0$, then apply Inductive Hypothesis to $(n-f_t)$. Hence $(n-f_t)$ can be expressed as the sum of a strictly increasing sequence of Fibonacci numbers where each term is strictly less than $f_t$ (since $n-f_t<f_t$). Thus $n=(n-f_t)+f_t$ can be expressed as the sum of the above-mentioned sequence and $f_t$. This completes the proof.