Cannot manage to solve $\sum _{i=0}^{h-1}\:2^i\left(h-i\right)$

Question

$$\sum _{i=0}^{h-1}\:2^i\left(h-i\right)$$ wolfram alpha says that $\sum _{i=0}^{h-1}\:=2^{h+1}-h-2$ Which I have no idea how to get to, because I do not know how to solve $$\sum _{i=0}^{h-1}\:=2^ii$$ I am taking data structures and I tried to find the time coplexity of building a heap... came up with this rough formula, then found online an easier way to compute the time complexity and wondered why my way of thinking did not work.

Answer 1

HINT

take into account the relation $$ \frac{d}{da}\sum_{i=0}^{h-1}{a^{i}}=\sum_{i=0}^{h-1}{ia^{i-1}} $$

Answer 2

As you've mentioned in the comment that you didn't take calculus yet. Here's an algebraic way.

Let the sum be denoted as $x$.

So, $$x =\sum_{i=0}^{h-1} 2^ii$$

$ x = 0\cdot2^0 + 1\cdot2^1+2\cdot2^2+\cdots+ (h-1)\cdot2^{h-1}$

$2x = \cdots\ + 0\cdot2^1+ 1\cdot2^2+2\cdot2^3+\cdots+ (h-1)\cdot2^h$

Subtracting the second eqn. from the first,

$x -2x = 0 + 2^1(1-0) + 2^2(2-1) +2^3(3-2) +\cdots+2^{h-1}\left[(h-1)-(h-2)\right] -2^h(h-1)$

$\Rightarrow -x = \left[2+2^2+\cdots+2^{h-1}\right]-2^h(h-1) = 2\left(\dfrac{2^{h-1}-1}{2-1}\right) - 2^h(h-1)$

$\Rightarrow-x = 2^h-2-2^h(h-1) \Rightarrow \color{red}{x = 2^h(h-2)+2} $

Thus, $$x =\sum_{i=0}^{h-1} 2^ii = 2^h(h-2)+2$$

---

$$\sum_{i=0}^{h-1}2^i(h-i) = h\sum_{i=0}^{h-1}2^i - \sum_{i=0}^{h-1}2^ii = 2\left(\dfrac{2^h-1}{2-1}\right)-\left[2^h(h-2)+2\right] =\color{red}{2^{h+1} - h - 2}$$

---

This can be done for any number $a$.

Let, $x =\sum_{i=0}^{h-1} a^ii$. multiply throughout by $a$ (here multiplied by $2$) and the rest of the process is same.