Induction Proof


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

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.


 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


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.