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$

enter image description here

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


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.