Solve Recurrence: $E(h) = \frac{1}{3} E(h-1) + \frac{2}{3} 2h$ 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.
 A: 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$.
A: 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.
