I am still very new to proofs. I am just getting some practice, as I am still struggling with the concepts. Any feedback would be greatly appreciated. Thank you in advance.
Claim: If $n^2-1$ is divisible by $8$, then $n$ is odd.
Proof: Suppose $n$ is even; that is, $n=2k$, for some $k \in \mathbb{Z}$. Then, $n^2-1 = (2k)^2-1$, which is odd. Therefore, $n$ must be odd and thus, contradicts our assumption that $n$ is even.
This is my second practice proof I am working on so please be gentle! I am still learning the logic and working through the proofs slowly. Any feedback, tips, or hints/tricks would be greatly appreciated! Thanks.
Best Answer
In your problem, proof-by-contradiction works as follows:
(Hypothesis) Suppose 8 divides $n^2-1$.
(Assumption) Let us assume that $n$ is even.
$n$ is even $\implies$ $n=2k$ for some $k \in \mathbb{Z}$
Then, $n^2-1 = (2k)^2-1$
$n^2-1 = 2(2k^2)-1 \implies n^2-1 $ is an odd number.
$n^2-1$ is odd $\implies$ 8 does not divide $n^2-1$.
Contradiction! That is, assuming n is even contradicts our hypothesis (i.e., $n^2-1$ is divisible by 8).
So our assumption is wrong. This means $n$ has to be odd.
Alternatively, we can prove the contrapositive (i.e., Proving $A\implies B $ is equivalent to proving $ \neg B \implies \neg A $ ). This works as follows in your case:
Suppose $n$ is even.
Then, $n = 2k$ for some $k \in \mathbb{Z}$
$\implies$ $n^2-1 = (2k)^2-1$
$\implies$ $n^2-1 = 2(2k^2)-1$
$\implies$ $n^2-1$ is odd.
$\implies$ $n^2-1$ is not divisible by 8.
Thus, we have proved this: $n$ is not odd $\implies$ $n^2-1$ is not divisible by 8, which is equivalent to proving this: $n^2-1$ is divisible 8 $\implies n$ is odd.