Linear Algebra/Techniques of Proof

Linear Algebra
 ← Quantifiers Techniques of Proof Sets, Functions, Relations → 


Many proofs are iterative, "Here's why the statement is true for for the case of the number  , it then follows for  , and from there to  , and so on ...". These are called proofs by induction. Such a proof has two steps. In the base step the proposition is established for some first number, often   or  . Then in the inductive step we assume that the proposition holds for numbers up to some   and deduce that it then holds for the next number  .

Here is an example.

We will prove that  .

For the base step we must show that the formula holds when  . That's easy, the sum of the first   number does indeed equal  .

For the inductive step, assume that the formula holds for the numbers  . That is, assume all of these instances of the formula.


From this assumption we will deduce that the formula therefore also holds in the   next case. The deduction is straightforward algebra.


We've shown in the base case that the above proposition holds for  . We've shown in the inductive step that if it holds for the case of   then it also holds for  ; therefore it does hold for  . We've also shown in the inductive step that if the statement holds for the cases of   and   then it also holds for the next case  , etc. Thus it holds for any natural number greater than or equal to  .

Here is another example.

We will prove that every integer greater than   is a product of primes.

The base step is easy:   is the product of a single prime.

For the inductive step assume that each of   is a product of primes, aiming to show   is also a product of primes. There are two possibilities: (i) if   is not divisible by a number smaller than itself then it is a prime and so is the product of primes, and (ii) if   is divisible then its factors can be written as a product of primes (by the inductive hypothesis) and so   can be rewritten as a product of primes. That ends the proof.

(Remark. The Prime Factorization Theorem of Number Theory says that not only does a factorization exist, but that it is unique. We've shown the easy half.)

There are two things to note about the "next number" in an induction argument.

For one thing, while induction works on the integers, it's no good on the reals. There is no "next" real.

The other thing is that we sometimes use induction to go down, say, from   to   to  , etc., down to  . So "next number" could mean "next lowest number". Of course, at the end we have not shown the fact for all natural numbers, only for those less than or equal to  .


Another technique of proof is to show something is true by showing it can't be false.

The classic example is Euclid's, that there are infinitely many primes.

Suppose there are only finitely many primes  . Consider  . None of the primes on this supposedly exhaustive list divides that number evenly, each leaves a remainder of  . But every number is a product of primes so this can't be. Thus there cannot be only finitely many primes.

Every proof by contradiction has the same form: assume that the false proposition is true and derive some contradiction to known facts. This kind of logic is known as Aristotelian Logic, or Term Logic

Another example is this proof that   is not a rational number.

Suppose that  .


Factor out the  's:   and   and rewrite.


The Prime Factorization Theorem says that there must be the same number of factors of   on both sides, but there are an odd number   on the left and an even number   on the right. That's a contradiction, so a rational with a square of   cannot be.

Both of these examples aimed to prove something doesn't exist. A negative proposition often suggests a proof by contradiction.

Linear Algebra
 ← Quantifiers Techniques of Proof Sets, Functions, Relations →