1. ## Proofs

Can someone point me in the direction of a good place to learn about proofs? I am starting a new chapter which is all about proofs and am stuck on the simplest of concepts:

Prove that the square of an even number is an even number using:
a direct proof
an indirect proof
a proof by contradiction

They just get harder from here and I have never been good at proofs.

2. Hello again ^^

Originally Posted by sjenkins
Can someone point me in the direction of a good place to learn about proofs? I am starting a new chapter which is all about proofs and am stuck on the simplest of concepts:

Prove that the square of an even number is an even number using:
a direct proof
$P \Rightarrow Q$
This would be "if x is an even number, prove that x² is an even number", using known facts.

Hint : use x=2k.

an indirect proof
$\overline{Q} \Rightarrow \overline{P}$
This would be "if x² is an odd number, then x is an odd number".

a proof by contradiction
$P \Rightarrow \overline{Q} \text{ : impossible.}$
If x is an even number, let's suppose that x² is an odd number. Then, get to a contradiction

I'm sorry I can't give you any book references for it, as I don't know anything about American or English litterature

3. Originally Posted by sjenkins
Can someone point me in the direction of a good place to learn about proofs? I am starting a new chapter which is all about proofs and am stuck on the simplest of concepts:

Prove that the square of an even number is an even number using:
a direct proof
an indirect proof
a proof by contradiction

They just get harder from here and I have never been good at proofs.
You should be able to find some good books on proofs. Look around a bit on Google or Amazon. This one by Eccles has a nice introduction. Perhaps others can give you more recommendations.

For some examples:

$n\text{ is even }\Rightarrow n^2\text{ is even }$

Direct: We form a chain of implications, starting with our given and ending with our desired result:

$n\text{ is even }$ (Given)

$\Rightarrow n = 2q,\;q\in\mathbb{Z}$ (By definition of an even number)

$\Rightarrow n^2 = (2q)^2$ (Squaring both sides)

$\Rightarrow n^2 = 4q^2$ (Expanding)

$\Rightarrow n^2 = 2(2q^2)$ (Factoring out a 2)

$\Rightarrow n^2 = 2p,\;p=2q^2\in\mathbb{Z}$

$\Rightarrow n^2\text{ is even }$ (By definition)

Therefore, $n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square$

Then you could put the proof in a more presentable form by cutting out any unnecessary explanatory comments and tidying it up into a nice paragraph.

Indirect: Let's prove the contrapositive (i.e. $p\Rightarrow q$ and $\lnot q\Rightarrow\lnot p$ are logically equivalent statements). So, we show that $n^2\text{ is odd}\Rightarrow n\text{ is odd}.$

$n^2\text{ is odd}$

$\Rightarrow$ 2 does not divide $n^2$

$\Rightarrow$ 2 does not divide any factor of $n^2$

$\Rightarrow$ 2 does not divide $n$

$\Rightarrow n\text{ is odd}$

Thus $n^2\text{ is odd}\Rightarrow n\text{ is odd}$, and it follows that $n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square$

Contradiction: Let's assume that our result is false, and show that such an assumption would lead to a contradiction.

Assume the contrary, and suppose there is some integer $n$ which is even and for which $n^2$ is odd.

Since $n$ is even, $n = 2p,\;p\in\mathbb{Z}$

$\Rightarrow n^2 = 2pn$

$\Rightarrow 2|n^2$ (since $pn$ is an integer)

$\Rightarrow n^2\text{ is even}$

But, by our assumption, $n^2$ is also odd, which is a contradiction. Thus our assumption that there is an even integer whose square is odd must be false, and

$n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square$