# Concrete Mathematics: Working through algebraic manipulations for second perturbation example

Summary

In Concrete Mathematics (Graham, Knuth, Patashnik) I am not able to find the algebraic manipulations to give the result described below to find $$S_n$$ (where $$S_n$$ stands in for $$\sum_{0 \leq k \leq n}k2^k$$)

Therefore we have $$S_n + (n + 1)2^{n+1} = 2S_n + 2^{n+2} - 2$$, and algebra yields

$$\sum_{0 \leq k \leq n}k2^k = (n - 1)2^{n+1} + 2$$

Context and My Attempt So Far

As mentioned above this is in the context of the book Concrete Mathematics (Graham, Knuth, Patashnik) just before equation 2.26 is presented (page 33). The book is illustrating the perturbation method to find a closed form of a sum. I feel like I understand the concepts they are conveying but can't quite replicate their algebraic maniupluations for the above quote.

I have tried the following (using the sum represented as $$S_n$$ for ease of writing):

\begin{align} S_n + (n + 1)2^{n+1} &= 2S_n + 2^{n+2} - 2 \\ S_n + 2^{n+1}n + 2^{n+1} &= 2S_n + 2^{n+2} - 2 \\ -S_n + 2^{n+1}n + 2^{n+1} &= 2^{n+2} - 2 \\ -S_n &= 2^{n+2} - 2^{n+1}n -2^{n+1} - 2 \\ S_n &= -2^{n+2} + 2^{n+1}n + 2^{n+1} + 2 \\ S_n &= - 2^{n+2} + 2^{n+1}(n + 1) + 2 \\ \end{align}

The way to $$S_n = (n - 1)2^{n+1} + 2$$ is not obvious to me so far.

• What you’re missing is that $2^{n+2}$ is just double $2^{n+1}$. – symplectomorphic Oct 15 '20 at 9:12

Solving $$S_n+(n+1)2^{n+1}=2S_n+2^{n+2}-2$$ for $$S_n$$, we find that

\begin{align*} S_n&=(n+1)2^{n+1}-2^{n+2}+2\\ &=(n+1)2^{n+1}-2\cdot 2^{n+1}+2\\ &=(n-1)2^{n+1}+2\,, \end{align*}

where by definition $$S_n=\sum_{0\le k\le n}k2^k$$.

$$S_n + (n + 1)2^{n+1} = 2S_n + \boxed{2^{n+2}} - 2$$

$$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\bigg\downarrow$$

$$S_n + (n + 1)2^{n+1} = 2S_n + \boxed{2^1.2^{n+1}} - 2$$

$$(n - 1)2^{n+1} + 2 = S_n$$

There are many ways to prove the identity $$S_n + (n+1)2^{n+1} = 2 S_n + 2^{n+2} - 2. \tag{1}$$ One way is to observe \begin{align} S_n + (n+1) 2^{n+1} = \sum_{0 \le k \le n+1} k 2^k &= 2 \sum_{1 \le k \le n+1} k 2^{k-1} \\ &= 2 \sum_{0 \le k \le n} (k+1) 2^k \\ &= 2 \left( \sum_{0 \le k \le n} k 2^k + \sum_{0 \le k \le n} 2^k \right) \\ &= 2 S_n + 2 \frac{2^{n+1} - 1}{2 - 1} \\ &= 2 S_n + 2^{n+2} - 2, \end{align} where in the first step, we note the first term is $$0 \cdot 2^0 = 0$$, so we may ignore it; in the second step, we shift the index of summation by $$1$$; in the third step, we distribute and separate the summand into two separate sums; in the fourth step, we use the formula for a finite geometric series: $$\sum_{0 \le k \le n} z^k = \frac{z^{n+1} - 1}{z - 1}, \quad z \ne 1.$$

Now that we have proven $$(1)$$, solving for $$S_n$$ yields \begin{align} 0 &= 2 S_n + 2^{n+2} - 2 - S_n - (n+1)2^{n+1} \\ &= S_n + 2 \cdot 2^{n+1} - 2 - (n+1)2^{n+1} \\ &= S_n - (n-1) 2^{n+1} - 2, \end{align} hence $$S_n = (n-1) 2^{n+1} + 2.$$