1. Mathematical induction is a proof technique used to show that a statement is true for all natural numbers $n \geq k$, where $k$ is a starting point, usually 1. 2. It has two main steps: - Base Case: Prove the statement is true for the initial value $n=k$. - Inductive Step: Assume the statement is true for $n=m$ (inductive hypothesis) and then prove it must be true for $n=m+1$. 3. Example 1: Prove that the sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$. - Base Case ($n=1$): $1 = \frac{1(1+1)}{2} = 1$, true. - Inductive Step: Assume $1+2+\dots+m = \frac{m(m+1)}{2}$. Then for $n=m+1$: $1+2+\dots+m+(m+1) = \frac{m(m+1)}{2} + (m+1) = \frac{m(m+1) + 2(m+1)}{2} = \frac{(m+1)(m+2)}{2}$, which matches the formula for $n=m+1$. Thus proven by induction. 4. Example 2: Prove $2^n \geq n+1$ for all $n \geq 1$. - Base Case ($n=1$): $2^1=2 \geq 2=1+1$, true. - Inductive Step: Assume $2^m \geq m+1$. Then $2^{m+1} = 2 \cdot 2^m \geq 2(m+1)$ since $2^m \geq m+1$. We need to show $2(m+1) \geq m+2$, or $2m+2 \geq m+2$ which simplifies to $m \geq 0$, true for all $m \geq 1$. Conclusion: $2^n \geq n+1$ holds by induction. 5. Induction is very useful to prove properties, formulas, and inequalities defined recursively or for all integers.