Examples of mathematical induction What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ where the number of terms depends on $n$ and you're doing induction on $n$?
Postscript three years later: I see that I phrased this last part in a somewhat clunky way. I'll leave it there but rephrase it here:



--- that are not instances of induction on the number of terms in a sum?




I like the ones that involve division.
For instance, prove that $7 \mid 11^n-4^n$ for $n=1, 2, 3, \cdots$

Another example would be perhaps proving that 
$$(3+\sqrt{5})^n+(3-\sqrt{5})^n$$
is an even integer for all natural numbers $n$.
