Mathematical induction I know there is one specific way of proving it which is say for instance the example:

Method 1

Prove using mathematical induction that: $$2^n>n+4, n\ge 3$$

I will skip straight to the induction step: We assume $P(k)$ is true and hence we have: $$2^k>k+4, k\ge 3$$ Now $P(k+1)$ states that: $$2^{k+1}=2\times2^{k}, k\ge 3$$ $$2^{k+1}=2\times2^{k}> 2(k+4)=2k+8>k+8>k+5=(k+1)+4 , k\ge 3$$ $$2^{k+1}>(k+1)+4$$

Alternative Method:

Going straight to the induction step:

$$2^k>k+4, k\ge 3$$ $$2^{k+1}>(k+1)+4$$ $$2\times 2^k-k-5>0$$ $$2\times 2^k-k-5>2(k+4)-k-5>0$$ $$2\times 2^k-k-5>k+3>0$$

But this is true as $k\ge 3$.

My question is, are both methods valid and is this valid for any mathematical induction inequality problems?

  • $\begingroup$ Your alternative method breaks down when you go from $2\times 2^k-k-5\gt 0$ to $2\times 2^k-k-5\gt 2(k+4)-k-5\gt 0$. Note that $x\gt 0$ and $x\gt y$ doesn't imply $x\gt y\gt 0$ $\endgroup$ – learner Mar 20 at 16:06
  • $\begingroup$ Why on earth would the alternative method be valid? Why would you assume $2^{k+1} > 2^k + 1$... if that is what you were assuming. Also it is very unclear what your "Methods" are. These are specific to this question about an exponential value's inequality to a linear value. How what you apply this to any other question, say a question about the number of divisors, or number of combinations, or paths? $\endgroup$ – fleablood Mar 20 at 16:11
  • $\begingroup$ Learner But we are saying $y>0$ and therefore $x>y $ implies $x>y>0.$ $\endgroup$ – Aurora Borealis Mar 20 at 17:06

Basically you did the same thing twice with a different form. Anyway I don't like that you write $$2^{k+1}>(k+1)+4$$ since this is to be proved. It is better to write $$2^{k+1}-(k+1)-4=...$$

and estimate that expression. And after all, if you write first one it is better to write it like this:


  • $\begingroup$ Could you elaborate further on this? What do you mean it is better to write it in that form? i have already did and made approximations acoordignly from there? $\endgroup$ – Aurora Borealis Mar 20 at 17:03

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.