# Prove that $\forall n \in \Bbb{N}, 1 <n, \left( 1 + \frac{1}{n} \right)^n < \sum_{i=0}^n \frac{1}{i!}$

I'm trying to do the following exercise:

Prove that $\forall n \in \Bbb{N}, 1 <n, \biggl( 1 + \frac{1}{n}$ $\biggr)^n < \sum_{i=0}^n \frac{1}{i!}$

(I can't use limits, e, or any other tool from calculus)

The textbook where I found this suggests using the binomial theorem.

This is what I've got so far:

$\biggl( 1 + \frac{1}{n} \biggr)^n = \sum_{i=0}^n \binom{n}{i} (\frac{1}{n})^i$

Therefore $\biggl( 1 + \frac{1}{n} \biggr)^n < \sum_{i=0}^n \frac{1}{i!} \iff \sum_{i=0}^n \binom{n}{i} (\frac{1}{n})^i < \sum_{i=0}^n \frac{1}{i!}$

$\iff \binom{n}{0} (\frac{1}{n})^0 + \binom{n}{1} (\frac{1}{n})^1 + \sum_{i=2}^n \binom{n}{i} (\frac{1}{n})^i < \frac{1}{0!} + \frac{1}{1!} + \sum_{i=2}^n \frac{1}{i!}$

$\iff 2 + \sum_{i=2}^n \binom{n}{i} (\frac{1}{n})^i < 2 + \sum_{i=2}^n \frac{1}{i!} \iff \sum_{i=2}^n \binom{n}{i} (\frac{1}{n})^i < \sum_{i=2}^n \frac{1}{i!}$

$\iff\sum_{i=2}^n \frac{n!}{i!(n-i)!n^i} < \sum_{i=2}^n \frac{1}{i!}$

$\iff \frac{n!}{(n-i)!n^i} < 1 , \forall i \ge 2$

Now I will prove by induction that $\frac{n!}{(n-i)!n^i} < 1$ :

Let $n \in \Bbb{N}, n >1$

Let $P(i)::$ "$\frac{n!}{(n-i)!n^i} < 1 , \forall i \ge 2$"

Base case:

$\frac{n!}{(n-2)!n^2} = \frac{n(n-1)(n-2)!}{(n-2)!n^2} = \frac{n-1}{n} < 1$ so P(2) is true.

Inductive step:

(I assume as an inductive hypothesis that P(i) is true)

P(i+1) is true if we have $\frac{n!}{(n-(i+1))!n^{i+1}} < 1 \iff \frac{n!}{(n-i-1)!n^i n} < 1$

$\iff \frac{n!}{(n-i)!n^i} * \frac{n-i}{n} < 1$

$\frac{n!}{(n-i)!n^i} < 1$ by the inductive hypothesis and $i \ge 2 \implies n-i < n \implies \frac{n-i}{n} < 1$.

So P(i+1) is true $\forall i \ge 2$

Is this correct? If it is not, what are my mistakes? And if it is, is there a less complicated proof (maybe without induction)?

By the binomial theorem $$\left(1+\tfrac{1}{n}\right)^n=1+n\cdot\frac{1}{n}+\tfrac{1}{2!}\left(1-\tfrac{1}{n}\right)+\tfrac{1}{3!}\left(1-\tfrac{1}{n}\right)\left(1-\tfrac{2}{n}\right)+...+\tfrac{1}{n!}\left(1-\tfrac{1}{n}\right)...\left(1-\tfrac{n-1}{n}\right)<$$ $$<2+\frac{1}{2!}+\frac{1}{3!}+...+\frac{1}{n!}.$$ I used $$\binom{n}{k}=\frac{1}{k!}\cdot n(n-1)...(n-k+1).$$