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.
Questions with solutions to Proof by Mathematical Induction
1. Using the principle of mathematical induction, prove that
a + ar + ar^{2} + ....... + ar^{n – 1} = (ar^{n – 1})/(r - 1) for r > 1 and all n ∈ N.
Solution:
Let the given statement be P(n). Then,
P(n): a + ar + ar
^{2} + ….... +ar
^{n - 1} = {a(r
^{n} -1)}/(r - 1).
When n = 1, LHS = a and RHS = {a(r
^{1} - 1)}/(r - 1) = a
Therefore LHS = RHS.
Thus, P(1) is true.
Let P(k) be true. Then,
P(k): a + ar + ar
^{2} + …… + ar
^{k - 1} = {a(r
^{k} - 1)}/(r - 1)
Now, (a + ar + ar
^{2} + …... + ar
^{k - 1}) + ar
^{k} = {a(r
^{k} - 1)}/(r - 1) + ar
^{2}
....... [using(i)]
= a(r
^{k + 1} - 1)/(r - 1).
Therefore,
P(k + 1): a + ar + ar
^{2} + …….. +ar
^{k - 1} + ar
^{k} = {a(r
^{k + 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
2. Let a and b be arbitrary real numbers. Using the principle of mathematical induction, prove that
(ab)^{n} = a^{n}b^{n} for all n ∈ N.
Solution:
Let the given statement be P(n). Then,
P(n): (ab)
^{n} = a
^{n}b
^{n}.
When = 1, LHS = (ab)
^{1} = ab and RHS = a
^{1}b
^{1} = 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} = a
^{k}b
^{k}.
Now, (ab)
^{k + 1} = (ab)
^{k} (ab)
= (a
^{k}b
^{k})(ab) [using (i)]
= (a
^{k} ∙ a)(b
^{k} ∙ b) [by commutativity and associativity of multiplication on real numbers]
= (a
^{k + 1} ∙ b
^{k + 1} ).
Therefore P(k+1): (ab)
^{k + 1} = ((a
^{k + 1} ∙ b
^{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.
More examples to Proof by Mathematical Induction
3. Using the principle of mathematical induction, prove that (x^{n} - y^{n}) is divisible by (x - y)for all n ∈ N.
Solution:
Let the given statement be P(n). Then,
P(n): (x
^{n} - y
^{n}) is divisible by (x - y).
When n = 1, the given statement becomes: (x
^{1} - y
^{1}) is divisible by
(x - y), which is clearly true.
Therefore P(1) is true.
Let p(k) be true. Then,
P(k): x
^{k} - y
^{k} is divisible by (x-y).
Now, x
^{k + 1} - y
^{k + 1} = x
^{k + 1} - x
^{k}y - y
^{k + 1}
[on adding and subtracting x)
^{k}y]
= x
^{k}(x - y) + y(x
^{k} - y
^{k}), which is divisible by (x - y) [using (i)]
⇒ P(k + 1): x
^{k + 1} - y
^{k + 1}is 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.
4. Using the principle of mathematical induction, prove that (10^{2n - 1} + 1) is divisible by 11 for all n ∈ N.
Solution:
Let P (n): (10
^{2n – 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): (10
^{2k - 1} + 1) is divisible by 11
⇒ (10
^{2k - 1} + 1) = 11 m for some natural number m.
Now, {10
^{2(k - 1) - 1} + 1} = (10
^{2k + 1} + 1) = {10
^{2} ∙ 10
^{(2k - 1)}+ 1}
= 100 × {10
^{2k - 1}+ 1 } - 99
= (100 × 11m) - 99
= 11 × (100m - 9), which is divisible by 11
⇒ P (k + 1): {10
^{2(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.
5. Using the principle if mathematical induction, prove that (7n – 3n) is divisible by 4 for all n ∈ N.
Solution:
Let P(n) : (7
^{n} – 3
^{n}) 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): (7
^{k} - 3
^{k}) is divisible by 4.
⇒ (7
^{k} - 3
^{k}) = 4m for some natural number m.
Now, {7
^{(k + 1)} - 3 (k + 1)} = 7
^{(k + 1)} – 7 ∙ 3
^{k} + 7 ∙ 3
^{k} - 3
^{ (k + 1) } (on subtracting and adding 7 ∙ 3k)
= 7(7
^{k} - 3
^{k}) + 3
^{k} (7 - 3)
= (7 × 4m) + 4 ∙ 3k
= 4(7m + 3
^{k}), 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
6. Using the principle if mathematical induction, prove that
(2 ∙ 7^{n} + 3 ∙ 5^{n} - 5) is divisible by 24 for all n ∈ N.
Solution:
Let P(n): (2 ∙ 7
^{n} + 3 ∙ 5
^{n} - 5) is divisible by 24.
For n = 1, the given expression becomes (2 ∙ 7
^{1} + 3 ∙ 5
^{1} - 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 ∙ 7
^{n} + 3 ∙ 5
^{n} - 5) is divisible by 24.
⇒ (2 ∙ 7
^{n} + 3 ∙ 5
^{n} - 5) = 24m, for m = N
Now, (2 ∙ 7
^{n} + 3 ∙ 5
^{n} - 5)
= (2 ∙ 7
^{k} ∙ 7 + 3 ∙ 5
^{k} ∙ 5 - 5)
= 7(2 ∙ 7
^{k } + 3 ∙ 5
^{k} - 5) = 6 ∙ 5
^{k} + 30
= (7 × 24m) - 6(5
^{k} - 5)
= (24 × 7m) - 6 × 4p, where (5
^{k} - 5) = 5(5
^{k - 1} - 1) = 4p
[Since (5
^{k - 1} - 1) is divisible by (5 - 1)]
= 24 × (7m - p)
= 24r, where r = (7m - p) ∈ N
⇒ P (k + 1): (2 ∙ 7
^{k} + 13 ∙ 5
^{k} + 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 ∈ 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
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.