Assignment 5b | Notion

Untitled

<aside> 🔖 A5 B1

(a)

$$ \text{Witness: }(1,28)\\ 3x^3+6x^4+4\le C(x^2+\frac{1}{4}x^4)\\\text{Let }k=1,C=28,\text{When }x>1：\\(3x^3+4)+6x^4\le (28x^2+x^4)+6x^4 $$

(b)

$$ \text{Witness:}(8,\frac{1}{24})\\x^2+\frac{1}{4}x^4\le C (3x^3+6x^4+4)\\\text{Let }k=8,C= \frac{1}{24},\text{ When }x>8:\\ x^2+\frac{1}{4}x^4\le(\frac{x^3}{8}+\frac{1}{6})+\frac{x^4}{4} $$

</aside>

Untitled

<aside> 🔖 A5 B2

(a) Yes, $f(x)$ is $\mathcal{O}\Big(g(x)\Big)$.

$$ \text{Since }\forall x>1\ s.t.\ x^2(\log x)^3\le x^3(\log x)^2 \\i.e\ |f(x)|\le C|g(x)| $$

(b) No, $g(x)$ is NOT $\mathcal{O}\Big(f(x)\Big)$.

Since there are no $(k,C)$ s.t $|g(x)|\le C|f(x)|$whenever $x> k$.

</aside>

Untitled

<aside> 🔖 A5 B3

(a)

$m$	$n$	$f((m,n))$	$m_{(2)}$	$n_{(2)}$	$(f((m,n)))_{(2)}$
0	0	0	0	0	0
0	1	2	0	1	10
0	2	4	0	10	100
0	3	6	0	11	110
0	4	8	0	100	1000
1	0	1	1	0	1
1	1	5	1	1	101
1	2	9	1	10	1001
1	3	13	1	11	1101
1	4	17	1	100	10001
2	0	3	10	0	11
2	1	11	10	1	1011
2	2	19	10	10	10011
2	3	27	10	11	11011
2	4	35	10	100	100011
3	0	7	11	0	111
3	1	23	11	1	10111
3	2	39	11	10	100111
3	3	55	11	11	110111
3	4	71	11	100	1000111
4	0	15	100	0	1111
4	1	47	100	1	101111
4	2	79	100	10	1001111
4	3	111	100	11	1101111
4	4	143	100	100	10001111

(b)

<aside> 💡 $37_{(2)}=1001\ 01$

Since $1001_{(10)}=9,$

$m=1, n=9$.

</aside>

If $f(x,y)=f(i,j)$, then $(x,y)=(i,j)$
$\forall a \in \N,\exist (x,y)\in \N\times\N(f(x,y)=a)$

and assume $F=f(x,y)\rArr g(x,y,z)=f(F,z):$

If $f(F,z)=f(k,l)=g(x,y,z)$,then $(F,z)=(k,l)=(x,y,z)$
$\forall a'\in \N,\exist(F,z)\in\N\times\N (f(F,z)=g(x,y,z)=a')$
- $(F,z)\in\N\times\N\equiv(x,y,z)\in\N\times\N\times\N$ since $f:\N\times\N\rarr\N$ is a bijection

so $g:\N\times\N\times\N\rarr\N$ defined by $g(x,y,z)=f(f(x,y),z)$ is bijection too.

</aside>

Untitled

<aside> 🔖 A5 B4

First,

If $f(x)=f(y)$, then $\frac{1}{1+e^x}=\frac{1}{1+e^y}$

i.e. $e^x=e^y\rarr x=y$

so $f:\R\rarr (0,1)$ is an injection.

On the other hand,

If $x=y\rArr f^{-1}(\frac{1}{1+e^x})=f^{-1}(\frac{1}{1+e^y})$,

then $\frac{1}{1+e^x}=\frac{1}{1+e^y}$

so $f^{-1}:(0,1)\rarr\R$ is an injection too.

Therefore, $f:\R\rarr (0,1)$ is a bijection.

i.e. $f:\R\rarr (0,1)$ is a surjection too.

And also $|R|=|(0,1)|$.

</aside>

Untitled

<aside> 🔖 A5 B5

(a)

$c_0$	$c_1$	$c_2$	$c_3$
0	1	4	10

<aside> 💡 (b)

$$ \begin{aligned}c_n&=\sum_{k=1}^{n}\left(\frac{1}{2}k^2+\frac{1}{2}k\right)\\&=\frac{1}{2}\left(\frac{n(n+1)}{2}+\frac{(2n+1)(n+1)n}{6}\right)\\&=\frac{n(n+1)(n+2)}{6}\end{aligned} $$

</aside>

<aside> 💡 (c)

$$ c_n-c_{n-1}=\frac{n(n+1)(n+2)-(n)(n+1)(n-1)}{6}\\=\frac{n(n+1)}{2} $$

</aside>

<aside> 💡 (d)

We can observe the defined of $c_n=\sum_{k=1}^{n}\left(\frac{1}{2}k^2+\frac{1}{2}k\right)$

and know that $c_n$ is the sum of sequence $b_n=(\frac{1}{2}n^2+\frac{1}{2}n)$ ,

so $c_n-c_{n-1}=b_n$.

</aside>

<aside> 💡 (e)

$$ c_6=\frac{6\times(6+1)\times(6+2)}{6}=56 $$

</aside>