Proof by Mathematical Induction


Using the principle to proof by mathematical induction we need to follow the techniques and steps exactly as shown.

We note that a prove by mathematical induction consists of three steps.

• Step 1. (Basis) Show that P(n₀) is true.

• Step 2. (Inductive hypothesis). Write the inductive hypothesis: Let k be an integer such that k ≥ n₀ and P(k) be true.

• Step 3. (Inductive step). Show that P(k + 1) is true. 

In mathematical induction we can prove an equation statement where infinite number of natural numbers exists but we don’t have to prove it for every separate numbers. 

We use only two steps to prove it namely base step and inductive step to prove the whole statement for all the cases. Practically it’s not possible to prove a mathematical statement or formula or equation for all the natural numbers but we can generalize the statement by proving with induction method. As if the statement is true for P (k), it will be true for P (k+1), so if it is true for P (1) then it can be proved for P (1+1) or P (2) similarly for P (3), P (4) and so on up to n natural numbers.

In Proof by mathematical induction the first principle is if the base step and inductive step are proved then P (n) is true for all natural numbers. In inductive step we need to assume P (k) is true and this assumption is called as induction hypothesis. By using this assumption we prove P (k+1) is true. While proving for the base case we can take P (0) or P (1).

Proof by mathematical induction uses deductive reasoning not inductive reasoning. An example of deductive reasoning: All trees have leaves. Palm is a tree. Therefore Palm must have leaves.

When the proof by mathematical induction for a set of countable inductive set is true for all numbers it is called as Weak Induction. This is normally used for natural numbers. It is simplest form of mathematical induction where the base step and inductive step are used to prove a set.

In Reverse Induction assumption is made to prove a negative step from inductive step. If P (k+1) is assumed to be true as induction hypothesis we prove P (k) is true. These steps are reverse to weak induction and this is also applicable for countable sets. From this it can be proved that the set is true for all numbers ≤ n and so the proof ends for 0 or 1 which is base step for weak induction.

Strong Induction is similar to weak induction. But for strong induction in inductive step we assume all P (1), P (2), P (3) …... P (k) are true to prove P (k+1) is true. When weak induction fails to prove a statement for all the cases we use strong induction. If a statement is true for weak induction, it is obvious that it is true for weak induction also.


Questions with solutions to Proof by Mathematical Induction

1. Let a and b be arbitrary real numbers. Using the principle of mathematical induction, prove that
(ab)n = anbn for all n ∈ N.

Solution:

Let the given statement be P(n). Then,

P(n): (ab)n = anbn.

When = 1, LHS = (ab)1 = ab and RHS = a1b1 = ab

Therefore LHS = RHS.

Thus, the given statement is true for n = 1, i.e., P(1) is true.

Let P(k) be true. Then,

P(k): (ab)k = akbk.

Now, (ab)k + 1 = (ab)k (ab)

                             = (akbk)(ab) [using (i)]

                              = (ak ∙ a)(bk ∙ b) [by commutativity and associativity of multiplication on real numbers]

                              = (ak + 1 ∙ bk + 1 ).

Therefore P(k+1): (ab)k + 1 = ((ak + 1 ∙ bk + 1)

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.



More examples to Proof by Mathematical Induction

2. Using the principle of mathematical induction, prove that (xn - yn) is divisible by (x - y)for all n ∈ N.

Solution:

Let the given statement be P(n). Then,

P(n): (xn - yn) is divisible by (x - y).

When n = 1, the given statement becomes: (x1 - y1) is divisible by (x - y), which is clearly true.

Therefore P(1) is true.

Let p(k) be true. Then,

P(k): xk - yk is divisible by (x-y).

Now, xk + 1 - yk + 1 = xk + 1 - xky - yk + 1

                              [on adding and subtracting x)ky]

= xk(x - y) + y(xk - yk), which is divisible by (x - y) [using (i)]

⇒ P(k + 1): xk + 1 - yk + 1is divisible by (x - y)

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the Principal of Mathematical Induction, P(n) is true for all n ∈ N.


3. Using the principle of mathematical induction, prove that
a + ar + ar2 + ....... + arn – 1 = (arn – 1)/(r - 1) for r > 1 and all n ∈ N.

Solution:

Let the given statement be P(n). Then, 

P(n): a + ar + ar2 + ….... +arn - 1 = {a(rn -1)}/(r - 1). 

When n = 1, LHS = a and RHS = {a(r1 - 1)}/(r - 1) = a 

Therefore LHS = RHS. 

Thus, P(1) is true. 

Let P(k) be true. Then, 

P(k): a + ar + ar2 + …… + ark - 1 = {a(rk - 1)}/(r - 1) 

Now, (a + ar + ar2 + …... + ark - 1) + ark = {a(rk - 1)}/(r - 1) + ar2                                                                      ....... [using(i)] 
                             = a(rk + 1 - 1)/(r - 1). 

Therefore,
P(k + 1): a + ar + ar2 + …….. +ark - 1 + ark = {a(rk + 1 - 1)}/(r - 1) 

⇒ P(k + 1)is true, whenever P(k) is true. 

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true. 

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N. 



Proof by Mathematical Induction

4. Let a and b be arbitrary real numbers. Using the principle of mathematical induction, prove that 
(ab)n = anbn for all n ∈ N.

Solution:

Let the given statement be P(n). Then, 

P(n): (ab)n = anbn

When = 1, LHS = (ab)1 = ab and RHS = a1b1 = ab

Therefore LHS = RHS. 

Thus, the given statement is true for n = 1, i.e., P(1) is true. 

Let P(k) be true. Then, 

P(k): (ab)k = akbk

Now, (ab)k + 1 = (ab)k (ab) 

                      = (akbk)(ab) [using (i)] 

                      = (ak ∙ a)(bk ∙ b) [by commutativity and associativity of multiplication on real numbers] 

                      = (ak + 1 ∙ bk + 1 ). 

Therefore P(k+1): (ab)k + 1 = ((ak + 1 ∙ bk + 1

⇒ P(k + 1) is true, whenever P(k) is true. 

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true. 

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.



More examples to Proof by Mathematical Induction

5. Using the principle of mathematical induction, prove that (xn - yn) is divisible by (x - y)for all n ∈ N.

Solution:

Let the given statement be P(n). Then, 

P(n): (xn - yn) is divisible by (x - y). 

When n = 1, the given statement becomes: (x1 - y1) is divisible by (x - y), which is clearly true. 

Therefore P(1) is true. 

Let p(k) be true. Then, 

P(k): xk - yk is divisible by (x-y). 

Now, xk + 1 - yk + 1 = xk + 1 - xky - yk + 1

                              [on adding and subtracting x)ky] 

= xk(x - y) + y(xk - yk), which is divisible by (x - y) [using (i)] 

⇒ P(k + 1): xk + 1 - yk + 1is divisible by (x - y) 

⇒ P(k + 1) is true, whenever P(k) is true. 

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true. 

Hence, by the Principal of Mathematical Induction, P(n) is true for all n ∈ N. 


6. Using the principle of mathematical induction, prove that (102n - 1 + 1) is divisible by 11 for all n ∈ N.

Solution: 

Let P (n): (102n – 1 + 1) is divisible by 11. 

For n=1, the given expression becomes {10(2 × 1 - 1) + 1} = 11, which is divisible by 11. 

So, the given statement is true for n = 1, i.e., P (1) is true. 

Let P(k) be true. Then, 

P(k): (102k - 1 + 1) is divisible by 11

⇒ (102k - 1 + 1) = 11 m for some natural number m. 

Now, {102(k - 1) - 1 + 1} = (102k + 1 + 1) = {102 ∙ 10(2k - 1)+ 1} 

                              = 100 × {102k - 1+ 1 } - 99

                              = (100 × 11m) - 99

                              = 11 × (100m - 9), which is divisible by 11

⇒ P (k + 1): {102(k + 1) - 1 + 1} is divisible by 11

⇒ P (k + 1) is true, whenever P(k) is true. 

Thus, P (1) is true and P(k + 1) is true , whenever P(k) is true. 

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.


7. Using the principle if mathematical induction, prove that (7n – 3n) is divisible by 4 for all n ∈ N.

Solution: 

Let P(n) : (7n – 3n) is divisible by 4. 

For n = 1, the given expression becomes (7 1 - 3 1) = 4, which is divisible by 4. 

So, the given statement is true for n = 1, i.e., P(1) is true. 

Let P(k) be true. Then, 

P(k): (7k - 3k) is divisible by 4. 

⇒ (7k - 3k) = 4m for some natural number m. 

Now, {7(k + 1) - 3 (k + 1)} = 7(k + 1) – 7 ∙ 3k + 7 ∙ 3k - 3 (k + 1) 
                                           (on subtracting and adding 7 ∙ 3k) 

                              = 7(7k - 3k) + 3 k (7 - 3) 

                              = (7 × 4m) + 4 ∙ 3k

                              = 4(7m + 3k), which is clearly divisible by 4. 

∴ P(k + 1): {7(k + 1) - 3 (k + 1)} is divisible by 4. 

⇒ P(k + 1) is true, whenever P(k) is true. 

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N. 



Solved examples to Proof by Mathematical Induction

8. Using the principle if mathematical induction, prove that
(2 ∙ 7n + 3 ∙ 5n - 5) is divisible by 24 for all n ∈ N.

Solution: 

Let P(n): (2 ∙ 7n + 3 ∙ 5n - 5) is divisible by 24. 

For n = 1, the given expression becomes (2 ∙ 71 + 3 ∙ 51 - 5) = 24, which is clearly divisible by 24. 

So, the given statement is true for n = 1, i.e., P(1) is true. 

Let P(k) be true. Then, 

P(k): (2 ∙ 7n + 3 ∙ 5n - 5) is divisible by 24. 

⇒ (2 ∙ 7n + 3 ∙ 5n - 5) = 24m, for m = N

Now, (2 ∙ 7k + 1 + 3 ∙ 5k + 1 - 5) 

                       = (2 ∙ 7k ∙ 7 + 3 ∙ 5k ∙ 5 - 5) 

                       = 7(2 ∙ 7+ 3 ∙ 5k - 5) - 6 ∙ 5k + 30

                       = (7 × 24m) - 6(5k - 5) 

                       = (24 × 7m) - 6 × 4p, where (5k - 5) = 5(5k - 1 - 1) = 4p
[Since (5k - 1 - 1) is divisible by (5 - 1)] 

                       = 24 × (7m - p) 

                       = 24r, where r = (7m - p) ∈ N 

⇒ P (k + 1): (2 ∙ 7k + 1 + 3 ∙ 5k + 1 - 5) is divisible by 24.

⇒ P(k + 1) is true, whenever P(k) is true. 

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true. 

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ 

 Mathematical Induction

Mathematical Induction

Problems on Principle of Mathematical Induction

Proof by Mathematical Induction

Induction Proof




11 and 12 Grade Math 

From Proof by Mathematical Induction to HOME PAGE


New! Comments

Have your say about what you just read! Leave me a comment in the box below. Ask a Question or Answer a Question.



Didn't find what you were looking for? Or want to know more information about Math Only Math. Use this Google Search to find what you need.



Share this page: What’s this?

Recent Articles

  1. Multiplication of a Number by a 3-Digit Number |3-Digit Multiplication

    Mar 28, 24 06:33 PM

    Multiplying by 3-Digit Number
    In multiplication of a number by a 3-digit number are explained here step by step. Consider the following examples on multiplication of a number by a 3-digit number: 1. Find the product of 36 × 137

    Read More

  2. Multiply a Number by a 2-Digit Number | Multiplying 2-Digit by 2-Digit

    Mar 27, 24 05:21 PM

    Multiply 2-Digit Numbers by a 2-Digit Numbers
    How to multiply a number by a 2-digit number? We shall revise here to multiply 2-digit and 3-digit numbers by a 2-digit number (multiplier) as well as learn another procedure for the multiplication of…

    Read More

  3. Multiplication by 1-digit Number | Multiplying 1-Digit by 4-Digit

    Mar 26, 24 04:14 PM

    Multiplication by 1-digit Number
    How to Multiply by a 1-Digit Number We will learn how to multiply any number by a one-digit number. Multiply 2154 and 4. Solution: Step I: Arrange the numbers vertically. Step II: First multiply the d…

    Read More

  4. Multiplying 3-Digit Number by 1-Digit Number | Three-Digit Multiplicat

    Mar 25, 24 05:36 PM

    Multiplying 3-Digit Number by 1-Digit Number
    Here we will learn multiplying 3-digit number by 1-digit number. In two different ways we will learn to multiply a two-digit number by a one-digit number. 1. Multiply 201 by 3 Step I: Arrange the numb…

    Read More

  5. Multiplying 2-Digit Number by 1-Digit Number | Multiply Two-Digit Numb

    Mar 25, 24 04:18 PM

    Multiplying 2-Digit Number by 1-Digit Number
    Here we will learn multiplying 2-digit number by 1-digit number. In two different ways we will learn to multiply a two-digit number by a one-digit number. Examples of multiplying 2-digit number by

    Read More