Theory

When you want to prove that

$$p\Rightarrow q$$ |

you must construct a proof of arguments that implies each other, such that

$$p\Rightarrow \cdots \Rightarrow q$$ |

With a direct proof, you are supposed to make a logical chain of reasoning. You begin with $p$. The claim $p$ needs to imply something, which then implies something else, and so on, until you end up implying $q$, where $q$ is what you were supposed to prove from $p$.

Example 1

**Prove that if $a$ is an even number and $b$ is an odd number, then $a+b$ is an odd number: **

When you are constructing a proof, it’s smart to make an expression you can work with. In this case you’ll need to make expressions for $a$ and $b$. Since $a$ is an even number, it can be written as $a=2n$, where $n$ is an integer. The number $b$ is an odd number, and can therefore be written as $b=2m+1$, where $m$ is an integer. You can insert these expressions into $a+b$, and then you get $$\begin{array}{llll}\hfill a+b& =2n+\phantom{\rule{-0.17em}{0ex}}\left(2m+1\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2n+2m+1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2\phantom{\rule{-0.17em}{0ex}}\left(n+m\right)+1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2k+1,\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$$

where $k=n+m$ is an integer, and so $a+b=2k+1$ is an odd number.

Q.E.D

Example 2

**You wish to prove that ${p}^{2}+p$ is always divisible by 2: **

You know that all even numbers have a factor that is even. This is true because all even numbers can be divided by 2 given the definition of even numbers.

So now you see that you can factorize ${p}^{2}+p$ as $p\phantom{\rule{-0.17em}{0ex}}\left(p+1\right)$. Then you see that $p$ and $p+1$ are two integers that follow each other on the real number line (like 3 and 4, 4 and 5$\dots $). You can now argue that no matter what $p$ is, one of the two factors has to be an even number, since every second integer on the real number line is even.

If $p=2k$ is an even number, then $p+1=2k+1$ has to be an odd number. If $p=2k+1$ is an odd number, then insert this expression for $p$ in $p+1$. Thus

$$\begin{array}{llll}\hfill p+1& =2k+1+1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2k+2\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2\phantom{\rule{-0.17em}{0ex}}\left(k+1\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =2l\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$$

$$p+1=2k+1+1=2k+2=2\phantom{\rule{-0.17em}{0ex}}\left(k+1\right)=2l$$ |

Mathematically, the proof looks like the one below, where the argument is constructed with implications:

$$\begin{array}{cc}{p}^{2}+p=p\phantom{\rule{-0.17em}{0ex}}\left(p+1\right)& \\ \Downarrow & \\ {p}^{2}+p\text{hasafactorthat}& \\ \text{isanevennumber}& \\ \Downarrow & \\ {p}^{2}+p\text{isevenand}& \\ \text{thereforedivisibleby2}& \end{array}$$

$$\begin{array}{cc}{p}^{2}+p=p\phantom{\rule{-0.17em}{0ex}}\left(p+1\right)& \\ \Downarrow & \\ {p}^{2}+p\text{hasafactorthatisanevennumber}& \\ \Downarrow & \\ {p}^{2}+p\text{isevenandisthereforedivisibleby2}& \end{array}$$

Q.E.D

Previous entry

What Is the Difference Between Equivalence and Implication?

Next entry

What Is Proof by Contrapositive?