0

Can anyone point me in the right directions for these recurrence problems? I'm having trouble figuring this out for my class

I have to find the explicit formula for $H(n)$ as a fuction of $n$. Assume that $n$ is the power of the appropiate integer (when applicable).

$$H(n) = 2H(n - 1) + 2,$$ where the base case is $$H(1) = 1.$$

This is what I think is right. But can it be double checked?

$$ \begin{align} H(n) &= 2H(n - 1) + 2 \\ &= 2(2H(n-2)+2)+2 \\ &= 2 \cdot 2H(n-2) + 2 \cdot 2 + 2 \\ &= 2 \cdot 2(2H(n - 3) + 2) + 2 \cdot 2 + 2 \\ &=\dots \text{(recurrence)} \\ &= 2^{n - 1}H(1) + 2^{n - 2} + 2^{n - 3} + \dots + 2^2 + 2 \end{align} $$

Then, because $H(1) = 1$, $$ H(n) = 2^n - 2 $$

Other recurrences: $$ T(n) = 3T(n - 1) + 3^n, \text{where the base case is } T(0) = 1 $$ Don't really quite grasp the concept of this yet because I'm new.

Another: $$ T(n) = T(n/2) + n, \text{where the base case is } T(1) = 1 $$

I'm looking for some really good help on how to approach these problems. I would like the help from this topic to be able to apply it with other problems that are similar! Thanks for any input on what you think should happen.

Cameron Buie
  • 102,994
Conor F
  • 103
  • 1
  • 1
    Welcome to MSE. I am going to edit your post to make the math look nice. You should check that it still reflects your original intent. – Sammy Black Apr 15 '13 at 16:22

1 Answers1

0

Often, a change of variables makes the recurrence easier to solve. For the first recurrence, $$ \begin{cases} H(n) = 2H(n - 1) + 2, & n > 1 \\ H(1) = 1, \end{cases} $$ Let $K(n) = H(n) + 2$, which is equivalent to $H(n) = K(n) - 2$. What recurrence does $K$ satisfy? $$ K(n) = H(n) + 2 = \big( 2H(n - 1) + 2 \big) + 2 = 2 \big( K(n) - 2 \big) + 4 = 2K(n) $$ What is the initial condition for $K$? $$ K(1) = H(1) + 2 = 3 $$ Putting these together, we have $$ \begin{cases} K(n) = 2K(n - 1), & n > 1 \\ K(1) = 3, \end{cases} $$ The recurrence gives $K(n) = a \cdot 2^n$ for some $a$, and the initial condition gives $$ a \cdot 2^1 = 3 \quad \Longrightarrow \quad a = \frac{3}{2} \quad \Longrightarrow \quad K(n) = \frac{3}{2} \cdot 2^n = 3 \cdot 2^{n - 1} $$ Finally, converting back to the original sequence, $$ H(n) = \left( 3 \cdot 2^{n-1} \right) - 2 = 3 \cdot 2^{n - 1} - 2 $$

You ought to check that this formula for $H$ actually works.

For the second recurrence, consider $U(n) = T(n) + a \cdot 3^n$? What value of $a$ makes the recurrence for $U$ particularly simple?

The last recurrence doesn't quite make sense? How can you expand $T(3)$?

Sammy Black
  • 25,273