Proof by Induction

We want to show that a statement $S(k)$ holds for all integers $k\ge 0$.

Step 1. Base Case: Show S(0) holds.  
Step 2. Inductive Step: Show that if S(k) holds, then S(k+1) holds where S(k) => S(k+1).  
Then we can keep doing step 2 until we prove whatever we are trying to prove.  

Sometimes in the inductive step, we require more than just S(k) to show that S(k+1) holds.

In strong induction, we replace step 2 with “if S(k) holds for all $\bar{k}\le k$, then $S(k+1)$ holds”. Where this looks just like a longer chain where we use S(0)=>S(1)=>S(2) where 0, and 1 both are used to imply 2 for example.