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.