Prove that $\forall n, n\geq 3$, $$ \sum_{i=1}^{n} \frac{2^i}{i} \leq n!+1 $$
By induction, I have that:
For $n=3$: $\displaystyle\sum_{i=1}^{3} \frac{2^i}{i} = 20/3 \leq 3!+1=7$
Suppose that the proposition is true for $n=k$. Then, for $n=k+1$
$$ \sum_{i=1}^{k+1} \frac{2^i}{i}=\sum_{i=1}^{n} \frac{2^i}{i}+\frac{2^{k+1}}{k+1} \leq k!+1+\frac{2^{k+1}}{k+1}=\frac{(k+1)!}{k+1}+1+ \frac{2^{k+1}}{k+1} $$
But I'm stuck here, I should get $\leq (k+1)!+1$
Assume its true for $n$ now we show for $n+1$:
$$\sum_{i=1}^{n+1}\frac{2^{i}}{i}=\sum_{i=1}^{n}\frac{2^{i}}{i}+\frac{2^{n+1}}{n+1}\le n!+1+\frac{2^{n+1}}{n+1}=n!+1+2\underbrace{\frac{2}{2}}_{\le1}\cdot\underbrace{\frac{2}{3}}_{\le1}\cdot...\cdot\underbrace{\frac{2}{n}}_{\le1}\cdot\underbrace{\frac{2}{n+1}}_{\le1}\cdot n!$$
$$\le n!+1+2n!=3n!+1\le(n+1)n!+1\le(n+1)!+1$$
Hint: $$\frac{2^{k+1}}{k+1}\leq \frac{k\cdot k!}{k+1}\leq k \cdot k!=(k+1)!-k!$$
It needs to be shown that $k! + 1 + \frac{2^{k+1}}{k+1} \le (k+1)! + 1$. To prove this, we can rearrange the terms.
The inequality holds
iff $(k+1)! - k! \ge \frac{2^{k+1}}{k+1}$
iff $k! (k+1-1) \ge \frac{2^{k+1}}{k+1}$
iff $k (k+1)! \ge 2^{k+1}$; that this last inequality holds can be proved in many ways.
The proof is complete. But if you want, we can now rewrite the proof by working backwards, by replacing $2^{k+1}$ in the given inequality by $\le k(k+1)!$, as follows:
$k! + 1 + \frac{2^{k+1}}{k+1} \le k!+1+ \frac{k(k+1)!}{k+1} \le k! + 1 + k k!= (k+1)!+1$. This reworking shows why sometimes the final proof might look cryptic but the steps of the proof were essentially derived by massaging the inequality you started out to prove.
