Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Exercises 6.6 Exercises

1.

Prove that for all \(n\in\mathbb Z\text{,}\) \(3\mid (n^3-n)\text{.}\)

2.

Prove that for all \(n, k\in\mathbb Z\text{,}\) if \(k\mid (2n+1)\) and \(k\mid (4n^2+1)\text{,}\) then \(k\in\set{-1,1}\text{.}\)

3.

For all \(n\in\mathbb Z\text{,}\) prove that if there exists \(a,b\in\mathbb Z\) such that \(a^2+b^2=n\text{,}\) then \(n\not\equiv 3\pmod 4\text{.}\)

4.

Prove or disprove the following statement:
\begin{equation*} \forall a,b\in\mathbb{Z}, \text{ if } 3\mid (a^2+b^2), \text{ then } 3\mid a \text{ and } 3\mid b. \end{equation*}

5.

Let \(n,a,b\in\mathbb{Z}\text{.}\) We know that if \(n\mid a\) or \(n\mid b\text{,}\) then \(n\mid ab\text{.}\) Is the converse true as well?

6.

Let \(f:\mathbb{R}\to\mathbb{R}\) be a function. We say that \(f\) is
  • even if \(f(-x)=f(x)\) for all \(x\in\mathbb{R}\text{;}\)
  • odd if \(f(-x)=-f(x)\) for all \(x\in\mathbb{R}\text{.}\)
Let \(f:\mathbb{R}\to\mathbb{R}\) and \(g:\mathbb{R}\to\mathbb{R}\text{.}\) If \(f+g\) is odd, are \(f\) and \(g\) also odd?

7.

Determine whether the following four statements are true or false. Explain your answers.
  1. \(\exists x\in\mathbb{Z} \text{ s.t. } \exists y\in\mathbb{Z} \text{ s.t. } x+y=3\text{.}\)
  2. \(\exists x\in\mathbb{Z} \text{ s.t. } \forall y\in\mathbb{Z}, x+y=3\text{.}\)
  3. \(\forall x\in\mathbb{Z}, \exists y\in\mathbb{Z} \text{ s.t. } x+y=3\text{.}\)
  4. \(\forall x\in\mathbb{Z}, \forall y\in\mathbb{Z}, x+y=3\text{.}\)

8.

Determine whether the following four statements are true or false. Explain your answers.
  1. \(\exists x\in\mathbb{R} \text{ s.t. } \exists y\in\mathbb{R} \text{ s.t. } x^2 \lt y\text{.}\)
  2. \(\exists x\in\mathbb{R} \text{ s.t. } \forall y\in\mathbb{R}, x^2 \lt y\text{.}\)
  3. \(\forall x\in\mathbb{R}, \exists y\in\mathbb{R} \text{ s.t. } x^2 \lt y\text{.}\)
  4. \(\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, x^2 \lt y\text{.}\)

9.

Let \(P\subset\mathbb N\) be the set of prime numbers \(P=\set{2,3,5,7,11,\ldots}\text{.}\) Determine whether the following statements are true or false. Prove your answers (“true” or “false” is not sufficient).
  1. \(\forall x\in P\text{,}\) \(\forall y\in P\text{,}\) \(x+y\in P\text{.}\)
  2. \(\forall x\in P\text{,}\) \(\exists y\in P\) such that \(x+y\in P\text{.}\)
  3. \(\exists x\in P\) such that \(\forall y\in P\text{,}\) \(x+y\in P\text{.}\)
  4. \(\exists x\in P\) such that \(\exists y\in P\text{,}\) \(x+y\in P\text{.}\)

10.

Given the sets,
\begin{equation*} A=\set{n\in\mathbb Z\st 3\mid n}, B=\set{n\in\mathbb Z\st 4\nmid n}, \text{ and } C=\set{n\in\mathbb Z\st 6\nmid n} \end{equation*}
determine whether the following statements are true or false, and justify your answer.
  1. \(\forall a\in A\text{,}\) \(\exists b\in B\) such that \(a+b\in C\text{.}\)
  2. \(\exists a\in A\) such that \(\forall b\in B\text{,}\) \(a+b\in C\text{.}\)
  3. \(\forall a\in A\text{,}\) \(\forall b\in B\text{,}\) \(a+b\in C\text{.}\)
  4. \(\exists a\in A\) and \(\exists b\in B\) such that \(a+b\in C\text{.}\)

11.

Determine whether the following statements are true or false. Explain your answers.
  1. \(\exists x\in\mathbb{R} \text{ s.t. } \exists y\in\mathbb{R} \text{ s.t. } (xy \gt 0) \implies (x+y \gt 0) \text{.}\)
  2. \(\exists x\in\mathbb{R} \text{ s.t. } \forall y\in\mathbb{R}, (xy \gt 0) \implies (x+y \gt 0) \text{.}\)
  3. \(\forall x\in\mathbb{R}, \exists y\in\mathbb{R} \text{ s.t. } (xy \gt 0) \implies (x+y \gt 0) \text{.}\)
  4. \(\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, (xy \gt 0) \implies (x+y \gt 0) \text{.}\)
  5. \(\exists x\in\mathbb{R} \text{ s.t. } \forall y\in\mathbb{R}, (xy \geq 0) \implies (x+y \geq 0) \text{.}\)
  6. \(\forall x\in\mathbb{R}, \exists y\in\mathbb{R} \text{ s.t. } (xy \geq 0) \implies (x+y \geq 0) \text{.}\)

12.

Determine whether the following four statements are true or false. Explain your answers.
  1. \(\forall y\in \mathbb{R}, \forall z\in \mathbb{R}, \exists x\in \mathbb{R} \text{ s.t. } x+y=z\text{.}\)
  2. \(\exists x\in \mathbb{R} \text{ s.t. } \forall y\in \mathbb{R}, \forall z\in \mathbb{R}, x+y=z\text{.}\)
  3. \(\forall x\in \mathbb{R}, \exists y \in \mathbb{R} \text{ s.t. } \exists z \in \mathbb{R} \text{ s.t. } \text{if }z \gt y \text{ then } z \gt x+y\text{.}\)
  4. \(\forall x\in \mathbb{R}, \exists y \in \mathbb{R} \text{ s.t. } \forall z \in \mathbb{R}, \text{ if }z \gt y \text{ then } z \gt x+y\text{.}\)

13.

Let \(f:\mathbb{R}\rightarrow\mathbb{R}\) and \(g:\mathbb{R}\to \mathbb{R}\) be functions. For just this question,
  • we call \(f\) type A, if \(\forall x\in\mathbb R\text{,}\) \(\exists y\in\mathbb R\) such that \(y\geq x\) and \(|f(y)|\geq 1\text{,}\) and
  • we say that \(g\) is type B if \(\exists x\in\mathbb R\) such that \(\forall y\in\mathbb R\text{,}\) if \(y\geq x\text{,}\) then \(|g(y)|\geq 1\text{.}\)
Prove or find a counterexample for the following statements.
  1. If a function is type A, then it is type B.
  2. If a function is type B, then it is type A.

14.

Write down the negation of each of the following statements. Then determine whether each statement is true or false. Justify your answers.
  1. \(\exists x\in \mathbb Z\) such that \((x \gt 84)\) and \(x\equiv 75 \pmod{84}\text{.}\)
  2. \(\exists x, y\in \mathbb Z\) such that if \(1\geq x^2\geq y^2\text{,}\) then \(x\geq y\text{.}\)
  3. \(\forall z\in\mathbb N\text{,}\) \(\exists x,y\in\mathbb Z\) such that \(z=x^2+y^2\text{.}\)
  4. \(\exists a\in \mathbb R\) such that \(a \gt 0\) and \(\forall x\in\mathbb R\text{,}\) if \(x\geq a\text{,}\) then \(2^{-x} \lt \dfrac{1}{100}\text{.}\)
  5. \(\forall n\in\mathbb R\text{,}\) \(n\) is even if and only if \(n^2\) is even.

15.

Prove or disprove the following statements.
  1. \(\forall a \in \mathbb N\text{,}\) \(\forall b\in\mathbb{N}\) if \(b \lt a\text{,}\) then \(b-b^2 \lt a\text{.}\)
  2. \(\forall p\in\mathbb N\text{,}\) \(\forall q\in\mathbb{N}\text{,}\) if \(\sqrt{\dfrac{p}{q}}\in\mathbb N\text{,}\) then \(\sqrt{p}\in\mathbb N\) and \(\sqrt{q}\in\mathbb N\text{.}\)
  3. \(\forall a,b\in\mathbb R\text{,}\) \(\exists c,d\in\mathbb R\text{,}\) such that if \(ab\geq cd\text{,}\) then \(a\geq c\) and \(b\geq d\text{.}\)
  4. \(\forall a,b\in\mathbb{N}\text{,}\) if \(\exists x,y\in\mathbb{Z}\) and \(\exists k\in\mathbb{N}\) such that \(ax+by=k\text{,}\) then \((k \mid a)\) and \((k \mid b)\text{.}\)

16.

Show that \(\displaystyle\lim_{x\to 4}\left(-3x+5 \right)=-7\text{.}\)

17.

Show that \(\displaystyle\lim_{x\to1}x^2=1\text{.}\)

18.

Show that \(\displaystyle\lim_{n\to\infty}1/n^2=0\text{.}\)

19.

Let \(f:\mathbb{R} - \{0\}\rightarrow\mathbb{R}\) be defined by
\begin{equation*} f(x)=6x\sin\left(\frac{1}{x}\right). \end{equation*}
Show that \(\displaystyle \lim_{x\to0}f(x)=0\text{.}\)

20.

Prove that the sequence \((x_n)_{n\in\mathbb{N}}=\left((-1)^n+\dfrac{1}{n}\right)_{n\in\mathbb{N}}\) does not converge to \(0\text{.}\)

21.

Prove that
\begin{equation*} \displaystyle \lim_{n\to\infty}\left(1-\frac{2}{n^2}-\frac{3}{n^3}\right)=1. \end{equation*}
You may use the following fact: Let \(x,y\) be positive real numbers. Then
\begin{equation*} \sqrt{x} \lt\sqrt{y} \iff x\lt y. \end{equation*}

22.

Let \((s_n)_{n\in\mathbb{N}}\) be a sequence. We say that \(\displaystyle\lim_{n\to\infty}s_n=+\infty\) if the following holds:
\begin{align*} \forall M\gt0, \exists N\in\mathbb{N} \text{ such that } \amp\\ \amp \forall n\in\mathbb{N}, n\geq N\implies s_n\geq M. \end{align*}
  1. In words, explain what the definition above means.
  2. Negate the statement above in order to describe what \(\displaystyle\lim_{n\to\infty}s_n\neq+\infty\) means.
  3. Show that \(\displaystyle\lim_{n\to\infty}\sqrt{n}=+\infty\)
  4. Show that \(\displaystyle\lim_{n\to\infty}(-1)^n\sqrt{n}\neq+\infty\)
  5. Show that \(\displaystyle\lim_{n\to\infty}(n^2-100n)=+\infty\)

23.

Let \(\{a_n\}_{n\in\mathbb{N}}\) be a sequence. We say that a sequence \(\{a_n\}_{n\in\mathbb{N}}\) is bounded if there is some \(M\in\mathbb{R}\) such that \(|a_n|\leq M\) for all \(n\in\mathbb{N}\text{.}\)
  1. Show that if \(\displaystyle\lim_{n\to\infty}a_n=L\) for some \(L\in \mathbb{R}\text{,}\) then \(\{a_n\}_{n\in\mathbb{N}}\) is bounded.
  2. Show that the converse of the statement in (a) is false.

24.

Before completing this question, you should look over Exercise 6.6.23.
A sequence \((a_n)_{n\in\mathbb{N}}\) is bounded if there is some \(M\geq 0\) such that \(|a_n|\leq M\) for all \(n\in\mathbb{N}\text{.}\) If no such \(M\) exists, then we say \((a_n)_{n\in\mathbb{N}}\) is unbounded.
We say that \((a_n)_{n\in\mathbb{N}}\) is increasing if \(a_{n+1}\geq a_n\) for all \(n\in\mathbb{N}\text{.}\)
  1. Show that there is an unbounded sequence \((a_n)_{n\in\mathbb{N}}\) with \(\displaystyle\lim_{n\to\infty}a_n\neq+\infty\text{.}\)
  2. Show that there is an increasing sequence \((a_n)_{n\in\mathbb{N}}\) with \(\displaystyle\lim_{n\to\infty}a_n\neq+\infty\text{.}\)
  3. Show that if \((a_n)_{n\in\mathbb{N}}\) is unbounded and increasing, then \(\displaystyle\lim_{n\to\infty}a_n=+\infty\text{.}\)
Parts (a) and (b) tell us that when proving the statement in part (c), we need to use both conditions given.

25.

Typically, we define the distance between two real numbers via the absolute value function: \(d(x,y)=|x-y|\text{.}\) This means that we can see the distance as a function on real numbers that takes two numbers and gives us a non-negative number as the distance. This helps us generalize the definition of a “distance”. However a function needs to satisfy more than being non-negative to be called a “distance”.
Indeed, we define a distance (or metric) on \(\mathbb{R}\text{,}\) as a function \(d:\mathbb{R}\times\mathbb{R}\rightarrow [0,\infty)\text{,}\) that satisfies the properties,
  • \(\forall x, y\in\mathbb{R}\text{,}\) \(d(x,y)=0\) if and only if \(x=y\text{.}\)
  • \(\forall x,y\in\mathbb{R}\text{,}\) \(d(x,y)=d(y,x)\text{.}\)
  • \(\forall x,y, z\in\mathbb{R}\text{,}\) \(d(x,y)\leq d(x,z)+d(z,y)\) (this property is also known as, as you guessed it, the “triangle inequality”).
Now, we can define the function \(D:\mathbb{R}\times\mathbb{R}\rightarrow [0,\infty)\text{,}\) as,
\begin{align*} D(x,y)=\left\{ \begin{array}{ll} 1 \amp \text{if } x\neq y \\ 0 \amp \text{if } x=y \end{array} \right. \end{align*}
  1. We see that \(D\) satisfies the first two properties. Show that \(D\) satisfies the triangle inequality to conclude that \(D\) is a distance.
  2. Given a distance function, \(d\text{,}\) we can define sequence convergence as follows,
    A sequence \((x_n)_{n\in\mathbb{N}}\) converges to a number \(L\) if and only if \(\forall \epsilon\gt 0\text{,}\) \(\exists N\in\mathbb{N}\) such that \(\forall n\gt N\text{,}\) \(d(x_n,L)\lt \epsilon\text{.}\)
    Using this definition and the distance function, \(D\text{,}\) as above, show that a sequence \((x_n)_{n\in\mathbb{N}}\) converges to \(L\) implies that the set \(\set{ n\in\mathbb{N}: x_n\neq L }\) is finite.
<Prev^TopNext>