0
$\begingroup$

I'm trying to use the principle of mathematical induction to prove that $n!+n\ge2^n$ for all $n\ge1$. I know how to prove $n!\ge2^n$, but I can't figure out what to do with the extra $n$. For instance, if I try to factor $n+1$ out of the inductive case,

$(n+1)!+(n+1)\ge2^{n+1}$

$(n+1)(n!+1)\ge2\times2^n$

I'm left with $n!+1$, which I don't know what to do with. Similarly, if I try to use multiplicative telescopy, which I used to prove $n!\ge2^n$, I get stopped by the random $n$ that I can't multiply.

Any help would be greatly appreciated.

$\endgroup$
6
$\begingroup$

Clearly $n!+n>n!$, so if you already could show that $n!\ge 2^n$ (at least for $n\ge2$), then you need only check $n!+n\ge 2^n$ for the remaining case $n=1$.

P.S.: Sometimes showing a stronger result is easier.

$\endgroup$
0
3
$\begingroup$

Case $n = 1$: $$ 1! + 1 = 2 \ge 2^1 $$ Assuming $n$ holds, checking the statement for $n+1$: $$ \begin{align} (n+1)! + (n + 1) &= (n+1) n! + n + 1 \\ &= 2 \underbrace{(n! + n)}_{\ge 2^n} + (n-1) n! - n + 1 \\ &\ge 2^{n+1} + (n-1) n! - n + 1 \\ &\ge 2^{n+1} + \underbrace{(n-1)}_{\ge 0} \underbrace{(n! - 1)}_{\ge 0} \\ &\ge 2^{n+1} \end{align} $$ The statement is then true for $n+1$ as well and by principle of induction true for all $n \in \mathbb{N}$.

$\endgroup$
1
$\begingroup$

If you know from induction that $n! \geq 2^{n}$, and $n!+n \geq n!$ for every $n$, then you have the inequality you want, right?

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