# Proof Techniques

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/proof-techniques

## Establishing Truth Beyond Doubt

Mathematics advances by **proof**: an airtight chain of logical steps from accepted premises to a conclusion. A correct proof settles a claim for all cases at once.

**Direct proof** assumes the hypothesis and derives the conclusion step by step. To prove "if $n$ is even then $n^2$ is even," write $n = 2k$, so $n^2 = 4k^2 = 2(2k^2)$, which is even.

**Proof by contrapositive** proves $p \to q$ by instead proving the equivalent $\neg q \to \neg p$. To prove "if $n^2$ is even then $n$ is even," it is cleaner to prove "if $n$ is odd then $n^2$ is odd."

## Contradiction, Disproof, and Pitfalls

**Proof by contradiction** assumes the claim is false, then derives an impossibility. The classic example proves $\sqrt{2}$ is irrational by assuming it equals a fraction in lowest terms and deriving that both parts are even.

**Disproof** uses a **counterexample** to show a universal claim is false. One failure demolishes it.

| Technique | What You Assume | What You Show |
| --- | --- | --- |
| **Direct** | $p$ | $q$ |
| **Contrapositive** | $\neg q$ | $\neg p$ |
| **Contradiction** | $\neg(\text{claim})$ | absurdity |

> **Common pitfall:** Confusing **contradiction** (assumes whole claim false, seeks **any** absurdity) with **contrapositive** (proves $\neg q \to \neg p$). A supporting example never **proves** a universal claim.

## Practice questions

4 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Order the steps of a direct proof that if n is even then n squared is even.

**Answer:**

1. Assume the hypothesis: n is even
2. Write n = 2k for some integer k, which is what being even means
3. Square both sides to get n squared = 4k squared
4. Rewrite 4k squared as 2 times (2k squared), an integer doubled
5. Conclude that n squared is even, as required

**Why:** A direct proof assumes the hypothesis, converts definitions into usable algebra, manipulates, and converts back. The final rewriting step matters: 4k squared is not obviously even until it is displayed as 2 times an integer, which is exactly the definition being claimed.

Page: https://tryals.app/practice/computer-science-i/proof-techniques/order-the-steps-of-a-direct-proof-that-if-n-is-even-then-n-squared-is

### 2. A proof by contradiction and a proof by contrapositive both begin by assuming something false. Which is preferred for an implication, and why?

A. Neither is preferred; they are notational variants of one technique
B. Contrapositive, which carries one assumption and a named target
C. Contradiction, because deriving any falsehood is easier than a specific conclusion
D. Contradiction, because contrapositive applies only to statements about numbers

**Answer:** B. Contrapositive, which carries one assumption and a named target

**Why:** Contrapositive assumes ¬q and aims at ¬p; contradiction assumes p and ¬q and searches for any absurdity. Fewer assumptions and a specific target make the first easier to write and to read. Contradiction earns its place where there is no implication to contrapose, the irrationality of √2 being the standard case.

Page: https://tryals.app/practice/computer-science-i/proof-techniques/a-proof-by-contradiction-and-a-proof-by-contrapositive-both-begin-by

### 3. A student proves "if $n^{2}$ is even then $n$ is even" by assuming $n$ is odd, writing $n = 2k+1$, and deriving that $n^{2}$ is odd. Which technique is this, and is the proof finished?

A. Contrapositive, and it is finished, since the two are logically equivalent.
B. Contrapositive, but unfinished, the converse "$n$ even $\Rightarrow n^{2}$ even" still has to be shown.
C. Contradiction, and it is unfinished, because no absurdity was ever reached.
D. A direct proof, and it is finished, because it starts from the definition of an odd number.

**Answer:** A. Contrapositive, and it is finished, since the two are logically equivalent.

**Why:** A conditional and its contrapositive are the same statement, so once "$n$ odd $\Rightarrow n^{2}$ odd" is proved there is nothing left to do. The last option confuses the contrapositive with the converse, which is a different claim.

Page: https://tryals.app/practice/computer-science-i/proof-techniques/a-student-proves-if-n-is-even-then-n-is-even-by-assuming-n-is-odd

### 4. The claim is: for every integer n, if n squared is odd then n is odd. Select every approach that would genuinely establish it.

A. Assume n squared is odd, write n squared = 2k + 1, and reason directly to n being odd
B. Check that the claim holds for n = 1, 3, 5 and 7
C. Assume n is even and show that n squared is even
D. Assume n squared is odd and n is even, and derive a contradiction
E. Exhibit an integer for which the claim fails

**Answer:** A. Assume n squared is odd, write n squared = 2k + 1, and reason directly to n being odd; C. Assume n is even and show that n squared is even; D. Assume n squared is odd and n is even, and derive a contradiction

**Why:** Option 1 is the contrapositive, option 4 is contradiction, option 1 is a direct proof, all three are valid routes. Checking particular values proves nothing about a universal claim, and a counterexample would disprove it, not prove it. Notice how naturally the contrapositive falls out here: 'if n is even then n squared is even' is a one-line argument.

Page: https://tryals.app/practice/computer-science-i/proof-techniques/the-claim-is-for-every-integer-n-if-n-squared-is-odd-then-n-is-odd