***Question 1*** i) We have $\frac{4n^{8}+7n + 3}{n^{9}} = \frac{\left( \frac{4}{n} + \frac{7}{n^{8}} + \frac{3}{n^{9}} \right)}{1} \to 0$, as $n\to \infty$ so indeed $4n^{8}+7n+3 = \mathcal{O}(n^{9})$. ii) g5t ***Question 2*** i) $a=4,b=2,d=2 \implies \frac{a}{b^{d}} = 1$ so $T(n) = \Theta(n^{2}\log_{2} n)$. ii) Note that $T(n)= \sum_{i=1}^{\log_{2}n} 2^{i} 3^{\frac{n}{2^{i}}} = 3^{n} \sum_{i=1}^{\log_{2}n} 2^{i} 3 ^{2^{-i}} $Now $\sum_{i=1}^{\log_{2}n} 2^{i} 3 ^{2^{-i}} \geq \sum_{i=1}^{\log_{2}n} 2^{i} = \frac{2(1-2^{\log_{2}n})}{1-2} = 2(n-1)$so $\sum_{i=1}^{\log_{2}n} 2^{i} 3 ^{2^{-i}} =\Omega(n)$. Also $\sum_{i=1}^{\log_{2}n} 2^{i} 3 ^{2^{-i}} \leq \sum_{i=1}^{\log_{2}n} 2^{i}\cdot 3 = 6(n-1) $so $\sum_{i=1}^{\log_{2}n} 2^{i} 3 ^{2^{-i}}=\mathcal{O}(n)$. Therefore $\sum_{i=1}^{\log_{2}n} 2^{i} 3 ^{2^{-i}}=\Theta(n)$. Hence $T(n) =\Theta(n{3}^n)$.l iii) $a=5,b=4,d=\frac{1}{2}\implies \frac{a}{b^{d}}=2.5>1$ so $T(n)=\Theta(n^{\log_{4}5})$. ***Question 3*** Consider the generating function $\begin{align} G(x) &= \sum_{n=0}^{\infty} a_{n}x^{n} \\ &= 1 - 2x + \sum_{n=2}^{\infty} a_{n} x^{n} \\ &= 1 - 2x + \sum_{n=2}^{\infty} (5 a_{n-1} x^{n} - 6 a_{n-2} x^{n}) \\ & = 1- 2x + 5x\sum_{n=2}^{\infty} a_{n-1}x^{n-1} -6x^{2} \sum_{n=2}^{\infty} a_{n-2} x^{n-2} \\ &= 1-2x+5x [G(x)-1 ] -6x^{2} G(x) \\ \implies G(x)[1-5x+6x^{2}] &= 1 -2x -5x = 1-7x \\ \end{align}$Hence $\begin{align} G(x) &= \frac{1-7x}{1-5x+6x^{2}} = \frac{5}{1-2x} - \frac{4}{1-3x} \\ & = 5\sum_{n=0}^{\infty} (2x)^{n} -4 \sum_{n=0}^{\infty} (3x)^{n} \\ &= \sum_{n=0}^{\infty} (5 \cdot 2^{n} -4 \cdot 3^{n} ) x^{n} \\ \end{align}$Therefore $a_{n} = 5 \cdot 2^{n} -4 \cdot 3^{n}$. ***Question 4*** Let $I,II,III$ denote the events that a toy car is produced by machine $I,II,III$ respectively. Let $D$ denote the event that a toy car is defective. We're given that $\mathcal{P}(D\mid I)=0.02$, $\mathcal{P}(D\mid II)= 0.01$, $\mathcal{P}(D\mid III)=0.03$ and $P(II)=0.25.$ Now $\mathcal{P}(D)=\mathcal{P}(D\mid I)\mathcal{P}(I)+\mathcal{P}(D\mid II)\mathcal{P}(II)+\mathcal{P}(D\mid III)\mathcal{P}(III)=0.0215$. Also $\mathcal{P}(D \cap II)=\mathcal{P}(D\mid II)\times\mathcal{P}(II)=0.01\times 0.25=0.0025$. Therefore $\mathcal{P}( II \mid D) = \frac{\mathcal{P}(D \cap II)}{P(D)}= \frac{0.0025}{0.0215}= \frac{5}{43}$. ***Question 5*** i) $\mathcal{P}(101)=\mathcal{P}(THH)+\mathcal{P}(HTH)+\mathcal{P}(HHT)=\frac{3}{8}$. ii) Let $p(n)=\mathcal{P}(300\mid n)$ denote the probability of reaching $N$ dollars on the condition that we currently hold $n$ dollars. Note that $\mathcal{P}(N\mid0) = 0$ and $\mathcal{P}(N\mid N)$ supposing the player plays the game repeatedly until the player either goes broke or increases his holdings to $N$ dollars. Suppose the player has $0<n<N$ dollars at the moment, the next round will leave the player with either $n + 1$ or $n − 1$ dollars, both with probability $1/2$ so $p(n) = \frac{1}{2} p(n+1)+ \frac{1}{2} p(n-1) $The corresponding characteristic equation is $x^{2}-2x+1=0\implies(x-1)^{2}=0$ so the recurrence relation has a general solution has the form $p(n) = (A+Bn)\times1^{n} =A+Bn$Note that $p(0)=0$ and $p(300)=1$ so $0=A$ and $1 =300B\implies B=\frac{1}{300}$. Therefore the required probability which is $p(100)= \frac{1}{3}$. iii) Let $y(n)$ denote the probability of reaching $N$ dollars on the condition that we currently hold $n$ dollars. Then $y(n)= p y(n+1) + ( 1- p) y(n-1)$with $y(0)=0$ and $y(N)=1$. The corresponding characteristic equation for this difference equation is $px^{2}-x+1-p=0$ so $x= \frac{1 \pm \sqrt{ 1-4p(1-p) }}{2p}= \frac{1\pm \sqrt{ (1-2p)^{2} }}{2p} \in \left\{ 1 , \frac{q}{p} \right\}.$Note that $p = q \iff p=\frac{1}{2}$ so we get two distinct real roots when the coin is biased. Hence the general solution has the form $ y(n)=A + B \left( \frac{q}{p} \right)^{n} $ Substituting $y(0)=0$ gives $0=A+B\implies A=-B$. Substituting $y(N)=1$ gives $1= A-A\left( \frac{q}{p} \right)^{N}=A\left( 1- \frac{q}{p}^{N} \right)$ So $A = \frac{1}{\left( 1-\left( \frac{q}{p} \right)^{N} \right)}$ the required probability is given by $y(n)= \frac{\left( 1 - \left( \frac{q}{p} \right)^{n} \right)}{\left( 1- \left( \frac{q}{p} \right)^N \right)}.$