(Exercises for Students) Classroom Exercise: Allow students to prove the following by mathematical induction 1. Prove that the sum of the first \( n \) odd numbers equals \( n^{2} \). 2. The sum of the first \( n \) natural numbers is \( (1 / 2) n(n+1) \). 3. \( 4^{n}-1 \) is diviciblen

Certainly! Here's a comprehensive guide for each of the exercises you've provided. These solutions use **mathematical induction**, a powerful technique for proving statements that are asserted to be true for all natural numbers \( n \). --- ### **Exercise 1:** **Prove that the sum of the first \( n \) odd numbers equals \( n^{2} \).** **Statement:** \[ 1 + 3 + 5 + \dots + (2n - 1) = n^2 \] #### **Proof by Mathematical Induction:** **1. Base Case (\( n = 1 \)):** Calculate the sum of the first odd number: \[ 1 = 1^2 \] Both sides equal 1. Thus, the base case holds true. **2. Inductive Hypothesis:** Assume that the statement is true for some arbitrary positive integer \( k \): \[ 1 + 3 + 5 + \dots + (2k - 1) = k^2 \] **3. Inductive Step:** We need to show that the statement holds for \( k + 1 \), i.e., \[ 1 + 3 + 5 + \dots + (2k - 1) + [2(k + 1) - 1] = (k + 1)^2 \] Start with the left-hand side (LHS): \[ \begin{align*} \text{LHS} &= \left(1 + 3 + 5 + \dots + (2k - 1)\right) + [2(k + 1) - 1] \\ &= k^2 + [2k + 2 - 1] \quad \text{(Using the inductive hypothesis)} \\ &= k^2 + (2k + 1) \\ &= k^2 + 2k + 1 \\ &= (k + 1)^2 \\ \end{align*} \] Which matches the right-hand side (RHS). **4. Conclusion:** By the principle of mathematical induction, the statement holds true for all natural numbers \( n \). --- ### **Exercise 2:** **Prove that the sum of the first \( n \) natural numbers is \( \frac{1}{2} n(n + 1) \).** **Statement:** \[ 1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2} \] #### **Proof by Mathematical Induction:** **1. Base Case (\( n = 1 \)):** Calculate the sum of the first natural number: \[ 1 = \frac{1(1 + 1)}{2} = \frac{2}{2} = 1 \] Both sides equal 1. Thus, the base case holds true. **2. Inductive Hypothesis:** Assume that the statement is true for some arbitrary positive integer \( k \): \[ 1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2} \] **3. Inductive Step:** We need to show that the statement holds for \( k + 1 \), i.e., \[ 1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2} \] Start with the left-hand side (LHS): \[ \begin{align*} \text{LHS} &= \left(1 + 2 + 3 + \dots + k\right) + (k + 1) \\ &= \frac{k(k + 1)}{2} + (k + 1) \quad \text{(Using the inductive hypothesis)} \\ &= \frac{k(k + 1) + 2(k + 1)}{2} \\ &= \frac{(k + 1)(k + 2)}{2} \\ &= \text{RHS} \end{align*} \] **4. Conclusion:** By the principle of mathematical induction, the statement holds true for all natural numbers \( n \). --- ### **Exercise 3:** **Prove that \( 4^{n} - 1 \) is divisible by 3 for all natural numbers \( n \).** **Statement:** \[ 4^{n} - 1 \text{ is divisible by } 3 \] #### **Proof by Mathematical Induction:** **1. Base Case (\( n = 1 \)):** Calculate \( 4^1 - 1 \): \[ 4^1 - 1 = 4 - 1 = 3 \] 3 is divisible by 3. Thus, the base case holds true. **2. Inductive Hypothesis:** Assume that the statement is true for some arbitrary positive integer \( k \): \[ 4^{k} - 1 \text{ is divisible by } 3 \] This means there exists an integer \( m \) such that: \[ 4^{k} - 1 = 3m \] **3. Inductive Step:** We need to show that the statement holds for \( k + 1 \), i.e., \[ 4^{k + 1} - 1 \text{ is divisible by } 3 \] Start by expressing \( 4^{k + 1} \): \[ \begin{align*} 4^{k + 1} &= 4 \cdot 4^{k} \\ &= (3 + 1) \cdot 4^{k} \\ &= 3 \cdot 4^{k} + 4^{k} \\ \end{align*} \] Now, compute \( 4^{k + 1} - 1 \): \[ \begin{align*} 4^{k + 1} - 1 &= 3 \cdot 4^{k} + 4^{k} - 1 \\ &= 3 \cdot 4^{k} + (4^{k} - 1) \\ \end{align*} \] From the inductive hypothesis, \( 4^{k} - 1 = 3m \). Substitute this: \[ \begin{align*} 4^{k + 1} - 1 &= 3 \cdot 4^{k} + 3m \\ &= 3(4^{k} + m) \\ \end{align*} \] Since \( 4^{k} + m \) is an integer, \( 4^{k + 1} - 1 \) is divisible by 3. **4. Conclusion:** By the principle of mathematical induction, \( 4^{n} - 1 \) is divisible by 3 for all natural numbers \( n \). --- **Summary:** Mathematical induction is a systematic method to prove statements for all natural numbers. The process involves: 1. **Base Case:** Verify the statement for the initial value (usually \( n = 1 \)). 2. **Inductive Hypothesis:** Assume the statement holds for an arbitrary \( n = k \). 3. **Inductive Step:** Prove the statement for \( n = k + 1 \) using the hypothesis. 4. **Conclusion:** Establish that the statement is valid for all natural numbers. Feel free to use these proofs as models for guiding students through similar induction problems!