Representation with Fibonacci numbers

1. Dec 27, 2007

ehrenfest

[SOLVED] Representation with Fibonacci numbers

1. The problem statement, all variables and given/known data
Let k >> m mean that $$m \geq m+2$$. Show that every positive integers n has a unique representation of the form $$n = F_{k_1} + F_{k_2} + \cdots F_{k_r}$$, where $$F_{k_i}$$ are Fibonacci nuimbers and $$k_1 >> k_2 >> \cdots k_r >> 0$$.

EDIT: The first sentence should be: Let k >> m mean that $$k \geq m+2$$.

2. Relevant equations

3. The attempt at a solution
I can show that the representation exists by induction.
To show that the representation is unique, I am also trying to use induction. The uniqueness holds for n = 1,2,3. Assume the result holds for n leq k. If k+1 has two such representations, then these two representation must be pairwise different or else the strong IH is violated. I need help drawing the contradiction in the case where the two representations are pairwise distinct. Then we have that 2k+2 is equal to a sum of distinct Fibonacci numbers leq k+1, which seems like it might be impossible, but I am not sure how to prove that.

Last edited: Dec 27, 2007
2. Dec 27, 2007

HallsofIvy

Staff Emeritus
Surely that's not what you meant to write! $m\ge m+ 2$ is NEVER true so that just says "K>> m" is never true. Did you intend to have a k in that?

3. Dec 27, 2007

ehrenfest

Yes. That was foolish.

4. Dec 28, 2007

ehrenfest

anyone?

Last edited: Dec 29, 2007
5. Dec 29, 2007

ehrenfest

6. Dec 29, 2007

AKG

First show that you can write any number as a sum of some Fibonacci numbers $F_{k_i}$ where we have the easier condition $F_{k_1} > \dots > F_{k_r} > 0$. Let's use a "binary-like" notation, where for example:

11011001F

means the sum of the first, fourth, fifth, seventh, and eight Fibonacci numbers (by the way, what convention are you using - what are your first and second Fibonacci numbers?). Now observe that any occurrence of 011 can be replaced with 100 because of the recurrence relation that the Fibonacci sequence satisfies. So the above is equal to:

100100001F

Now you yourself need to come up with a general procedure. By the way, look into "Zeckendorf Representation."

7. Dec 30, 2007