TAOCP 1.2.1: Mathematical Induction
Section 1.2.1 exercises: 15/15 solved.
Section 1.2.1. Mathematical Induction
Exercises from TAOCP Volume 1 Section 1.2.1: 15/15 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [05] | simple | verified | 31s |
| 2 | ▶ [15] | simple | verified | 35s |
| 3 | [18] | medium | verified | 37s |
| 4 | [20] | medium | verified | 27s |
| 5 | [21] | medium | verified | 38s |
| 6 | [20] | medium | solved | 3m38s |
| 7 | [23] | medium | verified | 1m46s |
| 8 | ▶ [25] | medium | verified | 1m58s |
| 9 | [20] | medium | verified | 1m28s |
| 10 | [M22] | math-medium | verified | 37s |
| 11 | [M30] | math-hard | solved | 4m32s |
| 12 | [M25] | math-medium | verified | 1m43s |
| 13 | ▶ [M23] | math-medium | solved | 4m20s |
| 14 | [50] | research | verified | 37s |
| 15 | ▶ [HM28] | hm-hard | verified | 2m18s |
TAOCP 1.2.1 Exercise 1
To prove a statement $P(n)$ for all nonnegative integers $n = 0, 1, 2, \ldots$, we modify the usual induction procedure by changing the base case.
TAOCP 1.2.1 Exercise 2
The error occurs in the inductive step when the proof attempts to establish $P(n+1)$ from the assumptions $P(1),\ldots,P(n)$.
TAOCP 1.2.1 Exercise 3
The mistake occurs in the basis step of the induction.
TAOCP 1.2.1 Exercise 4
Let P(n): \qquad F_n \ge \phi^{\,n-2}, where $\phi=(1+\sqrt5)/2$ and $n$ is a positive integer.
TAOCP 1.2.1 Exercise 5
Let $P(n)$ be the statement: “Every integer $m$ with $2 \le m \le n$ may be written as a product of one or more prime numbers.
TAOCP 1.2.1 Exercise 6
Let the values immediately before step E4 be a,b,a',b',c,d, and assume that the invariants
TAOCP 1.2.1 Exercise 7
Define S_n=n^2-(n-1)^2+(n-2)^2-\cdots+(-1)^{n-1}1^2 =\sum_{i=1}^n (-1)^{\,n-i} i^2.
TAOCP 1.2.1 Exercise 8
We prove by induction that for every positive integer $n$, n^3=(n^2-n+1)+(n^2-n+3)+\cdots+(n^2-n+(2n-1)).
TAOCP 1.2.1 Exercise 9
We prove by induction on $n$.
TAOCP 1.2.1 Exercise 10
Let $P(n)$ be the statement 2^n > n^3.
TAOCP 1.2.1 Exercise 11
Let S_n=\sum_{k=0}^{n}(-1)^k\frac{(2k+1)^3}{(2k+1)^4+4}.
TAOCP 1.2.1 Exercise 12
Let R=\mathbb Z[\sqrt2]=\{u+v\sqrt2 : u,v\in\mathbb Z\}.
TAOCP 1.2.1 Exercise 13
Let the assertions $A_1,\ldots,A_6$ be the assertions used in Knuth's verification of Algorithm E.