Vtyjkyuk

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 $ninmathbb N$ can be written as the sum of a strictly increasing sequence of Fibonacci numbers.

My attempt:

Let $(f_nmid ninmathbb 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+1notin 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 $niffbegincases
tin E_nimplies ttext is a Fibonacci number \
sum_tin E_nt=n \
endcases$

It' clear that $knotin Timplies$ there exists an F-expression of $k$.

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

Let $m_1=minninmathbb Nmid f_n+1notin E_m+1$, then $(nleq m_1implies f_nin E_m+1)$ and $f_m_1+1notin E_m+1$. We have two cases in total:

I'm not sure about the correctness of the below part. Please help me check it out.

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+2notin T$, which is a contradiction.

2. $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+2notin T$, which is a contradiction.

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

On the basis of @David's comment, I present a proof here.

Let $(f_nmid ninmathbb 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_tleq 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_tleq 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.