So what does it mean that we already proved it for all smaller numbers, that means we can use in the proof of our inductive step the fact that P of K is the most a times K for all K strictly less than N. All we gotta do is enlarge the range of N's to which this holds to one more to the current value N. And all we have to do is follow our nose. 