## Some Step by Step Proofs

#### Andy Novocin

## Daily Challenge 1 Solution

### Original: If \(x^2 = x+1\) then \(x = 1 + \sqrt{5}\) or \(x = 1 - \sqrt{5}\)

### Converse: If \(x = 1 + \sqrt{5}\) or \(x = 1 - \sqrt{5}\) then \(x^2 = x + 1\)

### Contrapositive: If \(x \neq 1 + \sqrt{5}\) and \(x \neq 1 - \sqrt{5}\) then \(x^2 \neq x + 1\)

## A Pigeonhole Proof

### Given \(n\) objects and \(k < n\) containers which hold them. Prove that at least one container has more than one object.

- Proof:
**Suppose not.**
- (That means that \(k < n\) and all containers have one or less objects.)
- Let \(n_i\) be the number of objects in container \(i\).
- Then \( n = n_1 + \ldots + n_k \).
- For each \(i\) we know \(n_i \leq 1\) (based on our supposition)
- Thus \(n = n_1 + \ldots + n_k \leq k < n\).
- That implies that \(n < n\) which is a contradiction.

### Daily Challenge 2 Solution

## If \(x^3\) is irrational then \(x\) is irrational.

### We will prove the contrapositive.

### Let \(x = \frac{m}{n}, n \neq 0\) for \(n,m\in\mathbb{Z}\).

### Then \(x^3 = \frac{m^3}{n^3}\).

### But \(m^3, n^3 \in \mathbb{Z}\) and \(n^3 \neq 0\) so \(x^3\) is rational.

#### Let \(n\) be an integer. Prove that \(9n^2 + 3n -2\) is even.

**Proof:** Solve first for evens, then for odds.
**EVENS:** Let \(n = 2k\) for some \(k\).
- \(9 (2k)^2 + 3(2k) -2 = 36k^2 + 6k - 2\)
- \( = 2(18k^2 + 3k -1) \) which is even.
**ODDS:** Let \(n = 2k + 1\) for some \(k\).
- We explore: \(9 (2k + 1)^2 + 3(2k + 1) -2 \)
- \( = 36k^2 + 36k + 9 + 6k + 3 - 2 \)
- \( = 36k^2 + 42k + 10 = 2(18k^2 + 21k + 5)\) even

## ICUP

#### Let \(a\) and \(b\) be integers. Explore \(a\) is even and odd, \(b\) is even and odd.

#### Find a necessary and sufficient condition for \(a^2 - b^2\) to be odd.

#### Can you prove it?

#### Show that \(\sqrt{2}\) is irrational

- Proof:
**Suppose not.**
- Let \(\sqrt{2} = \frac{m}{n}\)
- Without loss of generality we can say only one of \(m\) and \(n\) are even (remove common factors)
- Now \( 2 = \frac{m^2}{n^2}\) which is \(2n^2 = m^2\)
- That means that \(m^2\) is even.
- An odd number squared is odd, so \(m = 2k\) for some \(k\).
- Replacing: \(2n^2 = 4k^2\).
- Simplifying: \(n^2 = 2k^2\).
- This implies that \(n\) is also even.
- A contradiction.

#### Pythagorean Theorem \(a^2 + b^2 = c^2\)

#### \( (a+b)^2 = 4(ab/2) + c^2 \)

#### \( a^2 + b^2 + 2ab = 2ab + c^2 \)

#### ICUP

#### Show that the product of an irrational and an irrational is irrational.

**Counter-Example** \(\sqrt{2} \sqrt{2} = 2\)

##### Theorem: There exists two positive irrational numbers, \(s, t\) such that \(s^t\) is rational.

### Proof:

#### Look at \(\sqrt{2}^{\sqrt{2}}\).

#### Case 1: It is rational. Then let \(s = t = \sqrt{2}\).

#### Case 2: It is irrational. Then let \(s = \sqrt{2}^{\sqrt{2}}\) and \(t = \sqrt{2}\).

#### Notice that \(s^t = {(\sqrt{2}^{\sqrt{2}})}^{\sqrt{2}} = \sqrt{2}^2 = 2\)