Quote:
Originally Posted by BojanVujatovic
I got stuck solving this problem. I know it is a simple proof by induction, but there is something I keep missing here. Has anybody tried to solve it? Any hints would be greatly appreciated.

Take care of the small values of
(not just
) by inspection. Once you do that, the induction step will become easier.