Direct Proof in Discrete Mathematics

Welcome, students! In this lesson, you will learn one of the most important proof methods in mathematics: the direct proof ✍️. A direct proof is a step-by-step way to show that a statement is true by starting with known facts and logically moving forward until the conclusion is reached. This method is a core part of Proof Techniques I, along with contrapositive proof and contradiction.

What you will learn

By the end of this lesson, you should be able to:

Explain the main idea and vocabulary of a direct proof.
Use direct reasoning to prove statements in discrete mathematics.
Recognize when a direct proof is a good choice.
See how direct proof connects to other proof techniques.
Use examples involving integers, divisibility, and even numbers.

A direct proof is one of the clearest ways to prove a statement because every step follows naturally from the last. Think of it like following directions to get from your home to a school building 🏫: you begin at a starting point, take one correct step after another, and arrive at the destination without needing to backtrack.

What is a direct proof?

A direct proof is used to prove a statement of the form:

$$P \rightarrow Q$$

This means, “If $P$ is true, then $Q$ is true.” In a direct proof, you assume that $P$ is true and use definitions, algebra, and logical reasoning to show that $Q$ must also be true.

The key idea is simple: start with the hypothesis and end with the conclusion.

Here are some important terms:

Hypothesis: the “if” part of the statement, $P$.
Conclusion: the “then” part of the statement, $Q$.
Logical implication: the connection between $P$ and $Q$ written as $P \rightarrow Q$.
Definitions: exact meanings of words like even, odd, divisible, prime, and rational.

For example, if you want to prove, “If an integer is even, then its square is even,” you start by assuming the integer is even and then show the square must be even too.

How direct proofs work

A direct proof usually follows a pattern:

State what is given.
Use the definition of the given property.
Apply algebraic or logical steps.
Arrive at the statement to be proven.
Conclude the proof with a clear sentence.

Let’s look at the structure more closely.

Suppose we want to prove $P \rightarrow Q$.

We begin by assuming $P$ is true. Then we use facts we already know, such as definitions or previously proven results, to show $Q$ is true. If every step is valid, then the original statement is proven.

This works because mathematics is built on logic. A proof is not about guessing; it is about showing that the conclusion must follow from the assumptions. Direct proof is often the most natural method when the conclusion can be reached by straightforward reasoning.

Example 1: Even number squared is even

Let us prove:

$$\text{If } n \text{ is even, then } n^2 \text{ is even.}$$

Step-by-step direct proof

Assume $n$ is even. By definition of even, there exists an integer $k$ such that

$$n = 2k$$

Now square both sides:

$$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$

Since $2k^2$ is an integer, $n^2$ can be written in the form $2m$ for some integer $m$. Therefore, by definition of even, $n^2$ is even.

Why this is a direct proof

We started with the assumption that $n$ is even and used that definition to prove the conclusion. There was no need to work backward or show the opposite cannot happen. This is a classic direct proof ✅.

Example 2: Sum of two even integers is even

Now prove:

$$\text{If } a \text{ and } b \text{ are even integers, then } a+b \text{ is even.}$$

Assume $a$ and $b$ are even integers. Then there exist integers $r$ and $s$ such that

$$a = 2r \quad \text{and} \quad b = 2s$$

Add the two expressions:

$$a+b = 2r + 2s = 2(r+s)$$

Because $r+s$ is an integer, $a+b$ is of the form $2m$ for some integer $m$. Therefore, $a+b$ is even.

This proof is direct because it uses the definitions of even numbers and basic algebra to move straight from the hypothesis to the conclusion.

Example 3: A divisibility proof

Direct proof is very common in divisibility problems. Let us prove:

$$\text{If } 3 \mid n, \text{ then } 3 \mid n^2$$

Here, $3 \mid n$ means “$3$ divides $n$.” By definition, there exists an integer $k$ such that

$$n = 3k$$

Then

$$n^2 = (3k)^2 = 9k^2 = 3(3k^2)$$

Since $3k^2$ is an integer, $3 \mid n^2$.

Notice the pattern again: we begin with the given divisibility statement, rewrite it using the definition, and then transform the expression until the conclusion appears naturally. This is one reason direct proof is so useful in discrete mathematics 📘.

What makes a good direct proof?

A strong direct proof has several features:

It starts by clearly stating the assumption.
It uses definitions correctly.
It includes logical steps that follow one another.
It avoids unnecessary jumps.
It ends with a clear conclusion.

A common mistake is to assume what needs to be proven. For example, if the goal is to prove $P \rightarrow Q$, you should not start by saying $Q$ is true unless it has already been established from the assumption $P$. The proof should flow from the hypothesis to the conclusion.

Another useful habit is to look for keywords in the statement:

even means $2k$ for some integer $k$
odd means $2k+1$ for some integer $k$
divisible by $d$ means $n=dk$ for some integer $k$
rational means $\frac{a}{b}$ where $a$ and $b$ are integers and $b \ne 0$

Using these definitions makes direct proofs much easier.

Direct proof and the other proof techniques

Direct proof is one part of the larger topic Proof Techniques I. The other two major techniques in this topic are contrapositive and contradiction.

Here is how direct proof fits in:

Direct proof: assume $P$ and show $Q$.
Contrapositive proof: prove $\neg Q \rightarrow \neg P$ instead of $P \rightarrow Q$.
Contradiction proof: assume the statement is false and show that this leads to an impossibility.

Direct proof is usually the most straightforward method when the claim is already in a form that can be proven by definition and algebra. If direct proof seems difficult, the other techniques may be more powerful. Still, learning direct proof first is important because it builds the logical foundation for everything else in proof writing.

For example, proving that the sum of two odd numbers is even can be done directly. Let

$$a = 2m+1 \quad \text{and} \quad b = 2n+1$$

Then

$$a+b = (2m+1)+(2n+1)=2(m+n+1)$$

So $a+b$ is even. This direct reasoning is clean, efficient, and easy to follow.

Real-world connection

Direct proof is not just for abstract symbols. It shows up whenever you prove that one condition guarantees another. For instance, in computer science, if a program input has a certain property, you may need to prove that the output has another property. In everyday logic, if you know a rule and follow it carefully, you can show a result must happen.

Imagine a school policy: “If a student arrives before $8{:}00$ a.m., then the student is marked on time.” If the arrival time is before $8{:}00$ a.m., then the conclusion follows directly from the policy. That is the same reasoning style as a direct proof, even though the subject is everyday life rather than numbers.

Conclusion

Direct proof is one of the simplest and most powerful proof methods in discrete mathematics. It proves a statement of the form $P \rightarrow Q$ by assuming $P$ is true and using definitions, algebra, and logic to reach $Q$. You have seen that direct proofs work especially well with integers, even and odd numbers, and divisibility. This method is a major part of Proof Techniques I and provides the foundation for learning contrapositive and contradiction later.

When you face a new proof problem, students, ask yourself: Can I start from the hypothesis and move directly to the conclusion? If the answer is yes, a direct proof may be the best path forward ✅.

Study Notes

A direct proof proves a conditional statement of the form $P \rightarrow Q$.
The method starts by assuming the hypothesis $P$ is true.
Then it uses definitions, algebra, and logic to show the conclusion $Q$ must be true.
Common definitions used in direct proofs include:
even means $2k$ for some integer $k$
odd means $2k+1$ for some integer $k$
divisible by $d$ means $n=dk$ for some integer $k$
rational means $\frac{a}{b}$ with integers $a, b$ and $b \ne 0$
Direct proof is often the easiest method when the conclusion follows naturally from the hypothesis.
Examples include proving that the square of an even number is even and that the sum of two even numbers is even.
Direct proof is one of three major techniques in Proof Techniques I, along with contrapositive and contradiction.
A good proof is clear, logically ordered, and ends with a valid conclusion.