Problem Statement

Given an integer $n$, prove that $3n+2$ is odd if and only if $9n+5$ is even.

Proof

If and only if statements can be broken down into two separate statements. We will first prove that if $3n+2$ is odd, then $9n+5$ is even. Then we will prove that if $9n+5$ is even, then $3n+2$ is odd. This is sufficient for $p$ if and only if $q$.

---

Case 1 (contradiction)

Prove that for a given integer $n$, if $3n+2$ is odd, then $9n+5$ is even

Suppose for the sake of contradiction that $3n+2$ is even. Then by definition there exists some integer $k$ such that $3n+2=2k$ and it follows that $n = \frac{2k-2}{3}$ and

$$\begin{align*} 9n+5 &= 9(\frac{2k-2}{3}) + 5 \\ &= 3(2k-2) + 5 \\ &= 2(3k-3) + 5 \end{align*}$$

and the term $(3k-3)$ is just an integer we will denote $t$. It follows that

$$9n+5 = 2t + 5$$

It is a proven fact that the sum of an even integer and an odd integer is an odd integer. Notice how we have an odd term plus an even term on the right side of our equation. It follows that $9n+5$ is odd.

Here, we have reached a contradiction as $9n+5$ is odd when $3n+2$ is even. Therefore, if $3n+2$ is odd, then $9n+5$ is even.

---

Case 2 (contradiction)

Prove that for a given integer $n$, if $9n+5$ is even the $3n+2$ is odd

Suppose for the sake of contradiction that $9n +5$ is odd. Then by definition $9n+5 = 2k+1$ for some integer $k$. It follows that $n =\frac{2k-4}{9}$ and

$$\begin{align*} 3n+2 &= 3(\frac{2k-4}{9}) + 2 \\ &= 2(\frac{3k-6}{3}) + 2 \end{align*}$$

notice how the term $(\frac{3k-6}{3})$ is some integer we will denote $t$. It follows that

$$3n+2 = 2t + 2$$

It is a proven fact that the sum of two even integers is an even integer. Notice how the two terms on the right are both even. It follows that $3n+2$ is even.

Here we have reached a contradiction as $3n+2$ is even when $9n+5$ is odd. Therefore, if $9n+5$ is even, then $3n+2$ is odd

---

Conclusion

Proving $3n+2$ is odd when $9n+5$ is even and $9n+5$ is even when $3n+2$ is odd is sufficient for $3n+2$ is odd if and only if $9n+5$ is even for a given integer $k$

$$\blacksquare$$

Problem Statement

We say a function $f : \mathbb{R} \rightarrow \mathbb{R}$ is bijective (or invertible) if for any $y \in \mathbb{R}$ there exists a unique $x \in \mathbb{R}$ such that $f(x) = y$.

Proof

Let $y \in \mathbb{R}$, we will prove that there exists a unique element $x \in \mathbb{R}$ such that $f(x) = 2x + 1 = y$.

Let $x = \frac{y - 1}{2}$, then

$$f(x) = 2\left(\frac{y - 1}{2}\right) + 1 = y - 1 + 1 = y$$

Now suppose there exists another number $z \in \mathbb{R}$ such that $f(z) = y$. Then $f(z) = f(x)$ so

$$2z + 1 = 2x + 1 \implies 2z = 2x \implies z = x$$

Therefore, $x$ is unique. In conclusion, there exists a unique $x \in \mathbb{R}$ such that $f(x) = 2x + 1 = y$ for any $y \in \mathbb{R}$, so $f(x)$ is bijective.

$$\blacksquare$$

Problem Statement

Let $a,b,c$ be three real numbers and let $m$ be their average so $m = \frac{(a+b+c)}{3}$. Prove that at least one of $a,b,c$ is less than or equal to $m$

Proof (contradiction)

Let $a,b,c$ be three real numbers. Let $m$ denote the average of $a,b,c$ so $m = \frac{(a+b+c)}{3}$.

For the sake of contradiction suppose $a,b,c$ are all strictly greater than $m$. Therefore,

$$\begin{align*} a &> m \\ b &> m \\ c &> m \\ \end{align*}$$

Summing these together we see that

$$\begin{align*} a + b + c &> m + m + m \\ a + b + c &> 3m \\ \frac{a + b + c}{3} &> m \end{align*}$$

Here we have a contradiction as $m$ is the average and must equal $\frac{(a + b + c)}{3}$. Therefore, at least one of the real numbers $a,b,c$ is less than or equal to $m$.

$$\blacksquare$$

Problem Statement

Suppose there are two integers $x$ and $y$. Prove using the contrapositive statement that if $x^{2} * (y+3)$ is even then x is even or y is odd

Proof (contrapositive)

We will prove this statement by proving its contrapositive.

Contrapositive Statement: If $x$ is an odd integer and $y$ is an even integer, then $x^2(y + 3)$ is odd.

Suppose there is some odd integer $x$ and some even integer $y$. By definition, there exist integers $a$ and $k$ such that $x = 2a + 1$ and $y = 2k$.

Substituting for $x$ and $y$ respectively:

$$\begin{align*} x^{2}(y+3) &= (2a + 1)^{2} * (2k + 3) \\ &= (4a^2 + 4a + 1) * (2k + 3) \\ &= (8a^2k + 8ak + 2k) + (12a^2 + 12a + 3) \\ &= 2(4a^2k + 4ak + k + 6a^2 + 6a +1) + 1 \end{align*}$$

Now, notice that the term $(4a^2k + 4ak + k + 6a^2 + 6a +1)$ is an integer we will denote $j$. Thus $x^{2}(y + 3) = 2j + 1$ for some integer $j$. By definition, $x^{2}(y+3)^2$ is an odd integer.

We have shown that when $x$ is an odd integer and $y$ an even integer, $x^2(y + 3)$ is odd. Therefore, we have proven the contrapositive, which is equivalent to proving the original statement. Therefore, $x^{2} * (y+3)$ is even when $x$ is even or $y$ is odd.

$$\blacksquare$$

Problem Statement

A perfect square is an integer $n$ for which there exists an integer $k$ such that $n = k^2$. We aim to prove that if $n$ is a positive integer such that $(n \equiv 2 \mod 4)$ or $(n \equiv 3 \mod 4)$, then $n$ is not a perfect square.

Proof (contrapositive)

We will prove the above statement by proving its contrapositive:

Contrapositive Statement: If $n$ is a positive integer and $n$ is a perfect square, then $n$ mod four does not equal two and $n$ mod four does not equal 3.

Suppose $n$ is some positive integer and $n$ is a perfect square. It follows by the definition of a perfect square that there exists an integer $k$ such that $n = k^2$.

We will consider two cases when $k$ is even and when $k$ is odd.

---

Case 1 (k is even)

Suppose $k = 2a$ for some integer $a$. Then, $n = k^2 = (2a)^2 = 4a^2$ $n$ is divisible by four, hence $n \mod 4 = 0$.

---

Case 2 (k is odd)

Suppose $k = 2a + 1$ for some integer $a$. Then, $n = k^2 = (2a + 1)^2 = 4a^2 + 4a + 1 = 4(a^2 + a) + 1$ $n$ will always be one greater than a number divisible by four. Therefore, dividing $n$ by four will result in a remainder of one.

---

Conclusion

With these two cases, we have shown that for any positive integer $n$ that is a perfect square, $n$ mod four does not equal two and $n$ mod four does not equal 3. Therefore, we have proven the contrapositive statement, which is equivalent to proving the original statement. It follows that if $n$ is a positive integer such that $(n \equiv 2 \mod 4)$ or $(n \equiv 3 \mod 4)$, then $n$ is not a perfect square.

$$\blacksquare$$

Problem Statement

We aim to prove by contrapositive that if $a$ and $b$ are integers such that $4|(a^2 + b^2)$, then $a$ and $b$ must both be even.

Proof (contrapositive)

We will prove the above statement by proving its contrapositive:

Contrapositive Statement: Let $a$ and $b$ denote two integers. If $a$ or $b$ are odd, then $4 \nmid (a^2 + b^2)$.

Suppose $a$ is odd. Then by definition, there exists some integer $k$ such that $a = 2k + 1$. It follows:

$$(a^2 + b^2) = ((2k + 1)^2 + b^2) = (4k^2 + 4k + 1 + b^2) = (4(k^2 + k) + 1 + b^2)$$

We see that when $a$ is an odd integer, four does not divide $a^2$ and leaves a remainder of one. When $a$ is odd, we have two possible cases that follow: $b$ is either even or odd.

Case 1 (b is even)

Suppose $b$ is an even integer. Then by definition, there exists some integer $t$ such that $b = 2t$. It follows that:

$$(a^2 + b^2) = ((2k + 1)^2 + (2t)^2) = (4k^2 + 4k + 1 + 4t^2) = 4(k^2 + k + t^2) + 1$$

We see that there will always be a remainder of one. Therefore, when $a$ is odd and $b$ is even, four does not divide $(a^2 + b^2)$.

Case 2 (b is odd)

Suppose $b$ is an odd integer. Then by definition, there exists some integer $t$ such that $b = 2t + 1$. It follows that:

$$(a^2 + b^2) = ((2k + 1)^2 + (2t + 1)^2) = (4k^2 + 4k + 1 + 4t^2 + 1) = 4(k^2 + k + t^2) + 2$$

We see that there will always be a remainder of two. Therefore, when $a$ is odd and $b$ is odd, four does not divide $(a^2 + b^2)$.

We have shown that if $a$ is an odd integer, it is sufficient for $4 \nmid (a^2 + b^2)$.

The same argument holds if we had initially assumed $b$ to be an odd integer, resulting in the exact same conclusions.

Therefore, we have proven the contrapositive statement: if $a$ or $b$ are odd integers, then $4 \nmid (a^2 + b^2)$. It follows that if $a$ and $b$ are integers such that $4|(a^2 + b^2)$, then $a$ and $b$ must both be even.

$$\blacksquare$$

Problem Statement

Let $a, b, c, d$ be natural numbers such that

$$\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d} = 1$$

We aim to prove that at least one of the numbers $a, b, c, d$ is even.

Proof (contradiction)

We suppose, for the sake of contradiction, that the natural numbers $a, b, c, d$ are all odd and

$$\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d} = 1$$

By manipulating the given equality, we see that

$$1 = \frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d} = \frac{b + a}{ab} + \frac{d + c}{cd} = \frac{cd(b+a) + ab(d+c)}{abcd} = \frac{(cdb + cda) + (abd + abc)}{abcd}$$

It is known that the product of any two odd numbers is odd, and the sum of any two odd numbers is even.

We observe that the terms $cd$ and $ab$ are the product of two odd numbers, which is odd. When distributing the terms over $(b + a)$ and $(d + c)$ respectively, we are multiplying two odd numbers together: $(cd)b, (cd)a, (ab)d, (ab)c$, which is odd. The sum of two odd numbers is even.

Therefore, there exist some integers $k$ and $t$ such that $(cdb + cda) = 2k$ and $(abd + abc) = 2t$.

We see that the term in the denominator $abcd$ is the product of all odd numbers, therefore $abcd$ is odd and by definition $abcd = 2n + 1$ for some integer $n$. Therefore,

$$1 = \frac{(cdb + cda) + (abd + abc)}{abcd} = \frac{2(k + t)}{2n + 1}$$

Multiplying both sides by $2n + 1$, we reach the following equality:

$$(2n + 1) * 1 = 2(k + t)$$

This equality says that the product of two odd numbers $(2n+1)$ and $1$ equals some even number $2(k + t)$. However, it is known that the product of two odd numbers is odd. Therefore, we have reached a contradiction, and at least one of the natural numbers $a, b, c, d$ must be even.

$$\blacksquare$$

Problem Statement

Let $r$ be some nonzero rational number and $y$ be some irrational number. We aim to prove that the product of $r$ and $y$ is irrational.

Proof (contradiction)

Let $r$ be some nonzero rational number. Then by definition, there exist two integers $p$ and $q$ such that $q \neq 0$, gcd($p$,$q$)$= 1$, and $r = \frac{p}{q}$.

Let $y$ be some irrational number. Then by definition, there exist no two integers $n$ and $k$ such that $n \neq 0$, gcd($n$,$k$)$= 1$, and $y = \frac{n}{k}$.

Suppose for the sake of contradiction that the product of $y$ and $r$ is rational. Therefore, by definition, $r * y = \frac{a}{b}$ for two integers $a, b$.

We know that $r$ is a rational nonzero number. It follows that

$$r * y = \frac{a}{b}, \quad \frac{p}{q} * y = \frac{a}{b}, \quad y = \frac{aq}{bp}$$

We see that the terms $aq$ and $bp$ are integers denoted as $u$ and $v$ respectively. Therefore,

$$y = \frac{u}{v}$$

Here we have a contradiction. $y$ is irrational, and therefore no two integers $n,k$ exist such that $y = \frac{n}{k}$. Thus, the product of a nonzero rational number and an irrational number must be irrational.

$$\blacksquare$$

Problem Statement

Let the notation $n = \overline{ab}$ represent a two-digit integer $n$ with digits $a$ and $b$. We aim to prove that $3|n$ if and only if $3|(a+b)$.

Proof

Let $k = \overline{ab}$ represent a two-digit number with digits $a$ and $b$. Then $n = \overline{ab} = 10a + b$.

Let $z$ be an integer such that $z = (a + b)$.

---

Case 1 $\big($Proving if $3|n$ then $3|(a+b)\big)$

Suppose $3|n$, then $n \cong 0 \mod 3$. Consider $n - z = \overline{ab} - (a + b) = (10a + b) - (a + b) = 9a$. We can see that $3|9a$ so $3|(n - z)$. It follows by definition that $z \cong n \mod 3$, therefore $z \cong 0 \mod 3$, so $3|(a+b)$.

---

Case 2 $\big($Proving if $3|(a+b)$ then $3|n \big)$

Suppose $3|(a+b)$, then $(a+b) = z \cong 0 \mod 3$. Consider $z - n = (a+b) - \overline{ab} = (a+b) - (10a+b) = -9a$. We can see that $3|-9a$ so $3|(z - n)$. By definition, $n \cong z \mod 3$ and $n \cong 0 \mod 3$, so $3|n$.

---

In conclusion, we have shown that for $n = \overline{ab}$, $3|n$ if and only if $3|(a+b)$.

$$\blacksquare$$

Problem Statement

Prove that there exists a unique function defined on $\mathbb{R}$ with values in $\mathbb{R}$ that satisfies $f'(x) = 2x$ and $f(0) = 3$.

Proof

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be the function $f(x) = x^2 + 3$. Then $f'(x) = 2x$ and $f(0) = (0)^2 + 3 = 3$, so $f$ satisfies all desired properties.

We will now show that $f$ is unique. Suppose for the sake of contradiction that there exists a different function $g: \mathbb{R} \rightarrow \mathbb{R}$ such that $g'(x) = 2x$ and $g(0) = 3$.

We will integrate $g'(x)$ with respect to $x$:

$$\int g'(x) \, dx = g(x) = x^2 + c$$

It follows that $g(0) = c = 3$ and $g(x) = x^2 + 3$. Here we have reached a contradiction as we assumed $f(x) \neq g(x)$. In conclusion, $f(x) = x^2 + 3$ is the unique function satisfying $f'(x) = 2x$ and $f(0) = 3$.

$$\blacksquare$$