Induction Proof – Problems with Solutions
Mathematical induction is a technique for proving a statement – a theorem, or a formula — that is asserted about every natural number. It is a mathematical proof technique used to prove a given statement about any well-ordered set. Most commonly, it is used to establish statements for the set of all natural numbers.
1 + 2 + 3 + 4 + ..… + n = {n(n + 1)}/2.
For all positive integers n.
We denote this mathematical statement by P(n). If n = 1, then we find that {1(1 + 1)}/2= 1.
Hence the above statement is true for n = 1.
Suppose n = 2. Then 1 + 2 = 3 and {2(2 + 1)}/2= 3. So we find that the statement is true for n = 2.
Thus, it is easy to verify that P(n) is true for n = 1, 2, 3 or 4. But it is impossible to verify that the above statement is true for all positive integers.
In math induction proof we will work on some examples using mathematical induction.
Mathematical Induction – Problems with Solutions (induction proof):
- 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.
- 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.
Information Source:
