Q:

Shifting Method

I'm taking a Course in Computer Science where we're having a refresher on Calculus 2 material. There is a problem that I don't understand or know how to do.

Compute the following using the shifting method: $\sum_{i=1}^h i\,2^i$

Could anyone explain to me how I would solve this problem? Sorry if I've formatted the text wrong, just let me know and i'll change it!

A:

Well, let's say that $$S=\sum_{i=1}^h i2^i.$$ Now, we will let $i=j+1,$ so that $j=i-1$ and $j$ ranges from $0$ to $h-1,$ meaning that $$S=\sum_{j=0}^{h-1}(j+1)2^{j+1}\\S=\sum_{j=0}^{h-1}j2^{j+1}+\sum_{j=0}^{h-1}2^{j+1}.$$ Since $2^{j+1}=2\cdot 2^j,$ then we have $$S=2\sum_{j=0}^{h-1}j2^j+2\sum_{j=0}^{h-1}2^j,$$ and since $0\cdot 2^0=0,$ then $$S=2\sum_{j=1}^{h-1}j2^j+2\sum_{j=0}^{h-1}2^j.$$ Notice how similar that first sum looks to our first form of $S$? The only difference is that we're multiplying it by $2,$ calling our index variable by a different name, and missing the term $h2^h.$ So, to simplify our life by first making it slightly more complicated, we have $$S=2\left(-h2^h+h2^h+\sum_{j=1}^{h-1}j2^j\right)+2\sum_{j=0}^{h-1}2^j\\S=2\left(-h2^h+\sum_{j=1}^hj2^j\right)+2\sum_{j=0}^{h-1}2^j\\S=2\left(-h2^h+\sum_{i=1}^hi2^i\right)+2\sum_{j=0}^{h-1}2^j\\S=2\left(-h2^h+S\right)+2\sum_{j=0}^{h-1}2^j\\S=-2h2^h+2S+2\sum_{j=0}^{h-1}2^j\\S=-h2^{h+1}+2S+2\sum_{j=0}^{h-1}2^j.$$ Can you solve for $S$ from here?

