SP20:Lecture 12 Induction

From CS2800 wiki

We introduce the proof technique of weak induction.

Induction by example: A ∪ (B1 ∩ ... ∩ Bn) = (A∪B1) ∩ ... ∩ (A∪Bn)

We will prove a variety of claims to demonstrate a new proof technique called induction; we will discuss induction much more later in the semester.

claim 2

We start with a simple version of the claim, which I will refer to as claim 2 (for reasons that will become apparent):

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B\href{/cs2800/wiki/index.php/%E2%88%AA}{∪}C) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A\href{/cs2800/wiki/index.php/%E2%88%A9}{∩}B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A\href{/cs2800/wiki/index.php/%E2%88%A9}{∩}C) [/math]
Proof:
Choose arbitrary sets [math]A [/math], [math]B [/math], and [math]C [/math]. We want to show to show that every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math] is also in [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) [/math]. Choose an arbitrary [math]x [/math] in the left hand side. Then [math]x ∈ A [/math] and [math]x ∈ B \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C [/math]. This means either (1) [math]x ∈ B [/math] or (2) [math]x ∈ C [/math]. In case (1), we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math], and thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Case (2) is similar. In either case, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math], as required.

claim 3

We now graduate to claim 3:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]
Proof:
By claim 2 (with [math]B = B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 [/math] and [math]C = B_3 [/math]), we have [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]. Now, we can apply claim 2 to conclude that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) [/math]. In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]. Putting this together (and using the fact that ⊆ is transitive),

we have


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \end{align*} [/math]

as required.

claim 4

Notice that we used claim 2 to prove claim 3. Similarly, we can use claim 3 to prove claim 4:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_4) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) [/math]
Proof: claim 4
By claim 2 (with [math]B = B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3 [/math] and [math]C = B_4 [/math]), we have [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_4) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) [/math]. Now, we can apply claim 3 (above) to conclude that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) [/math]. In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) [/math]. Putting this together (and using the fact that ⊆ is transitive), we have


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_4) &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_3)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_3) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_4) \end{align*} [/math]

as required.

claim n

You may have noticed the proofs of claim 3 and claim 4 are almost identical. You might imagine that you could use claim 4 to prove claim 5, and claim 5 to prove claim 6, and so on. Indeed you can, and this is the idea behind induction.

Since we have proved claim 2, and, for any [math]n ≥ 2 [/math], we can use claim [math]n [/math] to prove claim [math]n+1 [/math] (this is called the inductive step), we can conclude claim [math]n [/math] for any [math]n [/math]. Here is the general inductive step:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]
Proof: claim n+1
Since A ∩ (B∪C) ⊆ (A∩B) ∪ (A∩C) (proven above), we have [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) [/math]. Now, we can apply claim n (above) to conclude that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]. In general, if A ⊆ B then A ∩ C ⊆ B ∩ C, so we know that [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) ⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) [/math]. Putting this together (and using the fact that ⊆ is transitive), we have


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) \end{align*} [/math]

as required.

Induction

Because this pattern is so common, there is some stylized language. Typically, instead of "claim n", people often write P(n); this is referred to as the inductive hypothesis. The first proof (in our case, the proof of claim 2) is referred to as the base case. The general proof (using P(n) to prove P(n+1)) is called the inductive step. Here is a stylized induction proof:

For any [math]n ≥ 2 [/math], [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]


Proof:
By induction. Let [math]P(n) [/math] be the statement "[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]."

We must show [math]P(2) [/math] and [math]P(n+1) [/math] assuming [math]P(n) [/math].

In the base case, when [math]n = 2 [/math], we want to show to show that every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) [/math] is also in [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) [/math]. Choose an arbitrary [math]x [/math] in the right hand side. Then [math]x ∈ A [/math] and [math]x ∈ B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 [/math]. This means either (1) [math]x ∈ B_1 [/math] or (2) [math]x ∈ B_2 [/math]. In case (1), we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B_1 [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1 [/math], and thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. B_2ase (2) is similar. In either case, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math], as required.

For the inductive step, choose an arbitrary [math]n [/math] and assume we have already proved [math]P(n) [/math]. Our goal is to show [math]P(n+1) [/math]. We compute:


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) &= A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by P(2)} \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by P(n) and }\href{/cs2800/wiki/index.php/If_A_%E2%8A%86_B_then_A_%E2%88%A9_C_%E2%8A%86_B_%E2%88%A9_C_claim}{ \text{lemma}} \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by definition} \end{align*} [/math]

Example: summation

Here is a straightforward example of induction:


For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], [math]\sum_{i=0}^n i = \frac{n(n+1)}{2} [/math]
Proof:
We prove this statement by weak induction on [math]n [/math]. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math]

be the statement "[math]\sum_{i=0}^n i = \frac{n(n+1)}{2} [/math]". We will show [math]P(0) [/math] and [math]P(n+1) [/math] (assuming [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math]).

Aside: Note that [math]P(n) [/math] does not include the "for all n". To see why, imagine that it did. Then [math]P(7) [/math] would say "for all 7, ...",
Aside: A common mistake people make when writing inductive proofs, especially those involving formulas, is to think of [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] as a 'number' and not a statement. If you find yourself writing [math]P(n) + n = 7 [/math], you are doing something wrong! Plugging this in would give [math]\left(\sum_{i=0}^n i = \frac{n(n+1)}{2}\right) + n = 7 [/math] which doesn't make sense.

In the case where [math]n = 0 [/math], the left hand side and the right hand side are both 0.

Now, to see [math]P(n+1) [/math], first assume [math]P(n) [/math]. We want to show [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n+1)} [/math], i.e. that [math]\sum_{i=0}^{n+1} i = \frac{(n+1)(n+2)}{2} [/math]. We compute:

[math]\begin{aligned} \sum_{i=0}^{n+1} i &= 0 + 1 + \cdots + n + (n+1) && \text{by definition} \\ &= \left(0 + 1 + \cdots + n\right) + (n+1) && \href{/cs2800/wiki/index.php?title=Algebra&action=edit&redlink=1}{\text{arithmetic}} \\ &= \frac{n(n+1)}{2} + (n+1) && \href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{\text{by P(n)}} \\ &= \frac{n(n+1) + 2n + 2}{2} = \frac{(n+1)(n+2)}{2} && \href{/cs2800/wiki/index.php/Arithmetic}{\text{algebra}} \end{aligned} [/math]

as required.

Aside: This proof uses a common pattern in inductive proofs (and in many other proofs too!): in the first few steps, we take what we want to show, and manipulate it so that we can use what we know ([math]P(n) [/math] in this case). If you get stuck, it's always good to look at what you've assumed already and try to find a way to apply it.

Example: prime factorization

We now give an example of a inductive proof that doesn't work; we will show how to patch it up in the next lecture.

Before we present the proof, a few (possibly familiar) definitions:

Definition: Composite
A natural number [math]n [/math] is composite if there exists [math]a, b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] with [math]a [/math] and [math]b [/math] both greater than 1 satisfying [math]ab = n [/math].
Definition: Prime

We will attempt to use weak induction to prove the following claim:

For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], if [math]n ≥ 2 [/math] then there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math].
Proof: Attempt with weak induction
We will prove the claim using weak induction. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] be the statement "there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math]. We will prove [math]P(2) [/math] and [math]P(n) [/math] assuming [math]P(n-1) [/math].

In the base case, when [math]n = 2 [/math] we see that 2 is prime. Therefore, we can choose [math]a_0 = 2 [/math]; clearly [math]2 = 2 [/math].

For the inductive step, we assume [math]P(n-1) [/math]; our goal is to show [math]P(n) [/math], in other words that [math]n [/math] has a prime factorization.

There are two cases: [math]n [/math] could be prime or composite. If [math]n [/math] is prime, we can proceed as in the base case: simply choose [math]a_0 = n [/math].

If, on the other hand, [math]n [/math] is composite, then we know that [math]n = ab [/math] for some natural numbers [math]a [/math] and [math]b [/math].

If we knew that [math]a [/math] and [math]b [/math] had prime factorizations, then we could combine them to form a prime factorization of [math]n [/math]. But we don't know that — it is what we are trying to prove. We do have an inductive hypothesis that tells us that [math]n-1 [/math] has a prime factorization, but that only helps if [math]a = b = n-1 [/math].

To fix this up, we need to either strengthen our inductive hypothesis or use strong induction.

We will show these techniques in the next lecture.