# How would I go about writing this proof in a formal way?

Let c ∈ Z: Write a detailed structured proof to prove the statement:

If c^5 + 7 is even, then c is odd.

I started out like this:

Assume c ∈ Z
Assume c^5 + 7 == 2n
Then c == 2n + 1


Also, is this claim true? I plugged in odd numbers for c, and haven't encountered a counter-example. Is there a way to determine the veracity of the claim before doing the proof?

-
If you still have doubts and think it necesary to plug in odd numbers for $c$ and look out for counterexamples, you do not have a trustworthy proof yet. Moreover, if you plug in odd values for testing, you do not do the testing right. Finally, $c=1$ gives you problems as $c^2+7=2n$ implies $n=4$ whereas $c=2n+1$ implies $n=0$ - you cannot have $n=4$ and $n=0$ at the same time. –  Hagen von Eitzen Oct 16 '13 at 18:33

You have left out quite a bit in between the "Assume" and "Then".

That said, might I suggest using the Contrapositive?

It's logically equivalent , and states:

If $c$ is even, then c^5 + 7 is odd.

This is quite simple to prove. Suppose that $c = 2k$ for some integer $k$. Then $c^5 + 7 = (2k)^5 + 7 = 2(16k^5 + 3) + 1$, which is odd. QED.

-

Your conclusion needs to be 'Then $c = 2m + 1$' for some other integer $m$ (it probably won't be the case that $c^5 + 7 = 2n$ and $c = 2n + 1$ for the same $n$).

Your first two steps are fine, though I would maybe expand the second step and say:

1. Assume $c\in\mathbb{Z}$
2. Assume $c^5 + 7$ is even
3. Then $c^5 + 7 = 2n$ for some $n\in\mathbb{Z}$

The next steps could go something along the lines of proving the statements

1. If $c^5 + 7$ is even, then $c^5$ is odd
2. If $c^5$ is odd, then $c$ must be odd.

A totally different approach

You could also try arguing the contrapositive, which is

'if $c$ is not odd, then $c^5 + 7$ is not even'

i.e.

'if $c$ is even, then $c^5 + 7$ is odd'

-

We have these equivalences

$$c^5+7\ \text{is even}\iff c^5\ \text{is odd}\iff c \ \text{is odd}$$

The last equivalence can be proved using a contrapositive proof and a direct proof

$\Rightarrow)$ by contrapositive: If $c=2n$ then $c^5=2\times 2^4n^5$ is even.

$\Leftarrow)$ If $c=2n+1$ then $(2n+1)^5=\sum_{k=0}^5{5\choose k}(2n)^k=1+\underbrace{\sum_{k=1}^5{5\choose k}(2n)^k}_{even}$

-
At this level, I don't think the second equivalence is something that can be taken for granted. –  Eric Tressler Oct 16 '13 at 18:32
@EricTressler I added some details for the second equivalence. –  Sami Ben Romdhane Oct 16 '13 at 18:37
How are you today, dear Sami? ;-) –  amWhy Mar 9 '14 at 13:09

The claim is indeed true.

Now, how to proceed: if $c\in\mathbb Z$ then $c^5$ has the same parity than $c$, let's see how to write the proof later.

Therefor if $c^5$ is odd, then $c$ is odd. And $c^5$ is odd because $c^5+\text{odd}=\text{even}$.

Now you have to write it backwards:

1. If $c^5+7$ is even, then $c^5$ is odd (because $7$ is odd and $\text{even}-\text{odd}$ is odd).
2. If $c^5$ is odd for an integer $c$, then $c$ is odd. (by contradiction: if $c$ were even, then there is $k\in\mathbb Z$ so that $c=2k$ and $c^5=32k^5=2(16k^5)$ which is even.)
3. Therefor $c$ is odd.
-