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$ ?


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.

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

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.