A&D assignment 2

exercise

2.1 Induction

a) IH: $2^n>n^2,n\ge 5$ Base: $n=5$ $2^5=32>25=5^2$ IS: $n\to n+1$

• $2^{n+1}=2\cdot 2^n\stackrel{IH}{>}2n^2$
• We need to show that $2n^2>(n+1{)}^2$
  • $⟺n^2>2n+1$
  • $⟺n^2-2n+1>2$
  • $⟺(n-1{)}^2-2>0$
  • for $n\ge 5$ the equation holds because for $n=5$: $(5-1{)}^2-2=14>0$ Hence $2n^2>(n+1{)}^2$ and $2^{n+1}>(n+1{)}^2$ Thus, the hypothesis is proved.

b) IH: $(1+x{)}^n={\sum }_{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i$ Base: $n=1$ $1+x={\sum }_{i=0}^1\left(\begin{array}{c}1\\ i\end{array}\right)x^i=\left(\begin{array}{c}1\\ 0\end{array}\right)x^0+\left(\begin{array}{c}1\\ 1\end{array}\right)x^1=1+x$ IS: $n\to n+1$

• $(1+x{)}^{n+1}=(1+x{)}^n(1+x)\stackrel{IH}{=}(1+x)\cdot {\sum }_{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i$
• $={\sum }_{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i+{\sum }_{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^{i+1}$
• $={\sum }_{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i+{\sum }_{i=1}^{n+1}\left(\begin{array}{c}n\\ i-1\end{array}\right)x^i$
• $={\sum }_{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i+{\sum }_{i=1}^n\left(\begin{array}{c}n\\ i-1\end{array}\right)x^i+x^{n+1}$
• =$\left(\begin{array}{c}n\\ 0\end{array}\right)x^0+{\sum }_{i=1}^n\left[\begin{array}{c}\left(\begin{array}{c}n\\ i\end{array}\right)+\left(\begin{array}{c}n\\ i-1\end{array}\right)\end{array}\right]x_i+\left(\begin{array}{c}n+1\\ n+1\end{array}\right)x^{n+1}$
• $=\left(\begin{array}{c}n+1\\ 0\end{array}\right)x^0+{\sum }_{i=0}^n\left(\begin{array}{c}n+1\\ i\end{array}\right)x^i+\left(\begin{array}{c}n+1\\ n+1\end{array}\right)x^{n+1}$
• $={\sum }_{i=0}^{n+1}\left(\begin{array}{c}n+1\\ i\end{array}\right)x^i$ The hypothesis is proved.

2.2 Fibonacci numbers

IH: $f_n\ge \frac{1}{3}\cdot 1.5^n$ for $n\ge 1$ Base: $n=1$ $f_1=1\ge 0.5=\frac{1}{3}\cdot 1.5^1$ $n=2$ $f_2=1\ge 0.75=\frac{1}{3}\cdot 1.5^2$ IS: $n\to n+1$

• $f_{n+1}=f_n+f_{n-1}\stackrel{IH}{\ge }\frac{1}{3}(1.5^n+1.5^{n-1})$
• We need to show that $\frac{1}{3}(1.5^n+1.5^{n-1})\ge \frac{1}{3}\cdot 1.5^{n+1}$
  • $⟺1.5^n+1.5^{n-1}\ge 1.5^{n+1}$
  • $⟺(1.5+1)1.5^{n-1}\ge 1.5^2\cdot 1.5^{n-1}$
  • $⟺2.5>2.25$ Hence $\frac{1}{3}(1.5^n+1.5^{n-1})\ge \frac{1}{3}\cdot 1.5^{n+1}$ Thus, the hypothesis is proved.

better bound

$f_n\le c\cdot {\alpha }^n$ $1+\alpha ={\alpha }^2$ $\alpha =\frac{1+\sqrt{5}}{2}$

Also known as the the golden ratio $\phi$

2.3 O-notation quiz

1. ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}={\lim }_{n\to \infty }\frac{2n^5+10n^2}{\frac{1}{100}{n}^6}={\lim }_{n\to \infty }\frac{200}{n}+{\lim }_{n\to \infty }\frac{1000}{n^4}=0+0=0$
   • Using Theorem 1, the statement is proved.
2. ${\lim }_{n\to \infty }\frac{n^{10}+2n^2+7}{100n^9}={\lim }_{n\to \infty }\frac{n+2n^{-7}+7n^{-9}}{100}=\infty$
   • Using Theorem 1, the statement is disproved.
3. ${\lim }_{n\to \infty }\frac{e^{1.2n}}{e^n}={\lim }_{n\to \infty }{e}^{0.2n}=\infty$
   • Using Theorem 1, the statement is disproved.
4. ${\lim }_{n\to \infty }\frac{n^{\frac{2n+3}{n+1}}}{n^2}={\lim }_{n\to \infty }{n}^{\frac{2n+3}{n+1}-2}={\lim }_{n\to \infty }{n}^{\frac{1}{n+1}}={\lim }_{n\to \infty }{e}^{\ln (n^{1/n+1})}={\lim }_{n\to \infty }{e}^{\frac{\ln n}{n+1}}=e^0=1$

$$f(n)=\{\begin{array}{l}1\text{when n is odd}\\ 2\text{when n is even}\end{array}$$ $$g(n)=\{\begin{array}{l}2\text{when n is odd}\\ 1\text{when n is even}\end{array}$$

2.4

a) Since $i>2^{j-1}$ $\frac{1}{i}\le \frac{1}{2^{j-1}}$ There are in total $2^j-(2^{j-1}+1)+1=2^{j-1}$ terms so the sum of the terms must be less or equal than $\frac{2^{j-1}}{2^{j-1}}=1$ Thus $S_j\le 1$ is proved.

b) Since $i\le 2^{j-1}$ $\frac{1}{i}\ge \frac{1}{2^j}$ There are in total $2^j-(2^{j-1}+1)+1=2^{j-1}$ terms so the sum of the terms must be greater or equal than $\frac{2^{j-1}}{2^j}=\frac{1}{2}$ Thus $S_j\ge \frac{1}{2}$ is proved.

c) ${\sum }_{i=1}^{2^k}\frac{1}{i}=1+{\sum }_{j=1}^k{S}_j$

• We know from (a) that $S_j\le 1$ so $1+{\sum }_{j=1}^k{S}_j\le 1+k\cdot 1=k+1$
• We know from (b) that $S_j\ge \frac{1}{2}$ so $1+{\sum }_{j=1}^k{S}_j\ge 1+k\cdot \frac{1}{2}=\frac{2+k}{2}>\frac{k+1}{2}$

d)

$$\sum _{i=1}^n\frac{1}{i}\le \sum _{i=1}^{2^{\lceil {\log }_{2}n\rceil }}\le \lceil {\log }_{2}n\rceil +1\le {\log }_{2}n=2$$ $$\sum _{i=1}^n\frac{1}{i}\ge \sum _{i=1}^{2^{\lfloor {\log }_{2}n\rfloor }}\ge \frac{\lfloor {\log }_{2}n\rfloor +1}{2}\ge \frac{{\log }_{2}n}{2}$$

2.5

a) we first show that $\ln (n!)\le n\ln n$ $⟺e^{\ln (n!)}\le e^{n\ln n}$ $⟺n!\le (e^{\ln n}{)}^n=n^n$ Using the Definition 1 of O-notation: We set $f(n)=\ln (n!),g(n)=n\ln n,C=1,N=1.$ Then $\ln (n!)\le C\cdot n\ln n\forall n\ge N$ Thus the statement is proved Another approach $\ln (n!)=\ln (1\cdot 2\cdot \cdots \cdot n)={\sum }_{i=1}^n\ln (i)\le {\sum }_{i=1}^n\ln (n)=n\ln n$

b) ${\left(\frac{n}{2}\right)}^{\frac{n}{2}}\le n!$ $⟺\ln \left({\left(\frac{n}{2}\right)}^{n/2}\right)\le \ln (n!)$ $⟺\frac{n}{2}\ln \left(\frac{n}{2}\right)\le \ln (n!)$ $⟺\frac{n}{2}\ln n-\frac{n}{2}\cdot \ln 2\le \ln (n!)$ so we know $\frac{n}{2}\ln n-\frac{n}{2}\cdot \ln 2\le O(\ln (n!))$ Hence $\frac{n}{2}\ln n\le O(\ln (n!))$ using Theorem 2 with the fact that $n<O(\ln (n!))$ And using theorem 2 again we know $n\ln n<O(\ln (n!))$

Bonus

prove $n^n\le O(n!)$ $n\ln n\le O(\ln (n!))$ $n\ln n\le c\cdot \ln (n!)$ $n^n\le (n!{)}^c$ statement disproved

Good to know: Stirling’s approximation