recursion

Induction is recursion, read backwards

Every recursive function you have written is a proof by induction you did not know you were writing. Seeing the correspondence makes both halves easier.