0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is just a thought, have you tried looking at a Leutonian number of length $L\gt2$ as a combination of a length $L-1$ and length $L-2$ Leutonian numbers and using the Fibanocci recurrence to do the induction case? $\endgroup$
    – Average
    Sep 25, 2014 at 5:01
  • $\begingroup$ Wikipedia: Zeckendorf's theorem. See also: math.stackexchange.com/questions/198253/… $\endgroup$ Sep 25, 2014 at 11:42
  • $\begingroup$ For the sake of completeness, you could also have added link to the original source: eecs.yorku.ca/course_archive/2014-15/F/2001/a2.pdf (Google does not return many hits for "Leutonian numbers", so I guess this might be where the problem comes from.) $\endgroup$ Sep 25, 2014 at 11:52

1 Answer 1

1
$\begingroup$

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

$\endgroup$

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.