<aside> 🔖 A6-B1
(a)
$$ (f_1)^2+(f_2)^2+(f_3)^2+(f_4)^2+(f_5)^2=1+1+2^2+3^2+5^2=40 $$
(b)
$$ f_5\times f_6=5\times(3+5)=40 $$
(c)
$$ f_n=f_{n-1}+f_{n-2}(n\ge2)\rArr f_{n+1}=f_n+f_{n-1}(n\ge1)\\\rArr f_{n+2}=f_{n+1}+f_{n}(n\ge0)\\\therefore f_nf_{n+1}+f_{n+1}^2=f_{n+1}(f_n+f_{n+1})=f_{n+1}f_{n+2}(n\ge0) $$
(d)
$$ P(k):\sum_{i=1}^kf^2_i=f_kf_{k+1} $$
<aside> 🔖 $\rm{(i)}$ When $j=1,P(1):f_1^2=1=f_1f_2=1\cdot1=1$ is true.
$\rm{(ii)}$ When $P(k)$ is true, then
$$ P(k+1):\begin{aligned}\sum_{i=1}^{k+1}f^2_i=f^2_{k+1}+\sum_{i=1}^kf^2_i=&f^2_{k+1}+f_kf_{k+1}\\=&f_{k+1}(f_{k+1}+f_k)\\=&f_{k+1}f_{k+2}\end{aligned} $$
it also true.
$\rm{(iii)}$ $P(20)$ is a true statement because of the Mathematic Induction: $P(1)$ is true, and “When $P(k)$ is true, $P(k+1)$ is also true”.
</aside>
</aside>
<aside> 🔖 A6-B2
(a)
Suppose that: $\exist (x_1,x_2,…x_k+1)$ and $(y_1,y_2,...,y_{k+1})$
$$ g_{k+1}(x_1,x_2,..,x_{k+1})=f(g_{k}(x_1,x_2,...,x_{k}),x_{k+1})\\g_{k+1}(y_1,y_2,..,y_{k+1})=f(g_{k}(y_1,y_2,...,y_{k}),y_{k+1}) $$
If $g_{k+1}(x_1,x_2,..,x_{k+1})=g_{k+1}(y_1,y_2,..,y_{k+1})$,
then $f(g_{k}(x_1,x_2,...,x_{k}),x_{k+1})=f(g_{k}(y_1,y_2,...,y_{k}),y_{k+1})$
Since $f$ is an injection, then $(g_{k}(x_1,x_2,...,x_{k}),x_{k+1})=(g_{k}(y_1,y_2,...,y_{k}),y_{k+1})$
Since $g$ is an injection, then
$(x_1,x_2,...,x_{k})=(y_1,y_2,...,y_{k})\rArr(x_1,x_2,...,x_{k+1})=(y_1,y_2,...,y_{k+1})$.
So $g_{k+1}$ is an injection, too.
(b)
$\forall (x_1,x_2,…x_{k+1})\in S^{k+1}$
$$ g_{k+1}(x_1,x_2,..,x_{k+1})=f(g_{k}(x_1,x_2,...,x_{k}),x_{k+1}) $$
Since $g_k$ is a surjection, then $\exist g_k(x_1,x_2,...,x_{k})$
Since $f$ is a surjection, then $\exist f(g_{k}(x_1,x_2,...,x_{k}),x_{k+1})$ i.e $g_{k+1}(x_1,x_2,..,x_{k+1})$
So $g_{k+1}$ is a surjection.
(c)
Base Case: $f$ is a bijection, then $g_2(x_1,x_2)=f(x_1,x_2)$ is also a bijection.
Induction Step:
From (a) and (b) we know that if $f$ and $g_k$ is a bijection, then $g_{k+1}$ is also a bijection.
So, If $f$ is a bijection, then $g_n$ is a bijection for all $n\ge2.\Box$
</aside>
<aside> 🔖 A6-B3
(a)
$$ \begin{aligned}\ell(5)=f(g_1(5),1)&=f(5,1)\\&=2^5(2\cdot1+1)-1\\&=95\\\ell(4,2)=f(g_2(4,2),2)&=f(f(4,2),2)\\&=5\cdot2^{5\cdot2^{4}-1}-1\\&=5\cdot2^{79}-1\\\ell(0,2,1,0)=f(g_4(0,2,1,0),4)&=f(f(g_3(0,2,1),0),4)\\&=f(f(f(g_2(0,2),1),0),4)\\&=f(f(f(f(0,2),1),0),4)\\&=9\cdot2^{2^{3\cdot2^{5\cdot2^{0}-1}-1}-1}-1\end{aligned} $$
(b)
$$ \ell^{-1}(12)=(0,6)\\\ell^{-1}(17)=(1,4) $$
</aside>
<aside> 🔖 A6-B4
To construct an injection $f$ from $Σ^*$ to $T$, we can use the fact that $h$ is an injection from the finite alphabet $Σ$ to the set of natural numbers $N$.
First, we define a function $g: Σ^*\rarr N$ as follows:
for any string $w = a_1a_2...a_n$ in $Σ^*$, where each ai is a symbol in $Σ$, we define $g(w) = p_1^{h(a_1)} * p_2^{h(a_2)} * ... * p_n^{h(a_n)}$, where $p_1, p_2, ..., p_n$ are distinct primes.
Next, we define a function $f: Σ^*\rarr T$ by $f(w) = \ell(g(w))$, where $\ell$ is the bijection defined in question B3 that maps $T\rarr\N$ .
To see that $f$ is an injection, suppose that $f(w_1) = f(w_2)$ for some strings $w_1$ and $w_2$ in $Σ^*$. Then, we have $\ell(g(w_1)) = \ell(g(w_2))$.
Since $\ell$ is a bijection, this implies that $g(w_1) = g(w_2)$.
Now, suppose that $w1$ and $w_2$ are distinct strings in $Σ^*.$ Then, there is some index $i$ such that $a_i≠ b_i$ , where $a_i$ and $b_i$ are the $i^{th}$ symbols of $w_1$ and $w_2$, respectively.
Without loss of generality, assume that $h(a_i) < h(b_i)$.
Then, we have $p_i^{h(a_i)} * q > p_i^{h(b_i)}$ for some prime $q$ and all primes $p_i ≠ p_j$.
Thus, we have
$$ \begin{aligned}g(w_1) &= p_1^{h(a_1)} * p_2^{h(a2)} * ... * p_i^{h(a_i)} * ... * p_n^{h(a_n)} * q\\ &> p_1^{h(b_1)} * p_2^{h(b_2)} * ... * p_i^{h(b_i)} * ... * p_n^{h(b_n)} = g(w_2)\end{aligned} $$
Therefore, $f(w_1) = \ell(g(w_1)) ≠ \ell(g(w_2)) = f(w_2)$. Thus, $f$ is injective.
Since $\ell$ is a bijection, $T$ is countable. Therefore, $Σ^$ is countable too as it has an injection to a countable set. Note that since the set of all valid computer programs in all languages is a subset of $Σ^$, there must be real numbers that cannot be described by any possible computer program.
</aside>
In step (b), $P(k):(1+v)^k\ge(1+kv)$ is true.
Then $v\in(-1,\infin)\rArr(1+v)>0$.
So $(1+v^k)(1+v)\ge(1+kv)(1+v)$
$x=(1+kv),y=(1+v)^k,x\le y$
$a=(1+v)>0$
$ax\le ay$
$$ a<b,b<c\rArr a<b<c\\\rArr a+b< b+b< b+c<c+c $$
$$ a\le b\le c\\\rArr c+c+c\ge a+b+c $$
$$ k\ge1\rArr k^2\ge k \ge 1\\\rArr k^2 + 2k^2 + k^2\ge k^2 + 2k + 1 $$