# induction

history dominoes example problem:

 ∀ integers n ≥ 0 define s(n) = 0+1+…+n = ∀ integers n ≥ 0 define f(n) = n(n+1)/2 ∀ integers n ≥ 0 s(n) = f(n) ?
• how proof by induction works

• prove claim holds in base case

• assume claim holds in arbitrary case (possibly base)

• prove claim holds in next case

• domino analogy

• show that the 1st domino falls

• assume that an arbitrary domino falls

• show that, under this assumption, the next domino falls

claim ∀ integers n ≥ 0, s(n) = f(n)

base case: n = 0

s(0) = = 0, and

f(0) = 0(0+1)/2 = 0, so claim holds in case case

inductive case

• inductive hypothesis: let k be a fixed integer at least 0 (base case), and assume s(k) = f(k)

• now we want to show s(k+1) = f(k+1), so

 s(k+1) = defn s( ) = + k+1 regroup terms of s(k+1) = s(k) + k+1 defn s( ) = f(k) + k+1 ind. hyp. = k(k+1)/2 + k+1 defn f( ) = (k+1)(k+2)/2 arithmetic = f(k+1) defn f( ) QED
```to tune of Amazing Grace

chorus: induction is a very strange thing
there are so many value for n
oh how do we prove that something is true
over and over again ?

the basis case we want to show
it's true for the smallest n
the inductive case we then will prove
it's true again and again.

chorus

so assume it's true for n equals k
where k might be very small
then show it's true for k plus one
so then it's true for them all

chorus
```