Proof By Induction

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

1. Write out $P(x)$ represents …
2. Prove P(1) - the base case. (Do a simple one-line equivalence)
3. Prove $\forall k\ge 1,P(k)⟹P(k+1)$ - induction step
   1. Take arbitrary $k$ and suppose $k\ge 1$
   2. Suppose $P(k)$ - induction hypothesis
   3. Prove $P(k+1)$

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$