# An Euler’s number binom-rational inequality.

Combining the Binomial Theorem with the sequence
$e(n) := (1+\frac{1}{n})^n$, we get the following rational inequality…

Claim. For $n> 1$ it holds that $2 < (1+1/n)^{n} < \frac{67}{2^3\cdot 3} = 2.7916666666666666666\cdots$
Proof.
Applying the binomial theorem,
$\displaystyle \left(1+\frac{1}{n}\right)^n = \sum_{k=0}^{n}\binom{n}{k}\frac{1}{n^k} =$ $\displaystyle = 1+\sum_{k=1}^{n}\binom{n}{k}\frac{1}{n^k}$
$\displaystyle = 1 + \sum_{k=1}^{n} \frac{1}{k!} \frac{(n-k+1)\cdots (n-1)n}{n^k}=1+\sum_{k=1}^{n} \frac{1}{k!} \prod_{i=0}^{k-1} \frac{n-i}{n} =$
$\displaystyle = 1+\sum_{k=1}^{n} \frac{1}{k!} \prod_{i=0}^{k-1} (1 - \frac{i}{n})$

Look at the factors of the product above: fix $i$ and define $f(n):=1-\frac{i}{n}, n\geq 1$, clearly $f(n+1)>f(n)$ for any $n \geq 1$, so $(1+\frac{1}{n})^n$ is a monotonically increasing function of $n$. This imply $\left(1+\frac{1}{n}\right)^n > 2$ provided that $n>1$.

Also $1-\frac{i}{n} < 1$, thus $1+\sum_{k=1}^{n} \frac{1}{k!} \prod_{i=0}^{k-1} (1 - \frac{i}{n}) < 1+\sum_{k=1}^{n} \frac{1}{k!}.$

Now for every $n\geq 4$ it holds $n! > 2^n$, this imply
$\displaystyle 1+\sum_{k=1}^{n} \frac{1}{k!} < 1 + (1+1/2 + 1/6) + \sum_{k=4}^{n}\frac{1}{2^k} =$
$= 1+(1+1/2+1/6)- (1+1/2+1/4+1/8) + \frac{1-1/2^{n+1}}{1-1/2} <$
$< 1+(1+1/2+1/6)- (1+1/2+1/4+1/8) + \frac{1}{1-1/2} =$
$3+1/6-1/4-1/8 = \frac{67}{2^3\cdot 3} = 2.7916666666666666666\cdots$.
Q.E.D.

# Fibonacci’s words.

The Fibonacci sequence $f_n = \left\{ \begin{array}{ll} 0 & \quad n = 1 \\ 1 & \quad n = 2 \\ f_{n-1} + f_{n-2} & \quad n \geq 3 \\ \end{array} \right.$
is a well known and ubiquitous sequence of natural numbers.

You can find Fibonacci numbers everywhere starting from… your personal rabbit hutch…

Similarly, there exists a well known formal language,

The Fibonacci Language

containing all the words defined by the following word concatenation:

$F_n = \left\{ \begin{array}{ll} ' 0 ' & \quad n = 1 \\ ' 1 ' & \quad n = 2 \\ F_{n-1} F_{n-2} & \quad n \geq 3 \\ \end{array} \right.$

We speak out loud the first ten Fibonacci words with the following python code:
 >>> def Fib(n): ...   if n < 1: ...      return 'illegal arg' ...   elif n == 1: ...      return '0' ...   elif n == 2: ...      return '1' ...   elif n > 3: ...      f = Fib(n-1)+Fib(n-2) ...      return f 
 >>> def SpeakOutLoudFibo(N): ...  if N < 1: ...     print 'illegal arg' ...   else: ...      for i in range(1,N): ...        print Fib(i)+'\n' ... 
 >>> SpeakOutLoudFibo(11) 0

 1 10 101 10110 10110101 1011010110110 101101011011010110101 1011010110110101101011011010110110 

1011010110110101101011011010110110101101011011010110101 

Then we look at the first Fibonacci words and see the following:

Claim. The fibonacci language contains no words having ’00’ nor ‘111’ as substrings.
Proof. We proceed by induction on $n$. The first two fibonacci words are of length $1$. Fix $n$ and assume that $F_m$ does not contain ’00’ nor ‘111’ for every $m < n$. Then $F_n$ does not contain '00', otherwise applying induction hypothesis it must be $F_n = F_{n-1}F_{n-2} = x00y$ with $F_{n-1}=x0$ and $F_{n-2}=0y$. Observe that the only Fibonacci word starting with 0 is $F_1$ because $F_2=1$ and every Fibonacci word has $F_1$ as a prefix. This imply $F_{n-2}=0=F_{1}$ hence $n = 3$, this is not possible since $F_3 = 10$.
Now we consider substring '111'. If $F_n$ contains '111', applying induction hypothesis it must be one of two cases:
case 1: $F_n = x11\cdot 1y$ for $F_{n-1} = x11$ and $F_{n-2} = 1y$
This imply that there exists a Fibonacci word that ends with ’11’. Consider the shortest Fibonacci word ending with ’11’, assume this is $F_s$, wlog $s\geq 3$. Then $F_{s-2}$ ends with ’11’ as well because is the suffix of $F_s$. This is against the minimality of $|F_s|$ and leads to a contradiction.
case 2: $F_n = x1\cdot 11y$ for $F_{n-1} = x1$ and $F_{n-2} = 11y$
every Fibonacci word has $F_3 = 10$ as a prefix so this case is not possible.
Q.E.D.