ML Aggarwal Class 11 Maths Solutions Chapter 04 Principle of Mathematical Induction

Introduction

When drawing mathematical or scientific conclusions, two main reasoning methods are used: induction and deduction. Induction involves reasoning from specific examples to reach a broad conclusion. Deduction works in the opposite direction - reasoning from a general principle to reach a specific conclusion. This chapter focuses on induction. The process of induction begins with observations. From these observations, we develop tentative conclusions known as conjectures. A conjecture may turn out to be true or false. The principle of mathematical induction is a powerful tool that helps verify whether certain conjectures that appear to be true actually hold for all cases.

4.1 Mathematical Statement

A statement that expresses a mathematical relation or set of relations is called a mathematical statement.

Consider these statements:

1. 6 is an even natural number.
2. (x + 2) is a factor of x² - 3x + 2.
3. Mumbai is the capital of Maharashtra.
4. Sum of first n natural numbers is \( \frac{n(n+1)}{2} \).
5. If A, B are any sets, then A ∩ B = B ∩ A.

Clearly, statements 1, 2, 4 and 5 are mathematical statements.

Notation for Mathematical Statements

Consider these mathematical statements:

1. n(n + 1) is divisible by 2.
2. 3^(2n) - 1 is divisible by 8.
3. n² - n + 41 is a prime integer.
4. If a set S contains n distinct objects, then the number of subsets of S is 2^n.

All these statements involve the natural number 'n', which takes values 1, 2, 3, and so on. Such statements are usually written as P(n) or S(n). By substituting specific values for n, we get particular statements. For example, if the statement "2^(3n) - 1 is divisible by 7" is written as P(n), then P(2) means "2^(3 × 2) - 1 is divisible by 7".

Illustrative Examples

Example 1. If P(n) is the statement "n³ + n is divisible by 3", show that P(3) is true but P(4) is not true.
Answer: P(n) is the statement "n³ + n is divisible by 3".

P(3) means 3³ + 3 = 27 + 3 = 30, and 30 is divisible by 3 - this is clearly true.

P(4) means 4³ + 4 = 64 + 4 = 68. Since 68 ÷ 3 = 22 remainder 2, the value 68 is not divisible by 3 - so this is clearly false.
In simple words: We replace n with 3 in the first case and get 30, which divides by 3. When we use 4 instead, we get 68, which does not divide by 3.

Exam Tip: Always check the arithmetic carefully when substituting values - a single calculation error will lead to a wrong conclusion about whether P(n) is true or false.

Example 2. Let P(n) be the statement "3^(2n) - 1 is divisible by 8". What is P(n + 1)?
Answer: P(n) is given as "3^(2n) - 1 is divisible by 8". To find P(n + 1), we replace n with (n + 1) everywhere it appears in P(n).

Therefore, P(n + 1) becomes "3^(2(n+1)) - 1 is divisible by 8", which simplifies to "3^(2n+2) - 1 is divisible by 8".
In simple words: Whenever you see n in the original statement, replace it with the new value (n + 1).

Exam Tip: Take care when substituting expressions with brackets - write out the intermediate step 3^(2(n+1)) before simplifying to 3^(2n+2).

Example 3. Let P(n) be the statement "n² + n is an odd integer". Show that if P(m) is true then P(m + 1) is also true.
Answer: Given statement P(n): "n² + n is an odd integer".

Assume P(m) is true, meaning m² + m is an odd integer. We need to prove that P(m + 1) is also true, meaning (m + 1)² + (m + 1) is odd.

Expanding: (m + 1)² + (m + 1) = m² + 2m + 1 + m + 1 = m² + 3m + 2 = (m² + m) + (2m + 2)

Since m² + m is odd (by our assumption), and 2m + 2 = 2(m + 1) is always even (because 2 divides it), the sum of an odd integer and an even integer must be odd.

Therefore, P(m + 1) is true.
In simple words: When you add the expression for m + 1, you get the old odd value plus an even number, and odd plus even always gives odd.

Exam Tip: Show the expansion step clearly and explain why 2(m + 1) is even - graders check for this reasoning.

Example 4. Let P(n) be the statement "2^(3n) - 1 is divisible by 7". Prove that if P(m) is true then P(m + 1) is also true.
Answer: Given statement P(n): "2^(3n) - 1 is divisible by 7".

Assume P(m) is true: 2^(3m) - 1 is divisible by 7.
This means 2^(3m) - 1 = 7λ for some integer λ.
Therefore, 2^(3m) = 1 + 7λ.

Now we work with P(m + 1):
2^(3(m+1)) - 1 = 2^(3m+3) - 1 = 2^(3m) · 2³ - 1
= (1 + 7λ) · 8 - 1 [substituting 2^(3m) = 1 + 7λ]
= 8 + 56λ - 1 = 7 + 56λ = 7(1 + 8λ)

Since 7(1 + 8λ) is divisible by 7, we have proven that P(m + 1) is true.
In simple words: We used the fact that 2^(3m) - 1 divides by 7 to rewrite 2^(3m) in a helpful form. Then multiplying by 8 and subtracting 1 still leaves us with a multiple of 7.

Exam Tip: Express divisibility as an equation (like 2^(3m) - 1 = 7λ) right away - this makes the algebraic steps clearer.

Example 5. Let P(n) be the statement "3^n > n". Show that if P(m) is true then P(m + 1) is also true.
Answer: Given statement P(n): "3^n > n".

Assume P(m) is true: 3^m > m.

Multiply both sides by 3:
3 · 3^m > 3 · m
3^(m+1) > 3m

We need to show 3^(m+1) > m + 1. Since 3m > m + 1 for every positive integer m (because 2m > 1 whenever m ≥ 1), we have:
3^(m+1) > 3m > m + 1

Therefore, P(m + 1) is true.
In simple words: When you multiply both sides by 3, you get 3^(m+1) on the left and 3m on the right. Since 3m is much bigger than m + 1, the inequality still holds.

Exam Tip: Include the step showing 2m > 1 - examiners need to see the reasoning for why 3m > m + 1.

Exercise 4.1

Question 1. If P(n) is the statement "n(n + 1)(n + 2) is divisible by 6", then what is P(3)?
Answer: Substitute n = 3 into P(n):
P(3): 3(3 + 1)(3 + 2) = 3 × 4 × 5 = 60

So P(3) means "60 is divisible by 6". Since 60 ÷ 6 = 10, this statement is true.
In simple words: Plug in 3 for n and multiply: 3 times 4 times 5 equals 60, which divides evenly by 6.

Exam Tip: Always verify the divisibility after calculating - show the division explicitly to confirm the result.

Question 2. If P(n) is the statement "10n + 3 is prime", then show that P(1) and P(2) are true but P(3) is not true.
Answer: P(1): 10(1) + 3 = 13. Since 13 is prime (divisible only by 1 and 13), P(1) is true.

P(2): 10(2) + 3 = 23. Since 23 is prime (divisible only by 1 and 23), P(2) is true.

P(3): 10(3) + 3 = 33 = 3 × 11. Since 33 has factors other than 1 and itself, 33 is not prime, so P(3) is false.
In simple words: When n is 1 or 2, the formula gives prime numbers. When n is 3, we get 33, which is not prime because it equals 3 times 11.

Exam Tip: For primality, always check if the number has factors by testing small primes like 2, 3, 5, etc.

Question 3. If P(n) is the statement "n(n + 1)(n + 2) is an integral multiple of 12", prove that P(3) and P(4) are true but P(5) is not true.
Answer: P(3): 3(3 + 1)(3 + 2) = 3 × 4 × 5 = 60. We check: 60 ÷ 12 = 5, so 60 is a multiple of 12 - P(3) is true.

P(4): 4(4 + 1)(4 + 2) = 4 × 5 × 6 = 120. We check: 120 ÷ 12 = 10, so 120 is a multiple of 12 - P(4) is true.

P(5): 5(5 + 1)(5 + 2) = 5 × 6 × 7 = 210. We check: 210 ÷ 12 = 17.5, so 210 is not a multiple of 12 - P(5) is false.
In simple words: We multiply the three numbers and divide by 12 to see if it works out evenly. It does for n = 3 and n = 4, but not for n = 5.

Exam Tip: Always show the division result clearly - if it is a whole number, the statement is true; if not, it is false.

Question 4. If P(n) is the statement "n² - n + 41 is prime", show that P(1), P(2), and P(3) are true but P(41) is not true.
Answer: P(1): 1² - 1 + 41 = 41. Since 41 is prime, P(1) is true.

P(2): 2² - 2 + 41 = 4 - 2 + 41 = 43. Since 43 is prime, P(2) is true.

P(3): 3² - 3 + 41 = 9 - 3 + 41 = 47. Since 47 is prime, P(3) is true.

P(41): 41² - 41 + 41 = 1681 - 41 + 41 = 1681 = 41². Since 1681 = 41 × 41, it is not prime, so P(41) is false.
In simple words: The formula gives prime numbers for n = 1, 2, and 3, but when n = 41, it produces 1681, which is 41 squared and therefore not prime.

Exam Tip: Notice how this formula produces primes for small values but fails at n = 41 - this illustrates why we cannot assume a formula works for all n just because it works for a few initial values.

Question 5. Let P(n) be the statement "n² + n is an even integer". Show that if P(k) is true then P(k + 1) is also true.
Answer: Given statement P(n): "n² + n is an even integer".

Assume P(k) is true: k² + k is even.

We need to show P(k + 1) is true, meaning (k + 1)² + (k + 1) is even.

Expanding: (k + 1)² + (k + 1) = k² + 2k + 1 + k + 1 = k² + 3k + 2 = (k² + k) + (2k + 2)

Since k² + k is even (by assumption), and 2k + 2 = 2(k + 1) is always even (it contains a factor of 2), the sum of two even integers must be even.

Therefore, P(k + 1) is true.
In simple words: The new expression equals the old even value plus 2(k + 1), which is even. Even plus even always gives even.

Exam Tip: Factor out common terms to show clearly that one part is even by assumption and the other part is even by construction.

Question 6. Let P(n) denote the statement "3^(2n) - 1 is a multiple of 8". Show that (i) P(1), P(2) are true (ii) if P(m) is true then P(m + 1) is also true.
Answer: (i) P(1): 3^(2·1) - 1 = 3² - 1 = 9 - 1 = 8. Since 8 ÷ 8 = 1, P(1) is true.

P(2): 3^(2·2) - 1 = 3⁴ - 1 = 81 - 1 = 80 = 8 × 10. Since 80 is a multiple of 8, P(2) is true.

(ii) Assume P(m) is true: 3^(2m) - 1 is a multiple of 8, so 3^(2m) - 1 = 8k for some integer k.
This means 3^(2m) = 1 + 8k.

For P(m + 1): 3^(2(m+1)) - 1 = 3^(2m+2) - 1 = 3^(2m) · 3² - 1 = (1 + 8k) · 9 - 1 = 9 + 72k - 1 = 8 + 72k = 8(1 + 9k)

Since 8(1 + 9k) is a multiple of 8, P(m + 1) is true.
In simple words: We check that the statement works for the first two values. Then we use the fact that it works for m to show it must work for m + 1.

Exam Tip: Write divisibility conditions as equations early (like 3^(2m) - 1 = 8k) - this helps organize the algebra that follows.

Question 7. If P(n) is the statement "n² > 100", then show that whenever P(m) is true, P(m + 1) is also true.
Answer: Assume P(m) is true: m² > 100.

We need to show P(m + 1) is true: (m + 1)² > 100.

Expanding: (m + 1)² = m² + 2m + 1

Since m² > 100 (by assumption), and 2m + 1 > 0 for all positive m, we have:
(m + 1)² = m² + 2m + 1 > 100 + 2m + 1 = 101 + 2m > 100

Therefore, P(m + 1) is true.
In simple words: If a number squared is already bigger than 100, adding more positive terms (2m + 1) to it will keep it bigger than 100.

Exam Tip: Show that you are adding positive quantities to the assumed result - this makes the logic transparent.

Question 8. Let P(n) be the statement "2^n ≥ 3n". Show that if P(m) is true, then P(m + 1) is also true.
Answer: Assume P(m) is true: 2^m ≥ 3m.

Multiply both sides by 2:
2 · 2^m ≥ 2 · 3m
2^(m+1) ≥ 6m

We need to show 2^(m+1) ≥ 3(m + 1) = 3m + 3.

Since 6m ≥ 3m + 3 when m ≥ 1 (because 6m - 3m = 3m ≥ 3 when m ≥ 1), we have:
2^(m+1) ≥ 6m ≥ 3m + 3 = 3(m + 1)

Therefore, P(m + 1) is true.
In simple words: After doubling the inequality, we get 2^(m+1) ≥ 6m. Since 6m is much larger than 3m + 3 for positive m, the required inequality still holds.

Exam Tip: Show the intermediate inequality 6m ≥ 3m + 3 separately to make it clear that this is the key step.

4.2 Principle of Mathematical Induction

4.2.1 Motivation

To grasp the basic idea of mathematical induction, imagine a set of thin rectangular tiles lined up in a row, each one standing upright and close to the next. When you push the first tile in a particular direction, it falls and strikes the second tile, which then falls and hits the third tile, causing it to fall, and so on. The domino effect continues all the way down the line. To know for certain that all tiles will fall, you need two things: (i) the first tile falls when pushed, and (ii) whenever any tile falls, it definitely causes the next tile to fall. This is the fundamental concept behind mathematical induction.

A set S is called an inductive set if 1 belongs to S, and whenever any number x is in S, the number x + 1 is also in S. The set of natural numbers N is a special ordered subset of the real numbers. It is the smallest subset of real numbers that is inductive.

4.2.2 Principle of Mathematical Induction

Let P(n) be a statement that depends on the natural number n. Then P(n) is true for all natural numbers n if and only if both of the following hold:

(i) P(1) is true
(ii) P(m + 1) is true whenever P(m) is true.

In other words, to establish that a statement P(n) holds for every natural number n, you must complete two steps:

(i) Verify that the statement is true when n = 1 (this is called the base case).
(ii) Assume the statement holds for some value n = m (this is called the inductive hypothesis), and then prove it holds for n = m + 1 (this is called the inductive step).

Remark

It is crucial to emphasize that a valid proof using mathematical induction demands that BOTH conditions (i) and (ii) above are satisfied. Proving only one of them is insufficient.

Illustrative Examples

Example 1. Prove by mathematical induction that the sum of first n odd natural numbers is n².
Answer: Let P(n) denote the statement: "1 + 3 + 5 + ... to n terms = n²"

This can also be written as: 1 + 3 + 5 + ... + (2n - 1) = n²
[Note: The n-th odd number follows the formula 2n - 1, since odd numbers form an arithmetic progression with first term 1 and common difference 2]

Base case - P(1): When n = 1, we need 1 = 1². This is clearly true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 1 + 3 + 5 + ... + (2m - 1) = m²

Inductive step - We must prove P(m + 1) is true:
1 + 3 + 5 + ... to (m + 1) terms
= 1 + 3 + 5 + ... + (2(m + 1) - 1)
= 1 + 3 + 5 + ... + (2m + 1)
= [1 + 3 + 5 + ... + (2m - 1)] + (2m + 1)
= m² + (2m + 1) [using the inductive hypothesis]
= m² + 2m + 1
= (m + 1)²

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n. Therefore, the sum of the first n odd natural numbers equals n².
In simple words: We start by checking it works for the first odd number (which is 1). Then we assume it works for m odd numbers and show it must work for m + 1 odd numbers. Since both parts are true, the formula works for all cases.

Exam Tip: Always identify the n-th term of the sequence being summed before starting - here it is 2n - 1 for the n-th odd number.

Example 2. Prove by induction that 1 + 5 + 9 + ... + (4n - 3) = n(2n - 1), for all n ∈ N.
Answer: Let P(n) denote the statement: 1 + 5 + 9 + ... + (4n - 3) = n(2n - 1)

Base case - P(1): 1 = 1(2·1 - 1) = 1(1) = 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1 + 5 + 9 + ... + (4m - 3) = m(2m - 1)

Inductive step - Prove P(m + 1) is true:
1 + 5 + 9 + ... + (4m - 3) + (4(m + 1) - 3)
= m(2m - 1) + (4m + 4 - 3) [using the inductive hypothesis]
= 2m² - m + 4m + 1
= 2m² + 3m + 1
= (m + 1)(2m + 1) [factoring]
= (m + 1)(2(m + 1) - 1)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We verify the formula for n = 1. Then we add the next term to the sum for m terms and show we get the formula for m + 1 terms.

Exam Tip: When factoring the result (like 2m² + 3m + 1), double-check by expanding (m + 1)(2m + 1) to confirm it matches.

Example 3. Prove by principle of mathematical induction that 1·2 + 2·3 + 3·4 + ... + n(n + 1) = \( \frac{n(n+1)(n+2)}{3} \), for all n ∈ N.
Answer: Let P(n) denote the statement: 1·2 + 2·3 + 3·4 + ... + n(n + 1) = \( \frac{n(n+1)(n+2)}{3} \)

Base case - P(1): 1·2 = \( \frac{1·2·3}{3} \) = \( \frac{6}{3} \) = 2 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1·2 + 2·3 + 3·4 + ... + m(m + 1) = \( \frac{m(m+1)(m+2)}{3} \)

Inductive step - Prove P(m + 1) is true:
1·2 + 2·3 + 3·4 + ... + m(m + 1) + (m + 1)(m + 2)
= \( \frac{m(m+1)(m+2)}{3} \) + (m + 1)(m + 2) [using the inductive hypothesis]
= (m + 1)(m + 2) \( \left[\frac{m}{3} + 1\right] \)
= (m + 1)(m + 2) \( \left[\frac{m + 3}{3}\right] \)
= \( \frac{(m+1)(m+2)(m+3)}{3} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the (m + 1)-th term to the sum of the first m terms and factor out the common part (m + 1)(m + 2) to get the formula for m + 1 terms.

Exam Tip: When combining fractions, always factor out the common expression first - this simplifies the algebra significantly.

Example 4. For all n ∈ N, prove by induction that 1² + 2² + 3² + ... + n² = \( \frac{n(n+1)(2n+1)}{6} \).
Answer: Let P(n) denote the statement: 1² + 2² + 3² + ... + n² = \( \frac{n(n+1)(2n+1)}{6} \)

Base case - P(1): 1² = \( \frac{1·2·3}{6} \) = 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1² + 2² + 3² + ... + m² = \( \frac{m(m+1)(2m+1)}{6} \)

Inductive step - Prove P(m + 1) is true:
1² + 2² + 3² + ... + m² + (m + 1)²
= \( \frac{m(m+1)(2m+1)}{6} \) + (m + 1)² [using the inductive hypothesis]
= \( \frac{m(m+1)(2m+1) + 6(m+1)^2}{6} \)
= \( \frac{(m+1)[m(2m+1) + 6(m+1)]}{6} \)
= \( \frac{(m+1)[2m^2 + m + 6m + 6]}{6} \)
= \( \frac{(m+1)(2m^2 + 7m + 6)}{6} \)
= \( \frac{(m+1)(m+2)(2m+3)}{6} \)
= \( \frac{(m+1)((m+1)+1)(2(m+1)+1)}{6} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add (m + 1)² to the existing sum and combine the fractions. After factoring, we obtain the formula with m replaced by m + 1.

Exam Tip: Verify the factorization 2m² + 7m + 6 = (m + 2)(2m + 3) by multiplying - this prevents errors in the final step.

Example 5. Prove by induction that 1³ + 2³ + 3³ + ... + n³ = \( \left[\frac{n(n+1)}{2}\right]^2 \), for all n ∈ N.
Answer: Let P(n) denote the statement: 1³ + 2³ + 3³ + ... + n³ = \( \left[\frac{n(n+1)}{2}\right]^2 \)

Base case - P(1): 1³ = \( \left[\frac{1·2}{2}\right]^2 \) = 1² = 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1³ + 2³ + 3³ + ... + m³ = \( \left[\frac{m(m+1)}{2}\right]^2 \)

Inductive step - Prove P(m + 1) is true:
1³ + 2³ + 3³ + ... + m³ + (m + 1)³
= \( \left[\frac{m(m+1)}{2}\right]^2 \) + (m + 1)³ [using the inductive hypothesis]
= (m + 1)² \( \left[\frac{m^2}{4} + (m + 1)\right] \)
= (m + 1)² \( \left[\frac{m^2 + 4(m+1)}{4}\right] \)
= (m + 1)² \( \left[\frac{m^2 + 4m + 4}{4}\right] \)
= (m + 1)² \( \left[\frac{(m+2)^2}{4}\right] \)
= \( \left[\frac{(m+1)(m+2)}{2}\right]^2 \)
= \( \left[\frac{(m+1)((m+1)+1)}{2}\right]^2 \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add (m + 1)³ to the sum. Factoring out (m + 1)² and simplifying the remaining expression gives us the formula with m replaced by m + 1.

Exam Tip: When working with squared expressions, look for common factors - here factoring out (m + 1)² early made the algebra much cleaner.

Example 6. For all n ∈ N, using principle of mathematical induction prove that \( 1 + \frac{1}{1+2} + \frac{1}{1+2+3} + ... + \frac{1}{1+2+3+...+n} = \frac{2n}{n+1} \).
Answer: Let P(n) denote the statement: \( 1 + \frac{1}{1+2} + \frac{1}{1+2+3} + ... + \frac{1}{1+2+3+...+n} = \frac{2n}{n+1} \)

Using the formula for the sum of first k natural numbers: \( 1 + 2 + 3 + ... + k = \frac{k(k+1)}{2} \), we can rewrite the statement as:
\( 1 + \frac{1}{\frac{2·3}{2}} + \frac{1}{\frac{3·4}{2}} + ... + \frac{1}{\frac{n(n+1)}{2}} = \frac{2n}{n+1} \)

Base case - P(1): 1 = \( \frac{2·1}{1+1} \) = 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( 1 + \frac{1}{1+2} + \frac{1}{1+2+3} + ... + \frac{1}{1+2+3+...+m} = \frac{2m}{m+1} \)

Inductive step - Prove P(m + 1) is true. The next term in the series is \( \frac{1}{1+2+3+...+(m+1)} = \frac{1}{\frac{(m+1)(m+2)}{2}} = \frac{2}{(m+1)(m+2)} \)

Left side for P(m + 1):
\( \frac{2m}{m+1} + \frac{2}{(m+1)(m+2)} \) [using the inductive hypothesis]
= \( \frac{2m(m+2) + 2}{(m+1)(m+2)} \)
= \( \frac{2(m(m+2) + 1)}{(m+1)(m+2)} \)
= \( \frac{2(m^2 + 2m + 1)}{(m+1)(m+2)} \)
= \( \frac{2(m+1)^2}{(m+1)(m+2)} \)
= \( \frac{2(m+1)}{m+2} \)
= \( \frac{2(m+1)}{(m+1)+1} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: Each denominator is a triangular number (sum of consecutive integers). We add the next fraction and use algebra to verify the formula still holds.

Exam Tip: Always use the sum formula for first k natural numbers to convert sums in denominators to simple fractions - this makes the algebra manageable.

Example 7. Using principle of mathematical induction prove that 1·3 + 2·3² + 3·3³ + ... + n·3ⁿ = \( \frac{(2n-1)3^{n+1}+3}{4} \), for all n ∈ N.
Answer: Let P(n) denote the statement: 1·3 + 2·3² + 3·3³ + ... + n·3ⁿ = \( \frac{(2n-1)3^{n+1}+3}{4} \)

Base case - P(1): 1·3 = \( \frac{(2·1-1)3^{1+1}+3}{4} \) = \( \frac{1·9+3}{4} \) = \( \frac{12}{4} \) = 3 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1·3 + 2·3² + 3·3³ + ... + m·3ᵐ = \( \frac{(2m-1)3^{m+1}+3}{4} \)

Inductive step - Prove P(m + 1) is true:
1·3 + 2·3² + 3·3³ + ... + m·3ᵐ + (m + 1)·3^(m+1)
= \( \frac{(2m-1)3^{m+1}+3}{4} \) + (m + 1)·3^(m+1) [using the inductive hypothesis]
= \( \frac{(2m-1)3^{m+1}+3+4(m+1)3^{m+1}}{4} \)
= \( \frac{(2m-1)3^{m+1}+4(m+1)3^{m+1}+3}{4} \)
= \( \frac{3^{m+1}[(2m-1)+4(m+1)]+3}{4} \)
= \( \frac{3^{m+1}[2m-1+4m+4]+3}{4} \)
= \( \frac{3^{m+1}[6m+3]+3}{4} \)
= \( \frac{3(2m+1)3^{m+1}+3}{4} \)
= \( \frac{(2m+1)3^{m+2}+3}{4} \)
= \( \frac{(2(m+1)-1)3^{(m+1)+1}+3}{4} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next term and factor out 3^(m+1) from the numerator. This reveals the same pattern with m replaced by m + 1.

Exam Tip: When combining terms involving powers, always factor out the common power to simplify - here factoring 3^(m+1) was key.

Example 8. Use induction to prove that \( \left(1+\frac{3}{1}\right)\left(1+\frac{5}{4}\right)\left(1+\frac{7}{9}\right)...\left(1+\frac{2n+1}{n^2}\right) = (n+1)^2 \), for all n ∈ N.
Answer: Let P(n) denote the statement: \( \left(1+\frac{3}{1}\right)\left(1+\frac{5}{4}\right)\left(1+\frac{7}{9}\right)...\left(1+\frac{2n+1}{n^2}\right) = (n+1)^2 \)

Rewriting each factor: \( 1+\frac{2k+1}{k^2} = \frac{k^2+2k+1}{k^2} = \frac{(k+1)^2}{k^2} \)

Base case - P(1): \( 1+\frac{3}{1} \) = 4 = (1+1)² ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \left(1+\frac{3}{1}\right)\left(1+\frac{5}{4}\right)...\left(1+\frac{2m+1}{m^2}\right) = (m+1)^2 \)

Inductive step - Prove P(m + 1) is true:
\( \left(1+\frac{3}{1}\right)\left(1+\frac{5}{4}\right)...\left(1+\frac{2m+1}{m^2}\right)\left(1+\frac{2(m+1)+1}{(m+1)^2}\right) \)
= (m+1)² · \( \left(1+\frac{2m+3}{(m+1)^2}\right) \) [using the inductive hypothesis]
= (m+1)² · \( \frac{(m+1)^2+2m+3}{(m+1)^2} \)
= (m+1)² · \( \frac{m^2+2m+1+2m+3}{(m+1)^2} \)
= (m+1)² · \( \frac{m^2+4m+4}{(m+1)^2} \)
= (m+1)² · \( \frac{(m+2)^2}{(m+1)^2} \)
= (m+2)² = ((m+1)+1)²

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: Each factor in the product simplifies to a perfect square divided by another perfect square. Multiplying these fractions together produces (n+1)².

Exam Tip: Always try to simplify the general factor first - converting \( 1+\frac{2k+1}{k^2} \) to \( \frac{(k+1)^2}{k^2} \) made the telescoping product clear.

Example 9. Using induction, prove that \( \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right)...\left(1-\frac{1}{n^2}\right) = \frac{n+1}{2n} \) for all natural numbers n, n ≥ 2.
Answer: Let P(n) denote the statement: \( \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right)...\left(1-\frac{1}{n^2}\right) = \frac{n+1}{2n} \), for n ≥ 2

Rewriting each factor: \( 1-\frac{1}{k^2} = \frac{k^2-1}{k^2} = \frac{(k-1)(k+1)}{k^2} \)

Base case - P(2): \( 1-\frac{1}{4} \) = \( \frac{3}{4} \) and \( \frac{2+1}{2·2} \) = \( \frac{3}{4} \) ✓ This is true, so P(2) is true.

Inductive hypothesis - Assume P(m) is true, for m ≥ 2:
\( \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)...\left(1-\frac{1}{m^2}\right) = \frac{m+1}{2m} \)

Inductive step - Prove P(m + 1) is true:
\( \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)...\left(1-\frac{1}{m^2}\right)\left(1-\frac{1}{(m+1)^2}\right) \)
= \( \frac{m+1}{2m} \) · \( \left(1-\frac{1}{(m+1)^2}\right) \) [using the inductive hypothesis]
= \( \frac{m+1}{2m} \) · \( \frac{(m+1)^2-1}{(m+1)^2} \)
= \( \frac{m+1}{2m} \) · \( \frac{(m+1-1)(m+1+1)}{(m+1)^2} \)
= \( \frac{m+1}{2m} \) · \( \frac{m(m+2)}{(m+1)^2} \)
= \( \frac{m(m+2)}{2m(m+1)} \)
= \( \frac{m+2}{2(m+1)} \)
= \( \frac{(m+1)+1}{2(m+1)} \)

So P(m + 1) is true.

By induction, P(n) is true for all natural numbers n, n ≥ 2.
In simple words: Each factor is a fraction that factors into a product of simpler terms. When multiplied together, many terms cancel, leaving just the first and last parts.

Exam Tip: Note that this proof starts with n = 2, not n = 1 - always check the problem statement for the starting value. This is called a "modified" induction.

Example 10. By principle of mathematical induction, prove that for all n ∈ N: \( \frac{1}{2·5} + \frac{1}{5·8} + \frac{1}{8·11} + ... + \frac{1}{(3n-1)(3n+2)} = \frac{n}{6n+4} \).
Answer: Let P(n) denote the statement: \( \frac{1}{2·5} + \frac{1}{5·8} + \frac{1}{8·11} + ... + \frac{1}{(3n-1)(3n+2)} = \frac{n}{6n+4} \)

Base case - P(1): \( \frac{1}{2·5} \) = \( \frac{1}{10} \) and \( \frac{1}{6·1+4} \) = \( \frac{1}{10} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{2·5} + \frac{1}{5·8} + ... + \frac{1}{(3m-1)(3m+2)} = \frac{m}{6m+4} \)

Inductive step - Prove P(m + 1) is true. The next term is \( \frac{1}{(3(m+1)-1)(3(m+1)+2)} = \frac{1}{(3m+2)(3m+5)} \)

\( \frac{m}{6m+4} + \frac{1}{(3m+2)(3m+5)} \) [using the inductive hypothesis]

Factor 6m + 4 = 2(3m + 2):
= \( \frac{m}{2(3m+2)} + \frac{1}{(3m+2)(3m+5)} \)
= \( \frac{m(3m+5) + 2}{2(3m+2)(3m+5)} \)
= \( \frac{3m^2+5m+2}{2(3m+2)(3m+5)} \)
= \( \frac{(3m+2)(m+1)}{2(3m+2)(3m+5)} \)
= \( \frac{m+1}{2(3m+5)} \)
= \( \frac{m+1}{6m+10} \)
= \( \frac{m+1}{6(m+1)+4} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: Each fraction can be viewed as a telescoping sum - adjacent factors share denominators that can be used to combine terms efficiently.

Exam Tip: For partial fractions, factor the denominator and try to express each fraction as a difference - this often leads to telescoping sums.

Exercise 4.2

Using the principle of mathematical induction prove that (1 to 26) for all n ∈ N:

Question 1. 2 + 4 + 6 + ... + 2n = n² + n.
Answer: Let P(n) denote the statement: 2 + 4 + 6 + ... + 2n = n² + n

Base case - P(1): 2 = 1² + 1 = 2 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
2 + 4 + 6 + ... + 2m = m² + m

Inductive step - Prove P(m + 1) is true:
2 + 4 + 6 + ... + 2m + 2(m + 1)
= m² + m + 2m + 2 [using the inductive hypothesis]
= m² + 3m + 2
= (m + 1)² + (m + 1)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add 2(m + 1) to the left side and simplify the right side to show the pattern continues.

Exam Tip: Always verify that your expansion of (m + 1)² + (m + 1) matches your simplification of m² + 3m + 2.

Question 2. 1 + 4 + 7 + ... + (3n - 2) = \( \frac{1}{2}n(3n - 1) \).
Answer: Let P(n) denote the statement: 1 + 4 + 7 + ... + (3n - 2) = \( \frac{1}{2}n(3n - 1) \)

Base case - P(1): 1 = \( \frac{1}{2}·1·2 \) = 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1 + 4 + 7 + ... + (3m - 2) = \( \frac{1}{2}m(3m - 1) \)

Inductive step - Prove P(m + 1) is true:
1 + 4 + 7 + ... + (3m - 2) + (3(m + 1) - 2)
= \( \frac{1}{2}m(3m - 1) \) + (3m + 1) [using the inductive hypothesis]
= \( \frac{m(3m-1)+2(3m+1)}{2} \)
= \( \frac{3m^2-m+6m+2}{2} \)
= \( \frac{3m^2+5m+2}{2} \)
= \( \frac{(m+1)(3m+2)}{2} \)
= \( \frac{(m+1)(3(m+1)-1)}{2} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next term and combine fractions, then factor the numerator to verify the formula holds for m + 1.

Exam Tip: When factoring quadratics like 3m² + 5m + 2, check: does (m + 1)(3m + 2) = 3m² + 5m + 2? Expand to verify before finalizing.

Question 3. 3x + 6x + 9x + ... to n terms = \( \frac{3}{2}n(n + 1)x \).
Answer: Let P(n) denote the statement: 3x + 6x + 9x + ... to n terms = \( \frac{3}{2}n(n + 1)x \)

This can be written as: \( 3x(1 + 2 + 3 + ... + n) = \frac{3}{2}n(n + 1)x \)

Base case - P(1): 3x = \( \frac{3}{2}·1·2·x \) = 3x ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
3x + 6x + 9x + ... + 3mx = \( \frac{3}{2}m(m + 1)x \)

Inductive step - Prove P(m + 1) is true:
3x + 6x + 9x + ... + 3mx + 3(m + 1)x
= \( \frac{3}{2}m(m + 1)x \) + 3(m + 1)x [using the inductive hypothesis]
= 3(m + 1)x \( \left[\frac{m}{2} + 1\right] \)
= 3(m + 1)x \( \left[\frac{m+2}{2}\right] \)
= \( \frac{3}{2}(m + 1)(m + 2)x \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next term 3(m + 1)x and factor out the common 3(m + 1)x to reveal the pattern with m + 1.

Exam Tip: Factor out the common expression before combining fractions - this simplifies the algebra significantly.

Question 4. 1² + 3² + 5² + ... to n terms = \( \frac{n(4n^2-1)}{3} \).
Answer: Let P(n) denote the statement: 1² + 3² + 5² + ... to n terms = \( \frac{n(4n^2-1)}{3} \)

Base case - P(1): 1² = \( \frac{1(4·1-1)}{3} \) = \( \frac{3}{3} \) = 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1² + 3² + 5² + ... + (2m - 1)² = \( \frac{m(4m^2-1)}{3} \)

Inductive step - Prove P(m + 1) is true. The next odd square is (2(m + 1) - 1)² = (2m + 1)²:
1² + 3² + 5² + ... + (2m - 1)² + (2m + 1)²
= \( \frac{m(4m^2-1)}{3} \) + (2m + 1)² [using the inductive hypothesis]
= \( \frac{m(4m^2-1)+3(2m+1)^2}{3} \)
= \( \frac{m(4m^2-1)+3(4m^2+4m+1)}{3} \)
= \( \frac{4m^3-m+12m^2+12m+3}{3} \)
= \( \frac{4m^3+12m^2+11m+3}{3} \)
= \( \frac{(m+1)(4m^2+8m+3)}{3} \)
= \( \frac{(m+1)(4(m+1)^2-1)}{3} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the square of the next odd number and verify the formula pattern continues through algebra.

Exam Tip: Verify that (m + 1)(4(m+1)² - 1) correctly expands to the numerator you derived - this confirms your factoring is right.

Question 5. \( \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{2^n} = 1 - \frac{1}{2^n} \).
Answer: Let P(n) denote the statement: \( \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{2^n} = 1 - \frac{1}{2^n} \)

Base case - P(1): \( \frac{1}{2} \) = 1 - \( \frac{1}{2} \) = \( \frac{1}{2} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{2^m} = 1 - \frac{1}{2^m} \)

Inductive step - Prove P(m + 1) is true:
\( \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{2^m} + \frac{1}{2^{m+1}} \)
= \( 1 - \frac{1}{2^m} \) + \( \frac{1}{2^{m+1}} \) [using the inductive hypothesis]
= \( 1 - \frac{2}{2^{m+1}} + \frac{1}{2^{m+1}} \)
= \( 1 - \frac{1}{2^{m+1}} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next fraction to the existing sum. Converting \( \frac{1}{2^m} \) to \( \frac{2}{2^{m+1}} \) allows us to combine the fractions.

Exam Tip: When working with powers of 2, remember that \( \frac{1}{2^m} = \frac{2}{2^{m+1}} \) - this helps align denominators.

Question 6. 3.6 + 6.9 + 9.12 + ... + 3n(3n + 3) = 3n(n + 1)(n + 2).
Answer: Let P(n) denote the statement: 3.6 + 6.9 + 9.12 + ... + 3n(3n + 3) = 3n(n + 1)(n + 2)

This can be rewritten as: \( 3·6 + 3·2·3·3 + 3·3·3·4 + ... + 3n·3(n+1) = 3n(n+1)(n+2) \)
Or: \( 3^2(1·2) + 3^2(2·3) + 3^2(3·4) + ... + 3^2 n(n+1) = 3n(n+1)(n+2) \)

Base case - P(1): 3·6 = 18 and 3·1·2·3 = 18 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
3.6 + 6.9 + 9.12 + ... + 3m(3m + 3) = 3m(m + 1)(m + 2)

Inductive step - Prove P(m + 1) is true:
3.6 + 6.9 + 9.12 + ... + 3m(3m + 3) + 3(m + 1)(3(m + 1) + 3)
= 3m(m + 1)(m + 2) + 3(m + 1)(3m + 6) [using the inductive hypothesis]
= 3(m + 1)[m(m + 2) + (3m + 6)]
= 3(m + 1)[m² + 2m + 3m + 6]
= 3(m + 1)(m² + 5m + 6)
= 3(m + 1)(m + 2)(m + 3)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next term and factor out 3(m + 1), then simplify to get the formula with m replaced by m + 1.

Exam Tip: When adding products, always look for common factors - here 3(m + 1) was common to both terms.

Question 7. 1.2 + 2.2² + 3.2³ + ... + n.2ⁿ = (n - 1).2^(n+1) + 2.
Answer: Let P(n) denote the statement: 1.2 + 2.2² + 3.2³ + ... + n.2ⁿ = (n - 1).2^(n+1) + 2

Base case - P(1): 1.2 = 2 and (1 - 1).2² + 2 = 0 + 2 = 2 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1.2 + 2.2² + 3.2³ + ... + m.2ᵐ = (m - 1).2^(m+1) + 2

Inductive step - Prove P(m + 1) is true:
1.2 + 2.2² + 3.2³ + ... + m.2ᵐ + (m + 1).2^(m+1)
= (m - 1).2^(m+1) + 2 + (m + 1).2^(m+1) [using the inductive hypothesis]
= 2^(m+1)[(m - 1) + (m + 1)] + 2
= 2^(m+1)[2m] + 2
= m.2^(m+2) + 2
= ((m + 1) - 1).2^((m+1)+1) + 2

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next term and factor out 2^(m+1) from the first two parts to combine them.

Exam Tip: When combining terms with the same power of 2, add their coefficients - here (m - 1) + (m + 1) = 2m.

Question 8. 1.2.3 + 2.3.4 + 3.4.5 + ... + n(n + 1)(n + 2) = \( \frac{n(n+1)(n+2)(n+3)}{4} \).
Answer: Let P(n) denote the statement: 1.2.3 + 2.3.4 + 3.4.5 + ... + n(n + 1)(n + 2) = \( \frac{n(n+1)(n+2)(n+3)}{4} \)

Base case - P(1): 1.2.3 = 6 and \( \frac{1·2·3·4}{4} \) = 6 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
1.2.3 + 2.3.4 + 3.4.5 + ... + m(m + 1)(m + 2) = \( \frac{m(m+1)(m+2)(m+3)}{4} \)

Inductive step - Prove P(m + 1) is true:
1.2.3 + 2.3.4 + 3.4.5 + ... + m(m + 1)(m + 2) + (m + 1)(m + 2)(m + 3)
= \( \frac{m(m+1)(m+2)(m+3)}{4} \) + (m + 1)(m + 2)(m + 3) [using the inductive hypothesis]
= (m + 1)(m + 2)(m + 3) \( \left[\frac{m}{4} + 1\right] \)
= (m + 1)(m + 2)(m + 3) \( \left[\frac{m+4}{4}\right] \)
= \( \frac{(m+1)(m+2)(m+3)(m+4)}{4} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We add the next product and factor out (m + 1)(m + 2)(m + 3), which appear in both terms.

Exam Tip: Always look for common factors in the last term - here (m + 1)(m + 2)(m + 3) appeared in both the existing sum and the new term.

Question 9. \( \left(1+\frac{1}{1}\right)\left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right)...\left(1+\frac{1}{n}\right) = n + 1 \).
Answer: Let P(n) denote the statement: \( \left(1+\frac{1}{1}\right)\left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right)...\left(1+\frac{1}{n}\right) = n + 1 \)

Simplify each factor: \( 1+\frac{1}{k} = \frac{k+1}{k} \)

Base case - P(1): \( 1+\frac{1}{1} \) = 2 = 1 + 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \left(1+\frac{1}{1}\right)\left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right)...\left(1+\frac{1}{m}\right) = m + 1 \)

Inductive step - Prove P(m + 1) is true:
\( \left(1+\frac{1}{1}\right)\left(1+\frac{1}{2}\right)\left(1+\frac{1}{3}\right)...\left(1+\frac{1}{m}\right)\left(1+\frac{1}{m+1}\right) \)
= (m + 1) · \( \left(1+\frac{1}{m+1}\right) \) [using the inductive hypothesis]
= (m + 1) · \( \frac{m+2}{m+1} \)
= m + 2 = (m + 1) + 1

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: The product is a telescoping product - each factor simplifies to (k + 1)/k, and when multiplied together, the numerators and denominators cancel except for the first denominator (1) and last numerator (n + 1).

Exam Tip: For products involving (1 + fraction), always simplify to a single fraction first - this makes the telescoping pattern clear.

Question 10. \( \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)...\left(1-\frac{1}{n+1}\right) = \frac{1}{n+1} \).
Answer: Let P(n) denote the statement: \( \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)...\left(1-\frac{1}{n+1}\right) = \frac{1}{n+1} \)

Simplify each factor: \( 1-\frac{1}{k} = \frac{k-1}{k} \)

Base case - P(1): \( 1-\frac{1}{2} \) = \( \frac{1}{2} \) = \( \frac{1}{1+1} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)...\left(1-\frac{1}{m+1}\right) = \frac{1}{m+1} \)

Inductive step - Prove P(m + 1) is true:
\( \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)...\left(1-\frac{1}{m+1}\right)\left(1-\frac{1}{m+2}\right) \)
= \( \frac{1}{m+1} \) · \( \left(1-\frac{1}{m+2}\right) \) [using the inductive hypothesis]
= \( \frac{1}{m+1} \) · \( \frac{m+1}{m+2} \)
= \( \frac{1}{m+2} \)
= \( \frac{1}{(m+1)+1} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: This is also a telescoping product. When factors like 1/2, 2/3, 3/4, ... are multiplied, only the first numerator and last denominator remain.

Exam Tip: In telescoping products, draw arrows showing which terms cancel - this helps visualize why the answer is so simple.

Question 11. \( \frac{1}{1·2} + \frac{1}{2·3} + \frac{1}{3·4} \) + ... to n terms = \( \frac{n}{n+1} \).
Answer: Let P(n) denote the statement: \( \frac{1}{1·2} + \frac{1}{2·3} + \frac{1}{3·4} \) + ... to n terms = \( \frac{n}{n+1} \)

Base case - P(1): \( \frac{1}{1·2} \) = \( \frac{1}{2} \) = \( \frac{1}{1+1} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{1·2} + \frac{1}{2·3} + \frac{1}{3·4} \) + ... + \( \frac{1}{m(m+1)} \) = \( \frac{m}{m+1} \)

Inductive step - Prove P(m + 1) is true:
\( \frac{1}{1·2} + \frac{1}{2·3} + \frac{1}{3·4} \) + ... + \( \frac{1}{m(m+1)} \) + \( \frac{1}{(m+1)(m+2)} \)
= \( \frac{m}{m+1} \) + \( \frac{1}{(m+1)(m+2)} \) [using the inductive hypothesis]
= \( \frac{m(m+2)+1}{(m+1)(m+2)} \)
= \( \frac{m^2+2m+1}{(m+1)(m+2)} \)
= \( \frac{(m+1)^2}{(m+1)(m+2)} \)
= \( \frac{m+1}{m+2} \)
= \( \frac{(m+1)}{(m+1)+1} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: Each fraction \( \frac{1}{k(k+1)} \) can be split using partial fractions. When all terms are added, it becomes a telescoping sum.

Exam Tip: Remember that \( \frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1} \) - this decomposition makes telescoping sums obvious.

Question 12. \( \frac{1}{3·6} + \frac{1}{6·9} + \frac{1}{9·12} + ... + \frac{1}{3n(3n+3)} = \frac{n}{9(n+1)} \).
Answer: Let P(n) denote the statement: \( \frac{1}{3·6} + \frac{1}{6·9} + \frac{1}{9·12} + ... + \frac{1}{3n(3n+3)} = \frac{n}{9(n+1)} \)

Base case - P(1): \( \frac{1}{3·6} \) = \( \frac{1}{18} \) and \( \frac{1}{9·2} \) = \( \frac{1}{18} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{3·6} + \frac{1}{6·9} + ... + \frac{1}{3m(3m+3)} = \frac{m}{9(m+1)} \)

Inductive step - Prove P(m + 1) is true:
\( \frac{1}{3·6} + \frac{1}{6·9} + ... + \frac{1}{3m(3m+3)} + \frac{1}{3(m+1)(3(m+1)+3)} \)
= \( \frac{m}{9(m+1)} \) + \( \frac{1}{3(m+1)(3m+6)} \) [using the inductive hypothesis]
= \( \frac{m}{9(m+1)} \) + \( \frac{1}{3(m+1)·3(m+2)} \)
= \( \frac{m}{9(m+1)} \) + \( \frac{1}{9(m+1)(m+2)} \)
= \( \frac{m(m+2)+1}{9(m+1)(m+2)} \)
= \( \frac{m^2+2m+1}{9(m+1)(m+2)} \)
= \( \frac{(m+1)^2}{9(m+1)(m+2)} \)
= \( \frac{m+1}{9(m+2)} \)
= \( \frac{m+1}{9((m+1)+1)} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: Factor out common terms from the denominator to align fractions before adding.

Exam Tip: Always simplify the denominator of the new fraction first - here 3(m+1)(3m+6) = 9(m+1)(m+2).

Question 13. \( \frac{1}{1·3} + \frac{1}{3·5} + \frac{1}{5·7} \) + ... to n terms = \( \frac{n}{2n+1} \).
Answer: Let P(n) denote the statement: \( \frac{1}{1·3} + \frac{1}{3·5} + \frac{1}{5·7} \) + ... to n terms = \( \frac{n}{2n+1} \)

Base case - P(1): \( \frac{1}{1·3} \) = \( \frac{1}{3} \) = \( \frac{1}{2·1+1} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{1·3} + \frac{1}{3·5} + \frac{1}{5·7} \) + ... + \( \frac{1}{(2m-1)(2m+1)} \) = \( \frac{m}{2m+1} \)

Inductive step - Prove P(m + 1) is true. The next fraction is \( \frac{1}{(2(m+1)-1)(2(m+1)+1)} = \frac{1}{(2m+1)(2m+3)} \):
\( \frac{1}{1·3} + \frac{1}{3·5} + ... + \frac{1}{(2m-1)(2m+1)} + \frac{1}{(2m+1)(2m+3)} \)
= \( \frac{m}{2m+1} \) + \( \frac{1}{(2m+1)(2m+3)} \) [using the inductive hypothesis]
= \( \frac{m(2m+3)+1}{(2m+1)(2m+3)} \)
= \( \frac{2m^2+3m+1}{(2m+1)(2m+3)} \)
= \( \frac{(2m+1)(m+1)}{(2m+1)(2m+3)} \)
= \( \frac{m+1}{2m+3} \)
= \( \frac{m+1}{2(m+1)+1} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: The denominators are products of consecutive odd numbers. Adding the fractions and factoring gives the pattern for m + 1.

Exam Tip: When factoring 2m² + 3m + 1, check: (2m + 1)(m + 1) = 2m² + 2m + m + 1 = 2m² + 3m + 1 ✓

Question 14. \( \frac{1}{1·4} + \frac{1}{4·7} + \frac{1}{7·10} + ... + \frac{1}{(3n-2)(3n+1)} = \frac{n}{3n+1} \).
Answer: Let P(n) denote the statement: \( \frac{1}{1·4} + \frac{1}{4·7} + \frac{1}{7·10} + ... + \frac{1}{(3n-2)(3n+1)} = \frac{n}{3n+1} \)

Base case - P(1): \( \frac{1}{1·4} \) = \( \frac{1}{4} \) = \( \frac{1}{3·1+1} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{1·4} + \frac{1}{4·7} + ... + \frac{1}{(3m-2)(3m+1)} = \frac{m}{3m+1} \)

Inductive step - Prove P(m + 1) is true. The next fraction is \( \frac{1}{(3(m+1)-2)(3(m+1)+1)} = \frac{1}{(3m+1)(3m+4)} \):
\( \frac{1}{1·4} + \frac{1}{4·7} + ... + \frac{1}{(3m-2)(3m+1)} + \frac{1}{(3m+1)(3m+4)} \)
= \( \frac{m}{3m+1} \) + \( \frac{1}{(3m+1)(3m+4)} \) [using the inductive hypothesis]
= \( \frac{m(3m+4)+1}{(3m+1)(3m+4)} \)
= \( \frac{3m^2+4m+1}{(3m+1)(3m+4)} \)
= \( \frac{(3m+1)(m+1)}{(3m+1)(3m+4)} \)
= \( \frac{m+1}{3m+4} \)
= \( \frac{m+1}{3(m+1)+1} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: The denominators are products of numbers in arithmetic progression with common difference 3. The partial fraction decomposition creates a telescoping sum.

Exam Tip: Verify the factorization: (3m + 1)(m + 1) = 3m² + 3m + m + 1 = 3m² + 4m + 1 ✓

Question 15. \( \frac{1}{3·5} + \frac{1}{5·7} + \frac{1}{7·9} + ... + \frac{1}{(2n+1)(2n+3)} = \frac{n}{3(2n+3)} \).
Answer: Let P(n) denote the statement: \( \frac{1}{3·5} + \frac{1}{5·7} + \frac{1}{7·9} + ... + \frac{1}{(2n+1)(2n+3)} = \frac{n}{3(2n+3)} \)

Base case - P(1): \( \frac{1}{3·5} \) = \( \frac{1}{15} \) and \( \frac{1}{3·5} \) = \( \frac{1}{15} \) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
\( \frac{1}{3·5} + \frac{1}{5·7} + ... + \frac{1}{(2m+1)(2m+3)} = \frac{m}{3(2m+3)} \)

Inductive step - Prove P(m + 1) is true. The next fraction is \( \frac{1}{(2(m+1)+1)(2(m+1)+3)} = \frac{1}{(2m+3)(2m+5)} \):
\( \frac{1}{3·5} + \frac{1}{5·7} + ... + \frac{1}{(2m+1)(2m+3)} + \frac{1}{(2m+3)(2m+5)} \)
= \( \frac{m}{3(2m+3)} \) + \( \frac{1}{(2m+3)(2m+5)} \) [using the inductive hypothesis]
= \( \frac{m(2m+5)+3}{3(2m+3)(2m+5)} \)
= \( \frac{2m^2+5m+3}{3(2m+3)(2m+5)} \)
= \( \frac{(2m+3)(m+1)}{3(2m+3)(2m+5)} \)
= \( \frac{m+1}{3(2m+5)} \)
= \( \frac{m+1}{3(2(m+1)+3)} \)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We combine the fractions with a common denominator structure and factor to reveal the pattern for m + 1.

Exam Tip: Check the factorization: (2m + 3)(m + 1) = 2m² + 2m + 3m + 3 = 2m² + 5m + 3 ✓

Question 16. 2^(2n) - 1 is divisible by 3.
Answer: Let P(n) denote the statement: "2^(2n) - 1 is divisible by 3"

Base case - P(1): 2² - 1 = 4 - 1 = 3, which is divisible by 3 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 2^(2m) - 1 is divisible by 3
This means 2^(2m) - 1 = 3k for some integer k.
Therefore, 2^(2m) = 1 + 3k.

Inductive step - Prove P(m + 1) is true:
2^(2(m+1)) - 1 = 2^(2m+2) - 1 = 2^(2m) · 2² - 1
= (1 + 3k) · 4 - 1 [substituting 2^(2m) = 1 + 3k]
= 4 + 12k - 1
= 3 + 12k
= 3(1 + 4k)

Since 3(1 + 4k) is divisible by 3, P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We multiply the expression 2^(2m) = 1 + 3k by 4 and subtract 1. The result is clearly a multiple of 3.

Exam Tip: For divisibility proofs, always express the assumption as an equation (like 2^(2m) - 1 = 3k) early - this makes substitution straightforward.

Question 17. 2^(3n) - 1 is divisible by 7.
Answer: Let P(n) denote the statement: "2^(3n) - 1 is divisible by 7"

Base case - P(1): 2³ - 1 = 8 - 1 = 7, which is divisible by 7 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 2^(3m) - 1 is divisible by 7
This means 2^(3m) - 1 = 7λ for some integer λ.
Therefore, 2^(3m) = 1 + 7λ.

Inductive step - Prove P(m + 1) is true:
2^(3(m+1)) - 1 = 2^(3m+3) - 1 = 2^(3m) · 2³ - 1
= (1 + 7λ) · 8 - 1 [substituting 2^(3m) = 1 + 7λ]
= 8 + 56λ - 1
= 7 + 56λ
= 7(1 + 8λ)

Since 7(1 + 8λ) is divisible by 7, P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: When we multiply by 8 and subtract 1, we get a number that has 7 as a factor.

Exam Tip: Notice the pattern - 2^(3n) - 1 is always divisible by 7 because 2³ = 8 ≡ 1 (mod 7), so 2^(3n) ≡ 1 (mod 7).

Question 18. 3^(2n) when divided by 8, leaves the remainder 1.
Answer: Let P(n) denote the statement: "3^(2n) when divided by 8, leaves the remainder 1" or equivalently "3^(2n) ≡ 1 (mod 8)"

Base case - P(1): 3² = 9 = 8 · 1 + 1, so remainder is 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 3^(2m) ≡ 1 (mod 8)
This means 3^(2m) = 1 + 8t for some integer t.

Inductive step - Prove P(m + 1) is true:
3^(2(m+1)) = 3^(2m+2) = 3^(2m) · 3²
= (1 + 8t) · 9 [substituting 3^(2m) = 1 + 8t]
= 9 + 72t
= 8 + 1 + 72t
= 8(1 + 9t) + 1

This shows 3^(2(m+1)) leaves remainder 1 when divided by 8, so P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: When we multiply 3^(2m) by 9, we get something that is 1 more than a multiple of 8.

Exam Tip: For remainder problems, express as "number = divisor × quotient + remainder" and verify the remainder part in each step.

Question 19. 10^(2n-1) + 1 is divisible by 11.
Answer: Let P(n) denote the statement: "10^(2n-1) + 1 is divisible by 11"

Base case - P(1): 10¹ + 1 = 11, which is divisible by 11 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 10^(2m-1) + 1 is divisible by 11
This means 10^(2m-1) + 1 = 11s for some integer s.
Therefore, 10^(2m-1) = 11s - 1.

Inductive step - Prove P(m + 1) is true:
10^(2(m+1)-1) + 1 = 10^(2m+1) + 1 = 10^(2m-1) · 10² + 1
= (11s - 1) · 100 + 1 [substituting 10^(2m-1) = 11s - 1]
= 1100s - 100 + 1
= 1100s - 99
= 11(100s - 9)

Since 11(100s - 9) is divisible by 11, P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We multiply by 100 and add 1, then factor out 11 from the result.

Exam Tip: Use the inductive hypothesis to substitute for 10^(2m-1), then simplify to show a multiple of 11 appears.

Question 20. 7^n - 3^n is divisible by 4.
Answer: Let P(n) denote the statement: "7^n - 3^n is divisible by 4"

Base case - P(1): 7¹ - 3¹ = 7 - 3 = 4, which is divisible by 4 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 7^m - 3^m is divisible by 4
This means 7^m - 3^m = 4u for some integer u.
Therefore, 7^m = 3^m + 4u.

Inductive step - Prove P(m + 1) is true:
7^(m+1) - 3^(m+1) = 7 · 7^m - 3 · 3^m
= 7(3^m + 4u) - 3 · 3^m [substituting 7^m = 3^m + 4u]
= 7 · 3^m + 28u - 3 · 3^m
= 4 · 3^m + 28u
= 4(3^m + 7u)

Since 4(3^m + 7u) is divisible by 4, P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We rewrite 7^m using the inductive hypothesis, then rearrange to factor out 4.

Exam Tip: When the statement involves differences of powers, use the inductive hypothesis to express one power in terms of the other.

Question 21. 4^n + 15n - 1 is divisible by 9.
Answer: Let P(n) denote the statement: "4^n + 15n - 1 is divisible by 9"

Base case - P(1): 4¹ + 15(1) - 1 = 4 + 15 - 1 = 18 = 9 · 2, which is divisible by 9 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 4^m + 15m - 1 is divisible by 9
This means 4^m + 15m - 1 = 9v for some integer v.
Therefore, 4^m = 9v - 15m + 1.

Inductive step - Prove P(m + 1) is true:
4^(m+1) + 15(m + 1) - 1 = 4 · 4^m + 15m + 15 - 1
= 4(9v - 15m + 1) + 15m + 14 [substituting 4^m = 9v - 15m + 1]
= 36v - 60m + 4 + 15m + 14
= 36v - 45m + 18
= 9(4v - 5m + 2)

Since 9(4v - 5m + 2) is divisible by 9, P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We replace 4^m using the inductive hypothesis and collect all the terms. The result is clearly a multiple of 9.

Exam Tip: Be careful with signs and coefficients when expanding - here multiplying by 4 required distributing to all three terms of 9v - 15m + 1.

Question 22. 3^(2n+2) - 8n - 9 is a multiple of 64.
Answer: Let P(n) denote the statement: "3^(2n+2) - 8n - 9 is a multiple of 64"

Base case - P(1): 3^(2·1+2) - 8(1) - 9 = 3⁴ - 8 - 9 = 81 - 17 = 64 = 64 · 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 3^(2m+2) - 8m - 9 is a multiple of 64
This means 3^(2m+2) - 8m - 9 = 64w for some integer w.
Therefore, 3^(2m+2) = 64w + 8m + 9.

Inductive step - Prove P(m + 1) is true:
3^(2(m+1)+2) - 8(m + 1) - 9 = 3^(2m+4) - 8m - 8 - 9
= 9 · 3^(2m+2) - 8m - 17
= 9(64w + 8m + 9) - 8m - 17 [substituting 3^(2m+2) = 64w + 8m + 9]
= 576w + 72m + 81 - 8m - 17
= 576w + 64m + 64
= 64(9w + m + 1)

Since 64(9w + m + 1) is a multiple of 64, P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We use the inductive hypothesis to replace 3^(2m+2), then collect and factor out 64 from all remaining terms.

Exam Tip: For problems involving larger divisors like 64, always check your arithmetic carefully - a single error in collecting terms will invalidate the proof.

Question 23. n(n + 1)(n + 5) is a multiple of 3.
Answer: Let P(n) denote the statement: "n(n + 1)(n + 5) is a multiple of 3"

Base case - P(1): 1(2)(6) = 12 = 3 · 4, which is a multiple of 3 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: m(m + 1)(m + 5) is a multiple of 3
This means m(m + 1)(m + 5) = 3x for some integer x.

Inductive step - Prove P(m + 1) is true:
(m + 1)(m + 2)(m + 6) = (m + 1)(m + 2)(m + 5 + 1)
= (m + 1)(m + 2)(m + 5) + (m + 1)(m + 2)
= (m + 1)[(m + 2)(m + 5) + (m + 2)]
= (m + 1)(m + 2)[m + 5 + 1]

Alternatively, note that among any three consecutive integers m, m+1, m+2, at least one is divisible by 3. Also, among m, m+1, m+5, we can check their residues modulo 3:

- If 3|m, then 3|m(m+1)(m+5) ✓
- If 3|(m+1), then 3|(m+1)(m+2)(m+6) ✓
- If 3|(m+5), then m ≡ 1 (mod 3), so m+2 ≡ 0 (mod 3), thus 3|(m+1)(m+2)(m+6) ✓

So P(m + 1) is true in all cases.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: In any group of consecutive integers, at least one is divisible by 3. Since our expression involves products of numbers that are either consecutive or close together, one of them must always be divisible by 3.

Exam Tip: For divisibility by small numbers like 3, checking residue classes modulo 3 is often clearer than algebraic expansion.

Question 24. n³ + (n + 1)³ + (n + 2)³ is a multiple of 9.
Answer: Let P(n) denote the statement: "n³ + (n + 1)³ + (n + 2)³ is a multiple of 9"

Base case - P(1): 1³ + 2³ + 3³ = 1 + 8 + 27 = 36 = 9 · 4, which is a multiple of 9 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true:
m³ + (m + 1)³ + (m + 2)³ is a multiple of 9
This means m³ + (m + 1)³ + (m + 2)³ = 9y for some integer y.

Inductive step - Prove P(m + 1) is true:
(m + 1)³ + (m + 2)³ + (m + 3)³
= (m + 1)³ + (m + 2)³ + [(m + 2) + 1]³

We know m³ + (m + 1)³ + (m + 2)³ = 9y.

Now, (m + 1)³ + (m + 2)³ + (m + 3)³ - [m³ + (m + 1)³ + (m + 2)³]
= (m + 3)³ - m³
= (m³ + 9m² + 27m + 27) - m³
= 9m² + 27m + 27
= 9(m² + 3m + 3)

Therefore, (m + 1)³ + (m + 2)³ + (m + 3)³ = 9y + 9(m² + 3m + 3) = 9(y + m² + 3m + 3)

So P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: The difference between consecutive triples of cubes is always a multiple of 9. Since the base case is true, all subsequent cases remain multiples of 9.

Exam Tip: When working with consecutive terms like (m+1), (m+2), (m+3), compute the difference from the previous case rather than expanding everything from scratch.

Question 25. x^(2n-1) - 1 is divisible by (x - 1), x ≠ 1.
Answer: Let P(n) denote the statement: "x^(2n-1) - 1 is divisible by (x - 1)"

Base case - P(1): x^(2·1-1) - 1 = x¹ - 1 = x - 1, which is clearly divisible by (x - 1) ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: x^(2m-1) - 1 is divisible by (x - 1)
This means x^(2m-1) - 1 = (x - 1)z for some polynomial z.
Therefore, x^(2m-1) = 1 + (x - 1)z.

Inductive step - Prove P(m + 1) is true:
x^(2(m+1)-1) - 1 = x^(2m+1) - 1 = x² · x^(2m-1) - 1
= x² [1 + (x - 1)z] - 1 [substituting x^(2m-1) = 1 + (x - 1)z]
= x² + x²(x - 1)z - 1
= (x² - 1) + x²(x - 1)z
= (x - 1)(x + 1) + x²(x - 1)z
= (x - 1)[(x + 1) + x²z]

Since this equals (x - 1) times a polynomial expression, P(m + 1) is divisible by (x - 1), so P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: We replace x^(2m-1) using the inductive hypothesis and factor out (x - 1) from the resulting expression.

Exam Tip: For polynomial divisibility, always express divisibility as an equation with a polynomial cofactor - this makes it clear how to combine terms.

Question 26. 3^n > n for all n ∈ N.
Answer: Let P(n) denote the statement: "3^n > n"

Base case - P(1): 3¹ > 1, i.e., 3 > 1 ✓ This is true, so P(1) is true.

Inductive hypothesis - Assume P(m) is true: 3^m > m

Inductive step - Prove P(m + 1) is true. We need 3^(m+1) > m + 1.

From P(m), we have 3^m > m.
Multiply both sides by 3:
3 · 3^m > 3 · m
3^(m+1) > 3m

For m ≥ 1, we have 3m ≥ 3 > m + 1. More precisely, 3m - m - 1 = 2m - 1 ≥ 1 > 0 for m ≥ 1.

Therefore, 3^(m+1) > 3m > m + 1, which means P(m + 1) is true.

By the principle of mathematical induction, P(n) is true for all n ∈ N.
In simple words: When you triple both sides of 3^m > m, you get 3^(m+1) > 3m. Since 3m is much larger than m + 1 for any positive m, the inequality still holds.

Exam Tip: When comparing 3m with m + 1, show the difference: 3m - (m + 1) = 2m - 1 ≥ 1 - this makes it obvious why the inequality holds.