I want to express an integer N by summation of some fibonacci number…
say i want to express 15 in fibonacci number…
The few first fibonacci numbers are 1,1,2,3,5,8,13,21,…
First number less than or equal to 15 is 13,so we took 13,then N=15-13=2…
The next 2 is equal to N.we took 2…
My questin is,why we are taking 13 (First number <=N ) ?
Isn’t there chance to get impossible result if we take just immediate number?
Solution can be remain in next numbers.But always we are taking immediate one…Why?
Thanks in advance 
It is a well known fact that any natural number can be represented as sum of distinct fib numbers. Say F_n < N < F_{n+1} , then N-F_n is also a natural number. So we can represent N-F_n as sum of some other fib numbers. That’s why in our first step we always choose the nearest fib number less than N.
And the other thing to observe is that (N-F_n) < (F_{n+1}-F_n)=F_{n-1} . So we can make it sure that no fib number will occur more than once. But if you subtract any other random fib number form N except F_n then same fib numbers can occur many times in the expression of the sum.
3 Likes
If the sequence is …
Fn=Fn-1 + Fn-2 + Fn-3 + … +Fn-m rather than Fn=Fn-1 + Fn-2
Then why it is working ?
Sorry, I don’t get you.
When it is fibonacci series(Fn=Fn-1 + Fn-2),N can be expressed by some fibonacci number…
But If the series’s each term is summation of previous 5 fibonacci number rather than 2.In this scenario,why it works?
It will never be impossible because the difference between N(the number you want to express) and Fn(the biggest number in the Fibonacci sequence smaller than N) will be less than F(n-1) and all numbers lesser than Fn can be expressed used numbers in the Fibonacci sequence.
1 Like
F_n=F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}+F_{n-5} is not a Fibonacci recurrence. A Fibonacci recurrence is defined by F_n=F_{n-1}+F_{n-2} only. And the result that I provided in my first answer was completely for F_n=F_{n-1}+F_{n-2} recurrence only.