Linear Algebra, Techniques of Proof

Induction

Many proofs are iterative,
"Here's why the statement is true for for the case of the number 1,
it then follows for 2, and from there to 3, 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 0 or 1.
Then in the inductive step
we assume that the proposition
holds for numbers up to some k
and deduce that it then holds for the next number k + 1.

Here is an example.

We will prove that {}1 + 2 + 3 + … + n = n ( n + 1 ) / 2.

For the base step we must show that the formula holds when n = 1.
That's easy, the sum of the first 1 number does indeed equal
{}1 ( 1 + 1 ) / 2.

For the inductive step, assume that the formula holds
for the numbers {}1 , 2 , … , k.
That is, assume all of these instances of the formula.

\begin{matrix}1 & = 1 ( 1 + 1 ) / 2 \\ \text{and} \ 1 + 2 & = 2 ( 2 + 1 ) / 2 \\ \text{and} \ 1 + 2 + 3 & = 3 ( 3 + 1 ) / 2 \\ & ⋮ \\ \text{and} \ 1 + … + k & = k ( k + 1 ) / 2\end{matrix}

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

{}1 + 2 + ⋯ + k + ( k + 1 ) = \frac{k ( k + 1 )}{2} + ( k + 1 ) = \frac{( k + 1 ) ( k + 2 )}{2}

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

Here is another example.

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

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

For the inductive step assume that each of {}2 , 3 , … , k is a
product of primes, aiming to show k + 1 is also a product of
primes.
There are two possibilities:
(i) if k + 1 is not divisible by a number smaller than itself then it
is a prime and so is the product of primes,
and (ii) if k + 1 is divisible then its
factors can be written as a product of primes (by the inductive hypothesis)
and so k + 1 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
10 to 9 to 8, etc., down to 0.
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 10.

Contradiction

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 {p}_{1} , … , {p}_{k}.
Consider {p}_{1} ⋅ {p}_{2} … {p}_{k} + 1.
None of the primes on this supposedly exhaustive list divides that number
evenly, each leaves a remainder of 1.
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
\sqrt{2} is not a rational number.

Suppose that \sqrt{2} = m / n.

{}2 {n}^{2} = {m}^{2}

Factor out the 2's:
n = {2}^{{k}_{n}} ⋅ \overset{̂}{n}
and
m = {2}^{{k}_{m}} ⋅ \overset{̂}{m}
and rewrite.

{}2 ⋅ ( {2}^{{k}_{n}} ⋅ \overset{̂}{n} {)}^{2} = ( {2}^{{k}_{m}} ⋅ \overset{̂}{m} {)}^{2}

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

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

Where this page came from

This page was imported from Wikibooks. From “Linear Algebra” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.