Proof Practical Class, Week 20

Question One §

Question §

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}$.

Solution §

…

Question Two §

Question §

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}$.

Solution §

…

Question Three §

Question §

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}$.

Solution §

…

Question Four §

Question §

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}$.

Solution §

…

Question Five §

Question §

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

Solution §

…

Question Six §

Question §

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}$$

Solution §

…

Question Seven §

Question §

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

Solution §

…

Question Eight §

Question §

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-negative integers.

Hint: Verify induction base for $n=8,9,10$, then use the Cumulative Axiom of Mathematical Induction (C.A.M.I).

Solution §

…

Question Nine §

Question §

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))$.

Hint: Calculate $f_1(x)$, $f_2(x)$, and $f_3(x)$, then make a guess the definition, and then prove your guess by induction.

Solution §

…