Direct proof

Back when we’ve been discussing set cardinality, we’ve successfully proved a statement: If A is a finite set of m elements, then there are 2^{m} subsets of A. Let’s talk about proofs in more detail, and discuss different proof techniques. A proof is a sequence of mathematical statements, a path from some basic truth to the desired outcome. An impeccable argument, if you will. The simplest form of proof is a direct proof. It’s a straightforward attempt to see what the statement means if we dare to play with it. Consider a theorem:

Theorem 1. If n is an odd positive integer, then n^2 is odd.

Proof. An odd positive integer can be written as n = 2k + 1, since something like 2k is even and adding 1 makes it definitely odd. We’re interested in what odd squared looks like, so let’s square this definition:

n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1

So, we have this final formula 2(2k^2 + 2k) + 1 and it follows the pattern of 2k + 1. This means it’s odd! We have a proof. \blacksquare¹.

This theorem is based on an idea that numbers described as 2k + 1 are definitely odd. This idea could be another theorem that requires another proof, and that proof would be based on some other theorems. The general idea of mathematics is that if you follow any theorem to the very beginning, you’ll meet the fundamental axioms, the basis of everything.