Theorem. Every odd integer is equal to the difference between the square of two integers.
For example, \begin{align*}1&=1^2-0^2\\3&=4-1=2^2-1^1\\5&=9-4=3^2-2^2\\7&=16-9=4^2-3^2\end{align*}
Note that an arbitrary odd integer can be written as $2k+1$ for some integer $k$. The above examples can be written as \begin{align*}1&=2\cdot 0+1=(0+1)^2-0^2\\3&=2\cdot 1+1=(1+1)^2-1^2\\5&=2\cdot 2+1=(2+1)^2-2^2\\7&=2\cdot 3+1=(3+1)^2-3^2\end{align*} Based on this observation we may conjecture that $$2k+1=(k+1)^2-k^2$$ for all nonnegative integer $k$. Proving this conjecture is equivalent to proving the above theorem. This can be shown straightforwardly. $$(k+1)^2-k^2=k^2+2k+1-k^2=2k+1$$
Theorem. For any integer $n$, $n^2$ is odd if and only if $n$ is odd.
In the statement you see the conjunction if and only if. The statement is actually the following two statements in one:
- $n^2$ is odd if $n$ is odd.
- $n^2$ is odd only if $n$ is odd.
The statement 1 means that if $n$ is odd then $n^2$ is odd. The statement 2 means that if $n^2$ is odd then $n$ is odd.
Proof. (Only if) We prove this by contradiction. (This is an indirect proof.) Suppose that there exists an integer $n$ such that $n^2$ is odd but $n$ is not. Then $n$ is even so $n=2k$ for some integer $k$. However $n^2=(2k)^2=4k^2$ is even so this is a contradiction. Therefore, there is no integer $n$ such that $n^2$ is odd but $n$ is even.
(If) Suppose that $n$ is odd. Then $n=2k+1$ for some integer $k$. \begin{align*}n^2=(2k+1)^2&=4k^2+4k+1\\&=2(2k^2+2k)+1\end{align*} is odd. (This is a direct proof.)
Corollary. If $n$ is odd, then $n^4$ is odd.
Proof. Since $n$ is odd, by the theorem $n^2$ is odd, and again by the theorem $n^4$ is odd.
“If $p$ then $q$” is logically equivalent to “If not $q$ then not $p$.” “If $p$ then $q$” and “If not $q$ then not $p$” are contrapositives of each other.
Example. The statements “If $n^2$ is odd then $n$ is odd and “If $n$ is not odd (i.e. $n$ is even) then $n^2$ is not odd (i.e. $n^2$ is even)” are contrapositives of each other, and they are logically equivalent statements.
Here is another example of proof by contradiction.
Theorem. $\sqrt{2}$ is irrational.
Proof. Suppose that $\sqrt{2}$ is rational Then $\sqrt{2}=\frac{a}{b}$ for some integer $a$ and $b\ne 0$. Without loss of generality we may also assume that at most one of $a$ and $b$ is even. Multiplying $\sqrt{2}=\frac{a}{b}$ by $b$, we get $\sqrt{2}b=a$. Squaring this we get $2b^2=a^2$ $\Longrightarrow$ $a^2$ is even and this means $a$ is even by the previous theorem. So, $a$ can be written as $a=2k$. Now, $2b^2=(2k)^2=4k^2$ $\Longrightarrow$ $b^2=2k^2$ $\Longrightarrow$ $b^2$ is even and by the previous theorem $b$ is even. A contradiction! Therefore, $\sqrt{2}$ is irrational.
References.
[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019