Why can we use mathematical induction to prove that $2^n \ge n^2$ for $ n \ge 5$
Normally, the proof via mathematical induction starts with $n =1$. Why does it still hold, when we start with other numbers?
Asked
Active
Viewed 99 times
1
-
Because of the "definition" of induction: we may start at any $n_0$. This is called the base $P(0)$ in the wikipedia article. – Dietrich Burde Oct 11 '17 at 18:47
-
1If you knock down the fifth domino instead of the first domino, all the other dominoes still fall down. – Neal Oct 11 '17 at 18:49
-
Please make the question body self-contained (add the question from the title to the body). – Mårten W Oct 11 '17 at 18:49
3 Answers
1
If you prefer, you can think of induction in terms of proof by contradiction. For your example, assume there are $n\geq 5$ such that $2^n<n^2$. In that case, there is a smallest such $n$. Call that $k$.
The definition of $n$ means $k\geq5$, and the base case establishes that $k\neq5$.
Therefore, we know, by definition of $k$, that $2^{k-1}\geq (k-1)^2$. From this we get $$ 2^k=2\cdot 2^{k-1}\geq 2(k-1)^2=2k^2-4k+1=k^2+k(k-4)+1\geq k^2 $$ and we have our contradiction (the last inequality uses that all terms are positive).
There is nothing in this proof that hinges on exactly where the base case occurs. Just that we establish the base case and also pick $k$ to be the smallest value where the proposition is untrue means we know it's true for $k-1$, and we have our induction hypothesis.
Arthur
- 199,419
0
multiplying $$2^k\geq k^2$$ by $2$ we get $$2^{k+1}\geq 2k^2$$ now you have to prove that $$2k^2\geq (k+1)^2$$
Dr. Sonnhard Graubner
- 95,283
-
4It seems to me the point of the question is not to get a proof, but rather to understand why an induction can start at a starting value other than $n=1$. I am afraid you post does not adress this. – quid Oct 11 '17 at 18:51