1. Say whether the following is true or false and support your answer by a proof.

$(\exists m \in \mathbb{N})(\exists n \in \mathbb{N})(3m + 5n = 12)$

Proof:

Let $x = 3m + 5n\, (\,m, n \in \mathbb{N},\, m, n > 0)$ be given. Then $x > 0$.

Take $n = 1$. Then $x = 3(m + 1) + 2$. So $x\ge6$ and $x\equiv 2 \pmod{3}$.

Take $n = 2$. Then $x = 3(m + 3) + 1$. So $x\ge13$ and $x\equiv 1 \pmod{3}$.

But $6 \lt 12 \lt 13$ and $3 | 12$, so $x = 12$ is not possible.

Thus $(\exists m \in \mathbb{N})(\exists n \in \mathbb{N})(3m + 5n = 12)$ is false. $\blacksquare$

2. Say whether the following is true or false and support your answer by a proof: The sum of any five consecutive integers is divisible by 5 (without remainder).

Proof:

Let the five consecutive integers be $n, n+1, n+2, n+3, and \, n+4 \, (n \in \mathbb{Z},\, n < n + 1 < n + 2 < n + 3 < n + 4)$.

Then $n + (n+1) + (n+2) + (n+3) + (n+4) = 5n + 10$.

$5n + 10$ is a multiple of 5, since $5n + 10 = 5(n+2)$.

So the sum of any five consecutive integers is divisible by $5$, for any $n$.

Thus the statement is true. $\blacksquare$

3. Say whether the following is true or false and support your answer by a proof: For any integer n, the number $n^2 + n + 1$ is odd.

Proof:

$n(n+1)$ is a product of two consecutive integers and show the product of any two consecutive integer is even.

Let $n$ be $2k$ and $n + 1$ be $2k + 1$.

Then $n(n+1) = 2k(2k+1) = 4k^2+2k = 2(2k^2+k)$

So $n(n+1)$ is even, since $2|n(n+1)$, for any $n$.

$n^2 + n +1$ is not even, since $n^2 + n +1 \equiv 1 \pmod{2}$, for any $n$.

$n^2 + n +1$ is not even, then $n^2 + n +1$ is odd.

This proves the statement, so the statement is true. $\blacksquare$

4. Prove that every odd natural number is of one of the forms $4n + 1$ or $4n + 3$, where $n$ is an integer.

Proof:

Let $2k+1$ denote an odd natural number . Then $k$ can be expresed as $2n$ if even or expresed as $2n + 1$ if odd.

If $k = 2n$, then $2(2n)+1 = 4n+1$.

If $k = 2n + 1$, then $2(2n+1)+1 = 4n+3$.

So every odd natural number is of one of the forms $4n+1$ or $4n+3$.

This proves the statement. $\blacksquare$

5. Prove that for any integer $n$, at least one of the integers $n$, $n+2$, $n+4$ is divisible by $3$.

Proof:

Let $k$ be an arbitrary integer.

If $3|n$, then $n = 3k$,

$n + 2 = 3k + 2$, so $n + 2 \equiv 2 \pmod{3}$ and $n + 4 = 3(k + 1) + 1$, so $n + 4 \equiv 1 \pmod{3}$.

If $3|n+2$, then $n + 2 = 3k$,

$n = 3(k - 1) + 1$, so $n \equiv 1 \pmod{3}$ and $n + 4 = 3k + 2 \equiv 2 \pmod{3}$.

If $3|n+4$, then $n + 4 = 3k$,

$n = 3(k - 2) + 2$, so $n \equiv 2 \pmod{3}$ and $n + 2 = 3(k - 1) + 1 \equiv 1 \pmod{3}$.

Thus for any integer $n$, at least one of the integers $n$, $n+2$, $n+4$ is divisible by $3$. $\blacksquare$

6. A classic unsolved problem in number theory asks if there are infinitely many paris of 'twin primes', pairs of primes separated by $2$, such as $3$ and $5$, $11$ and $13$, or $71$ and $73$. Prove that the only prime triple (i.e. three primes, each 2 from the next) is $3,5,7$.

Proof: By contradiction.

Assume $n, n+2, n+4$ are prime. ($n \in \mathbb{N}, n \gt 3$).

For any $n$, at least one of $n, n+2, n+4$ is divisible by 3, since $n+1 \equiv n+4 \equiv 1 \pmod{3}$.

So the prime triple $n, n + 2, n + 4$ is always expressed as the three consecutive numbers $n, n+1, n+2$ . Contradiction.

$3$ is the only prime that is a multiple of 3. Hence the only prime triple is $3,5,7$.

This proves the statement. $\blacksquare$

7. Prove that for any natural number $n$, $2+2^2+2^3+...+2^n = 2^{n+1}-2$

Proof: By induction on $n$

For the case $n = 1$ is true, since the left side $2^1 = 2$ and the right side is $2^{1+1}-2 = 4 - 2 = 2$.

Assume the identity holds for n. Add $n+1$ to both sides of $2 + 2^2 + 2^3 + ... + 2^n = 2^{n+1}-2$.

i.e. $2 + 2^2 + 2^3 + ... + 2^n + 2^{n+1}= 2^{(n+1)+1}-2$

$2 + 2^2 + 2^3 + ... + 2^n + 2^{n+1} = 2^{(n+1)+1}-2 = 2^{n+1+1}-2$ by algebra.

which is the identity with $n + 1$ in place of n.

Hence, by the principle of mathematical induction, the identity holds for all $n$. $\blacksquare$

8. Prove (from the definition of a limit of a sequence) that if the sequence $\{a_n\}^\infty_{n=1}$ tends to limit $L$ as $n \rightarrow \infty$, then for any fixed numer $M \gt 0$, the sequence $\{Ma_n\}^\infty_{n=1}$ tends to the limit $ML$.

Proof:

Let $\varepsilon > 0$ be given.

Then since $a_n$ converges to $L$, we need to find an $\bar{n} \in \mathbb{N}$ such that $|a_n - L| < \frac{\varepsilon}{M}, \forall{n} \ge \bar{n}$.

So for all $n$, we will find

$|Ma_n-ML| = M|a_n-L| < M\frac{\varepsilon}{M} = \varepsilon$

Thus $\{Ma_n\}^\infty_{n=1}$ tends to the limit $ML$. $\blacksquare$

9. Given an infinite collection $A_n, n = 1,2, ...$ of intervals of the real line, their intersection is defined to be $\bigcap_{n=1}^{\infty} A_n = \{x | (\forall{n})(x \in A_{n})\}$. Give an example of a family of intervals $A_{n}, n = 1,2, ...$, such that $A_{n+1} \subset A_{n}$ for all $n$ and $\bigcap_{n=1}^{\infty} A_n = \emptyset$. Prove that your example has the stated property.

Example: $A_{n} = (0, \frac{1}{n}), n = 1,2, ...$

Proof:

First, show $(\forall{n})(A_{n+1} \subset A_{n})$.

Let $n$ be an arbitrary natural number. Then $A_{n} = (0, \frac{1}{n})$ and $A_{n+1} = (0, \frac{1}{n+1})$.

$A_{n+1} \subset A_{n}$, i.e. $(0, \frac{1}{n+1}) \subset (0, \frac{1}{n})$.

Let $x$ denote an arbitraly element of $(0, \frac{1}{n+1})$. Then $0 \lt x \lt \frac{1}{n+1}, 0 \lt x \lt \frac{1}{n}$, since $\frac{1}{n+1} \lt \frac{1}{n}$.

So every element of $A_{n+1}$ is an element $A_{n}$. Thus $(\forall{n})(A_{n+1} \subset A_{n})$.

Next, show $\bigcap_{n=1}^{\infty} A_n = \emptyset$.

We need to find an empty intersection such that $A_{n} \supset A_{n+1} \supset A_{n+2} ... \supset A_{n \rightarrow \infty}$ for all $n$.

$A_{n}, n \rightarrow \infty, \lim \limits_{n \rightarrow \infty} A_{n} = 0$, so if $n \rightarrow \infty, (0, \frac{1}{n}) = (0, 0)$.

$(0, 0)$ is an empty set. Thus $\bigcap_{n=1}^{\infty} A_n = \emptyset$. $\blacksquare$

10. Give an example of a family of intervals $A_{n}, n = 1,2, ...$, such that $A_{n+1} \subset A_{n}$ for all $n$ and $\bigcap_{n=1}^{\infty} A_n$ consists of a single real number. Prove that your example has the stated property.

Example: $A_{n} = (\frac{-1}{n}, \frac{1}{n})$

Proof:

First, show $\{0\} \subset \bigcap_{n=1}^{\infty} A_{n}$.

For every positive integer, $0$ is an element of $(\frac{-1}{n}, \frac{1}{n})$, so $0 \in \bigcap_{n=1}^{\infty} (\frac{-1}{n}, \frac{1}{n})$.

$0 \in \{0\}$, so every element of $\{0\}$ is in $\bigcap_{n=1}^{\infty} (\frac{-1}{n}, \frac{1}{n})$

Hence, $\{0\} \subset \bigcap_{n=1}^{\infty} (\frac{-1}{n}, \frac{1}{n})$ by the definition of subset.

Next, show $\bigcap_{n=1}^{\infty} A_{n} \subset \{0\}$.

Let $x$ be an element of $\bigcap_{n=1}^{\infty} A_{n}$. Then $x \in (\frac{-1}{n}, \frac{1}{n})$ for every positive integer.

Assume that $x \neq 0$.

Then $|x| \gt 0$ and there is a positive insteger $N$ such that $0 \lt \frac{1}{N} \lt \frac{1}{x}$ by archimedean principle.

Hence, $x \notin (\frac{-1}{n}, \frac{1}{n})$, but this leads to a contracition, so $x = 0$.

Therefore $0$ is the only element of $\bigcap_{n=1}^{\infty} A_{n}$ and $\bigcap_{n=1}^{\infty} A_{n} \subset \{0\}$. $\blacksquare$


In [ ]:


In [ ]: