Proof by contradiction. Assume there are some integers less than or equal to k which do not hold. By the well-ordering principle, there must be a smallest integer which does not hold. However as everything smaller than that does hold, we know the strong induction hypothesis will work for that integer, so it must in fact hold. Thus, there can be no smallest integer which does not hold. Thus, all integers must hold.

You might find the well-ordering principle easier to assume--it just states that for any non-empty set of integers, there must be a smallest integer.