Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can anyone hint me to prove:

$\forall n\in \mathbb{N}: \exists$ Fibonacci numbers $ F_{i_1},\ldots,F_{i_k}$ such that: $$\sum F_{i_k}=n$$

Note: Every Fibonacci number can appear only once. Thanks

share|improve this question
    
Is there any conditions on the numbers? Since $F_1 = 1$, we have $\underbrace{F_1 + \ldots + F_1}_{\textrm{n times}} = n$ –  sxd Sep 17 '12 at 23:01
    
Well $1 \in F_n$ so... –  Juan S Sep 17 '12 at 23:01
    
The title does say "different" Fibonacci numbers –  mathguy Sep 17 '12 at 23:02
    
We are only allowed to use every Fibonacci number, at most once. –  Hooman Sep 17 '12 at 23:02
    
@Hooman, write that in the body of your question then as well! –  sxd Sep 17 '12 at 23:03
show 2 more comments

2 Answers

up vote 7 down vote accepted

In fact every positive integer can be written uniquely as a sum of one or more non-consecutive Fibonacci numbers; this is known a Zeckendorf’s theorem. There is even a simple algorithm for finding this representation: just use the greedy algorithm, always picking the largest Fibonacci number that will still ‘fit’. E.g., $32=21+8+3$. This fact should suggest that a proof by induction might work: if $n$ is not a Fibonacci number, and $F_k$ is the largest Fibonacci number less than $n$, look at $n-F_k$.

Proving uniqueness (which is true only with the restriction that the Fibonacci numbers used be non-consecutive) takes a little more work, and in any case you weren’t asked to do it. Still, you might find it interesting to try. You might also find some of the odds and ends here interesting.

share|improve this answer
add comment

Hint: Induction! (Start from $n=4$)

share|improve this answer
2  
Note: This is known as Zeckendorf's Theorem –  Juan S Sep 17 '12 at 23:05
    
This even allows that the Fibonacci numbers used are not sequential. –  Ross Millikan Sep 17 '12 at 23:15
1  
I assume by "sequential" you mean something that I would call "adjacent"? –  Ben Millwood Sep 17 '12 at 23:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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