## Tag Archives: mathematical induction

### A variant of mathematical induction — for IITJEE Math and RMO Math

As is generally known, the principal of mathematical induction is used in the following form: We are supposed to prove a proposition for natural numbers. We check whether it is true for the natural number 1, and then assume it to be true for another natural number m. Then, we got to  show  that the proposition also holds for the natural number $m+1$.

Here is a variation of the principle of mathematical induction:

Assume the proposition to be true for a first natural number k (you have to  find the particular value of k under the conditions of the given problem). Then, assume it to be true for the natural number m. Finally, we gotta show that the proposition is true for the natural number $m+1$.

Example. Show that $n! > 3^{n}$ if n is large enough.

Solution. How large is large? We have to find that “first” value for which the above proposition is true. We actually need to check whether the inequality holds for $n=1, 2, 3, 4, 5, 6, 7, 8 \ldots$

So, if we tabulate the values of LHS and RHS, we find that the first natural number for which this holds is $n=7$..

Hence, the proposition $n! > 3^{n}$ is true for n=7.

Assume the proposition to be true for some natural number m where $m > 7$.

That is, $m! > 3^{m}$ holds true. Multiplying both sides by $m+1$, we get $(m+1)m! > 3^{m} (m+1)$ that is, $(m+1)! > m \times 3^{m} + 3^{m}$, but $m>7$. Hence, we get $(m+1)! > 7 \times 3^{m} + 3^{m}$ which equals $8 \times 3^{m}$.

Hence, obviously, $(m+1)! > 3^{m} \times 3$ that is, $(m+1)! > 3^{m+1}$. That is, the proposition holds for all natural numbers. Thus, the proof.

More later,

Nalin Pithwa