Direct Proof Discrete Math Original Question:

Show that if $n$ is an odd integer, then $n^2$ is odd.

Possible Solution:

Proof :
  Assume that $n$ is an odd integer. This implies that there is some integer $k$ such that $n = 2k + 1$. Then $n^{2} = (2k+1)^{2} = 4k^{2} + 4k + 1 = 2(2k^{2} + 2k) + 1$. Thus, $n^{2}$ is odd.

Logical Questions:
Why does the solution assume $n$ to be $2k + 1$ ?
How do you know $n^{2}$ is odd based on $2(2k^{2}+2k)+1$ ? 
I don't see how $2k + 1$ for $n$ and $2(2k^{2}+2k)+1$ for $n^{2}$ means an odd integer. Some clarification would be helpful. 
 A: Lemma: An integer $m$ is odd if and only if it can be written as the sum of an even integer and $1$, if and only if there exists an integer $q$ such that $$m = 2q+1.$$
...
In the proof, assumption that $n$ is odd implies the existence of an integer $k$ such that $n = 2k + 1$ (that is the only if part of the lemma). As for $n^2 = 2(2k^2+2k) + 1$, letting $q = 2k^2+2k$ we have $$ n^2 = 2q+1,$$
from which it follows that $n^2$ is odd (that is the if part of the lemma).
A: By definition:
integer $n$ is even iff there exists an integer $k$ such that $n = 2k$
integer $n$ is odd iff there exists an integer $k$ such that $n = 2k+1$
So in the first step we use the definition to go from $n$ is odd to $n = 2k+1$, and in the other step we again use the definition to go from $n^2 = 2(2k^2+2k)+1$ to $n^2$ is odd.
A: $2k+1$ is a useful definition for the concept of an "odd number" because it expresses what it means for a number to be "odd" in terms of algebraic relationships.
In particular, you can prove that a number is odd if and only if it can be written in terms of $2k+1$ for some $k$, where $k$ must be an integer.
For example, $3$ is odd because:
$$3 = 2k + 1$$
$$2 = 2k$$
$$1 = k$$
As a negative example, 8 is not odd because:
$$8 = 2k + 1$$
$$7 = 2k$$
$$3.5 = k$$
But $3.5$ is not an integer, so $8$ is not odd.
If you accept that $2k+1$ encodes "odd-ness", then, the proof asserts through algebra that for some odd integer $n = 2k+1$:
$$n^2 = 2(2k^2 + 2k) + 1$$
Here, we can write $n^2 = 2k' + 1$, where $k' = (2k^2 + 2k)$. Note that $k'$ is an integer if $k$ is an integer. Therefore, $n^2$ is odd.
A: Show that if n is an odd integer, then $n^2$ is odd.
Often in mathematics, when we are given only two strict possibilities for a claim, we can "guess" or assume one possibility, and try to arrive at an obvious contradiction (given that assumption). This is often called "proof by contradiction", and is prevalent in real analysis/proof based math.
The proof is as follows.
We assume the wrong case, that is, assume given a number $n\in \mathbb{Z}$, that its mapping $n^2$ is even.
That is, $n = (2a+1)$ such that $a\in\mathbb{N} \Rightarrow n^2=(2a+1)^2=(2a+1)(2a+1)=4a^2+4a+1 = 4a(a+1)+1.$
We note $4a(a+1)$ is even, seeing that a natural number multiplied by an even natural number yields an even number. If we add one to this, it yields an odd number.
What does this mean? Well we assumed that given an odd number $n$, that $n^2$ was even, but we just algebraically proved it must be odd! So by contradiction, $n^2$ must be odd. 
This is redundant though, as you can set n to be odd and take it's square, which immediately proves this result. The above method should instead be applied when you're asked to prove $n$ is odd, given $n^2$ being odd.
