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.
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)$?