(Weak) Induction

Introductory example

P(n) = "∑_i=0..n i = n(n+1)/2" -- Yet another way to prove this sum.
Proof by induction of ∀n∈N.P(n):
- Base case: P(0)
- Inductive case: P(n)→P(n+1) — ∀n∈N
Compare to corresponding recursive function definition:
- sum(0) = 0
- sum(n+1) = sum(n)+(n+1)

We probably won't have time for all of these. There are more examples in the book.

∀ n∈N, n³-n is divisible by 3
∀ n≥5 and n∈N, 2ⁿ>n²
- For motivation, first compare 2ⁿ and n² for small values.
- Compare to equivalent: &forall n∈N, (n≥5 → 2ⁿ>n²)
- Compare to equivalent: &forall n∈N, 2ⁿ⁺⁵>(n+5)²
Suppose R is a partial order on a set A. Prove that every finite, nonempty set B⊆A has an R-minimal element.
- How to reword as &forall n, P(n)?
- &forall n≥1, &forall B⊆A, (B has n elements → B has an R-minimal element)
∀ n≥3, if n distinct points on a circle are connected in consecutive (i.e., consistently clockwise or consistently counter-clockwise) order with straight lines, then the interior angles of the resulting polygon add up to (n-2)×180°.

Note that we've generalized induction to the form: To prove ∀n∈{k,k+1,k+2,…}.P(n)

Example:

Okay, we'll patch that problem for this example:

Example:

False claim: All Rice students are in the same college. P(n) = "for all sets of n students, those students are all in the same college". Prove ∀n≥1.P(n). We know this conclusion is wrong, so what's wrong with the following?
P(1): Yep, in a singleton set {s₁}, every student is in s₁'s college.
P(i) → P(i+1): We can assume that P(i) holds: for all sets of i students, those students are all in the same college. We need to show P(i+1). Start with an arbitrary set of k+1 students, S = {s₁, …, s_k, s_k+1}, and we'll show they all are in the same college as s₁.

By inductive assumption, the set {s₁, …, s_k} are all in the same college as s₁. Similarly, so are {s₁, … s_k-1, s_k+1}. Since "is in the same college as" is transitive, all elements of S are in the same college as s₁. Q.E.D.