It said use induction, so here goes.

Base case: Clearly the claim is true for , since that is given.

Induction hypothesis: Assume the claim is true for some , that is . We show that the claim is true for , that is, .

Since , we have that , for some integer

Now

since (since it is a multiple of ) we have the desired result.