2.4 A few examples of proofs

1 Introduction 2 Mathematics is not only about computing 2.1 Computation and abstraction 2.2 The structure of a mathematical text 2.3 What is a proof? 2.4 A few examples of proofs 2.5 What is not a proof? 3 Basic concepts 4 Elementary functions 5 Analytical geometry 6 Warning 7 List of the used symbols Index Bibliography

In this section, we will show some simple proofs of well-known and important statements. The reader will get acquainted to further proofs in the following chapters. In chapter 3.6 we will continue to practice this skill in proving several sum formulas.

Before we begin our first proof, let us refresh a few concepts, which will appear in the proven claim. We recall first the notions of rational and irrational real number.

Definition 2.1

A real number $x$ , which is the ratio of two integers, is called rational. A real number, which is not rational, is called irrational.

Furthermore, let us recall the notions of coprime and non-coprime numbers.

Definition 2.2

If two integer numbers $m$ and $n$ have common divisors (factors) other than $1$ , they are said non-coprime. We say that two integer numbers $m$ and $n$ are coprime, if the only positive integer that divides both of them is $1$ .

Question 2.1

Which of the following numbers are rational and which are irrational?

\frac{π}{2}, \frac{3}{4}, \sin \frac{π}{4}, \sin \frac{π}{6} .

Show answer

The numbers $\frac{3}{4}$ and $\sin \frac{π}{6} = \frac{1}{2}$ are rational, $\frac{π}{2}$ and $\sin \frac{π}{4} = \frac{\sqrt{2}}{2}$ are irrational.

Question 2.2

Which of the following pairs of numbers are coprime or non-coprime?

$7$ and $6330079$ ,
$\sqrt{2}$ and $2$ ,
$5192311$ and $36551$

Show answer

1. non-coprime (both can be divided by $7$ ), 2. neither coprime nor non-coprime, it is not a pair of integers, 3. coprime (both are prime numbers).

2.4.1 Proof by contradiction

We can use the so-called contradiction. The idea at the basis of a proof by contradiction is simple. One of the logic axioms says that every statement $T$ must be either true or false. Thus, if we show that the logical opposite (negation) of $T$ is false, then the original statement $T$ is true.

Theorem 2.1

The square root of $2$ is irrational .

We assume the opposite, that is $\sqrt{2}$ is rational . Thus, since it is also a positive number, there exist two natural and coprime integer numbers $p$ and $q$ satisfying

\sqrt{2} = \frac{p}{q} .

It follows⁵ the equality

2 = \frac{p^{2}}{q^{2}}, thus 2 q^{2} = p^{2} .

Since $2 q^{2}$ is even (it clearly can be divided by $2$ ), we see that also $p^{2}$ is even (otherwise above we would have an equality between an even and an odd number, which is impossible). The only way this can be true is that $p$ itself is even. Thus,⁶ $p = 2 k$ , where $k$ is a natural number. Substituting this equality into the above equation and dividing both sides by $2$ , we get $q^{2} = 2 k^{2}$ . If we use the same argument again, we get that also $q$ is even. Therefore, $p$ and $q$ are non-coprime (both can be divided by $2$ ). But such a situation cannot occur. Since by our assumption $p$ and $q$ are coprime , here we have come to a contradiction with our assumption, which therefore must be false. Thus $\sqrt{2}$ is irrational.

$◻$

Let us summarize the principle of the proof by contradiction. We want to be convinced of the truth of a certain claim $T$ (i.e. we want to prove it). We show that the logical opposite (negation) of $T$ is false. Thus, necessarily $T$ must be true.

2.4.2 Proof by mathematical induction

In the following, we illustrate the proof by mathematical induction. This type of proof is often used when we have infinitely many statements numbered by natural indices⁷, for example $T_{1}, T_{2}, T_{3}, \dots$ and we need to prove they are all true. The proof is done in two steps:

proove the first claim $T_{1}$ ,
for any natural $n$ prove the so-called induction step: if $T_{n}$ is true, then also $T_{n + 1}$ is true.

A graphical representation of this procedure is shown in figure 2.1. The red arrows correspond to the induction step. The starting point, i.e. the proof of $T_{1}$ , is indicated in blue.

Figure 2.1: Scheme of the proof by mathematical induction. Instead of proving that all

T_{n}

are true, for

n = 1, 2, \dots

, we can just prove that both

T_{1}

and the induction step, i.e. the assertion

T_{n} \Rightarrow T_{n + 1}

(red arrows) are true.

Mathematical induction can be compared to demolish a domino spiral. Each domino piece represents a „statement“ and can be in two states. A piece can be standing, or falling (similarly a statement can be true, or false). If we want to find out if the assembled domino spiral falls, we have two options. We can check all the pieces one by one and see if they fall. The second option is to check:

if the first piece falls,
two adjacent pieces are located at such a distance that if the first one falls (the one closer to the first piece) then its neighbor also falls (analog of the induction step).

Then we automatically know that all the pieces would fall. Let us emphasize the substantial difference in these approaches. The second method (ie, mathematical induction) controls the state of only the first piece, while it does not checks whether the others are standing or not, unless they are adjacent.

Let us illustrate the proof by mathematical induction for the so-called binomial theorem. In the statement of the theorem, we use the abbreviated sum, i.e. the summation notation, which the reader can find described more in detail in 3.6. Factorials, bynomial coefficients and general combinatorics are treated in section 3.7.

Theorem 2.2 (Binomial theorem)

For any real number $a$ and $b$ and any non negative integer number $n$ , i.e. for $a, b \in R$ and $n \in N_{0}$ , the following equality holds

\begin{matrix} (2.1) & (a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} . \end{matrix}

Let us verify that the equality being examined is true for the first $n$ considered, i.e. for $n = 0$ . The left-hand side of (2.1) is $(a + b)^{0} = 1$ and for the right-hand side we have

\sum_{k = 0}^{0} (\binom{0}{k}) a^{k} b^{0 - k} = 1 \cdot 1 \cdot 1 = 1.

The equality $1 = 1$ is certainly true. Now let us assume that (2.1) holds for $n \in N_{0}$ . Let us verify that (2.1) is true for $n + 1$ instead of $n$ . Thus we want to find out whether

(a + b)^{n + 1} = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) a^{k} b^{n + 1 - k} .

By direct calcuclation, we get⁸

\begin{aligned} (a + b)^{n + 1} & = (a + b) \cdot (a + b)^{n} \overset{!}{=} (a + b) \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} = \\ = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k} = \\ = \sum_{k = 1}^{n + 1} (\binom{n}{k - 1}) a^{k} b^{n + 1 - k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k} = \\ = \underset{a^{n + 1}}{\underset{⏟}{(\binom{n}{n}) a^{n + 1} b^{n + 1 - (n + 1)}}} + \sum_{k = 1}^{n} (\underset{(\binom{n + 1}{k})}{\underset{⏟}{(\binom{n}{k - 1}) + (\binom{n}{k})}}) a^{k} b^{n + 1 - k} + \\ + \underset{b^{n + 1}}{\underset{⏟}{(\binom{n}{0}) a^{0} b^{n + 1 - 0}}} = \\ = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) a^{k} b^{n + 1 - k} . \end{aligned}

In the equality marked by the exclamation point, we used the inductive assumption (the validity of the relation for $n$ ) and then we just performed algebraic operations. If we read the beginning and end of the calculation, we see that we have derived (2.1) for $n + 1$ , which was our goal.

$◻$

The claim of the binomial theorem contains well kown algebraic „formulas“

\begin{aligned} (a + b)^{2} & = a^{2} + 2 a b + b^{2}, \\ (a + b)^{3} & = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3} . \end{aligned}

The above formulas represent special cases of the binomial theorem for a particular chosen $n$ ( $n = 2, 3)$ . For such small values of $n$ , the formulas can be easily verified in an alternative way, by brackets expansion. For example for the first formula, thus for $n = 2$ we have

(a + b)^{2} = (a + b) \cdot (a + b) = a^{2} + a b + b a + b^{2} = a^{2} + 2 a b + b^{2} .

This calculation effectively proves the binomial theorem for $n = 2$ . Although in a similar way we could verify its validity also for $n = 3$ , this cannot be considered as a proof of the binomial theorem. We would lack the proof all the claims for $n = 3, 4, 5, \dots$ ! Fortunately, we did not have to prove all of them, thanks to the mathematical induction.

The importance ad utility of the binomial theorem can be further demonstrated on a concrete example (someone would say „trick“). Let us imagine that we are going to count $48^{2}$ quickly by our heads. We can take advantage of the fact that the number $48$ is close to $50$ , whose square is easy to calculate. Specifically, according to binomial theorem we have

48^{2} = (50 - 2)^{2} = 50^{2} - 2 \cdot 50 \cdot 2 + 4 = 2500 - 200 + 4 = 2304.

Question 2.3

What is the sum of the first $n$ odd natural numbers? I.e. what is the value of the sum

1 + 3 + 5 + \dots + (2 n - 1) = \sum_{j = 1}^{n} (2 j - 1), n \in N

equal to? Proove your claim.

Show answer

$\sum_{j = 1}^{n} (2 j - 1) = n^{2}$ . The proof by mathematical induction is easy and left to the reader.

2.4.3 Direct proof

Another type of proof is the direct proof. So to speak, without any detours, straightforwardly, we derive the claim from the assumptions. Consider the following theorem.

Theorem 2.3

For any real number $a$ and $b$ and $n \in N$ the following equality holds

\begin{matrix} (2.2) & a^{n} - b^{n} = (a - b) \sum_{k = 0}^{n - 1} a^{k} b^{n - 1 - k} . \end{matrix}

Show proof

Let us take $a, b \in R$ a $n \in N$ . We have to proove the equality (2.2). Let us start from the right-hand side of this equality and gradually adjust it through algebraic manipulation, to get the left-hand side of (2.2). Namely,

\begin{aligned} (a - b) \sum_{k = 0}^{n - 1} a^{k} b^{n - 1 - k} & = a \cdot \sum_{k = 0}^{n - 1} a^{k} b^{n - 1 - k} - b \cdot \sum_{k = 0}^{n - 1} a^{k} b^{n - 1 - k} = \\ = \sum_{k = 0}^{n - 1} a^{k + 1} b^{n - 1 - k} - \sum_{k = 0}^{n - 1} a^{k} b^{n - k} = \\ = \sum_{k = 1}^{n} a^{k} b^{n - k} - \sum_{k = 0}^{n - 1} a^{k} b^{n - k} = \\ = a^{n} + \sum_{k = 1}^{n - 1} a^{k} b^{n - k} - b^{n} - \sum_{k = 1}^{n - 1} a^{k} b^{n - k} = \\ = a^{n} - b^{n} . \end{aligned}

In other words, after multiplying the sum by the bracket $(a - b)$ , the majority of terms cancel each other by subtraction, leaving only the difference $a^{n} - b^{n}$ .

$◻$

Alternatively, it would be possible to proove theorem 2.3 by mathematical induction (try it!).

There are well known special cases of theorem 2.3:

\begin{aligned} a^{2} - b^{2} & = (a - b) (a + b), \\ a^{3} - b^{3} & = (a - b) (a^{2} + a b + b^{2}) . \end{aligned}

These formulas and the general formula 2.2 will be useful (not only) in calculating the limits in the future. What makes theorem 2.3 so useful? It allows us to express the difference of same powers of two numbers by the difference of the numbers themselves. In other words, if we have some information about the difference $a - b$ , then using this theorem we can infer something on the difference $a^{n} - b^{n}$ .

Remark 2.2

The proven equality (2.2) also contained the formula for the sum of the first terms of a geometric sequence with ratio $q \neq 1$ and starting by $1$ . Indeed, considering the formula in the theorem for $a = q \neq 1$ and $b = 1$ , we get

q^{n} - 1 = (q - 1) \sum_{k = 0}^{n - 1} q^{k}

and dividing by the non zero factor $q - 1$ , it follows

\sum_{k = 0}^{n - 1} q^{k} = \frac{q^{n} - 1}{q - 1}

section

Chapter