Chapter 4

Draw a recursion tree diagram for $$ T(n)= \begin{cases}4 T(n / 2)+n^{2} & \text { if } n \geq 2, \\ 3 & \text { if } n=1 .\end{cases} $$ Use it to find the exact solution to the recurrence. Assume \(n\) is a power of 2 .

Find a big \(\Theta\) bound to solutions to the recurrences \(T(n / 4)+T(3 n / 4)+d n \leq T(n) \leq T(n / 4)+T(3 n / 4)+c n .\)

Prove that \(\sum_{i=j}^{n}\left(\begin{array}{l}i \\\ j\end{array}\right)=\left(\begin{array}{c}n+1 \\ j+1\end{array}\right)\). In addition to an inductive proof, there is a nice "story" proof of this formula. It is well worth trying to figure out both proofs.

Prove Corollary \(4.8\) by showing that for any \(x, y\), and \(z\), each greater than \(1, x^{\log _{y} z}=z^{\log _{y} x}\).

Prove that every number greater than 7 is a sum of a nonnegative integer multiple of 3 and a nonnegative integer multiple of 5 .

Draw a recursion tree diagram for $$ T(n)= \begin{cases}3 T(n / 3)+1 & \text { if } n \geq 2 \\ 2 & \text { if } n=1\end{cases} $$ Use it to find the exact solution to the recurrence. Assume \(n\) is a power of 3 .

Find a big \(O\) upper bound (the best you know how to get) on solutions to the recurrence \(T(n)=T(n / 4)+T(n / 2)+n^{2}\), with \(T(n)=1\) if \(n<4 .\)

Show by induction that $$ T(n)= \begin{cases}8 T(n / 2)+n \log n & \text { if } n>1 \\ d & \text { if } n=1\end{cases} $$ has \(T(n)=O\left(n^{3}\right)\) for any solution \(T(n)\).

At the end of each year, a state fish hatchery puts 2000 fish into a lake. The number of fish in the lake at the beginning of the year doubles by the end of the year due to reproduction. Give a recurrence for the number of fish in the lake after \(n\) years, and solve the recurrence.

We can define the nonnegative powers of a number \(a\) by the rules \(a^{0}=1\) and \(a^{n+1}=a^{n} \cdot a\). Explain why this defines \(a^{n}\) for all nonnegative integers \(n\). From this definition, prove the rule of exponents \(a^{m+n}=a^{m} a^{n}\) for nonnegative integers \(m\) and \(n\).