Then there exists some positive integer b such that k = 2b+1. But then n_0 = 2(b+1)+1 ∉ S, contradiction.
This concludes the proof.
EDIT: Well, let's see... you never use the inductive hypothesis from what I can tell... your hypothesis would be P(k) (you must change your symbolic form of the proof) and then you need to show P(k+1)... so you could say
Prove: For all positive integers n, n is even or odd.
Proof (by Induction):
Basis step. Let n=1. Then n is clearly odd.
Inductive step: Suppose k, an arbitrary positive integer, is even or odd. We need to show k+1 is odd or even.
Case 1: k is even
Then there exists a positive integer a such that k = 2a. Then
k+1 = 2a+1 is odd,
as desired.
Case 2: k is odd
Then there exists a positive integer b such that k = 2b+1. Then
k+1 = 2b+1+1 = 2(b+1) is even,
as desired.
See how I use the inductive hypothesis (k is even) or (k is odd), break into cases, and in each case, prove k+1 is even or k+1 is odd?
What I said about the PMI working on any well-ordered set is true, the way you set up the proof is problematic.