Table of Contents

Last modified on March 8th, 2024

Mathematical induction (or weak mathematical induction) is a method to prove or establish mathematical statements, propositions, theorems, or formulas for all natural numbers ‘n ≥1.’

It involves two steps:

**Base Step**: It proves whether a statement is true for the initial value (n), usually the smallest natural number in consideration.**Inductive Step**: It proves that when the statement is true for the natural number (n) (or n^{th}iteration), it must also be true for the next number (n + 1) or (n+1)^{th}iteration.

Here, we will discuss this method with an example.

Let us consider the statement:

For all natural numbers up to n, 1^{2} + 2^{2} + 3^{2} + … + n^{2} = ${\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}}$

For the initial value, n = 1, 1^{2} = 1 = ${\dfrac{1\left( 1+1\right) \left( 2\times 1+1\right) }{6}}$, which is true.

Assuming the statement is also true for n = k, we get

1^{2} + 2^{2} + … + k^{2} = ${\dfrac{k\left( k+1\right) \left( 2k+1\right) }{6}}$

Here, we have to prove the given statement for n = k + 1,

1^{2} + 2^{2} + 3^{2} + … + (k + 1)^{2}

= 1^{2} + 2^{2} + 3^{2} + … + k^{2} + (k + 1)^{2}

= {1^{2} + 2^{2} + 3^{2} + … + k^{2}} + (k + 1)^{2}

= ${\dfrac{k\left( k+1\right) \left( 2k+1\right) }{6}}$ + ${\left( k+1\right) ^{2}}$

= ${\dfrac{k\left( k+1\right) \left( 2k+1\right) +6\left( k+1\right) ^{2}}{6}}$

= ${\dfrac{\left( k+1\right) \left[ k\left( 2k+1\right) +6\left( k+1\right) \right] }{6}}$

= ${\dfrac{\left( k+1\right) \left( 2k^{2}+7k+6\right) }{6}}$

= ${\dfrac{\left( k+1\right) \left( k+2\right) \left( 2k+3\right) }{6}}$

= ${\dfrac{\left( k+1\right) \left[ \left( k+1\right) +1\right] \left[ 2\left( k+1\right) +1\right] }{6}}$, which proves that the given statement is true for n = k + 1.

Thus, 1^{2} + 2^{2} + 3^{2} + … + n^{2} = ${\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}}$, is true for all natural numbers n.

Hence, the method of mathematical induction proves the given statement: For all natural numbers up to n, 1^{2} + 2^{2} + 3^{2} + … + n^{2} = ${\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}}$

**Using Mathematical Induction, prove the given statement: For any natural number n, 2 ^{2n} – 1 is divisible by 3.**

Solution:

Considering n = 1, we get,

2^{2(1)} – 1 = 2^{2} – 1 = 4 – 1 = 3, divisible by 3

Thus, the given statement is true for n = 1.

Assuming n = k, the statement 2^{2k} – 1 is divisible by 3

It means 2^{2k} – 1 = 3p, where p is a natural number.

Now, considering n = k + 1, we get

2^{2(k + 1)} – 1

= 2^{2k + 2} – 1

= (2^{2k} × 2^{2}) – 1

= 4(2^{2k}) – 1

= (2^{2k} – 1) + 3(2^{2k})

= 3p + 3(2^{2k})

=3(p + 2^{2k}), divisible by 3, which proves that the given statement is true for n = k + 1

Thus, 2^{2n} – 1 is divisible by 3 for any natural number ‘n.’

**Prove that (xy) ^{n} = x^{n}y^{n} is true for every natural number n using mathematical induction.**

Solution:

Considering n = 1, we get the given statement (xy)^{1} = xy = x^{1}y^{1}, true

Assuming n = k, the statement (xy)^{k} = x^{k}y^{k} is true.

Now, considering n = k + 1, we get

(xy)^{k + 1}

= (xy)(xy)^{k}

= (xy)(x^{k}y^{k})

= (x^{k}x)(y^{k}y)

= x^{k + 1}y^{k + 1}, which proves that the given statement is true for n = k + 1

Thus, (xy)^{n} = x^{n}y^{n} is true for every natural number ‘n.’

**Use induction to prove that 1 + 2 + 3 + … + n = ${\dfrac{n\left( n+1\right) }{2}}$, where n is any natural number.**

Solution:

Considering n = 1, we get the statement 1 = 1, which is true.

Assuming n = k, the statement can be written as 1 + 2 + 3 + … + k = ${\dfrac{k\left( k+1\right) }{2}}$ is true.

Now, considering n = k + 1, we get

1 + 2 + 3 + … + (k + 1)

= 1 + 2 + 3 + … + k + (k + 1)

= ${\dfrac{k\left( k+1\right) }{2}+\left( k+1\right)}$

= ${\dfrac{k\left( k+1\right) +2\left( k+1\right) }{2}}$

= ${\dfrac{\left( k+1\right) \left( k+2\right) }{2}}$

= ${\dfrac{\left( k+1\right) \left[ \left( k+1\right) +1\right] }{2}}$, which proves that the given statement is true for n = k + 1

Thus, 1 + 2 + 3 + … + n = ${\dfrac{n\left( n+1\right) }{2}}$, where n is any natural number.

**More Resources**

Last modified on March 8th, 2024