Representation with Fibonacci numbers

[ehrenfest]

[SOLVED] Representation with Fibonacci numbers

Homework Statement

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

Homework Equations

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.

 

[HallsofIvy]

Homework Statement

Let k >> m mean that $$m \geq m+2$$.

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?

 

[ehrenfest]

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?

Yes. That was foolish.

 

[ehrenfest]

anyone?

 

[ehrenfest]

please?

 

[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:

11011001_F

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:

100100001_F

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

 

[ehrenfest]

By the way, look into "Zeckendorf Representation."

That was EXTREMELY helpful.

http://planetmath.org/encyclopedia/ProofThatTheZeckendorfRepresentationOfAPositiveIntegerIsUnique.html