Massachusetts Institute of Technology Lecture 3 6.042J/18.062J: Mathematics for Computer Science September 14, 2000 Professors Nancy Lynch and Shlomi Dolev

Proof by Induction, continued

1 Inductive Proofs

1.1 Fibonacci numbers

Prove: ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1})

1. (Base) Σ_{i=0}^{0}F_{i}^{2} = F_{0}F_{1}

2. (Inductive step) ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1} ⇒ Σ_{i=0}^{n+1}F_{i}^{2} = F_{n+1}F_{n+2})

???

3. QED Induction

Complete proof:

Prove: ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1})

1. (Base) Σ_{i=0}^{0}F_{i}^{2} = F_{0}F_{1} Both sides are 0.

2. (Inductive step) ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1} ⇒ Σ_{i=0}^{n+1}F_{i}^{2} = F_{n+1}F_{n+2})

1. Fix n ≥ 0.

2. Assume Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1}

3. Σ_{i=0}^{n+1}F_{i}^{2} = F_{n+1}F_{n+2} 1. Σ_{i=0}^{n+1}F_{i}^{2} = Σ_{i=0}^{n}F_{i}^{2} + F_{n+1}^{2} Summation has one extra term 2. Σ_{i=0}^{n}F_{i}^{2} + F_{n+1}^{2} = F_{n}F_{n+1} + F_{n+1}^{2} Inductive hypothesis (2.2)

3. F_{n}F_{n+1} + F_{n+1}^{2} = F_{n+1}(F_{n} + F_{n+1}) Algebra

4. F_{n+1}(F_{n} + F_{n+1}) = F_{n+1}F_{n+2} Fibonacci definition

5. QED Combining the equations

4. QED Implication, UG 3. QED Induction

1.2 Double Induction

Define: f(0, k) = 1 for all k ≥ 0. f(n, 0) = 1 for all n ≥ 0. For n, k ≥ 0 : f(n + 1, k + 1) = f(n, k + 1) + f(n + 1, k).

Lemma 1.1 ∀n[∀k[f(n, k) = \frac{(n+k)!}{n!k!}]]

Q(n, k) : f(n, k) = \frac{(n+k)!}{n!k!}. P (n) : ∀k[Q(n, k)], that is, ∀k[f(n, k) = \frac{(n+k)!}{n!k!}].

Proof skeleton:

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0)

1. ∀k[f(0, k) = \frac{(0+k)!}{0!k!}] Both sides are 1 (for any k)

2. QED Definition of P (0)

2. (Inductive step) ∀n ≥ 0[P (n) ⇒ P (n + 1)] 1. Fix n ≥ 0.

2. Assume P (n), that is, row n is correct.

3. P (n + 1), that is, row n + 1 is correct. ???

4. QED Implication, UG

3. QED Induction

Adding some more steps:

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0)

1. ∀k[f(0, k) = \frac{(0+k)!}{0!k!}] Both sides are 1 (for any k)

2. QED Definition of P (0)

2. (Inductive step) ∀n ≥ 0[P (n) ⇒ P (n + 1)] 1. Fix n ≥ 0.

2. Assume P (n).

3. P (n + 1)

1. ∀k[Q(n + 1, k)]

1. (Base) Q(n + 1, 0) ???
2. (Inductive step) ∀k ≥ 0[Q(n + 1, k) ⇒ Q(n + 1, k + 1)].

???

3. QED Induction

2. QED Definition of P (n + 1)

4. QED Implication, UG

3. QED Induction

1. (Base) Q(n + 1, 0)

1. f(n + 1, 0) = \frac{(n+1+0)!}{(n+1)!0!} Both sides are 1

2. QED Definition of Q(n + 1)

2. (Inductive step) ∀k ≥ 0[Q(n + 1, k) ⇒ Q(n + 1, k + 1)].

1. Fix k ≥ 0.

2. Assume Q(n + 1, k).

3. Q(n + 1, k + 1)

1. f(n + 1, k + 1) = f(n, k + 1) + f(n + 1, k)

Definition of f(n + 1, k + 1)

2. f(n + 1, k) = \frac{(n+1+k)!}{(n+1)!k!} Inductive hypothesis 2.3.1.2.2, definition of Q(n + 1, k).

3. f(n, k + 1) = \frac{(n+k+1)!}{n!(k+1)!} Inductive hypothesis 2.2, definition of P (n, k + 1).

4. f(n + 1, k + 1) = \frac{(n+k+1)!}{n!(k+1)!} + \frac{(n+1+k)!}{(n+1)!k!} = \frac{(n+1+k+1)!}{(n+1)!(k+1)!} Combining equations, algebra

5. QED Definition of Q(n + 1, k + 1)

4. QED Induction

2 Strong induction

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0)

2. (Inductive step) ∀n ≥ 0[(∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

Prove: ∀n ≥ k[P (n)]

1. (Base) P (k)

2. (Inductive step) ∀n ≥ k[(∀i, k ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

3 Strong Induction Proof Examples

3.1 Block towers

P (n) : “We can build a tower of height n”.

Prove: ∀n ≥ 12(P (n))

1. (Base) P (12) Use 3+3+3+3

2. (Inductive step) ∀n ≥ 12[(∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

2. (Inductive step) ∀n ≥ 12[(∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 12.

2. (∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)

1. Assume ∀i, 12 ≤ i ≤ n(P (i)
2. P (n + 1))
1. n = 12 ⇒ P (n + 1) Use 7+3+3
2. n = 13 ⇒ P (n + 1) Use 7+7
3. n ≥ 14 ⇒ P (n + 1)

1. Assume n ≥ 14.

2. P (n − 2) By inductive hypothesis 2.2.1 and the fact that n − 2 ≥ 12

3. P (n + 1) Add one block to the tower from the previous step.

4. QED Implication

4. QED Cases

3. QED Implication 3. QED UG

3.2 Fibonacci examples

3.2.1 A lower bound

P (n) : F_{n} ≥ (\frac{3}{2})^{n−2} Prove: ∀n ≥ 2[P (n)]

1. (Base) P (2) F_{2} = 1 = (\frac{3}{2})^{0}

2. (Base) P (3) F_{3} = 2 ≥ (\frac{3}{2})^{1}

3. (Inductive step) ∀n ≥ 3[(∀i, 2 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 3

2. Assume ∀i, 2 ≤ i ≤ n(P (i))

3. P (n + 1)

1. F_{n} ≥ (\frac{3}{2})^{n−2} Inductive hypothesis 3.2

2. F_{n−1} ≥ (\frac{3}{2})^{n−3} Inductive hypothesis 3.2

3. F_{n+1} = F_{n} + F_{n−1} Definition

4. F_{n+1} ≥ (\frac{3}{2})^{n−2} + (\frac{3}{2})^{n−3} Plug the inequalities into the equation

5. F_{n+1} ≥ (\frac{3}{2})^{n−1}

1. \frac{3}{2} + 1 ≥ (\frac{3}{2})^{2} Arithmetic

2. (\frac{3}{2})^{n−2} + (\frac{3}{2})^{n−3} ≥ (\frac{3}{2})^{n−1} Algebra

3. QED Algebra (3.3.4 and 3.3.5.2)

6. QED Definition of P (n + 1)

4. QED Implication, UG 4. QED Strong induction