Продолжаем попытки подружиться с методом мат.индукции:
- доказываем базу;
- делаем предположение;
- доказываем переход.

Вуаля - мы решили задачу!