1

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?

Aurora Borealis
  • 1,747
  • 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$ – learner Mar 20 '19 at 16:06
  • 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? – fleablood Mar 20 '19 at 16:11
  • Learner But we are saying $y>0$ and therefore $x>y $ implies $x>y>0.$ – Aurora Borealis Mar 20 '19 at 17:06

1 Answers1

1

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:

$$2^{k+1}\stackrel{?}{>}(k+1)+4$$

Mefitico
  • 1,845
nonuser
  • 90,026
  • 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? – Aurora Borealis Mar 20 '19 at 17:03