Instead of binary or decimal, the Kingdom of Leutonia uses an unusual system to represent numbers, based on the Fibonacci sequence. The Fibonacci sequence $F_0,F_1,F_2,\dots$ is defined recursively as follows $$ \begin{align*} F_0&=1\\ F_1&=1\\ F_n&=F_{n-1}+F_{n-2}\text{ for }n\ge 2 \end{align*} $$ A Leutonian number is a string of 0’s and 1’s that begins with a 1 and never has two consecutive 1’s. If $s=s_\ell s_{\ell-1}\dots s_1$ is such a string of length $\ell$, where each $s_i$ is in $\{0,1\}$, the number represented by $s$ is $n(s)=\sum\limits_{i=1}^\ell s_i\cdot F_i$.
For example, $n(1000101)=F_7+F_3+F_1=21+3+1=25$.
(a) Write out the Leutonian numbers that represent the first 12 positive integers.
(b) Prove: For every $\ell\ge1$, if $s$ is a Leutonian number of lenght $\ell$, $n(s)\ge F_\ell$
I am trying to do (b).
That's what I did:
Basis: $p(1) : \sum_{i=1}^1 s_i \cdot F_1 \ge F_1$
$ = \sum_{i=1}^1 s_1 \cdot 1 \ge 1$
Since a leutonian number must starts with 1. $s_1 = 1$
so the base case is true.
I can't do the induction case.
I'm not quite sure why you want to use induction to prove this. Can't you say that a Leutonian number $s$ of length $l$ has $s_l=1$, hence $s=\sum_{i=1}^ls_iF_i=F_l+\sum_{i=1}^{l-1}s_iF_i\geq F_l$, since each term $>0$?