Deduction, contradiction and induction
Introducido| English | Significado |
|---|---|
| proof by induction | A proof that shows a statement is true for n = 1 and that truth for n = k implies truth for n = k + 1. |
| basis/ˈbeɪsɪs/ | The first part of an induction proof, showing the statement is true for the first value, usually n = 1. |
| inductive step/ɪnˈdʌktɪv step/ | The part of an induction proof that uses the case n = k to prove the case n = k + 1. |
Maurolico's odd numbers, 1575
- In 1575, the Sicilian monk Francesco Maurolico proved that the first $n$ odd numbers add to $n^2$. He showed it holds for 1, and that whenever it holds for one number it holds for the next — the first known proof by induction 数学归纳法.
- Like a line of dominoes: knock over the first, and make sure each one knocks over the next, and every domino falls.
The four parts of an induction proof
- Basis 基础步骤: show the statement is true for $n = 1$.
- Assumption and inductive step 归纳步骤: assume it is true for $n = k$, and use that to show it is true for $n = k + 1$. Conclusion: write the standard sentence that it is therefore true for all $n \in \mathbb{Z}^+$.
Deduction, contradiction and induction
A deductive proof starts from stated definitions or assumptions
Distinguish a proof for all integers from one counterexample.
Put the parts of an induction proof in order.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Basis, assumption, step, conclusion.
Induction on a sum
- To prove $\displaystyle\sum_{r=1}^{n}(2r - 1) = n^2$: for $n = 1$, both sides are 1.
- Assume $\displaystyle\sum_{r=1}^{k}(2r - 1) = k^2$. Then $\displaystyle\sum_{r=1}^{k+1}(2r - 1) = k^2 + (2k + 1) = (k + 1)^2$, which is the formula with $n = k + 1$.
In proving $\sum_{r=1}^{n} r = \tfrac{1}{2}n(n + 1)$, what do you add to $\tfrac{1}{2}k(k + 1)$ in the step?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The sum to $k + 1$ is the sum to $k$ plus the term $r = k + 1$.
Worked example: divisibility
Prove by induction that $f(n) = 3^{2n} + 11$ is divisible by 4 for all $n \in \mathbb{Z}^+$.
- Basis: $f(1) = 9 + 11 = 20 = 4 \times 5$ ✓.
- Step: assume $4 \mid f(k)$. Then $f(k + 1) - f(k) = 9 \cdot 3^{2k} - 3^{2k} = 8 \cdot 3^{2k}$, so $f(k + 1) = f(k) + 8 \cdot 3^{2k}$. Both terms are divisible by 4, so $4 \mid f(k + 1)$.
- Conclusion: true for $n = 1$, and if true for $n = k$ then true for $n = k + 1$; so by induction it is true for all $n \in \mathbb{Z}^+$.
A favor $f(n) = 7^n - 1$, which is divisible by 6, find $f(1)$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$7 - 1 = 6 = 6 \times 1$, so the basis holds.
A favor $f(n) = 7^n - 1$, what is $f(k + 1) - f(k)$?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
$7^{k+1} - 7^k = 7^k(7 - 1) = 6 \cdot 7^k$, which is divisible by 6.
Induction on matrices
- Prove $\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}^n = \begin{pmatrix}1 & n\\0 & 1\end{pmatrix}$: for $n = 1$ it is the matrix itself.
- Assume it for $k$; then $\begin{pmatrix}1 & k\\0 & 1\end{pmatrix}\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix} = \begin{pmatrix}1 & k + 1\\0 & 1\end{pmatrix}$, as required.
If $\mathbf{M}^k = \begin{pmatrix}1 & k\\0 & 1\end{pmatrix}$, then $\mathbf{M}^{k+1} = \mathbf{M}^k\mathbf{M}$ gives the top-right entry $k + 1$.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Row 1 times column 2: $1 \times 1 + k \times 1 = k + 1$.
Induction on a recurrence
- $u_1 = 2$ and $u_{n+1} = 3u_n - 2$. Prove that $u_n = 3^{n-1} + 1$. Basis: $u_1 = 3^0 + 1 = 2$ ✓.
- Assume $u_k = 3^{k-1} + 1$. Then $u_{k+1} = 3(3^{k-1} + 1) - 2 = 3^k + 1$, which is the formula with $n = k + 1$.
$u_1 = 2$ y $u_{n+1} = 3u_n - 2$, so $u_n = 3^{n-1} + 1$. Find $u_5$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$3^4 + 1 = 82$; check: $2, 4, 10, 28, 82$.
Checking several cases instead of proving the step. Showing that $n = 1, 2, 3$ work is not a proof: $n^2 - n + 41$ is prime for $n = 1$ to 40 and fails at $n = 41$. The marks are for using the $n = k$ assumption to reach $n = k + 1$, and for the conclusion sentence.
An induction proof has a basis ($n = 1$), an assumption ($n = k$), a step that uses the assumption to prove $n = k + 1$, and a conclusion for all positive integers. It works for sums, divisibility, matrix powers and recurrences.
Prove by induction that $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n + 1)(2n + 1)}{6}$ for all $n \in \mathbb{Z}^+$.
All four parts earn marks.