Now if more than one element is 2k+1 or 2k+2, then P(k+1) is true as any number is divisible by itself.
If only one element or no element is greater than 2k then we can apply the induction hypothesis (by looking at the first k+1).
Precisely one element is 2k+1 and one 2k+2, in which case we have k elements that are less than or equal to 2k (we need k+1).
If we have 2 in our set, then 2|(2k+2) and we are done.
Suppose that 2 is not in our set and notice that for , a|(2k+2) iff a|(k+1), as 2 is prime. Also . So replace the element 2k+2 by k+1, and you get k+1 elements that are less than 2k. Apply the inductive hypothesis to conclude this case.