Let be the statement that if , then for some .

Base case: is a trivial statement. is the theorem you have.

Inductive Step:

Assume to be true, that is, if then for some . It remains to show that also holds, that is, if , then for some .

So if we have that , by your theorem, we have 2 cases: (1) or (2) .

(1) By the inductive hypothesis, we already have some such that , namely .

(2) Then let and we're done.