Proof Summary Questions

Proof Practical Class, Week 19 Proof Tutorial Class, Week 20 Proof Practical Class, Week 20 Proof Tutorial Class, Week 21 Proof Practical Class, Week 21 Proof Tutorial Class, Week 22 Proof Practical Class, Week 22 Proof Tutorial Class, Week 23 Proof Practical Class, Week 23 Proof Tutorial Class, Week 24 Proof Practical Class, Week 24 Proof Tutorial Class, Week 25 Proof Practical Class, Week 25 <- Week 24 Proof Practical.pdf

1. Use mathematical induction to prove that $5^n+3$ is divisible by $4$ for all positive integers $n$.

2. Use mathematical induction to prove that $11^n-4^n$ is divisible by $7$ for all positive integers $n$.

3. Use the method of undetermined coefficients to guess a formula for $1+3+5+\cdots +(2n-1)$ as a quadratic expression in $n$, and then use mathematical induction to prove this formula.

4. Use mathematical induction to prove the following for any positive integer $n$,

$$\frac{1}{1\cdot 2\cdot 3}+\frac{1}{2\cdot 3\cdot 4}+\cdots +\frac{1}{n(n+1)(n+2)}=\frac{1}{4}-\frac{1}{2(n+1)(n+2)}$$

5. Use mathematical induction to prove that $n!>3^n$ for any $n\ge 7$.

6. What is wrong in the following “proof” that all men are bald? We use induction on the number of hairs on the head, $n$:

   1. If $n=1$, then a man with just one hair is of course bald.
   2. Suppose the assertion is true for $n=k$, that is, having $k$ hairs means the man is bald. Now, if he has $k+1$ hairs, then it is just one more, so, surely, does not transform a man from being bald to non-bald.
   3. Thus, by the Axiom of Mathematical Induction, a man is bald if he has $n$ hairs, for any $n$.

7. Prove by induction that for $x\ne 1$ we have the following, for any positive integer $n$: $1+x+x^2+\cdots +x^{n-1}=\frac{1-x^n}{1-x}$

8. Use mathematical induction to prove the following for all positive integers $n$: $\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{n}{2^n}=2-\frac{n+2}{2^n}$

9. Use mathematical induction to prove that $n^3<2^n$ for any $n\ge 10$.

10. Prove by induction that $6^n-1$ is divisible by $5$ for any $n\in \mathbb{N}$.

11. Suppose that $a$ is a real number such that $a+\frac{1}{a}$ is an integer. Use Cumulative Induction to prove that then $a^n+\frac{1}{a^n}$ is also an integer for every $n=1,2,3,\dots$.

12. Use induction on $n$ to prove that any ‘map’ formed by intersections of $n$ straight lines can be coloured in two colours in such a way that no two countries of the same colour have a common boundary segment. (Each country is coloured in one colour; corner points between two countries of the same colour are allowed.)

13. Let $(a_i{)}_{i\in \mathbb{N}}$ be a sequence defined recursively as $a_1=1$ and $a_{i+1}=3a_i-1$. Use induction to prove that $a_n=\frac{3^{n-1}+1}{2}$ for all $n\in \mathbb{N}$.

14. Let $(b_i{)}_{i\in \mathbb{N}}$ be a sequence defined recursively as $b_1=0$, $b_2=1$, and $b_i=3b_{i-1}-2b_{i-2}$ for $i\ge 3$. Use induction to prove that $b_n=2^{n-1}-1$ for all $n\in \mathbb{N}$.

15. Let the universal set be $\mathcal{U}=\{x\in \mathbb{Z}:-9\le x\le 9\}$, and let $\mathbb{A}$ be the set of all odd integers in $\mathcal{U}$, let $\mathbb{B}=\{x\in \mathcal{U}:x^2>25\}$, and $\mathbb{C}=\{x\in \mathcal{U}:x<0\}$. Determine each of the following sets and list their elements:

    1. $\mathbb{A}\cap \mathbb{B}\cap \mathbb{C}$;
    2. $\mathbb{A}\cap \overline{\mathbb{B}}$;
    3. $\mathbb{A}\cap \overline{\mathbb{C}}$;
    4. $\mathbb{B}\cup \mathbb{C}$.

16. Use Venn diagrams to prove that $\mathbb{A}\cup (\mathbb{B}\cap \mathbb{C})=(\mathbb{A}\cup \mathbb{B})\cap (\mathbb{A}\cup \mathbb{C})$ for any sets $\mathbb{A}$, $\mathbb{B}$, and $\mathbb{C}$.

17. Use the properties of operations on sets to simplify the expression $\mathbb{B}\cup \overline{(\overline{\mathbb{A}}\cap \overline{\mathbb{B}})}$.

18. Solve the simultaneous system of inequalities using intersection of solutions of individual inequalities and write the solution as a set:

$$\{\begin{array}{ll}{x}^2+x-6& \ge 0\\ x^2-7x+10& \ge 0\end{array}$$

19. Prove, based on the definitions, that $\overline{(\mathbb{A}\cap \mathbb{B})}=\overline{\mathbb{A}}\cup \overline{\mathbb{B}}$.

20. Use mathematical induction to prove that every positive integer $n\ge 8$ can be represented as $n=3a+5b$ where $a$ and $b$ are non-positive integers.

21. Consider the function $f(x)=\frac{x}{x+1}$, and define recursively a sequence of functions $f_1(x)=f(x)$ and $f_{i+1}(x)=f(f_i(x))$.

22. Use mathematical induction to prove that $2^n>100n$ for any $n\ge 10$.

23. Where is the mistake in the following “proof” that all triangles have the same area?

    Obviously, it is sufficient to prove that, given any $n$ triangles, they all have the same area. We use induction on $n$. Indeed,

1. If we have one triangle, the assertion is of course true.
2. Suppose the assertion is true for $n=k$. Consider any $k+1$ triangles $T_1,\dots ,T_{k+1}$. Apply the induction hypothesis to the first $k$ of the triangles: $T_1,\dots ,T_{k+1}$ all have the same area. Then apply the induction hypothesis to the last $k$ of them: $T_2,\dots ,T_{k+1}$ all have the same area. Then obviously all $k+1$ triangles $T_1,\dots ,T_{k+1}$ have the same area: area of $T_1=\text{area of }{T}_2=\cdots =\text{area of }{T}_k=\text{area of }{T}_{k+1}$. Thus, by the Axiom of Mathematical Induction, the assertion is true for all $n$, and therefore all triangles have the same area.

24. How does one tie a goat so it can eat grass within exactly a semicircle? It can be leashed multiple times, with several pegs. For example, one peg and a leash mean that the goat eats within a circle. It is also allowed to string one rope tightly between two pegs, and to tie the goat with a leash to a small ring sliding on the first rope. Hint: use intersections of sets.

25. Use a diagram to prove the property $A\times (B\cup C)=(A\times B)\cup (A\times C)$.

26. Let $A=\{1,2,\dots ,100\}$ be the set of all integers from 1 to 100. Let $R$ be a relation on $\mathcal{P}(A)$ (the set of all subsets of $A$) defined as $BRC$ if $|B|\le |C|$. Determine if $R$ is…

    1. …transitive,
    2. …reflexive,
    3. …symmetric,
    4. …antisymmetric, and in each case giving a proof if yes, or a counterexample if not. Hence state whether $R$ is an order, or an equivalence, or neither.

27. On the set $S=\{1,2,3,4,5,6,7,8,9\}$, consider the relation $R$ defined as $aRb$ if $a|b$ (that is, $a$ divides $b$). Draw the diagram $R$ as a subset of $S\times S$.

28. Let $\sim$ be a relation on the set $\mathbb{R}\times \mathbb{R}$ defined by $(x,y)\sim (a,b)$ if $y-|x|=b-|a|$.

    1. Show that $\sim$ is an equivalence.
    2. What is the equivalence class of $(2,-3)$ with respect to this equivalence $\sim$?

29. Consider the order relation on $\mathbb{N}$ defined by divisibility: $a|b$ (when $b=ak$ for $k\in \mathbb{N}$). What are the infimum and supremum of the set $S=\{8,12,36\}$? Does this set have the greatest element? What about the smallest element?

30. Consider the lexicographical order ${\le }_L$ on $\mathbb{R}\times \mathbb{R}$, which means that by definition $(a,b){\le }_L(c,d)$ if either $a<c$ (while $b$ and $d$ can be any), or $a=c$ and $b\le d$.

    1. Find the supremum (least upper bound), if it exists, with respect to ${\le }_L$ of the set $D=\{(x,y):x^2+y^2\le 1\}$ (the disc of radius $1$ with centre at the origin, including the unit circle).
    2. Find the supremum (least upper bound), if it exists, with respect to ${\le }_L$ of the set $D_0=\{(x,y):x^2+y^2<1\}$ (the disc of radius $1$ with centre at the origin, without the boundary unit circle).

31. On the set $S=\mathbb{N}\times \mathbb{N}$, consider the relation $\sim$ defined as $(m_1,n_1)\sim (m_2,n_2)$ if $m_1\cdot n_2=m_2\cdot n_1$. Show that $\sim$ is an equivalence. Describe the equivalence class of $(1,2)$ with respect to this equivalence $\sim$.

32. Give an example of finite sets $A,B,X,Y$ such that $(A\times Y)\cup (B\times Y)\ne (A\cup B)\times (X\cup Y)$. Hint: try small sets, say, subsets of $1,2,3,4$.

33. For a fixed set $S$, consider $\mathcal{P}(S)$ (set of all subsets of $S$) ordered by inclusion. For $A,B\subset S$, what is $\sup \{A,B\}$ with respect to this order? What is $\inf \{A,B\}$?

34. How to tie a goat so as it can eat grass exactly within a square? It is allowed to use several leashes, with several pegs. For example, one peg and leash mean that the goat eats within a circle. It is also allowed to string one rope tightly between two pegs, and to tie the goat with leash to as small ring sliding on the first rope. *Hint: use intersections of sets.

35. For which of the following pairs $A,B\subset \mathbb{R}$ does the relation $f=\{(x,y):x=\mid y|\}\subset A\times B$ define a mapping $f:A\to B$? Give reasons to your answers:

    1. $A=\mathbb{R},B=[0,\infty )$.
    2. $A=[0,\infty ),B=\mathbb{R}$.
    3. $A=[0,\infty ),B=(-\infty ,0]$.

36. Given the following mappings, determine which of the composites $f\circ g,g\circ f$ is defined, and write the resulting mapping in standard form:

$$\begin{array}{c}f:\mathbb{Z}\times \mathbb{Z}\to \mathbb{R},f((x,y))=x+y,\text{and}\\ g:\mathbb{R}\to \mathbb{R},g(a)=a^2+1\end{array}$$

37. For each of the following mappings, determine whether it is injective and/or surjective:

    1. $f:\mathbb{Z}\to \mathbb{N},f(k)=k^2+2$.
    2. $f:\mathbb{R}\times \mathbb{R}\to \mathbb{R},f((x,y))=x+y$.
    3. $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N},f((m,n))=2^{m-1}\cdot (2n-1)$.

38. Let $A=\mathcal{P}(\{u,v,w\})$ be the set of all subsets of $\{u,v,w\}$ and let $f:A\to A,f(x)=X\cap \{u,v\}$. Draw the diagram of the Cartesian product $A\times A$ and indicate $f$ as a subset of $A\times A$. What is the image of $f$?

39. Find the image of the mapping $f:\mathbb{R}\to \mathbb{R},f(x)=\frac{1}{x^2+5}$.

40. Show that $f:[3,\infty )\to (0,1],f(x)=\frac{2}{x-1}$ is a bijection and find the inverse mapping $f^{-1}$ - indicating its domain and image.

41. Let $f:\mathbb{R}\to \mathbb{R},f(x)=2x+1$. Define recursively the mappings $F_1=f$ and $F_{k+1}=f\circ F_k$ for all $k\in \mathbb{N}$. Compute several first mappings, conjecture an expression for $F_n$, and prove it by induction.

42. Draw the mapping $g:\mathbb{R}\to \mathbb{R}$ on the $(x,y)$ plane defined by the rule following rule - is it injective, surjective?

$$g(x)=\text{largest integer}\le x$$

43. For the following mapping, what is the image of $g$? What is the full inverse image $g^{-1}(2)$?

$$g(x)=\text{largest integer}\le x$$

44. Given any mapping $f:A\to B$, prove that the relation $\sim$ on $A$ defined by $a_1\sim a_2$ if $f(a_1)=f(a_2)$ is an equivalence relation. What are the equivalence classes?

45. Prove that the following sets have the same cardinality by producing explicitly a bijection between the sets and describing this bijection…

    1. … by a formula for $|(-\infty ,0]|=|[3,+\infty )$;
    2. … by representing the set on the right as a sequence: $|\mathbb{N}|=|\{a,b,c\}\cup \mathbb{N}|$;
    3. … by any method: $|\{a,b\}\times \mathbb{Z}|=|\mathbb{Z}|$;
    4. … by using a sequence of points: $|[0,1]|=|(0,1)|$;
    5. … geometrically: $|(0,1)|=|(0,\infty )|$.

46. Use this theorem to prove that $|\mathbb{N}\times \mathbb{N}\times \mathbb{N}|={\aleph }_0$.

47. Let $S$ be the set of all sequences of the form $(a_1,a_2,a_3,\dots )$, where every $a_i$ is either $A$ or $B$. Use Cantor’s “diagonal method” to prove that the set $S$ is not countable.

48. Recall that $\{0,1\}\times \{0,1\}\times \{0,1\}$ consists of triples of $1$s and $0$s, and $\mathcal{P}(\{a,b,c\})$ is the set of all subsets of $\{a,b,c\}$. Consider the following mapping, in which a subset $X\subset \{a,b,c\}$ is mapped to a string of length $3$ consisting of $0$s and $1$s depending on which of the elements $a,b,c$ belong to $X$ (with $1$ indicating yes and $0$ indicating no). Write the images $f(\varnothing )$, $f(\{a,c\})$, $f(\{b\})$. Is $f$ a bijection?

$$f:\mathcal{P}(\{a,b,c\})\to \{0,1\}\times \{0,1\}\times \{0,1\}$$

49. Use this theorem to show that any set consisting of pairwise disjoint intervals of the real line (each of $\text{length}>0$) is countable.

50. How does the graph of the function $f(x)$ change under the following transformations (where $a$ is a constant)? That is, how to obtain the graph of $F(x)$ from the graph of $f(x)$, where…

    1. $F(x)=f(x)+a$;
    2. $F(x)=f(x+a)$;
    3. $F(x)=f(ax)$.

51. Assume the mapping $f:[0,1)\to [1,\infty )$, $f(x)=\frac{1}{\sqrt{1-x^2}}$, is a bijection. Apply transformations from the previous question to the mapping $f$ to produce a bijection $F:[2,4)\to [0,\infty )$.

52. Prove that the set $W$ of all finite sequences (‘words) composed of two letters $A,B$ is countable.

53. Translate the following statements between logical formulae and plain statements, given that…

$$\begin{array}{rl}R& =\text{it is raining}\\ S& =\text{the sun is shining}\\ B& =\text{there is a rainbow}\end{array}$$

1. There is a rainbow only if it is raining but the sun is shining.
2. There is no rainbow although it is raining and the sun is shining.
3. $(\neg B\land R)\implies \neg S$.
4. $S\lor (R\land B)$.

54. Use truth tables to prove the logical equivalences… 1. $\neg (P⟹Q)\equiv P\wedge \neg Q$. 2. $(P\wedge Q)\vee R\equiv (P\vee R)\wedge (Q\vee R)$.

55. Use the properties of logical operations to simplify the expression $\neg P\wedge \neg (Q\wedge \neg P)$.

56. Prove by contradiction:

    1. if $k$ is an integer such that $k^2$ is not divisible by $3$, then $k$ is not divisible by $2$.
    2. $\sqrt{5}\text{centernot}\in \mathbb{Q}$.

57. Use the Cantor-Bernstein-Schroder theorem to show that $|A|=|B|$ by producing injective mappings $A\to B$ and $B\to A$, where $A$ is the square $A=[0,1]\times [0,1]$ and $B$ is the disc $B=\{(x,y):x^2+y^2\le 1\}$.