Use induction to prove $ S(n) = \sum_{k=1}^n \sum_{i=1}^k 2^{n-k} = 2^{n+1} - (n+2)$ Use induction to prove $$ S(n) = \sum_{k=1}^n \sum_{i=1}^k 2^{n-k} = 2^{n+1} - (n+2)$$
So far I worked out that you can convert the two summations into one:
$$\sum_{k=1}^n k\cdot 2^{n-k} $$
My problem comes when I try to write $S(n+1)$ as the sum of $S(n)$ plus the 'last term'. I realised that finding $n+1^{th}$ term isn't as simple as I am used to. Here is an example:
$$S(3) = 1 \cdot 2^2 + 2 \cdot 2^1 + 3 \cdot 2^0 = 11$$
$$S(4) = 1 \cdot 2^3 + 2 \cdot 2^2 + 3 \cdot 2^1 + 4 \cdot 2^0  = 26$$
Ideally I would like to write $$\sum_{k=1}^n k\cdot 2^{n-k} = 1 \cdot 2^{n-1} + 2 \cdot 2^{n-2} + ... + n \cdot 2^{n-n}$$
Then $$\sum_{k=1}^{n+1} k\cdot 2^{n+1-k} = 1 \cdot 2^{n+1-1} + 2 \cdot 2^{n+1-2} + ... + (n+1) \cdot 2^{n+1-n-1}$$
Then substitute from the induction hypothesis that $$\sum_{k=1}^n k\cdot 2^{n-k} = 2^{n+1} - (n+2)$$
But now I'm totally stuck and don't know how to proceed. Any help would be most appreciated!

$$S(n+1)=\sum_{k=1}^{n+1} k \, 2^{n+1-k} = 2 \sum_{k=1}^n k \, 2^{n-k} + (n+1) \\ \stackrel{\text{I.H.}}{=} 2\left(2^{n+1}-n-2\right) + n + 1 = 2^{n+2} - n - 3$$
which is what you would expect.
