Subtract the difference of the squares:

(n + 1)^2 - n^2

n^2 + 2n + 1 - n^2

n^2 terms cancel, we get:

2n + 1

2 is even. For n, if we use an even:

we have even * even = Even

Add 1 we have Odd

2 is even. For n, if we use an odd:

we have even * odd = Even

Add 1 we have Odd

Since both cases are odd, we've proven our statement.