Math 116: Midterm Study Guide (Part I)

2.1 Natural Numbers and Arithmetic
Exercise 1 Rewrite (142)_5 in base 10.

    \begin{align*} (142)_5 &= 1\cdot 5^2+4\cdot 5^1 + 2\cdot 5^0 \\ &= 25+20+2=47 \end{align*}

Exercise 2 Rewrite (151)_9 in base 10.

    \begin{align*} (151)_9 &= 1\cdot 9^2+5\cdot 9^1 + 1\cdot 9^0 \\ &= 81+45+1=127 \end{align*}

Exercise 3 Rewrite (111)_6 in base 8.

    \begin{align*} (111)_6 &= 1\cdot 6^2+1\cdot 6^1 + 1\cdot 6^0 \\ &= 36+6+1=43 \\ &= 5\cdot8^1 + 3\cdot 8^0 \\ &= (53)_8 \end{align*}

Exercise 4 Rewrite (16)_7 in base 2.

    \begin{align*} (16)_7 &= 1\cdot 7^1+6\cdot 7^0 \\ &= 7+6=13 \\ &= 1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0\\ &= (1101)_2 \end{align*}

Exercise 5 What is the successor of (123)_4?

    \begin{align*} (123)_4+(1)_4 &= (100)_4+(20)_4+(3)_4+(1)_4 \\ &= (100)_4+(20)_4+(10)_4 \\ &= (100)_4+(30)_4 \\ &= (130)_4 \end{align*}

Exercise 6 What is the successor of (555)_6?

    \begin{align*} (555)_6+(1)_6 &= (500)_6+(50)_6+(5)_6+(1)_6 \\ &= (500)_6+(50)_6+(10)_6 \\ &= (500)_6+(100)_6 \\ &= (1000)_6 \end{align*}

Exercise 7 Compute (142)_6 + (152)_6.

    \begin{align*} (142)_6+(152)_6 &= (100)_6+(40)_6+(2)_6 + (100)_6+ (50)_6 + (2)_6 \\ &= (200)_6+(130)_6+(4)_6 \\ &= (334)_6 \end{align*}

Exercise 8 Compute (142)_5 + (221)_5.

    \begin{align*} (142)_5+(221)_5 &= (100)_5+(40)_5+(2)_5 + (200)_5+ (20)_5 + (1)_5 \\ &= (300)_5+(110)_5+(3)_5 \\ &= (413)_5 \end{align*}

Exercise 9 Is it possible to have a base b=1 number system? Yes, one can simply count in base b=1 by tallying.
Exercise 10 Is it possible to have a base b=0 number system? No. We need at least one digit to count.
2.2 Induction
Exercise 1 Show for all n \in \mathbb{N}, \sum\limits_{i=1}^ni=\frac{n(n+1)}{2}. The base case is given by

    \[\sum_{i=1}^1 i =1 = \frac{1(2)}{2}\]

Assume that \sum\limits_{i=1}^ki=\frac{k(k+1)}{2}, then

    \begin{align*} \sum_{i=1}^{k+1}i &= \sum_{i=1}^k i +(k+1) \\ &= \frac{k(k+1)}{2} +k+1 \\ &= \frac{k(k+1)+2(k+1)}{2} \\ &= \frac{k^2+3k+2}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{align*}

Therefore, the formula holds for all n \in \mathbb{N}.
Exercise 2 Show for all n \in \mathbb{N}, \sum\limits_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}. The base case is given by

    \[\sum_{i=1}^1 i^2 =1^2=1 = \frac{1(2)(3)}{6}\]

Assume that \sum\limits_{i=1}^ki^2=\frac{k(k+1)(2k+1)}{6}, then

    \begin{align*} \sum_{i=1}^{k+1}i^2 &= \sum_{i=1}^k i^2 +(k+1)^2 \\ &= \frac{k(k+1)(2k+1)}{6} +(k+1)^2 \\ &= \frac{k(k+1)(2k+1)+6(k+1)^2}{6} \\ &= \frac{(k+1)(k(2k+1)+6(k+1))}{6} \\ &= \frac{(k+1)(2k^2+7k+6)}{6} \\ &= \frac{(k+1)(k+2)(2k+3)}{6} \end{align*}

Therefore, the formula holds for all n \in \mathbb{N}.
Exercise 3 Show for all n \in \mathbb{N}, \sum\limits_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}. The base case is given by

    \[\sum_{i=1}^1 i^3 =1^3 = \frac{(1)^2(2)^2}{4}\]

Assume that \sum\limits_{i=1}^ki^3=\frac{k^2(k+1)^2}{4}, then

    \begin{align*} \sum_{i=1}^{k+1}i^3 &= \sum_{i=1}^k i^3 +(k+1)^3 \\ &= \frac{k^2(k+1)^2}{4} +(k+1)^3 \\ &= \frac{k^2(k+1)^2+4(k+1)^3}{4} \\ &= \frac{(k+1)^2(k^2+4(k+1))}{4} \\ &= \frac{(k+1)^2(k^2+4k+4)}{4} \\ &= \frac{(k+1)^2(k+2)^2}{4} \end{align*}

Therefore, the formula holds for all n \in \mathbb{N}.
Exercise 4 Show for all n \in \mathbb{N}, \sum\limits_{i=1}^n\frac{1}{i(i+1)}=\frac{n}{n+1}. The base case is given by

    \[\sum_{i=1}^1\frac{1}{i(i+1)} = \frac{1}{1(1+1)} = \frac{1}{1+1}\]

Assume that \sum\limits_{i=1}^k\frac{1}{i(i+1)}=\frac{k}{k+1}, then

    \begin{align*} \sum\limits_{i=1}^{k+1}\frac{1}{i(i+1)} &= \sum\limits_{i=1}^k\frac{1}{i(i+1)} + \frac{1}{(k+1)(k+2)} \\ &= \frac{k}{k+1}+\frac{1}{(k+1)(k+2)} \\ &= \frac{k(k+2)+1}{(k+1)(k+2)} \\ &= \frac{k^2+2k+1}{(k+1)(k+2)} \\ &= \frac{(k+1)^2}{(k+1)(k+2)} \\ &= \frac{k+1}{k+2} \end{align*}

Therefore, the formula holds for all n \in \mathbb{N}.
2.3 Some useful functions
Exercise 1 Compute \vert 2 \vert, \lfloor 2 \rfloor, and \lceil 2 \rceil.

    \begin{align*} \vert 2 \vert &= 2 \\ \lfloor 2 \rfloor &= 2 \\ \lceil 2 \rceil &= 2 \end{align*}

Exercise 2 Compute \vert -3 \vert, \lfloor -3 \rfloor, and \lceil -3 \rceil.

    \begin{align*} \vert -3 \vert &= 3 \\ \lfloor -3 \rfloor &= -3 \\ \lceil -3 \rceil &= -3 \end{align*}

Exercise 3 Compute \vert 1.4 \vert, \lfloor 1.4 \rfloor, and \lceil 1.4 \rceil.

    \begin{align*} \vert 1.4 \vert &= 1.4 \\ \lfloor 1.4 \rfloor &= 1 \\ \lceil 1.4 \rceil &= 2 \end{align*}

Exercise 4 Compute \vert 2.7 \vert, \lfloor 2.7 \rfloor, and \lceil 2.7 \rceil.

    \begin{align*} \vert 2.7 \vert &= 2.7 \\ \lfloor 2.7 \rfloor &= 2 \\ \lceil 2.7 \rceil &= 3 \end{align*}

Exercise 5 Compute \vert -3.3 \vert, \lfloor -3.3 \rfloor, and \lceil -3.3 \rceil.

    \begin{align*} \vert -3.3 \vert &= 3.3 \\ \lfloor -3.3 \rfloor &= -4 \\ \lceil -3.3 \rceil &= -3 \end{align*}

Exercise 6 Compute \vert -8.6 \vert, \lfloor -8.6 \rfloor, and \lceil -8.6 \rceil.

    \begin{align*} \vert -8.6 \vert &= 8.6 \\ \lfloor -8.6 \rfloor &= -9 \\ \lceil -8.6 \rceil &= -8 \end{align*}

Exercise 7 True or False: If x is an integer, then \vert x \vert =x. False. Example: \vert -3\vert = 3.
Exercise 8 True or False: If x is an real number, then \lfloor x \rfloor =x. False. Example: \lfloor 2.3 \rfloor=2\not=2.3.
Exercise 9 True or False: If x is an negative integer, then \lceil x \rceil =x. True.
Exercise 10 True or False: 0!=0 False. 0!=1.
Exercise 11 True or False: n!=n(n-1)! True.