COMP 2711 HW 5

1

a

$$\gcd (1260,23)=jx+ky$$ $$k=jq+r$$ $$\begin{array}{cccccc}k& j& r& q& x& y\\ 1260& 23& 18& 54& -493& 9\\ 23& 18& 5& 1& 9& -7\\ 18& 5& 3& 3& -7& 2\\ 5& 3& 2& 1& 2& -1\\ 3& 2& 1& 1& -1& 1\\ 2& 1& 0& 2& 1& 0\end{array}$$ $$d=-493+1260=767$$

b

$$767=512+128+64+32+16+8+4+2+1$$ $$\begin{array}{rl}& 2^1\mathrm{mod}1333=2\\ & 2^2\mathrm{mod}1333=4\\ & 2^4\mathrm{mod}1333=16\\ & 2^8\mathrm{mod}1333=256\\ & 2^{16}\mathrm{mod}1333=256^2\mathrm{mod}1333=219\\ & 2^{32}\mathrm{mod}1333=219^2\mathrm{mod}1333=1306\\ & 2^{64}\mathrm{mod}1333=1306^2\mathrm{mod}1333=729\\ & 2^{128}\mathrm{mod}1333=729^2\mathrm{mod}1333=907\\ & 2^{256}\mathrm{mod}1333=907^2\mathrm{mod}1333=188\\ & 2^{512}\mathrm{mod}1333=188^2\mathrm{mod}1333=686\end{array}$$ $$\begin{array}{rl}x& =m^d(\mathrm{mod}n)\\ x& =2^{767}(\mathrm{mod}31\cdot 43)\\ x& =2^{767}(\mathrm{mod}1333)\\ x& =2^{512+128+64+32+16+8+4+2+1}(\mathrm{mod}1333)\\ x& =686\cdot 907\cdot 729\cdot 1306\cdot 219\cdot 256\cdot 16\cdot 4\cdot 2(\mathrm{mod}1333)\\ x& =39\cdot 907\cdot 729\cdot 1306\cdot 219\cdot 256\cdot 16\cdot 4(\mathrm{mod}1333)\\ x& =156\cdot 907\cdot 729\cdot 1306\cdot 219\cdot 256\cdot 16(\mathrm{mod}1333)\\ x& =1163\cdot 907\cdot 729\cdot 1306\cdot 219\cdot 256(\mathrm{mod}1333)\\ x& =469\cdot 907\cdot 729\cdot 1306\cdot 219(\mathrm{mod}1333)\\ x& =70\cdot 907\cdot 729\cdot 1306(\mathrm{mod}1333)\\ x& =70\cdot 907\cdot 729\cdot 1306(\mathrm{mod}1333)\\ x& =776\cdot 907\cdot 729(\mathrm{mod}1333)\\ x& =512\cdot 907(\mathrm{mod}1333)\\ x& =500(\mathrm{mod}1333)\end{array}$$

2

a

$$A=n^{1000}+100n^2,B=1.1^n$$

$A$ is polynomial, $B$ is exponential, therefore $A=O(B)$

b

$$A={\log }_{2}n,B={\log }_3(n^5)=5{\log }^{3}n$$ $$\Theta (A)=\log n,\Theta (B)=\log n$$ $$A=\Theta (B)$$

$\text{pagebreak}$

c

$$\begin{array}{rl}A& =3^{{\log }_{2}n}\\ & =e^{({\log }_{2}n)(\ln 3)}\\ & =e^{(\ln n/\ln 2)(\ln 3)}\\ & =e^{(\ln n)(\ln 2/\ln 3)}\\ & =n^{\ln 2/\ln 3}\\ & =n^{{\log }_{2}3}\end{array}$$ $$\begin{array}{rl}B& =3^{{\log }_{3}n}\\ & =n\end{array}$$ $$A=\Omega (B)$$

d

$$\begin{array}{rl}A& =\log (n!)\\ & =\log (n)+\log (n-1)+\cdots +\log (1)\\ & \\ & \le \log (n)+\log (n)+\cdots +\log (n)\\ & =n\log n\\ & =O(n\log n)\\ & \\ & \ge \log (n)+\log (n-1)+\cdots +\log \left(\frac{n}{2}\right)\\ & \ge \log \left(\frac{n}{2}\right)+\log \left(\frac{n}{2}\right)+\cdots +\log \left(\frac{n}{2}\right)\\ & =\frac{n}{2}\log \left(\frac{n}{2}\right)\\ & =\Omega (n\log n)\\ & \\ & \therefore A=\Theta (n\log n)\end{array}$$ $$A=\Theta (B)$$

e

$$\begin{array}{rl}\underset{n\to \infty }{\lim }\frac{({\log }_{2}n{)}^{100}}{n}& =\underset{n\to \infty }{\lim }\frac{1}{n}{\left(\frac{\log n}{\log 2}\right)}^{100}\\ & =\frac{1}{(\log 2{)}^{100}}\underset{n\to \infty }{\lim }\frac{(\log n{)}^{100}}{n}\\ & =\frac{100}{(\log 2{)}^{100}}\underset{n\to \infty }{\lim }\frac{(\log n{)}^{99}}{n}\\ & =\frac{100\cdot 99}{(\log 2{)}^{100}}\underset{n\to \infty }{\lim }\frac{(\log n{)}^{98}}{n}\\ & ⋮\\ & =\frac{100!}{(\log 2{)}^{100}}\underset{n\to \infty }{\lim }\frac{1}{n}\\ & =0\end{array}$$ $$A=O(B)$$

$\text{pagebreak}$

3

a

1. Base Case

For $n=2$, $1-\frac{1}{4}=\frac{3}{4}=\frac{2+1}{2\cdot 2}$

2. Inductive Hypothesis

Assume the statement is true for some $k$, i.e. $\left(1-\frac{1}{4}\right)\left(1-\frac{1}{9}\right)\dots \left(1-\frac{1}{k^2}\right)=\frac{k+1}{2k}$

3. Inductive Steps

For $n=k+1$,

$$\begin{array}{rl}\left(1-\frac{1}{4}\right)\left(1-\frac{1}{9}\right)\dots \left(1-\frac{1}{(k+1{)}^2}\right)& =\left(1-\frac{1}{4}\right)\left(1-\frac{1}{9}\right)\dots \left(1-\frac{1}{k^2}\right)\left(1-\frac{1}{(k+1{)}^2}\right)\\ & =\frac{k+1}{2k}\left(1-\frac{1}{(k+1{)}^2}\right)\\ & =\frac{k+1}{2k}-\frac{k+1}{2k(k+1{)}^2}\\ & =\frac{k+1}{2k}-\frac{1}{2k(k+1)}\\ & =\frac{(k+1{)}^2-1}{2k(k+1)}\\ & =\frac{k^2+2k+1-1}{2k^2+2k}\\ & =\frac{k(k+2)}{k(2k+2)}\\ & =\frac{(k+1)+1}{2(k+1)}\end{array}$$

Therefore, by M.I., the statement is true for any $n\ge 2$

$\text{pagebreak}$

b

$$\begin{array}{lllllllllllll}{f}_n& 1& 1& 2& 3& 5& 8& 13& 21& 34& 55& 89& 144\\ n& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\end{array}$$

Prove $3\mid f_n⟺4\mid n$

1. Base Case

For $n=4$, $3\mid (f_4=3)$ and $4\mid (n=4)$

2. Inductive Hypothesis

Assume $3\mid f_k⟺4\mid k$ for all $1\le k<n$, i.e. $3\mid f_{4m}$ for $1\le 4m<n$ and $m\in \mathbb{N}$

3. Inductive Step

Show that $3\mid f_{4m}\to 3\mid f_{4(m+1)}$

$$\begin{array}{rl}{f}_{4(m+1)}& =f_{4m+4}\\ & =f_{4m+3}+f_{4m+2}\\ & =f_{4m+2}+f_{4m+1}+f_{4m+1}+f_{4m}\\ & =f_{4m+1}+f_{4m}+f_{4m+1}+f_{4m+1}+f_{4m}\\ & =3f_{4m+1}+2f_{4m}\end{array}$$

Since $3f_{4m+1}$ and $f_{4m}$ are both divisible by 3, $f_{4(m+1)}$ is divisible by 3

Therefore, by strong M.I., $3\mid f_n⟺4\mid n$

$\text{pagebreak}$

4

a

Assume $1+\frac{1}{x}$ is an integer

1. Base Case

For $n=1$, $x^1+\frac{1}{x^1}=x+\frac{1}{x}$ is an integer from the assumption

2. Inductive Hypothesis

Assume $x^k+\frac{1}{x^k}$ is an integer for any $k<n$

3. Inductive Steps

$$\begin{array}{rl}\left(x+\frac{1}{x}\right)\left(x^{n-1}+\frac{1}{x^{n-1}}\right)& =x^{1+n-1}+\frac{x}{x^{n-1}}+\frac{x^{n-1}}{x}+\frac{1}{x^{n-1+1}}\\ & =x^n+x^{2-n}+x^{n-2}+x^{-n}\\ & =\left(x^n+\frac{1}{x^n}\right)+\left(x^{n-2}+\frac{1}{x^{n-2}}\right)\end{array}$$

Rearranging the terms we get

$$\begin{array}{rl}{x}^n+\frac{1}{x^n}& =\left(x+\frac{1}{x}\right)\left(x^{n-1}+\frac{1}{x^{n-1}}\right)-\left(x^{n-2}+\frac{1}{x^{n-2}}\right)\end{array}$$

Where the RHS is the product of integers minus another integer

Therefore, by strong M.I., $x^n+\frac{1}{x^n}$ is an integer

$\text{pagebreak}$

b

1. Base Case

If $n=2$, ${\sum }_{\forall a,b(a+b=n)}(a\cdot b)=1\cdot 1=1=\left(\genfrac{}{}{0ex}{}{2}{2}\right)$, the statement is true

2. Inductive Hypothesis

Assume the statement is true for all $k<n$, i.e. ${\sum }_{\forall a,b(a+b=k)}(a\cdot b)=\left(\genfrac{}{}{0ex}{}{k}{2}\right)$

3. Inductive Steps

For $n=k+1$

$$\begin{array}{rl}\sum _{\forall a,b(a+b=k+1)}(a\cdot b)& =\sum _{\forall a,b(a+b=a^{\prime })}(a\cdot b)+\sum _{\forall a,b(a+b=b^{\prime })}(a\cdot b)+(a^{\prime }\cdot b^{\prime })\\ & =\left(\genfrac{}{}{0ex}{}{a^{\prime }}{2}\right)+\left(\genfrac{}{}{0ex}{}{b^{\prime }}{2}\right)+(a^{\prime }\cdot b^{\prime })\\ & =\frac{a^{\prime }!}{2!(a^{\prime }-2)!}+\frac{b^{\prime }!}{2!(b^{\prime }-2)!}+(a^{\prime }\cdot b^{\prime })\\ & =\frac{a^{\prime }(a^{\prime }-1)}{2}+\frac{b^{\prime }(b^{\prime }-1)}{2}+(a^{\prime }\cdot b^{\prime })\\ & =\frac{{a^{\prime }}^2-a^{\prime }+{b^{\prime }}^2-b^{\prime }+2a^{\prime }{b}^{\prime }}{2}\\ & =\frac{(a^{\prime }+b^{\prime })(a^{\prime }+b^{\prime }-1)}{2}\\ & =\frac{(a^{\prime }+b^{\prime })!}{2!(a^{\prime }+b^{\prime }-2)!}\\ & =\frac{(k+1)!}{2!(k+1-2)!}\\ & =\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)\end{array}$$

Therefore, by strong M.I., the statement is true for all $n\ge 2$

$\text{pagebreak}$

5

a

For the base case 2 x 1, there is 1 way
For the base case 2 x 2, there are 3 ways
For 2 x 3, there are 3 + 2 = 5 ways
For 2 x 4, there are 5 + 6 = 11 ways

For each step, since we can place 1x2 or 2x2 tile carpets, we can go back either 1 or 2 steps
For going back 1 step, we have 1 way to add 1x2 carpets for each of the cases, i.e. $a_{n-1}$ ways
For going back 2 steps, excluding the case where we place 1x2 carpet at the last step (covered in going back 1 step), we have $2a_{n-2}$ ways to do so

Therefore, the recursive formula for $a_n$ is

$$a_n=a_{n-1}+2a_{n-2}$$

b

1. Basis

$a_1=\frac{2^{1+1}-(-1{)}^{1+1}}{3}=\frac{2^2-(-1{)}^2}{3}=1$

$a_1$ is true

2. Inductive Hypothesis

Assume $a_k$ is true for $k<n$, i.e. $a_k=\frac{2^{k+1}-(-1{)}^{k+1}}{3}$

3. Inductive Steps

$$\begin{array}{rl}{a}_{k+1}& =a_k+2a_{k-2}\\ & =\frac{2^{k+1}-(-1{)}^{k+1}}{3}+2\frac{2^{k-2+1}-(-1{)}^{k-2+1}}{3}\\ & =\frac{2^{k+1}-(-1{)}^{k+1}+2^k-2(-1{)}^k}{3}\\ & =\frac{2\cdot 2^k+2^k-(-1{)}^{k+1}-(-1{)}^{k+1}}{3}\\ & =\frac{2^{2k+2}-(-1{)}^{2k+2}}{3}\end{array}$$

Therefore, by strong M.I., $a_n=\frac{2^{n+1}-(-1{)}^{n+1}}{3}$

6

a

$k$ choices for the 1st sector

$$a_1=k$$

$k$ choices for the 1st sector, $k-1$ choices for the 2nd sector (cannot repeat 1st choice)

$$a_2=k(k-1)$$

$k$ choices for the 1st sector, $k-1$ choices for the 2nd sector (cannot repeat 1st choice), $k-2$ choices for the 3rd sector (cannot repeat 1st or 2nd choice)

$$a_3=k(k-1)(k-2)$$

b

For the 1st sector we have $k$ choices, then for the 2nd to the nth sector we have $(k-1)$ choice for each of them, however we have to exclude the case where the nth sector is the same color as the 1st sector, therefore subtracting $a_{n-1}$

$$a_n=k(k-1{)}^{n-1}-a_{n-1}$$