I’m stuck on an induction proof and need some help on proofs in general

Question

The problem is: show that $n! \geq 2^{n-1}$ given that $n\geq 1$.

So I started by checking the smallest case $p(1)$ and it evaluated to be true and then I assumed that $p(k)$ for the above given equation was true.

Following those two steps I plugged in $(n+1)$ to prove for the above claim $(n+1)! \geq 2^{(n+1)-1}$. I’m not entirely sure where to go from here to prove the equation.

Also in addition to all of this, I was wondering if anyone could provide me with resources to really lock down proofs and practice? Thanks for any and all help in advance

Answer 1

We consider $n\geq 1$. Then, using the induction hypothesis $n!\geq 2^{n-1}$, we obtain

$$(n+1)!=(n+1)\times n! \geq (n+1)\times 2^{n-1}\geq 2\times 2^{n-1}=2^n$$

(NB: In your post, please restrain from complaining about personnal issues. We are interested in your maths related questions, and that is all. If you want to make a reference request, then just ask for it without talking down about your teacher.)

Answer 2

$n!\ge 2^{n-1}$ so

$2*n! \ge 2*2^{n-1}$

And $n+1\ge 2$

So $(n+1)n!\ge 2*n!\ge 2*2^{n-1} $.

Answer 3

For an inductive proof of an inequality $A(n)\geq B(n)$ it is often useful to first re-write it as $A(n)/B(n)\geq 1$ (when sure that $B(n)>0$ for all $n$), and re-write the statement $A(n+1)\geq B(n+1)$ as $A(n+1)/B(n+1)\geq 1.$

Second, write out the relationship between $A(n+1)$ and $A(n),$ and the relationship between $B(n)$ and $B(n+1).$

Third, "plug in" the statements of these relationships into the statement $A(n+1)/B(n+1)\geq 1.$ (Some useful simplification may occur at this step.)

Fourth, see whether this new version of the statement $A(n+1)\geq B(n+1)$ is implied by the statement $A)n)/B(n)\geq 1.$ The allowable range of $n$ will matter here.

In this Q, $A(n)=n!$ and $B(n)=2^{n-1}.$ First step: $A(n)\geq B(n)\iff \frac {A(n)}{B(n)}\geq 1$ and $A(n+1)\geq B(n+1)\iff \frac {A(n+1)}{B(n+1)}\geq 1.$

Second step: $A(n+1)=n!(n+1)=A(n)\cdot (n+1)$ and $B(n+1)=2^n=2^{n-1}\cdot 2=B(n)\cdot 2.$

Third, "plug in": $$\frac {A(n+1)}{B(n+1)}=\frac {A(n)\cdot (n+1)}{B(n+1)}=\frac {A(n)(n+1)}{B(n)\cdot 2}=\frac {A(n)}{B(n)}\cdot \frac {n+1}{2}.$$ The last expression above is a re-arrangement of the 2nd-last. It is done because it "isolates" the expression $\frac {A(n)}{B(n)},$ and we are interested in the consequences of $\frac {A(n)}{B(n)}\geq 1.$

Fourth (where we actually prove something important). Does $\left(\;\frac {A(n)}{B(n)}\geq 1 \text { and } n\geq 1\right) $ imply $\frac {A(n)}{B(n)}\cdot \frac {n+1}{2}\geq 1\;$?.... If the number $\frac {A(n)}{B(n)}$ is at least $1$ and if the number $\frac {n+1}{2}$ is at least $1$ then their product is at least $1$.

NOTES. The figure of speech "plug in" simply means that if we have a known equality , as C=D, than wherever C appears we can replace it with D... Since we have a hypothesis "If $A(n)/B(n)\geq 1.....$" we would prefer that other terms, like $A(n+1)$ and $B(n+1)$ be replaced by things involving $A(n)$ and $B(n).$

In many problems it is more useful to re-write $A(n)\geq B(n)$ as $A(n)-B(n)\geq 0$ rather than as $A(n)/B(n).$ There is no "formula" to tell you in advance which one may be better.