Solve Recurrence: $E(h) = \frac{1}{3} E(h-1) + \frac{2}{3} 2h$

Question

Solve the recurrence relation with

$E(0) = 0$, $E(1) = \frac{2}{3} * 2$ and $E(h) = \frac{1}{3} E(h-1) + \frac{2}{3} 2h$

In other words, I want an explicit formula for $E(h)$.

I tried different approaches and the most promising was to rewrite it as follows:

$E(h) = \sum\limits_{i=1}^h \frac{4}{3^i} (h-(i-1))$

I got rid of the recurrence, but the formula is still not how I want it. When using Wolfram Alpha, I get a formula without a sum ($E(h) = 2h + 3^{-h} -1$). I have already tried many things with the above sum, but it could not be completely dissolved. How do I get to a formula without a sum?

Any tips would be really appreciated.

Answer 1

The general solution of the linear homogeneous recurrence relation $E(h)=\frac{1}{3}E(h-1)$ is $E(h)= a \left(\frac{1}{3}\right)^h$. The original non-homogeneous recurrence relation has particular solution of the form $b h + c$. So $$E(h)= a \left(\frac{1}{3}\right)^h + b h + c.$$ Use the initial conditions to find the constants $a$, $b$, and $c$.

Alternatively, rewrite your summation as $$E(h) = 4h \sum_{i=1}^h \left(\frac{1}{3}\right)^i - 4 \sum_{i=1}^h (i-1) \left(\frac{1}{3}\right)^i$$ and apply known formulas for $\sum_{k=1}^n r^k$ and $\sum_{k=1}^n (k-1) r^k$.

Answer 2

This recurrence relation can be solved as follows:

Multiplying both sides of the equality by $3^h$.

$$3^{h}E(h) = 3^{h-1} E(h-1) + 4h 3^{h-1}$$

Now, we have a telescoping summation.

$$3^{h}E(h) - 3^{h-1} E(h-1) = 4h 3^{h-1}$$

$$\sum_{h=1}^{n} 3^{h}E(h) - 3^{h-1} E(h-1) = 4\sum_{h=1}^{n}h 3^{h-1}$$

$$3^{n}E(n) - E(0) = 4\left(\frac{(2n -1) 3^{n}+1}{4}\right) $$

$$E(n) = \left(\frac{1}{3^n}(2n -1) 3^{n}+1\right) = (2n-1) + \frac{1}{3^n}$$

You can find how to compute $\sum_{h=1}^{n}h 3^{h-1}$ in many questions in this website, for example here.