What are good examples of proofs by induction that are relatively low on algebra? Examples might include simple results about graphs.
My aim is to help students get a sense of the logical form of an induction proof (in particular proving a statement of the form 'if $P(k)$ then $P(k+1)$'), independent of the way one might show that in a proof about series formulae specifically.