The hint pertains to the following part of the proof, where you generalize the inequality from n of the form 2^{k}to arbitrary n. It is not used in the claim you wrote.

The induction on n is pretty straightforward. You prove the claim for n = 2 and assume it for n = k. In proving it for n = k + 1, you use the induction hypothesis as well as the base case (for n = 2).

Please post here if you are still having difficulties.