A conjecture about Fibonacci numbers

Let $\{F_n\}_{n=1}^\infty$ be the Fibonacci sequence (defined by $F_n=F_{n-1}+F_{n-2}$ with $F_1=F_2=1$).

Is it true that for every integer number $N$ there exist positive integers $n,m,k,l$ such that $N=F_n+F_m-F_k-F_l$ ?

2 Answers

Short answer: No, because the Fibonacci sequence grows exponentially.

Longer answer: First suppose $\{n,m\} \cap \{k,\ell\} \neq \emptyset$, say $n=l$. Then $N = F_m - F_k$. This implies that $N = F_m - F_k \geq F_m - F_{m-1} = F_{m-2}$. It follows that $m = O(\log(N))$ because the Fibonacci sequence is exponential. Similarly we have $k = O(\log(N))$. It follows that for large $N$ we can choose $m$ and $k$ in at most $O(\log(N)^2)$ ways.

Now suppose $\{n,m\}$ and $\{k,\ell\}$ are disjoint. Then we similarly find that we can choose $n$, $m$, $k$, $\ell$ in at most $O(\log(N)^4)$ ways.

Consequently, to write the numbers $1$, $2$, ..., $N$ in the desired form, there are at most $O(\log(N)^2 + \log(N)^4)$ possible choices for $n$, $m$, $k$, $\ell$. However this becomes strictly smaller than $N$ for large $N$.

Edit: I'm wrong. 😑

I'm getting yes! Take k,l = 1. Then it follows.

N = F(n) + F(m) - 2 => N + 2 = F(n) + F(m),Take N' = N+2. Therefore, we get.

=> N' = F(n) + F(m) ,N'>=2. Which is possible since every natural number is a combination of two Fibonacci number. For N=0 & 1 also we have possible solution trivially. Therefore your conjecture is correct.

Please correct me if I'm wrong since I'm newbie. Thanks.

• "every natural number is a combination of two Fibonacci number": no it's not. Take for instance $N'=12$. – TonyK Sep 11 '16 at 16:28
• Yes, I've mistaken. Every number is combination of Fibonacci numbers not 'two'. Thanks. – Mr.Sigma. Sep 11 '16 at 16:30