Study Guide

# Logic and Proof - Types of Proofs

## Types of Proofs

We've been proving stuff left and right. Now it's time to take a peek at what's going on under the hood. It's like we just learned to drive, and now we're about to get a crash course on how car engines work. Except our version will be way less greasy. Hopefully.

Proofs are all about logic, but there are different types of logic. Specifically, we're going to break down three different methods for proving stuff mathematically: deductive and inductive reasoning, and proof by contradiction.

Long story short, deductive proofs are all about using a general theory to prove something specific. Inductive proofs flip this around: we use a specific example to prove a general theory. Proofs by contradiction are their own weird thing: we prove something by showing that its opposite can't possibly be true.

Different strokes for different folks…er, different proofs, we mean.

• ### Proof by Deduction

Deduction is a type of reasoning that moves from the top down: it starts with a general theory, then relates it to a specific example. We start with a broad statement that we know to be true, and then we apply it to a particular situation.

It's like the Ten Commandments. No, really; hear us out.

Number eight says "do not steal," which is a general statement: stealing is bad, in general. We could then use deductive reasoning to apply that statement to a specific example: "I probably shouldn't steal this particular Xbox from my best friend's bedroom after knocking him out, right?" Right. That's an example of deductive reasoning: we applied the general theory (stealing is bad) to the particular case (therefore, stealing your friend's Xbox is also bad).

Good news: you already know how to prove stuff deductively. Most of the algebraic and geometric proofs you've done so far have been deductive proofs. We start with some kind of general rule, like "supplementary angles always add up to 180°," and apply it to a specific example, like "angle 1 has a measure of 75°, so an angle supplementary to angle 1 must have a measure of 105°."

With deductive proofs, we usually use postulates and theorems as our general statements and apply 'em to specific examples. And we usually do this a bunch of different times in a single proof.

For example, take a gander at the following formal proof.

Given: w = x, x = y, y = z
Prove: w = z

 Statements Reasons 1. w = x Given 2. x = y Given 3. y = z Given 4. w = y Transitive Property (1 and 2) 5. w = z Transitive Property (4 and 3)

Check out Statement #4. We used the transitive property as our general theory, since we know it's always true. Then we used deductive reasoning to apply the transitive property to our specific example: if w = x and x = y, then it must be true that w = y.

After that, we used deduction again in Statement #5. We can stack up mini-deductions like this, over and over, until we finally prove whatever we set out to prove. It's like building a LEGO set out of mind-bricks.

• ### Proof by Induction

Deduction is all about going from general theories to specific examples. Induction flips this whole shebang around, like a fun-house mirror. Inductive proofs go from the bottom up: we start with a specific statement and use it to prove a general theory.

Let's revisit our Ten Commandments example. Say you'd never heard the rule "thou shalt not steal" before, but then you noticed that you felt kinda bad after taking your buddy's Xbox without his permission. He probably got really mad at you, if the steam shooting out of his ears was any indication.

Using inductive reasoning, you could go from the specific ("stealing this Xbox was a bad idea") to a general theory ("hey guys, let's maybe not steal anything anymore"). It reverses the deductive direction.

We usually use induction to prove mathematical statements involving a variable (typically n) for all integer values of n, or sometimes just positive integer values. For example, we might want to prove that 2n is always an even number when n is any integer.

That's all fine and well, but what does induction mean for an actual algebra proof? Here's how mathematical induction works in three easy(ish) steps.

1. Prove the base case. In other words, show that when n = 1 (or some easy number in our set), the claim is true.
2. Assume the statement is true for n = k. This is called the induction hypothesis.
3. Prove that the statement is true when n = k + 1.

Let's look at each of 'em in a bit more detail.

1. Prove the base case.

First, we test our claim out on a small, easy value to see if it even works at all. For example, say we're trying to prove the general theory that 2n is always an even number when n is any positive integer.

We'd start out by plugging in n = 1, because it's easy, we're lazy, and it's the first positive integer.

2(1) = 2

Yep, 2 is even. We just proved our base case, which means our statement is true for at least that one value. Remember, inductive proofs start from the bottom, like Drake. Specific to general. Example to theory. It sounds out there, but it works.

By the way, one funny quirk of inductive proofs is that a single counterexample will ruin the entire proof. A counterexample is any value of n that makes the statement not true. If there's even one measly counterexample, then the general statement or theory can't possibly be true.

2. Induction hypothesis: assume the statement is true for n = k.

This is probably both the easiest and weirdest step, because it involves some Peter Pan-style make-believe. All we're doing here is swapping out the general term, n, for k, which stands for a specific term. Except we don't even need to pick an actual number. Literally just replace n with k in our original statement. For example:

2k is an even number.

Sure, it's an assumption, but we already know it's true for at least one specific number: the base case. We're just laying the groundwork here; we'll see why in a sec.

3. Prove that the statement is true when n = k + 1.

This is where the real meat of the proof comes in. Since we're already assuming our statement is true for n = k, now we need to prove that it's also true for the next integer, k + 1. If we can prove that, then we can prove the general theory.

In our example, now we'd replace k with k + 1:

2(k + 1) is an even number.

How do we prove that? The strategy will depend on the specific proof, but we usually want to manipulate our expression until the induction hypothesis n = k case shows up somewhere (that's the assumption that we "proved" in step 2). Let's multiply it out real quick.

2(k + 1) = 2k + 2

Now we're trying to prove that 2k + 2 is even. But hey, we already know that 2k is even from our assumption earlier. So it really looks like this:

2k + 2 = (even number) + 2

What happens when we add 2 to an even number? We always get another even number as our answer, that's what. Try it out:

2 + 2 = 4 (even)
6 + 2 = 8 (also even)
380 + 2 = 382 (yep, still even)

It's all even, all the time. There aren't any possible counterexamples where adding 2 to an even number doesn't give us an even number, so it must be true for all values of k.

We just proved that 2(k + 1) is an even number. Let's break down what exactly we've done.

We started out by proving that our statement was true for n = 1. We could also think of this as k = 1, since k can be any integer we want it to. From there, since we went from k to k + 1 and it worked just fine, we could run the whole proof again and again by adding 1 over and over. We're not gonna, but we could. If 2k is even, then 2(k + 1) is even, which means 2(k + 2) is even, which means 2(k + 3) is even, and so on for every possible positive integer, forever and ever, which means our original statement is true:

2n is always an even number when n is any positive integer.

Pretty tricky, right? We used one very specific statement to prove a general theory. We proved that the base case was true, and then we showed that every case after that would be true too, as long as we started with a true statement.

That example was at the shallow end of the pool, though. In the next section, we'll use these steps to dive into the deep end with a slightly harder proof. Better grab your sunscreen and water wings.

• ### Induction in Action

All this talk about mathematical induction might sound pretty abstract at first, so let's run through another specific example, yeah? Actually, let's walk through it, nice and slow-like.

### Sample Problem

Use mathematical induction to prove that 5n + 1 is always an even number when n is any positive integer.

Can we use our new inductive chops to make this happen? You bet. Just remember those three basic steps:

1. Prove the base case. In other words, show that when n = 1 (or some easy number in our set), the claim is true.
2. Induction hypothesis: assume the statement is true for n = k.
3. Prove that the statement is true when n = k + 1.

Let's start with the base case. Since n can be any positive integer in the known universe, we'll go with a nice, small value to make things easy: n = 1. Let's plug it in and see what happens.

51 + 1 = 5 + 1 = 6

Hey, look at that: 6 is definitely an even number, so our base case is true. That means we're in the clear and we can move on to the actual induction. Ready?

Now it's hypothesis time. We're gonna make the assumption that our claim is true when n = k. We don't actually know that's true for sure, but it's cool—inductive proofs always have an assumption like this in the middle. That means we can just swap out our n for a k:

5k + 1 is an even number.

This is probably the easiest part of the whole proof. Now comes the last step: we need to prove that the claim is also true for the next integer: k + 1. So we replace our k with k + 1.

5(k + 1) + 1

Now we just need to prove that this expression is also an even number. A good trick for doing this is to mess with our expression until the original n = k case shows up somewhere (since we already know that's even, from our induction hypothesis above), along with some other part of the expression we can also prove is an even number. Here we go.

First, let's split 5(k + 1) into two parts, using our handy exponent rules:

5(k + 1) + 1 = 5(5k) + 1

See what we did there? Since multiplying the same base means adding the exponents together (like how x2x3 = x(2 + 3) = x5), we can turn 5(k + 1) into 5(5k). So far, so good.

But remember, we wanna get our original 5k + 1 expression into the mix somehow. So what if we split up the 5(5k) part into two more pieces? If we think of that first 5 as a coefficient, we can split it into 4 + 1, right? For example, if we had 5x, we could split that into 4x + x. Well, just think of that x as 5k instead, and we can do 5(5k) = (4 + 1)5k = 4(5k) + 5k. It looks kinda gnarly, but it's the same exact thing. Let that sink in for a sec if you need to.

Now let's see what that does to our entire expression.

5(5k) + 1 = 4(5k) + 5k + 1

Hey, lookie there—we've got the original 5k + 1 on the right side. That means we're really dealing with two parts here: 4(5k) and 5k + 1. We already know the second half, 5k + 1, is an even number, since we "proved" it earlier. But what about 4(5k)?

Here's the thing: if we multiply 4 by any integer in the world, we're gonna get an even number back. Or to put it in fancy math-terms, the product of 4 and any integer will itself be a factor of 4, and all factors of 4 are even. Go ahead and try it out:

4 × 3 = 12
4 × 7 = 28
4 × 16 = 64
4 × 1,000,000 = 4,000,000

Yep, all even numbers. That means 4(5k) is always even too, no matter what 5k is. So both halves of our expression—4(5k) and 5k + 1—are even numbers, all the time. But we also learned a handy little theorem back in our early algebra days: the sum of two even numbers is always another even number. Remember that? We can check that baby out, too:

2 + 4 = 6
18 + 32 = 50
98 + 632 = 730

No matter which two even numbers we start with, we'll always get another even number as our sum. There aren't any counterexamples. And that means that the sum of 4(5k) and 5k + 1 is gonna be even, since both 4(5k) and 5k + 1 are even numbers on their own.

4(5k) is even,
5k + 1 is even,
therefore 4(5k) + (5k + 1) is even.

Boom! We just proved that our claim is true for n = k + 1, so we've proven that 5n + 1 is always an even number.

You may be asking yourself, how did what we did actually prove the statement? Think of it this way: we showed that if the statement is true for one integer, it's true for the next integer as well. Since we know the statement is true for n = 1 (that was our base case) it must now be true for n = 2 as well. Now that we know it's true for n = 2, it must be true for the next integer, 3. We can play this game all day long. The pattern continues, so the statement is true for every whole number.

We can use induction to prove all kinds of theorems and rules in math. What it basically tells us is that if we knock over the first domino in a set of dominoes, then the rest of the dominoes will fall down also. Now if we can only find someone to pick up the dominoes once we're through with them.

The proofs we've looked at so far have been all about directly proving something is true. That seems pretty obvious, but sometimes it's simpler to prove something isn't true. The truth is fun and all, but now it's time to put on your best fibbing face and tell some straight-up lies.

In a proof by contradiction (sometimes called an indirect proof), we prove our conclusion by showing that the opposite is impossible. To do this, we assume that the thing we're trying to prove is not true, and then show how that assumption leads to some kind of logical contradiction.

It's like trying to prove to your parents that you finished reading The Catcher in the Rye for your English class. They won't let you take the family station wagon to the movies this weekend otherwise, so you've got a lot riding on this proof.

You can't let them see inside your head to prove you read the book, so instead, you might show them a copy of your English midterm. "See? I got an A," you might say. "If I hadn't done the reading, there's no way I could've got that grade. Therefore, I did the reading."

You assumed the opposite was true (that you didn't do the reading), then you showed how your A on the midterm contradicted that assumption. Your parents would be suitably impressed by your proof by contradiction skills and hopefully let you off the hook.

Believe it or not, this type of proof is used fairly frequently by mathematicians. Proof by contradiction forms the bedrock of all kinds of theorems we take for granted, like the fact that intersecting lines cross at only one point, or that the square root of 2 is an irrational number.

1. Assume the statement you're trying to prove is false.
2. Try to prove the opposite statement (i.e., the negation).
4. State that since the contradiction disproves the negation, the original statement must be true.

Let's take these steps for a quick test drive.

### Sample Problem

Use contradiction to prove that there are an infinite number of positive integers.

Obviously, this would be obscenely hard to prove normally—how do we count to infinity? But with contradiction, it's actually pretty straightforward.

1. Assume the statement you're trying to prove is false.

Okay, let's assume that there isn't an infinite number of positive integers. In other words, there's a finite number of them, which means we should be able to count them all.

2. Try to prove the opposite statement (i.e., the negation).

Now we're trying to prove there's a finite number of positive integers. That means there must be one integer that's the biggest, right? "Finite" means they end somewhere, so there must be one integer at the end of the line.

We'll call this king of integers N. We should be able to theoretically count all the positive integers like this:

I = 1, 2, 3, 4, …, N

So far, so good.

We can always add 1 to any number. What happens if we add 1 to N? We already decided N was just some really huge integer, so there's nothing stopping us from adding 1 to it.

N + 1

Hey, wait a sec: N + 1 must, by definition, be larger than N. Or, in more math-y language:

N + 1 > N

Again, that's just how numbers work. Adding 1 makes any number larger. Plus, N + 1 must be an integer, because that's what happens when we add two integers together.

But since there exists a number N + 1 that's bigger than N, and since N + 1 must also be an integer, we just broke our proof. This is a contradiction: N can't be the biggest integer and also not the biggest integer.

That must mean there's no greatest integer, because we can keep on adding 1 as many times as we want.

4. State that since the contradiction disproves the negation, the original statement must be true.

Now we formalize our proof with some fancy language:

"Since it's always possible to find an integer N + 1 that's greater than an integer N, this contradicts the supposition that there's a finite number of positive integers. Hence, our original proposition is true: there's an infinite number of positive integers."

By the way, a proposition is just the statement we're proposing to be true (i.e., the original statement we're proving). A supposition is the statement we're supposing is true (i.e., our assumed opposite statement). We should always end our contradiction proofs with that same format we used above:

Since __________, this contradicts the supposition that __________. Hence, our original proposition is true: __________.

Like a mathematical Mad Lib, we can just fill in the blanks with the details from our actual problem.

## This is a premium product 