Mathematical Induction Principle

• Mathematical induction establishes a given statement for all natural numbers greater than or equal to some initial value.

Principle of Mathematical Induction

• Base Case: Proof that the statement is true for the initial value (e.g., n = 1).
• Inductive Hypothesis: Assume the statement is true for an arbitrary natural number k (where k is greater than or equal to the initial value).
• Inductive Step: Demonstrate that if the statement is true for k, then it must also be true for k + 1.
• Conclusion: If the base case and inductive step are both proven, the statement is true for all natural numbers greater than or equal to the initial value by the principle of mathematical induction.

Steps for Mathematical Induction

• State the proposition: Clearly define the statement P(n) you want to prove for all n ≥ b, where b is usually 1 but can be any integer.
• Base case: Show that P(b) is true by substituting n = b into the statement and verifying that it holds.
• Inductive hypothesis: Assume that P(k) is true for some arbitrary integer k ≥ b; this assumption is crucial for the next step.
• Inductive step: Prove that P(k+1) is true, assuming that P(k) is true. This is done by manipulating the expression for P(k+1) and using the assumption that P(k) is true to show that P(k+1) also holds.
• Conclusion: State that by the principle of mathematical induction, P(n) is true for all integers n ≥ b.

Example: Sum of the First n Natural Numbers

• Proposition: Prove that 1 + 2 + 3 + ... + n = n(n+1)/2 for all natural numbers n.
• Base Case: For n = 1, the left-hand side is 1, and the right-hand side is 1(1+1)/2 = 1, thus the statement is true for n = 1.
• Inductive Hypothesis: Assume that 1 + 2 + 3 + ... + k = k(k+1)/2 for some natural number k.
• Inductive Step: Prove that 1 + 2 + 3 + ... + (k + 1) = (k + 1)(k + 2)/2.
• Starting with the left-hand side: 1 + 2 + 3 + ... + (k + 1) = (1 + 2 + 3 + ... + k) + (k + 1)
• Using the inductive hypothesis: = k(k+1)/2 + (k + 1)
• = [*k(k+1) + 2(k+1)] / 2
• = (k² + k + 2k + 2) / 2
• = (k² + 3k + 2) / 2
• = (k + 1)(k + 2) / 2
• This equals the right-hand side, so the statement is true for n = k + 1.
• Conclusion: By the principle of mathematical induction, 1 + 2 + 3 + ... + n = n(n+1)/2 for all natural numbers n.

Example: Divisibility

• Proposition: Prove that n³ - n is divisible by 3 for all natural numbers n.
• Base Case: For n = 1, 1³ - 1 = 0, which is divisible by 3.
• Inductive Hypothesis: Assume that k³ - k is divisible by 3 for some natural number k, implying k³ - k = 3m for some integer m.
• Inductive Step: Prove that (k + 1)³ - (k + 1) is divisible by 3.
• (k + 1)³ - (k + 1) = k³ + 3k² + 3k + 1 - k - 1
• = k³ - k + 3k² + 3k
• = (k³ - k) + 3(k² + k)
• Using the inductive hypothesis, k³ - k = 3m:
• = 3m + 3(k² + k)
• = 3(m + k² + k)
• Since m + k² + k is an integer, (k + 1)³ - (k + 1) is divisible by 3.
• Conclusion: By the principle of mathematical induction, n³ - n is divisible by 3 for all natural numbers n.

Example: Inequality

• Proposition: Prove that 2ⁿ > n for all natural numbers n ≥ 1.
• Base Case: For n = 1, 2¹ = 2 > 1, so the statement is true.
• Inductive Hypothesis: Assume that 2ᵏ > k for some natural number k ≥ 1.
• Inductive Step: Prove that 2ᵏ⁺¹ > k + 1.
• Starting with the left-hand side, 2ᵏ⁺¹ = 2 * 2ᵏ.
• Using the inductive hypothesis, 2ᵏ > k, so 2 * 2ᵏ > 2k.
• Therefore, 2ᵏ⁺¹ > 2k.
• If 2k ≥ k + 1, then 2ᵏ⁺¹ > k + 1.
• 2k ≥ k + 1 is equivalent to k ≥ 1, which is true by our assumption.
• Thus, 2ᵏ⁺¹ > 2k ≥ k + 1, hence 2ᵏ⁺¹ > k + 1.
• Conclusion: By the principle of mathematical induction, 2ⁿ > n for all natural numbers n ≥ 1.

Common Mistakes

• Forgetting the base case can invalidate the entire proof.
• The inductive hypothesis must be clearly stated and used correctly in the inductive step.
• The inductive step must logically show that if P(k) is true, then P(k+1) must also be true.
• Avoid assumptions or skipping steps in the inductive step.
• Errors in algebraic manipulation can invalidate the proof.

Strong Induction

• Strong induction differs from weak induction in the inductive hypothesis.
• Instead of assuming P(k) is true only for k, strong induction assumes P(j) is true for all j such that b ≤ j ≤ k, where b is the base case.
• This allows you to use the truth of multiple previous cases to prove the truth of the next case, P(k+1).

When to Use Strong Induction

• Use strong induction when the truth of P(k+1) depends on the truth of more than just P(k).
• Use strong induction in situations where you need to refer back to multiple previous values to prove the next one.
• Applicable to problems involving recursively defined sequences or algorithms where the next term depends on several previous terms.

Example: Fibonacci Sequence

• Proposition: Show that every Fibonacci number F(n) can be written as a sum of distinct Fibonacci numbers, where the numbers in the sum are smaller than F(n).
• Base Cases:
  • F(1) = 1, which is trivially true (no smaller Fibonacci numbers to sum).
  • F(2) = 1, same as above.
  • F(3) = 2, which is also trivially true.
• Inductive Hypothesis: Assume that F(j) can be written as a sum of distinct Fibonacci numbers smaller than F(j) for all j such that 1 ≤ j ≤ k.
• Inductive Step: Prove that F(k+1) can be written as a sum of distinct Fibonacci numbers smaller than F(k+1).
• By definition, F(k+1) = F(k) + F(k-1).
• By the inductive hypothesis, F(k) can be written as a sum of distinct Fibonacci numbers smaller than F(k), and F(k-1) can be written as a sum of distinct Fibonacci numbers smaller than F(k-1).
• Therefore, F(k+1) can be written as a sum of distinct Fibonacci numbers that are smaller than F(k) and F(k-1), and thus also smaller than F(k+1).
• Conclusion: By the principle of strong induction, every Fibonacci number F(n) can be written as a sum of distinct Fibonacci numbers, where the numbers in the sum are smaller than F(n).