krit.club logo

Number and Algebra - Mathematical induction (HL)

Grade 12IB_AA

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

The Principle of Mathematical Induction (PMI) is a formal method of proof used to show that a statement P(n)P(n) is true for all natural numbers n∈Z+n \in \mathbb{Z}^+ (or for n≥n0n \geq n_0).

•

Basis Step: Prove that the statement holds for the smallest possible value of nn, usually n=1n = 1. This is denoted as showing P(1)P(1) is true.

•

Inductive Hypothesis: Assume that the statement is true for some arbitrary positive integer kk, i.e., assume P(k)P(k) is true.

•

Inductive Step: Use the assumption P(k)P(k) to prove that the statement must also be true for the next integer k+1k+1, i.e., prove P(k)  ⟹  P(k+1)P(k) \implies P(k+1).

•

Conclusion: State that since P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), then by the Principle of Mathematical Induction, P(n)P(n) is true for all n∈Z+n \in \mathbb{Z}^+.

•

Common applications in IB AA HL include proving series summations, divisibility rules, inequalities, and expressions for the nthn^{th} derivative or powers of matrices.

📐Formulae

Step 1: Show P(1) is true.\text{Step 1: Show } P(1) \text{ is true.}

Step 2: Assume P(k) is true: ∑r=1kf(r)=Sk\text{Step 2: Assume } P(k) \text{ is true: } \sum_{r=1}^{k} f(r) = S_k

Step 3: Prove P(k+1) is true: Sk+1=Sk+f(k+1)\text{Step 3: Prove } P(k+1) \text{ is true: } S_{k+1} = S_k + f(k+1)

Divisibility: f(n)=M⋅m where M is the divisor and m∈Z\text{Divisibility: } f(n) = M \cdot m \text{ where } M \text{ is the divisor and } m \in \mathbb{Z}

💡Examples

Problem 1:

Prove by mathematical induction that ∑r=1n(2r−1)=n2\sum_{r=1}^{n} (2r - 1) = n^2 for all n∈Z+n \in \mathbb{Z}^+.

Solution:

Let P(n)P(n) be the statement ∑r=1n(2r−1)=n2\sum_{r=1}^{n} (2r - 1) = n^2.

Basis Step: For n=1n=1: LHS=2(1)−1=1LHS = 2(1) - 1 = 1 RHS=12=1RHS = 1^2 = 1 Since LHS=RHSLHS = RHS, P(1)P(1) is true.

Inductive Hypothesis: Assume P(k)P(k) is true for some k∈Z+k \in \mathbb{Z}^+: ∑r=1k(2r−1)=k2\sum_{r=1}^{k} (2r - 1) = k^2

Inductive Step: We need to prove P(k+1)P(k+1) is true, i.e., ∑r=1k+1(2r−1)=(k+1)2\sum_{r=1}^{k+1} (2r - 1) = (k+1)^2. ∑r=1k+1(2r−1)=[∑r=1k(2r−1)]+[2(k+1)−1]\sum_{r=1}^{k+1} (2r - 1) = \left[ \sum_{r=1}^{k} (2r - 1) \right] + [2(k+1) - 1] Using the inductive hypothesis: =k2+(2k+2−1)= k^2 + (2k + 2 - 1) =k2+2k+1= k^2 + 2k + 1 =(k+1)2= (k+1)^2 This is the required RHS for P(k+1)P(k+1).

Conclusion: Since P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), the statement is true for all n∈Z+n \in \mathbb{Z}^+ by the Principle of Mathematical Induction.

Explanation:

This example demonstrates the standard summation proof. We isolate the (k+1)th(k+1)^{th} term, substitute the hypothesis for the sum of the first kk terms, and use algebraic expansion/factoring to reach the goal.

Problem 2:

Prove that 7n−17^n - 1 is divisible by 66 for all n∈Z+n \in \mathbb{Z}^+.

Solution:

Let P(n)P(n) be the statement 7n−1=6m7^n - 1 = 6m for some m∈Zm \in \mathbb{Z}.

Basis Step: For n=1n=1: 71−1=67^1 - 1 = 6, which is divisible by 66. So P(1)P(1) is true.

Inductive Hypothesis: Assume P(k)P(k) is true: 7k−1=6A7^k - 1 = 6A for some A∈ZA \in \mathbb{Z}. This implies 7k=6A+17^k = 6A + 1.

Inductive Step: Consider n=k+1n = k+1: 7k+1−1=7⋅7k−17^{k+1} - 1 = 7 \cdot 7^k - 1 Substitute the hypothesis 7k=6A+17^k = 6A + 1: =7(6A+1)−1= 7(6A + 1) - 1 =42A+7−1= 42A + 7 - 1 =42A+6= 42A + 6 =6(7A+1)= 6(7A + 1) Since AA is an integer, (7A+1)(7A + 1) is an integer. Thus, 7k+1−17^{k+1} - 1 is divisible by 66.

Conclusion: Since P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), the statement is true for all n∈Z+n \in \mathbb{Z}^+.

Explanation:

For divisibility proofs, the key is to express f(k+1)f(k+1) in terms of f(k)f(k) and then factor out the divisor.