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).$$