Consider the following algorithm segment.

For each positive integer $n,$ let $b_n$ be the number of iterations of the following while loop.

while $)>(0$

$n$:$=$ndiv$(3)$

end while

Find a recurrence relation for $b_n.$

To answer this question, observe that for each integer $k3,$ndiv$(3)=$

Thus, when the algorithm segment is run for a particular $k$ and the while loop has iterated one time, the input to the next iteration is

It follows that the number of iterations of the loop for $k$ is more than the number of iterations for

In other words, for every integer $k,$ we have which of the following?

$|)$

In addition, the initial values for the sequence $b_1,b_2,b_3,$dots are $b_1=,$ and $b_2=$

Need Help?