4.02 Proof by deduction
When we solve a quadratic equation by factorisation, we are reasoning deductively.
By reasoning in this way we mean using a series of established algebraic procedures and laws to deduce a solution to the equation.
In some sense reasoning deductively is the process of distilling or drawing out new information out of things either taken as axiomatic or things that have previously been established. The machinery of distillation can include such things as axioms, established procedures, working rules of inference and other theorems.
Deductive reasoning often requires great insight and intuition and there is no shortage of great thinkers over the ages who have used their creativity and ingenuity to made important discoveries in mathematics.
Direct and Indirect proofs
There are two basic types of deductive proof. The first type of proof is called a direct proof.
direct proof:
Put simply, a direct proof begins with a given statement $p$p that is taken as true, and, through the application of rules, laws and/or axioms, establishes a new result $q$q.
A direct proof is based on the argument form called The Law of Detachment. The argument is given symbolically as:
| $P1$P1 | $:$: | $p\Rightarrow q$p⇒q |
| $P2$P2 | $:$: | $p$p |
| $C$C | $:$: | $\therefore$∴ $q$q |
Hence, assuming that $p$p is true, our aim is to deduce directly from $p$p that $q$q is also true.
As a simple example, consider the proof of the quadratic formula.
If we take as true that $ax^2+bx+c=0$ax2+bx+c=0 then, using the working rules of algebra, we can prove that$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$x=−b±√b2−4ac2a.
As another example, we can take the sum $S=1+2+3+...+n$S=1+2+3+...+n and apply algebraic processes to show that $S$S can also be expressed as $\frac{n\left(n+1\right)}{2}$n(n+1)2.
Thus if it is true that $S=1+2+3+...+n$S=1+2+3+...+n, then it is also true that $S=\frac{n\left(n+1\right)}{2}$S=n(n+1)2.
These two examples are explored further below.
indirect proof:
The logic of an indirect proof is based on the argument form called The Law of Contraposition:
| $P1$P1 | $=$= | $p\Rightarrow q$p⇒q |
| $P2$P2 | $=$= | $\sim q$~q |
| $C$C | $=$= | $\therefore$∴ $\sim p$~p |
In some instances, instead of trying to prove a statement like $p\Rightarrow q$p⇒q, we revert to an indirect approach and try to prove the statement $\sim q\Rightarrow\sim p$~q⇒~p.
In fact this is the approach taken prior to proving that $\sqrt{2}$√2 is irrational.
The standard approach to the that proof is based on the following argument:
| $P1$P1 | If $\sqrt{2}$√2 is rational, then it can be put into the form $\frac{m}{n}$mn, with $m,n$m,n integers and $n\ne0$n≠0 |
|---|---|
| $P2$P2 | $\sqrt{2}$√2 is not of the form $\frac{m}{n}$mn, with $m,n$m,n integers and $n\ne0$n≠0 |
| $C$C | $\therefore$∴ $\sqrt{2}$√2 is not rational. |
In other words if we can show that $\sqrt{2}$√2 is not of the form $\frac{m}{n}$mn where $m$m and $n$n are integers and $n$n non-zero, then we can conclude that $\sqrt{2}$√2 is not rational.
The actual proof is done using a proof type that is known as proof by contradiction. A description of this proof type can be found in the chapter headed Logic and Reasoning: Proof by Contradiction.
However we have included, in what follows, an example of an indirect proof (see example $6$6 below).
Examples of deductive proofs
We now discuss a number of examples of interesting and significant deductive proofs.
Example 1: The sum of the integers
As a famous example of this, consider the problem of finding the sum of consecutive positive integers from $1$1 through to $n$n.
If we write the sum in two ways, forward and reverse, as:
| $S_n$Sn | $=$= | $1+2+3+...+\left(n-2\right)+\left(n-1\right)+n$1+2+3+...+(n−2)+(n−1)+n $(1)$(1) |
| $S_n$Sn | $=$= | $n+\left(n-1\right)+\left(n-2\right)+...+3+2+1$n+(n−1)+(n−2)+...+3+2+1 $(2)$(2) |
If we add the two equations $(1)$(1) and $(2)$(2) together, term by term and vertically, we arrive at:
| $2S_n$2Sn | $=$= | $\left(n+1\right)+\left(n+1\right)+\left(n+1\right)+...+\left(n+1\right)+\left(n+1\right)+\left(n+1\right)$(n+1)+(n+1)+(n+1)+...+(n+1)+(n+1)+(n+1) |
| $2S_n$2Sn | $=$= | $n\left(n+1\right)$n(n+1) |
| $\therefore$∴ $S_n$Sn | $=$= | $\frac{n\left(n+1\right)}{2}$n(n+1)2 |
The insight to the sum formula is perhaps best understood by imagining two equal $n$n-step staircases, one turned upside down and placed carefully on top of the first, so as to create a rectangle of width $n$n and height $n+1$n+1. The sum is thus half the product of $n$n and $n+1$n+1.
Example 2: the sum of the squares of integers
Even more insightful is the formula for the sum of the squares of integers.
One way to proceed is to recognise, insightfully, that the difference in the two cubes $n^3$n3 and $\left(n-1\right)^3$(n−1)3 is the expression $3n^2-3n+1$3n2−3n+1.
Suppose we wrote down substitution instances of this fact from $1$1 to $n$n as follows:
| $1^3-0^3$13−03 | $=$= | $3\left(1^2\right)-3\left(1\right)+1$3(12)−3(1)+1 |
| $2^3-1^3$23−13 | $=$= | $3\left(2^2\right)-3\left(2\right)+1$3(22)−3(2)+1 |
| $3^3-2^3$33−23 | $=$= | $3\left(3^2\right)-3\left(3\right)+1$3(32)−3(3)+1 |
| $4^3-3^3$43−33 | $=$= | $3\left(4^2\right)-3\left(4\right)+1$3(42)−3(4)+1 |
| $...$... | $=$= | $...$... |
| $n^3-\left(n-1\right)^3$n3−(n−1)3 | $=$= | $3\left(n^2\right)-3\left(n\right)+1$3(n2)−3(n)+1 |
Remarkably, by adding all of the equations up vertically, term by term, the left hand side reduces to $n^3$n3.
The first terms on the right hand side add to $3\left(1^2+2^2+3^2+...+n^2\right)$3(12+22+32+...+n2) containing the very series we seek a formula for. The middle terms of each equation add to $-3\left(1+2+3+...+n\right)$−3(1+2+3+...+n) which, from the previous result becomes $-\frac{3n\left(n+1\right)}{2}$−3n(n+1)2. Of course the last terms add to $n$n.
Thus we can write the sum of these equations and rearrange as follows:
| $n^3$n3 | $=$= | $3\left(1^2+2^2+3^2+...+n^2\right)-\frac{3n\left(n+1\right)}{2}+n$3(12+22+32+...+n2)−3n(n+1)2+n |
| $3\left(1^2+2^2+3^2+...+n^2\right)$3(12+22+32+...+n2) | $=$= | $n^3+\frac{3n\left(n+1\right)}{2}-n$n3+3n(n+1)2−n |
| $1^2+2^2+3^2+...+n^2$12+22+32+...+n2 | $=$= | $\frac{1}{3}\left[n^3+\frac{3n\left(n+1\right)}{2}-n\right]$13[n3+3n(n+1)2−n] |
| $=$= | $\frac{n}{6}\left(2n^2+3n+2\right)$n6(2n2+3n+2) | |
| $=$= | $\frac{1}{6}n\left(n+1\right)\left(2n+1\right)$16n(n+1)(2n+1) | |
Example 3: ALL Primes greater than 3 are of the form 6n+1 or 6n-1
Any non-negative integer $N$N is expressible as either $6n$6n, $6n\pm1$6n±1, $6n\pm2$6n±2 or $6n+3$6n+3, where $n$n is an integer.
For example the number $23$23 is expressible as $6\left(4\right)-1$6(4)−1, and the number $1$1 is expressible as $6\left(0\right)+1$6(0)+1.
For $N>=3$N>=3.
- If $N$N is of the form $6n$6n then $N$N cannot be prime because it obviously contains the factor $6$6.
- If $N$N is of the form $6n\pm2$6n±2, it also cannot be prime because $6n\pm2=2\left(3n\pm1\right)$6n±2=2(3n±1) showing that $N$N contains the factor $2$2.
- If $N$N is of the form $6n+3$6n+3, then it too cannot be prime because, similarly, $6n+3=3(2n+1)$6n+3=3(2n+1) and thus $N$N contains the factor $3$3.
Hence, all primes greater than $3$3 must have the form $6n\pm1$6n±1.
Here is a diagram showing the first $36$36 positive integers in $6$6 by $6$6 grid. The two columns where primes greater than $3$3 reside are coloured yellow, and primes are highlighted in red. It's intriguing to think that every single prime greater than $3$3, no matter how large, is to be found in just one of two columns.
Example 4: The quadratic formula
Prove that, for the variable $x$x and constants $a$a, $b$b and $c$c, if $ax^2+bx+c=0$ax2+bx+c=0, then $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$x=−b±√b2−4ac2a.
Then we have:
| $ax^2+bx+c$ax2+bx+c | $=$= | $0$0 |
| $x^2+\frac{b}{a}x+\frac{c}{a}$x2+bax+ca | $=$= | $0$0 |
| $x^2+\frac{b}{a}x+\left(\frac{b}{2a}\right)^2+\frac{c}{a}$x2+bax+(b2a)2+ca | $=$= | $\left(\frac{b}{2a}\right)^2$(b2a)2 |
| $\left(x+\frac{b}{2a}\right)^2$(x+b2a)2 | $=$= | $\left(\frac{b}{2a}\right)^2-\frac{c}{a}$(b2a)2−ca |
| $\left(x+\frac{b}{2a}\right)^2$(x+b2a)2 | $=$= | $\frac{b^2-4ac}{4a^2}$b2−4ac4a2 |
| $x+\frac{b}{2a}$x+b2a | $=$= | $\pm\frac{\sqrt{b^2-4ac}}{2a}$±√b2−4ac2a |
Thus, isolating $x$x, we have that $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$x=−b±√b2−4ac2a, as required.
Example 5: in Any list of primes, at least one prime is missing
This famous proof by Euclid shows deduction at its best. Without continually searching for primes to see if there is a last highest prime, we can deduce that, given any list of primes, there is at least one prime missing. This implies that there is no list long enough to contain all primes, so that the number of primes must be infinite in extent.
Let's see if we can convince you:
Suppose we write down a list of three primes, say $p_1,p_2,p_3$p1,p2,p3.
Form the number $N=p_1\times p_2\times p_3+1$N=p1×p2×p3+1
Now $N$N could be prime, in which case our list of three primes is missing at least one prime!
But suppose $N$N was composite, so that $N$N contains prime factors.
Of those prime factors, we know that $p_1$p1 is not among them, because:
$\frac{N}{p_1}=\frac{p_{1\times}p_2\times p_3+1}{p_1}=\left(p_2\times p_3\right)+\frac{1}{p_1}$Np1=p1×p2×p3+1p1=(p2×p3)+1p1.
In other words, dividing by $p_1$p1 leaves a remainder of $1$1, so $p_1$p1 cannot be a prime factor of $N$N.
For exactly the same reason, $p_2$p2 and $p_3$p3 can't be prime factors of $N$N either, so that can only mean there is at least one prime (a prime factor of $N$N) that is not on our list!
Hence, no matter whether $N$N is prime or composite, we are missing at least one prime from our list.
Now it didn't really matter how many primes were on our list at the beginning. We can always form a number $N$N as $1$1 more than the product of the "list" primes, and deduce exactly the same result.
Hence, any list of primes is incomplete, implying without any doubt that the number of primes is infinite.
Example 6 If N^2 is odd, then so is N (An indirect approach)
It is quite difficult to prove directly that if $N^2$N2 is odd then $N$N is odd also.
So the trick is to take an indirect approach.
That is, by the Law of Contraposition, we can just as validly prove that if $N$N is not odd, then $N^2$N2 is not odd also.
If $N$N is not odd, then it is even, and thus of the form $2k$2k for some integer $k$k.
Thus $N^2=\left(2k\right)^2=2\left(2k^2\right)=2t$N2=(2k)2=2(2k2)=2t for some integer $t$t.
Therefore $N^2$N2 is even, and thus not odd. The proof is done!