Proof By Induction

Proving using patterns. It is technically a form of Proof By Direct Proof.

• Uses only a few base cases compared to PCI
• Assumption is weaker for Induction Hypothesis compared to PCI

Form

Base Case

1. Write out $P(x)$ represents …
2. Let $n=b$
   1. Proof of $P(n)$

Induction Step

1. Let $n>b$
2. Suppose $P(n)$ Induction Hypothesis
   1. Proof of $P(n+1)$
3. Therefore, by induction $P(n)$ holds for all $n\ge b$ $\square$

Analogies

Dominoes

If a domino falls, it will collapse the next one, which will collapse the next one. The reason why all of them fall is because any domino falling will collapse another one.

Examples

$P(n)$ : the sum of the first $n$ odd positive integers is $n^2$ Prove: $\forall k\ge 1⟹(P(k)⟹P(k+1))$ Proving base case:

1. $P(k)$ by definition: ${\sum }_{i=1}^k(2i-1)=k^2$
2. Then ${\sum }_{i=1}^1(2i-1)=2-1=1=1^2$
3. Then $P(1)$ by definition of $P(k)$ Proving induction step:
4. Let $k\ge 1$ be arbitrary
5. Assume $P(k)$
6. $P(k)$ by definition: ${\sum }_{i=i}^k(2i-1)=k^2$
7. Then, ${\sum }_{i=i}^{k+1}(2i-1)={\sum }_{i=i}^k+2(k+1)-1$
8. Then, ${\sum }_{i=i}^{k+1}(2i-1)=k^2+2k+1$
9. Then, ${\sum }_{i=i}^{k+1}(2i-1)=(k+1{)}^2$
10. Then, $P(k+1)$ by 6, definition of $P(k)$
11. Then, $P⟹P(k+1)$ by 2, 7 implies
12. Then, $k\ge 1⟹(P⟹P(k+1)$ by 2, 7 implies
13. Then, $\forall k\ge 1⟹(P⟹P(k+1)$ by 1, 9 universal gen $\square$