Induction Proof

In math induction proof we will work on some examples using mathematical induction.

Induction proof is a mathematical method of proving a set of formula or theory or series of natural numbers. Induction proof is used from the theory of mathematical induction which is similar to the incident of fall of dominoes. When we push a domino in a set of dominoes the falling of first domino leads to the falling of other dominoes. So if there is a set of infinite dominoes then a falling effect of single domino will lead to the falling of other dominoes one by one. Now to prove this incident we can say the first domino falls to second and the second will fall to third and this way others will fall. Similarly in induction proof for infinite series of n numbers set where P (n) is the set property, we do not need to prove the property for all natural numbers. We prove it for two instances. First is for P (0) or P (1) and this step is called base step. In the second step we need to assume first that the property P (k) is true which is called induction hypothesis. By using inductive hypothesis we need to prove the P (k+1) is true and this step is called inductive step. This is how in induction proof for property P (n), we need to prove it for P (0) or P (1) and P (k+1) and then it can be stated that the property statement is true or holds for all the natural numbers.

Now we will try to understand induction proof from an example. First we take a property of sum of n natural numbers.

1 + 2 + 3 + ……. + n = n(n+1)2

The above set of natural numbers is property P (n) which is simply a formula of sum of n natural numbers. By using induction proof technique we need to prove that this formula holds true for all natural numbers. As stated before the first step is base step P (1).

For P (1), 

LHS = 1

RHS = 1(1+1)2 = 1.

So, LHS = RHS.

It is proved that P (1) is true.

Now in second step by using induction hypothesis of mathematical induction we assume P (k) is true.

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

We need to prove P(k + 1) is true by using P (k) true.

For P(k + 1),

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

       = k(k+1)2 + (k+1) ………by using induction hypothesis

       = (k+1)(k+2)2

       = (k+1)((k+1)+12 = RHS for P(k + 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. 

Mathematical Induction - Problems with Solutions (induction proof):

1. Using the principle of mathematical induction, prove that n(n + 1)(n + 5) is a multiple of 3 for all n ∈ N. 

Solution: 

Let P(n): n(n + 1)(n + 5) is a multiple of 3. 

For n = 1, the given expression becomes (1 × 2 × 6) = 12, which is a multiple of 3. 

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

Let P(k) be true. Then, 

P(k): k(k + 1)(k + 5) is a multiple of 3

⇒ K(k + 1)(k + 5) = 3m for some natural number m, ... (i) 

Now, (k + 1l)(k + 2)(k + 6) = (k + 1)(k + 2)k + 6(k + 1)(k + 2) 

                             = k(k + 1)(k + 2) + 6(k + 1)(k + 2) 

                             = k(k + 1)(k + 5 – 3) + 6(k + 1)(k + 2) 

                             = k(k + 1)(k + 5) – 3k(k + 1) + 6(k + 1)(k + 2) 

                             = k(k + 1)(k + 5) + 3(k + 1)(k +4) [on simplification] 

                             = 3m + 3(k + 1 )(k + 4) [using (i)] 

                             = 3[m + (k + 1)(k + 4)], which is a multiple of 3

⇒ P(k + 1): (k + 1 )(k + 2)(k + 6) is a multiple of 3

⇒ 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. 



Induction Proof

2. Using the principle of mathematical induction, prove that (n² + n) is even for all n ∈ N.

Solution:

Let P(n): (n² + n) is even.

For n = 1, the given expression becomes (1² + 1) = 2, which is even.

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

Let P(k) be true. Then,

P(k): (k² + k) is even

⇒ (k² + k) = 2m for some natural number m. ... (i)

Now, (k + 1)² + (k + 1) = k² + 3k + 2

                             = (k² + k) + 2(k + 1)

                             = 2m + 2(k + 1) [using (i)]

                             = 2[m + (k + 1)], which is clearly even.

Therefore, P(k + 1): (k + 1)² + (k + 1) is even

⇒ 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.



Induction Proof

More Examples on math Induction Proof

3. Using the principle of mathematical induction, prove that

(1 + x)n ≥ (1 + nx)for all n ∈ N,where x > - 1.


Solution:

Let P(n): (1 + x) )n ≥ (1 + nx).

For n = 1, we have LHS = (1 + x) )1 = (1 + x),and

RHS = (1 + 1 ∙ x) = (1 + x).

Therefore LHS ≥ RHS is true.

Thus, P(1) is true.

Let P(k) is true. Then,

P(k): (1 + X)k ≥ (1 + kx). …….. (i)

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

                              ≥ (1 + kx)(1 + x) [using (i)]

                              =1 + (k + 1)x + kx2

                              ≥ 1 + (k + 1)x + x [Since kx2 ≥ 0]

Therefore P(k + 1): (1 + x)k + 1 ≥ 1 + (k + 1)x

⇒ 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.







Induction Proof

4. Using the principle of mathematical induction, prove that n < 2n for all n ∈ N.

Solution:

Let P(n): n <2n.

When n = 1, LHS = 1 and RHS = 21 = 2.

Clearly, 1 < 2.

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

Let P(1) be true. Then,

P(k): k < 2k.

Now, k < 2k ⇒ 2k < 2k + 1

                          ⇒ (k + k) < 2k + 1

                          ⇒ (k + 1) ≤ (k + k) < 2k + 1 [Since 1 ≤ k]

                          ⇒ (k + 1) < 2k + 1

Therefore P(k + 1): (k + 1) < 2k + 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.



Induction Proof

5. Using the principle of mathematical induction, prove that 

(1² + 2² + …... + n²) > n³/3 for all values of n ∈ N.
 


Solution:

Let P(n): (1² + 2² + ….. + n²) > n³/3. 

When = 1, LHS = 1² = 1 and RHS = 1³/3 = 1/3. 

Since 1 > 1/3, it follows that P(1) is true. 

Let P(k) be true. Then, 

P(k): (1² + 2² + ….. + k²) > k³/3 .... (i) 

Now, 1² + 2² + ..... + k² + (k + 1)² 

                          = {1² + 2² + ..... + k² + (k + 1)²} + (k + 1)²

                          > k³/3 + (k + 1)² [using (i)] 

                          = 1/3 ∙ (k³ + 3 + (k + 1)²) = 1/3 ∙ {k² + 3k² + 6k + 3} 

                          = 1/3[k³ + 1 + 3k(k + 1) + (3k + 2)]

                          = 1/3 ∙ [(k + 1)³ + (3k + 2)] 

                          > 1/3(k + 1)³

P(k + 1): 1² + 2² + ….... + k² + (k + 1) ² > 1/3 ∙ (k + 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. 



6. Using the principle of mathematical induction, prove that 

(2n + 7) < (n + 3)² for all values of n ∈ N. 


Solution: 

Let P(n): (2n + 7) < (n + 3)² 

When = 1, LHS = (2 × 1 + 7) = 9 and RHS = (1 + 3)² = 4² = 16. 

Clearly, 9 < 16. 

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

Let P(k) be true. Then

P(k): (2k + 7) < (k + 3)². ... (i) 

Now, 2(k + 1) + 7 = (2k + 7) + 2

                              < (k + 3)² + 2 = (k² + 6k + 11) [using(i)] 

                              < (k² + 8k + 16) = (k + 4)² = (k + 1 + 3)².

P(k + 1): 2(k + 1) + 7 < (k + 1 + 3)². 

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 Principle of Mathematical Induction, P(n) is true for all n ∈ N.


From the above examples it can be understood that induction proof can be divided into four parts.

1) The Set P (n) that we need to prove.

2) The base step P (1).

3) Induction Hypothesis or the assumption step for P (k).

4) Inductive step where P (k+1) is to be proved.

Induction proof is used to prove general structures such as trees termed as Structural Induction. This structural induction is used in computer science like recursion. Also for correctness proofs induction proof is used for programs in computer science.

 Mathematical Induction

Mathematical Induction

Problems on Principle of Mathematical Induction

Proof by Mathematical Induction

Induction Proof





11 and 12 Grade Math

From Induction Proof to HOME PAGE




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.



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.




Share this page: What’s this?

Recent Articles

  1. Multiplication of Decimal Numbers | Multiplying Decimals | Decimals

    May 03, 25 04:38 PM

    Multiplication of Decimal Numbers
    The rules of multiplying decimals are: (i) Take the two numbers as whole numbers (remove the decimal) and multiply. (ii) In the product, place the decimal point after leaving digits equal to the total…

    Read More

  2. Magic Square | Add upto 15 | Add upto 27 | Fibonacci Sequence | Videos

    May 03, 25 10:50 AM

    check the magic square
    In a magic square, every row, column and each of the diagonals add up to the same total. Here is a magic square. The numbers 1 to 9 are placed in the small squares in such a way that no number is repe

    Read More

  3. Division by 10 and 100 and 1000 |Division Process|Facts about Division

    May 03, 25 10:41 AM

    Divide 868 by 10
    Division by 10 and 100 and 1000 are explained here step by step. when we divide a number by 10, the digit at ones place of the given number becomes the remainder and the digits at the remaining places…

    Read More

  4. Multiplication by Ten, Hundred and Thousand |Multiply by 10, 100 &1000

    May 01, 25 11:57 PM

    Multiply by 10
    To multiply a number by 10, 100, or 1000 we need to count the number of zeroes in the multiplier and write the same number of zeroes to the right of the multiplicand. Rules for the multiplication by 1…

    Read More

  5. Adding and Subtracting Large Decimals | Examples | Worksheet | Answers

    May 01, 25 03:01 PM

    Here we will learn adding and subtracting large decimals. We have already learnt how to add and subtract smaller decimals. Now we will consider some examples involving larger decimals.

    Read More