1
$\begingroup$

Im and quite new to induction and I don't know how use induction to prove inequalities such as $4^n>n^2$ and $2^n>n$ both for $n≥1$.

For $2^n>n$ first I proved a base case 2>1. Then I substituted n for k then tried $k+1$. $2 \cdot 2^k>2k>k+1$ but now I clueless as to what to do to finish the proof.

May someone please outline steps for how to use induction to prove an inequality. All help is appreciated.

$\endgroup$
1
  • 4
    $\begingroup$ Does this answer your question? Show by induction that 2^n > n for all integers n > 0 - found using an Approach0 search. This is for the specific inequality you tried to answer, but your question also seems to be asking about how to, in general, use induction to prove inequalities. However, I believe that's something which is too general to be able to answer here. $\endgroup$ Dec 10, 2022 at 21:03

2 Answers 2

0
$\begingroup$

Induction has 3 steps to follow:

  • You prove that something is true for the base
  • Then assume it's true for $n=m$
  • Show that it is also true for $n=m+1$.

Proving the third point should do it, as you have. You just have to present it nicely.

$\endgroup$
0
$\begingroup$

Prove that $2^n>n$ for $n>0$.

Base case ($n=1$):

$$2^1>1$$ which is correct

Induction step (for $n$): $$2^n>n$$

Proof (for $n+1$): $$2^{n+1}>n+1$$ $$2^{n+1}-n>1$$

Now we use the step $2^n>n$

So

$$2^{n+1}-n>2^{n+1}-2^n>1$$ $$2^{n+1}-2^n>1$$ $$2^n(2-1)>1$$ $$2^n>1$$

And that's true for every $n>0$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .