Here's another possible example. Let S(0), S(1), S(2), ..., be the sequence of numbers defined by the formula $S(n) = 1 + \sum_{k=0}^{n-1} S(k)$ for every nonnegative integer n. Then we can show that $S(n) = 2^n$ by strong induction on $n$.