Proof Techniques | Computer Science

To prove $P \implies Q$: assume $P$Derive $Q$ by a chain of logical deductions.

Example. Prove: if $n$ is odd, then $n^2$ is odd.

Proof. Let $n = 2k + 1$. Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$Which is odd. $\blacksquare$

Worked Example. Prove: the sum of any two rational numbers is rational.

To prove $P \implies Q$: prove $\neg Q \implies \neg P$ instead.

Example. Prove: if $n^2$ is even, then $n$ is even.

Proof. Contrapositive: if $n$ is odd, then $n^2$ is odd. This was proved above. $\blacksquare$

Worked Example. Prove: if $3n + 2$ is odd, then $n$ is odd.

To prove $P$: assume $\neg P$ and derive a contradiction.

Example (Euclid). There are infinitely many primes.

Proof. Suppose there are finitely many primes $p_1, p_2, \ldots, p_n$. Consider $N = p_1 p_2 \cdots p_n + 1$. $N$ is not divisible by any $p_i$ (it leaves remainder 1). So $N$ is either prime itself or has a prime Factor not in the list. Either way, the list was incomplete. Contradiction. $\blacksquare$

Worked Example. Prove: $\sqrt{2}$ is irrational.

Principle of Mathematical Induction. To prove $P(n)$ for all $n \geq n_0$:

1. Base case: Prove $P(n_0)$.
2. Inductive step: Prove $P(k) \implies P(k+1)$ for all $k \geq n_0$.

Strong Induction. The inductive step assumes $P(n_0), P(n_0+1), \ldots, P(k)$ to prove $P(k+1)$.

Example. Prove: $\sum_{i=1}^{n} i = n(n+1)/2$ for all $n \geq 1$.

Proof. Base case: $n = 1$: $1 = 1 \cdot 2 / 2$. True.

Inductive step: Assume $\sum_{i=1}^{k} i = k(k+1)/2$. Then

$\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

$\blacksquare$

Worked Example. Prove by strong induction: every integer $n \geq 2$ can be factored into primes.

Worked Example. Prove: $\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$ for all $n \geq 0$.

For recursively defined structures (lists, trees, formulas), prove a property by induction on the Structure:

1. Base cases (empty list, leaf node, atomic formula).
2. Inductive cases (cons, node with children, compound formula).

Well-Ordering Principle (WOP). Every nonempty set of nonnegative integers has a least element.

Theorem 3.1. The Well-Ordering Principle is equivalent to the Principle of Mathematical Induction.

Proof (WOP implies induction). Let $P(n)$ be a property with $P(0)$ true and $P(k) \implies P(k+1)$. Suppose for contradiction that $P(n)$ fails for some $n \geq 0$. Let S = \\{n \geq 0 : P(n)\; \mathrm{is\; false{}\\}. By assumption $S \neq \emptyset$ So by WOP, $S$ has a least Element $m$. Since $P(0)$ is true, $m \geq 1$. Then $P(m - 1)$ is true (by minimality of $m$), And $P(m - 1) \implies P(m)$ by the inductive hypothesis, so $P(m)$ is true, contradicting $m \in S$. Therefore $S = \emptyset$ and $P(n)$ holds for all $n \geq 0$.

Proof (induction implies WOP). Let $S \subseteq \mathbb{N}$ be nonempty. We prove by induction that If $S \cap \\{0, 1, \ldots, n\\} \neq \emptyset$ Then $S$ has a least element. For $n = 0$, $S$ Contains $0$Which is the least element. Assume the claim for $n = k$. If $0 \in S \cap \\{0, \ldots, k+1\\}$ Then $0$ is the least element. Otherwise $S \cap \\{0, \ldots, k+1\\} = S \cap \\{1, \ldots, k+1\\}$ And by The induction hypothesis applied to the shifted set, a least element exists. $\blacksquare$

Worked Example. Use the WOP to prove that every $n \geq 1$ can be written as a sum of distinct Powers of 2.

flowchart TD
    A[3_Proof Techniques] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

Proof techniques establish mathematical truth. Direct proof assumes premises and derives conclusions. Proof by contradiction assumes the negation and finds a contradiction. Mathematical induction proves statements for all natural numbers by showing a base case and inductive step. These techniques are essential for verifying algorithm correctness, proving complexity bounds, and establishing security properties.

Circular reasoning in direct proofs. A proof is circular when the conclusion is assumed (even implicitly) in the premises. For example, proving “if $n$ is even then $n^2$ is even” by writing $n = 2k$ so $n^2 = 4k^2 = 2(2k^2)$ is valid, but assuming $n^2$ is even to prove $n$ is even is not. Always verify that your assumptions do not presuppose the result.

Incorrect base case in mathematical induction. Students sometimes start induction at $n = 0$ when the statement only holds for $n \geq 1$, or verify only one base case when the inductive step requires two (as with Fibonacci-type recurrences). Check that the base case matches the domain of the statement and that enough base cases are proven.

Confusing contrapositive with converse. The contrapositive of $P \implies Q$ is $\neg Q \implies \neg P$, which is logically equivalent to the original. The converse is $Q \implies P$, which is not equivalent. Proving the converse does not prove the original statement.

• [[1-discrete-mathematics/1_propositional-and-predicate-logic]] - Logical foundations

• [[1-discrete-mathematics/2_sets-relations-and-functions]] - Set-theoretic proofs

• [[1-algorithms/algorithm_design]] - Algorithm correctness proofs

• [[1-algorithms/complexity-theory]] - Complexity proofs

• Discrete Mathematics

• Algorithm Implementation

• Discrete Mathematics
• Propositional and Predicate Logic
• Sets, Relations, and Functions