Introduction to Proofs

In this video, we are going to discuss mathematical proofs, different methods of proving things, and why proofs are useful.

In mathematics, a proof is a type of logical exercise in which someone pieces together known information to form a conclusion that was previously unknown. Proofs are typically written as a series of logical statements that flow from one to another until the conclusion is reached.

For example, consider the following statement: “If \(x\) is an odd integer, then \(3x+1\) must be an even integer.” How can we know that this statement is true? We can validate this claim with a proof. Let’s write one now. Start by writing what we want to show; this way, we can keep in mind exactly where we are trying to go with the proof.

Let’s write the first line of the formal proof. The first line is typically used to set up the elements of the problem, which are given in the claim. In this example, we are going to go ahead and establish that \(x\) is going to be an odd integer. This statement is usually called the hypothesis.

Now that we’ve set that up, the next line of the proof needs to be some statement which logically follows as a direct consequence of the first. Odd integers can be expressed in the form \(2k+1\), where \(k\) is any integer, let’s now write that \(x\) is equal to \(2k+1\).

Let’s see how this changes the expression \(3x+1\). When we substitute \(x=2k+1\), into the expression \(3x+1\), we get \(3x+1=32(k+1)+1\).

From here, simplify.

Do you remember how even numbers are defined in math? We say that a number is even if it can be represented in the form \(2k\), where \(k\) is some integer. If we factor out a 2 from \(6k+4\), we then end up with \(2(3k+2)\).

Because 3, \(k\), and 2 are all integers, \(3k+2\) is also some integer. This all implies that because \(3k+2\) is an integer, multiplying it by 2 results in an even integer.

To signal that we have reached the end of the proof, we can draw a small square after the final statement.

This is one example of what a proof may look like, and this particular example is called a direct proof. Direct proofs start with some known information, and through a series of logical steps, transform the known information into a statement which verifies the claim.

One of the other types of proofs in math is the indirect proof, in which you verify the claim by showing that all of its alternatives cannot be true. This is like a process of elimination.

Sometimes in math, though, direct proofs and indirect proofs are not the most efficient types of proof. For example, consider the following statement: “No two integers can be added together to form a fraction.” In order to validate this claim with a direct or indirect proof, we would have to check every pair of integers and make sure that their sums do not yield a fraction. There are infinitely many integer pairs to check, so it is impossible to check them all. Instead, a method called proof by contradiction would be much more efficient.

In a proof by contradiction, you establish the hypothesis (the given statements) of the proof, then make a statement saying “suppose the claim is not true.” From here, you would follow the logical implications of that “not” statement. Eventually, you would come to some later statement which directly contradicts one of the earlier statements in the proof.

For example, if we assume that “there are two integers whose sum is a fraction,” then the eventual logical implication of that would be that one or both of those numbers were not integers at all. This forms a contradiction with the hypothesis that two integers are being examined, and this contradiction nullifies the supposition that the claim was false. As a result, it is proven by contradiction that the claim was true after all.

Another proof method, which has a similar name but a different technique, is called proof by contraposition. In order to utilize this method, we must understand conditional statements, their negations, and their reversals. Conditional statements are “if-statements” and are usually given in the format “if this, then that.” For example, “If it is a holiday, then there is no school.” We can switch the order of the conditional statement if we negate both sides. This gives an equivalent statement, “If there is school, then it is not a holiday.”

More formally, we can write this idea as “p implies q” is equivalent to “not-q implies not-p.”

We use tildes, or squiggles, to denote the negation of p and q. So just like “holiday” implies “no school,” “yes school” implies “no holiday.”

So, if you find yourself having trouble proving a conditional “if p, then q” statement, try rewriting the claim as “if not-q, then not-p.” This method of proof by contraposition can sometimes simplify the steps needed in a proof!

The last method we will discuss is proof by induction. This technique is used whenever you need to show that some claim is true for an infinite number of cases. For example, consider the following claim: “For every positive integer n greater than or equal to 2, \(n\lt (n+1)(n-1)\).”

To prove this claim, we would seemingly need to test every single integer greater than or equal to 2. But because that would take an infinite amount of time, proof by induction must be used.

There are three steps in proof by induction. First, you must prove that the base case is true. For this claim, the base case would be \(n=2\), because that is the first time the claim applies. Let’s prove that now.

Because it is true that \(2\lt 3\), the claim is true in the base case \(n=2\).

The second step in proof by induction is assuming that the claim is true for the case \(n=k\).

This will help in the third step, which is proving that because the claim works for the \(n=k\) case, it must also work for the successive \(n=k+1\) case. If this part can be proven, then it is consequentially shown that the claim is true for any case \(n\geq 2\).

Notice from our previous statement that anywhere we had a \(k\) we replaced it with \(k+1\). Now we’re going to simplify.

Then we can move our 1 to the right side by subtracting 1 from both sides.

Now we can distribute our \(k\).

Now we can factor \(k^{2}-1\).

We finish the proof by stating:

Proof by induction is a helpful method for proving claims that apply to infinite integer cases. To use proof by induction, we started by proving that the claim was true in the base case, then we assumed that it was also true in the \(n=k\) case. Finally, we showed that this implied that the claim was true in the \(n=k+1\) case.

Proofs are used by mathematicians to verify claims about the behaviors of different functions and to validate theorems which can be used in further research. Students perform mathematical proofs to better understand why these functions and theorems work and why they are trustworthy. Proofs are also great tools for engaging an active mind with logical thought.

While proofs are typically regarded as difficult exercises, they are also very rewarding when completed. Now that you have an idea of how the different types of proofs are generally structured, you’ll soon be completing proofs of your own.

I hope that this video was helpful. Thanks for watching, and happy studying!