I posted an answer on sci.math.research recently where I used induction with a base case, and then thought I could use strong induction instead. Later another poster came up with a nice argument that hid or did away with the induction. Perhaps you can frame it to fit your needs.
The problem: Given an ascending sequence b_i and descending sequence a_i, both containing n positive numbers, show that for every permutation p on n letters that max (a_i*b_i, 1 <=i <= n) <= max (a_i*b_p(i), 1 <= i <= n) .
Proof sketch (by strong induction?): Assume the result is true for all m < n. If p fixes n, we're done. Otherwise, swap b_n and b_p(n) and note that the maximum will not increase. Done.
The above may not be the most natural example nor the best proof of the result.
It may suggest something that will help. Although it could be argued that this is a "strong inductive" example of a different proof, I think it could also be argued that the different proof is one that hides the inductive principle at work. Now let the community judge.
Gerhard "Ask Me About System Design" Paseman, 2010.01.15