12
$\begingroup$

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

  • 0
    Is there any conditions on the numbers? Since $F_1 = 1$, we have $\underbrace{F_1 + \ldots + F_1}_{\textrm{n times}} = n$2012-09-17
  • 0
    Well $1 \in F_n$ so...2012-09-17
  • 0
    The title does say "different" Fibonacci numbers2012-09-17
  • 0
    We are only allowed to use every Fibonacci number, at most once.2012-09-17
  • 0
    @Hooman, write that in the body of your question then as well!2012-09-17
  • 0
    Just try to do it a few times, it should become clear, especially if you already know about binary (Fibonacci numbers are strictly closer together than powers of two).2012-09-17
  • 0
    @Hooman : If you type \sum instead of \Sigma, then not only is the character bigger, but also in some contexts it's formatted differently. In particular, in a "displayed" setting, typing \sum makes the subscript and superscript appear directly above and below the symbol, thus: $\displaystyle\sum_{i=1}^n a_i$. (As opposed to $\displaystyle\Sigma_{i=1}^n a_i$.)2012-09-18

2 Answers 2

16

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.

1

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

  • 2
    Note: This is known as Zeckendorf's Theorem2012-09-17
  • 0
    This even allows that the Fibonacci numbers used are not sequential.2012-09-17
  • 2
    I assume by "sequential" you mean something that I would call "adjacent"?2012-09-17