Fibonacci Coding Inductive Proof

Question

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.

Answer 1

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.