Top

Mathematical Induction

There are many theorems and statements in mathematics that are to be proved with the help of mathematical induction. This is a way of proving statements that those statements are true for all positive integers.

 Related Calculators Inductance Calculator Inductive Reactance Calculator Mathematical Equation Solver Acceleration Formula Calculator

Strategy of Mathematical Induction

The technique of mathematical induction is based on the principle that if a statement is true for integers - 1, 2, 3 and so on, up to k, then it is also true for all integers.

Following steps are to be followed while proving a statement by mathematical induction -

Let us consider that we are to prove that a statement P(n) holds for all positive integers.

Step 1:
Prove that P(1) holds, i.e. P(n) holds for n = 1.

Step 2:
Now, assume that the statement P does hold for some arbitrary integer (say k). i.e. P(k) holds.

Step 3:
Assuming P(k) is true, prove that the statement P holds for a successor of k, i.e. prove that the P (k + 1) holds.

Step 4:
If P (k + 1) holds, then it can be concluded that the statement holds for all integers. This means that P(n) is true.

Examples:

1) Using mathematical induction, prove that sum of n positive integers is $\frac{n}{2}$$(n+1). Solution: We have to prove that 1 + 2 + 3 + 4 + ...... + n = \frac{n}{2}$$(n+1)$

To prove that above statement is true for n = 1

First integer = 1 whose sum will also be 1.

Therefore, it holds for n = 1

Now, we can assume that given statement is true for k positive integers

Hence,
1 + 2 + 3 + 4 + ...... + k = $\frac{k}{2}$$(k+1) We shall prove the validity of statement for k + 1 Sum of k\ +\ 1 positive integers = 1 + 2 + 3 + 4 + .... + (k + 1) = (1 + 2 + 3 + 4 + .... + k) + (k + 1) We know the sum of k positive integers = \frac{k}{2}$$(k\ +\ 1)\ +\ (k\ +\ 1)$

= $\frac{k\ (k\ +\ 1)\ +\ 2(k\ +\ 1)}{2}$

=
$\frac{(k\ +\ 1)(k\ +\ 2)}{2}$

= $(k+1)$ $\frac{[(k\ +\ 1)\ +\ 1]}{2}$

This proves that statement holds for $n$ = $k\ +\ 1$.

Therefore, we conclude that the statement holds of all n positive integers.

 More topics in  Mathematical Induction Formula Principle of Mathematical Induction
*AP and SAT are registered trademarks of the College Board.