Mathematical Induction Notes

Mathematical Induction

Introduction

• The core idea revolves around proving a statement $P(n)$ is true for all nonnegative integers $n$.

• It's based on two key conditions:

  • Base Case: $P(0)$ is true.

  • Inductive Step: For every nonnegative integer $k$, if $P(k)$ is true, then $P(k+1)$ is true ($P(k) \rightarrow P(k+1)$).

Domino Analogy

• Each domino represents a proposition $P(n)$.

• Domino 0 corresponds to $P(0)$, Domino 1 to $P(1)$, and so on.

• Knocking over a domino is akin to proving that the corresponding proposition holds true.

Examples

1. Sum of first n integers:

   • $0 + 1 + … + n = \frac{n(n+1)}{2}$ for each $n \ge 0$.

2. Sum of the first n odd integers:

   • $1 + 3 + 5 + … + (2n-1) = n^2$ for all $n \ge 1$.

3. Divisibility by 7:

   • $8^n - 1$ is divisible by 7 for all $n \ge 0$.

Proof by Contradiction

• Assume that both conditions of mathematical induction hold.

• Suppose $P(n)$ is not true for every nonnegative integer $n$.

• Then, there must exist an n such that P(n) is false.

• Let $n^{}$ be the smallest such integer (a "minimal criminal").

• P(n)is false, butP(n-1) is true, which contradicts condition 2.

Detailed Example 1: Sum of First n Integers

• Proposition: $0 + 1 + 2 + … + n = \frac{n(n+1)}{2}$

Base Case

• When $n = 0$, the left-hand side (LHS) is 0.

• The right-hand side (RHS) is also 0.

• Since LHS = RHS, the base case holds.

Inductive Case

• Induction Hypothesis: Assume $P(k)$ is true, i.e., $0 + 1 + 2 + … + k = \frac{k(k+1)}{2}$.

• Goal: Show that $P(k+1)$ is true.

• LHS of $P(k+1)$: $0 + 1 + 2 + … + k + (k+1)$.

• Using the induction hypothesis:

  • $0 + 1 + 2 + … + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$

  • $= (k+1)(\frac{k}{2} + 1) = (k+1)(\frac{k+2}{2}) = \frac{(k+1)(k+2)}{2}$

• This is the RHS of $P(k+1)$, so the inductive step holds.

Conditions for Mathematical Induction

• Both conditions (base case and inductive step) are necessary.

• If the base case fails (e.g., domino 0 is nailed to the floor), we cannot start the chain reaction.

• If the inductive step fails (e.g., a large gap between dominos), the chain reaction will break.

Detailed Example 2: Sum of First n Odd Integers

• Proposition: The sum of the first $n$ odd integers is $n^2$ for all $n \ge 1$.

Base Case

• For $n=1$, the sum of the first odd integer is 1, which is equal to $1^2$.

Inductive Case

• Let $k$ be some positive integer, and assume $P(k)$ holds. That is:

  • $1 + 3 + 5 + … + (2k-1) = k^2$

• We want to show that the sum of the first $k+1$ odd integers is $(k+1)^2$.

• $1 + 3 + 5 + … + (2k-1) + (2k+1) = k^2 + (2k+1) = (k+1)^2$

• Therefore, $P(k+1)$ holds.

Detailed Example 3: Divisibility by 7

• Proposition: $8^n - 1$ is divisible by 7 for all $n \ge 0$.

Base Case

• When $n = 0$, $8^0 - 1 = 1 - 1 = 0$, which is divisible by 7. Thus, $P(0)$ is true.

Inductive Case

• Assume $P(k)$ holds (i.e., $8^k - 1$ is divisible by 7 for some $k \ge 0$).

• This means $8^k - 1 = 7l$ for some integer $l$.

• Now consider $8^{k+1} - 1$:

  • $8^{k+1} - 1 = 8 Imes 8^k - 1 = 8 Imes (7l + 1) - 1 = 8 Imes 7l + 8 - 1 = 8 Imes 7l + 7 = 7(8l + 1)$

• Since $8l + 1$ is an integer, $8^{k+1} - 1$ is divisible by 7. Therefore, $P(k+1)$ holds.