Number and Algebra

Proof by mathematical induction

This is a powerful technique used in mathematics to establish the truth of an infinite number of cases. It involves a base case, an inductive step, and an assumption known as the inductive hypothesis. The principle is similar to a row of dominoes falling: if you can knock over the first one (base case) and prove that if one domino falls, the next one will too (inductive step), then all the dominoes will fall in sequence (infinite cases proven).

The process of proof by induction involves the following steps:

$$\begin{align*} 1.\ & \text{Base Case: Show that the property holds for the first case, usually } n = 1.\\ 2.\ & \text{Inductive Step: Assume the property holds for } n = k. \text{(Inductive Hypothesis)}\\ 3.\ & \text{Prove that the property holds for } n = k + 1. \end{align*}$$

Here's an example to illustrate the process, proving that the sum of the first $n$ natural numbers is $\frac{n \cdot (n + 1)}{2}$.

$$\begin{align*} & \text{Base Case (} n = 1 \text{): } 1 = \frac{1 \cdot (1 + 1)}{2}, \text{ which is true.}\\ & \\ & \text{Inductive Step: Assume the formula holds for } n = k, \text{ i.e., } 1 + 2 + 3 + \cdots + k = \frac{k \cdot (k + 1)}{2}.\\ & \\ & \text{We need to prove for } n = k + 1, \text{ i.e., } 1 + 2 + 3 + \cdots + k + (k + 1) = \frac{(k+1) \cdot ((k + 1) + 1)}{2}.\\ & \\ & \text{Start from the left hand side of the equation we need to prove: }\\ & \\ & \text{LHS} = 1 + 2 + 3 + \cdots + k + (k + 1)\\ & \phantom{LHS} = \frac{k \cdot (k + 1)}{2} + k + 1 \quad \text{(By the inductive hypothesis)}\\ & \phantom{LHS} = \frac{k^2 + k + 2k + 2}{2}\\ & \phantom{LHS} = \frac{(k^2 + 3k + 2)}{2}\\ & \phantom{LHS} = \frac{(k+1) \cdot ((k + 1) + 1)}{2}\\ & \phantom{LHS} = \text{RHS} \end{align*}$$

Since both the base case and the inductive step have been proven, by the principle of mathematical induction, the statement is true for all positive integers $n$.

---

Proposition Notation

We can use $P_n$ to represent a proposition which is defined for every integer $n \ge a, \quad a \in \mathbb{Z}$

If $P_a$ is true, and if $P_{k+1}$ is true whenever $P_k$ is true then $P_n$ is true for all $n \ge a$.

---

Concluding Statement

Here is a typical concluding statement that is seen at the end of a proof by induction.

Since $P_0$ is true, and $P_{k+1}$ is true whenever $P_k$ is true, then $P_n$ is true for all $n \in \mathbb{Z}, \; n \ge 0$. {principle of mathematical induction}

---

Proof: Irrationality of $\sqrt{3}$ and $\sqrt[3]{5}$

Statement: (a) The square root of 3 is irrational. (b) The cube root of 5 is irrational.

Proof (a): Irrationality of $\sqrt{3}$

Let's prove by contradiction. Assume that $\sqrt{3}$ is rational.

Then, $\sqrt{3}$ can be expressed as a fraction $\frac{p}{q}$ where $p$ and $q$ are coprime integers (i.e., their greatest common divisor is 1) and $q \neq 0$.

$$\sqrt{3} = \frac{p}{q}$$

Squaring both sides:

$$3 = \left( \frac{p}{q} \right)^2$$

$$3q^2 = p^2$$

This implies that $p^2$ is divisible by 3, so $p$ must also be divisible by 3. Let $p = 3k$ for some integer $k$.

Substitute $p = 3k$ back into the equation $3q^2 = p^2$:

$$3q^2 = (3k)^2$$

$$3q^2 = 9k^2$$

$$q^2 = 3k^2$$

This implies that $q^2$ is also divisible by 3, so $q$ must also be divisible by 3.

However, this is a contradiction because we assumed that $p$ and $q$ are coprime, but we have shown that both are divisible by 3. Therefore, $\sqrt{3}$ must be irrational.

Proof (b): Irrationality of $\sqrt[3]{5}$

Let's prove by contradiction. Assume that $\sqrt[3]{5}$ is rational.

Then, $\sqrt[3]{5}$ can be expressed as a fraction $\frac{m}{n}$ where $m$ and $n$ are coprime integers and $n \neq 0$.

$$\sqrt[3]{5} = \frac{m}{n}$$

Cubing both sides:

$$5 = \left( \frac{m}{n} \right)^3$$

$$5n^3 = m^3$$

This implies that $m^3$ is divisible by 5, so $m$ must also be divisible by 5. Let $m = 5l$ for some integer $l$.

Substitute $m = 5l$ back into the equation $5n^3 = m^3$:

$$5n^3 = (5l)^3$$

$$5n^3 = 125l^3$$

$$n^3 = 25l^3$$

This implies that $n^3$ is also divisible by 5, so $n$ must also be divisible by 5.

However, this is a contradiction because we assumed that $m$ and $n$ are coprime, but we have shown that both are divisible by 5. Therefore, $\sqrt[3]{5}$ must be irrational.

Conclusion: Both $\sqrt{3}$ and $\sqrt[3]{5}$ are irrational numbers.

---

Euclid’s Proof of an Infinite Number of Prime Numbers

Euclid's proof is a classic example of a proof by contradiction. It is found in Euclid's Elements, Book IX, Proposition 20. Here's a simplified version of the proof:

Assumption:

Assume that there are only a finite number of prime numbers, say $p_1, p_2, p_3, \ldots, p_n$.

Construction:

1. Consider the number $N$ formed by multiplying all these assumed finite prime numbers together and then adding 1:

$$N = p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_n + 1$$

Contradiction:

2. Now, $N$ is either prime or composite.

• If $N$ is prime, then we have found a prime number not in our original list, which is a contradiction.
• If $N$ is composite, then it must have a prime factor.

3. Any prime factor of $N$ cannot be one of the primes in our original list because it would leave a remainder of 1 when divided by any of them.

For example, if $p$ is any prime in the list, then:

$$N \mod p = (p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_n + 1) \mod p = 1$$

4. Therefore, the prime factor of $N$ is another prime number not in our original list, which is again a contradiction.

Conclusion:

Since the assumption that there are only a finite number of prime numbers leads to a contradiction, we conclude that there must be an infinite number of prime numbers.

This elegant proof demonstrates that no matter how many prime numbers we have, we can always construct a new number that reveals the existence of yet another prime number, thus showing the infinitude of the primes.

---

Proof: Sum of a Rational and an Irrational Number

Statement: If $a$ is a rational number and $b$ is an irrational number, then $a + b$ is an irrational number.

Proof:

Let's prove this statement by contradiction. We will assume that the sum of a rational number $a$ and an irrational number $b$ is rational, and show that this leads to a contradiction.

Assumption:

Assume that $a$ is a rational number and $b$ is an irrational number, but $a + b$ is rational.

By definition, a rational number can be expressed as the quotient of two integers. So, we can write:

$$a = \frac{p}{q}$$

where $p$ and $q$ are integers and $q \neq 0$.

Since we are assuming that $a + b$ is rational, we can write:

$$a + b = \frac{m}{n}$$

where $m$ and $n$ are integers and $n \neq 0$.

Contradiction:

Now, let's isolate $b$ in the equation $a + b = \frac{m}{n}$:

$$b = \frac{m}{n} - a = \frac{m}{n} - \frac{p}{q} = \frac{mq - np}{nq}$$

Since the subtraction of two rational numbers is also a rational number, this implies that $b$ is rational, which is a contradiction because we assumed $b$ to be irrational.

Conclusion:

Since our assumption that $a + b$ is rational leads to a contradiction, we conclude that the sum of a rational number $a$ and an irrational number $b$ must be irrational.

---

Proof: Not All Elements of Set P are Prime

Statement: Consider the set $P$ of numbers of the form $n^2 + 41n + 41$ where $n$ belongs to the set of natural numbers $\mathbb{N}$. We need to show that not all elements of $P$ are prime.

Proof:

To show that not all elements of $P$ are prime, it is sufficient to find one value of $n$ for which $n^2 + 41n + 41$ is not a prime number.

Let's consider the expression:

$$n^2 + 41n + 41$$

For a number to be prime, it must be greater than 1 and have no positive divisors other than 1 and itself.

Let’s find a value of $n$ for which the expression yields a composite (non-prime) number:

Consider $n = 41$,

$$41^2 + 41 \cdot 41 + 41$$

$$41(41 + 41 + 1)$$

$$41(83)$$

Conclusion:

Since $41(83)$ is a product of two integers, both greater than 1, it is a composite number. Therefore, we have found a value of $n$, namely $n = 41$, for which $n^2 + 41n + 41$ is not a prime number. This demonstrates that not all elements of the set $P$ are prime.

---

Counterexample for Integer Solutions

We are given the statement that there are no positive integer solutions to the equation:

$$x^2 + y^2 = 10$$

To disprove this statement, we need to find at least one pair of positive integers $x$ and $y$ that satisfy the equation. A counterexample exists if we can find such a pair.

Let's consider the pair $(x, y) = (1, 3)$. Substituting these values into the equation gives:

$$1^2 + 3^2 = 1 + 9 = 10$$

Since $10 = 10$, the pair $(1, 3)$ is a solution to the equation, and thus, it serves as a counterexample to the given statement.

Now, let's delve into why this example serves as a counterexample. A counterexample is an example that refutes a statement or proposition. In this case, the statement to be disproven posits that there are no positive integer solutions to the equation $x^2 + y^2 = 10$. By finding a pair of positive integers, $(1, 3)$, that satisfies the equation, we have effectively shown that the original statement is not always true. Hence, the existence of this pair of positive integers serves as a counterexample, disproving the assertion that no such pairs exist.

In conclusion, the statement that there are no positive integer solutions to the equation $x^2 + y^2 = 10$ is not always true, as demonstrated by the counterexample $(x, y) = (1, 3)$.

---