# 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.

• anything times 2 is an even number, so 2k+1 must be odd. Thus, in order to show that $n^2$, you just apply square to 2k+1 just as you did and get 2 times value $2c+1$ where c =$(2k^2+2k)$ so this is also must be odd. – YOUSEFY Apr 5 '17 at 18:36
• Hmm, yes you are right. Anything times 2 + 1 is odd. :) – Kourosh Apr 5 '17 at 18:40

$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.

• Great response. I was also confused for why 2k^2 + 2k is replaced by k in 2k + 1, but you clarified it as well. Thanks. – Kourosh Apr 5 '17 at 18:45

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).

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.

• Makes sense now, thank you. – Kourosh Apr 5 '17 at 18:45

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.

• Ok you mean using proof by contradiction is more effective than a direct proof ? – Kourosh Apr 5 '17 at 19:00
• In your case, a direct proof is much more efficient. Proof by contradiction is redundant in this specific case. But consider the opposite of your claim, that if given n^2 odd, prove n is odd. This cannot be proven as you say "directly", and thus a contradiction proof must be used. – Mark Pineau Apr 5 '17 at 19:48
• No it can be proven directly. Just replace k with a fixed number like 3 and test it out. – Kourosh Apr 5 '17 at 19:49
• This proves it for that specific case, but what if we want to prove it for all odd natural numbers? Well we know the set of natural numbers is "infinite," thus implying the set of all odd natural numbers is also "infinite." Surely you cannot test the claim for all odd numbers. This way, we generalize it with some value n, and prove via contradiction. – Mark Pineau Apr 5 '17 at 21:55