1
$\begingroup$

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:

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+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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steve B Aug 10 '18 at 6:24
  • $\begingroup$ 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}$. $\endgroup$ – MadnessFor MATH Aug 10 '18 at 6:31
  • $\begingroup$ 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. $\endgroup$ – Steve B Aug 10 '18 at 6:46
  • $\begingroup$ 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. $\endgroup$ – David Aug 10 '18 at 6:53
  • $\begingroup$ @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}+...$ $\endgroup$ – MadnessFor MATH Aug 10 '18 at 9:00
1
$\begingroup$

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


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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.