Alrighty, lets give induction a go.
First, we need to define even and odd. The standard definitions are as follows:
An integer n is even if it can be expressed in the form n = 2k, where k is some integer
An integer n is odd if it can be expressed in the form n = 2k + 1, where k is some integer
We are now equipped to prove the statement via induction. We assume that the natural number n is either even or odd. We seek to show that this implies that the natural number (n+1) is also either even or odd.
Case 1: n is an even number
If n is an even number, then it can be expressed as n = 2k, with k some integer. Thus, n+1 = 2k+1, and by the definition of an odd number, n+1 is odd.
Case 2: n is an odd number
If n is an odd number, then it can be expressed as n = 2k + 1, with k some integer. Thus, n+1 = 2k+1 +1 = 2k+2 = 2(k+1). Since k is an integer, k+1 is an integer, and thus by the definition of an even number, n+1 is even.
In either of these two cases, n+1 is either even or odd.
Finally, we show that n= 1 is either even or odd. Since k=0 is an integer, note that 1 can be expressed as n = 2k+1 -> 1 = 2(0) + 1. Thus n is odd, and more generally, n=1 is either even or odd.
By induction, we may say that any natural number n is either even or odd.