91Ó°ÊÓ

What is wrong with the following definition of \(f: \mathbb{R} \rightarrow \mathbb{R} ? f(0)=1\) and \(f(x)=f(x / 2) / 2\) if \(x \neq 0\).

Use the substitution \(G(n)=T(n)^{2}\) to solve \(T(n)^{2}-T(n-1)^{2}=1\) for \(n \geq 1,\) with \(T(0)=10\).

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-S(k-1)-6 S(k-2)=-30, S(0)=7, S(1)=10 $$

Prove by induction that if \(n \geq 0, \sum_{k=0}^{n}\left(\begin{array}{c}n \\\ k\end{array}\right)=2^{n}\).

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-5 S(k-1)=5^{k}, S(0)=3 $$

Solve as completely as possible: (a) \(Q(n)=1+Q(\lfloor\sqrt{n}\rfloor), n \geq 2, Q(1)=0\). (b) \(R(n)=n+R(\lfloor n / 2\rfloor), n \geq 1, R(0)=0 .\)

Suppose Step 1 of the merge sort algorithm did take a significant amount of time. Assume it takes 0.1 time unit, independent of the value of \(n\). (a) Write out a new recurrence relation for \(T(n)\) that takes this factor into account. (b) Solve for \(T\left(2^{r}\right), r \geq 0\) (c) Assuming the solution for powers of 2 is a good estimate for all \(n\), compare your result to the solution in the text. As gets large, is there really much difference?

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-5 S(k-1)+6 S(k-2)=2, S(0)=-1, S(1)=0 $$

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-4 S(k-1)+4 S(k-2)=3 k+2^{k}, S(0)=1, S(1)=1 $$

A game is played by rolling a die five times. For the \(k^{\text {th }}\) roll, one point is added to your score if you roll a number higher than \(k .\) Otherwise, your score is zero for that roll. For example, the sequence of rolls 2,3,4,1,2 gives you a total score of three; while a sequence of 1.2,3,4,5 gives you a score of zero. Of the \(6^{5}=7776\) possible sequences of rolls, how many give you a score of zero? of one? ... of five?