(adsbygoogle = window.adsbygoogle || []).push({}); [SOLVED] Representation with Fibonacci numbers

1. The problem statement, all variables and given/known data

Let k >> m mean that [tex]m \geq m+2[/tex]. Show that every positive integers n has a unique representation of the form [tex] n = F_{k_1} + F_{k_2} + \cdots F_{k_r}[/tex], where [tex]F_{k_i}[/tex] are Fibonacci nuimbers and [tex] k_1 >> k_2 >> \cdots k_r >> 0[/tex].

EDIT: The first sentence should be: Let k >> m mean that [tex]k \geq m+2[/tex].

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Representation with Fibonacci numbers

**Physics Forums | Science Articles, Homework Help, Discussion**