2
$\begingroup$

Prove by induction on $n$, that every positive integer has a Fibonacci representation, as in the Fibonacci code representation.

So, while I understand the premise behind the Fibonacci coding, and I can see that every single positive integer is going to have its own unique representation by taking into account the fact that the length of the code increases for every Fibonacci number that $n$ passes, allowing for more combinations of 1's in the resulting string, I have to somehow relate this to the difference between two consecutive Fibonacci numbers, and I'm really struggling to formalize all of this. It seems pretty foreign to me in comparison to a typical algebraic induction proof.

For reference, here's some Python code that generates the the Fibonacci representation of $n$.

def FibEncode(n):
  Fib = [0, 1]
  while Fib[-1] <= n:
    Fib += [Fib[-1] + Fib[-2]]
  Fib = Fib[:-1]
  rep = '1'
  for i in range(len(Fib) - 1, 1, -1):
    if Fib[i] <= n:
      rep = '1' + rep
      n = n - Fib[i]
    else:
      rep = '0' + rep
  return rep

for i in range(1, 15):
  print("i:", i, "\t|FibEncode(i):", FibEncode(i))

How would you formalize all of the different aspects you'd need to refer to in order to prove this by induction?

Edit:

So I am a bit closer, but still unsure of how to proceed.

Denote $F_a$ as the $a^{th}$ Fibonacci number, and $G_n$ as the number of Fibonacci numbers less than or equal to $n$ (counting $1$ twice). We wish to show that $\forall n\in\mathbb{Z}^+\exists$ a sequence of $x_i$, $x_i\in\{0, 1\}, 2\le i\le G_n$ such that $n=\sum_{j=1}^{G_n-1}x_jF_{j+2}$.

For $n=1,2,3$ those are just Fibonacci numbers, so those base cases are simple enough.

For $n=4$, then $x_1=1,x_2=0,x_3=1$ which implies that $4=1*1+0*2+1*3$ which is indeed true.

So now I just have to take the inductive step, but I'm really not sure how I would write it given the way that I've set it up so far.

$\endgroup$
  • $\begingroup$ What if I told you that just by changing the rules for generating your array, you would produce the binary encoding for the number? ie change Fib += [Fib[-1] + Fib[-2]] into Fib += [2* Fib[-1]] and suddenly your code is spitting out the binary for numbers. Does that help at all? $\endgroup$ – user24142 Aug 30 '18 at 4:11
  • $\begingroup$ In particular, the binary for a number represents a number by a sum of powers of two. Is there a sum that we can talk about here? $\endgroup$ – user24142 Aug 30 '18 at 5:49
  • $\begingroup$ @user24142, I see your point now, and I have updated my question with the beginning of my proof. I'm still unsure of how to complete it. $\endgroup$ – ereHsaWyhsipS Aug 30 '18 at 21:19
1
$\begingroup$

Using strong induction, assume that all numbers up to $n$ have a Fibonacci representation. We need to prove that $n+1$ has a Fibonacci representation. If you subtract the largest Fibonacci number $F_k$ less than or equal to $n+1$ you will get a result smaller than $F_{k-1}$. We know $n+1-F_k$ has a Fibonacci representation and does not include $F_{k-1},$ so $n+1$ has a Fibonacci representation.

$\endgroup$
  • $\begingroup$ one of the conditions of the fibonnacci representation of a number is that it should have no consecutive 1s. I'm not sure how your proof makes it clear that the resulting representation has this property. $\endgroup$ – user24142 Aug 31 '18 at 3:11
  • $\begingroup$ @user24142: I had missed that, but have updated the answer to cover it. $\endgroup$ – Ross Millikan Aug 31 '18 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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