# Sum rule and $\sum_{k=1}^n (n-k)2^{k-1}$

I am trying to obtain a closed form for $\sum_{k=1}^n (n-k)2^{k-1}$ by a combinatorial argument. Unfortunately, nothing seems to strike. If I write this as $n\sum 2^{k-1}-\sum k2^{k-1}$ then I do have the first term $n\sum 2^{k-1}=n2^{n+1}-n2^n-n$ but am unable to make sense of the second term.

• You may as well sum only up to $n-1$, since $n-n=0$. Or maybe rewrite the sum in terms of $n-1=t$ or something. – coffeemath Aug 12 '13 at 12:32
• I don't know about a combinatorial argument, but if you let $f(x)=\sum(1+x)^k$, differentiate, and let $x=1$, you should be able to evaluate your sum. – Gerry Myerson Aug 12 '13 at 12:33
• @GerryMyerson: The question specifically asks for using the sum rule. – Shahab Aug 12 '13 at 12:34
• Then maybe you had better tell us what "the sum rule" is! – Gerry Myerson Aug 12 '13 at 12:36
• See this post for ideas. – David Mitra Aug 12 '13 at 12:36

Hint:

How many binary sequences of length $n$ contain at least two 0's, with the second 0 occurring in position $n-k+1$?

• This is how I proceeded: The 1st zero may be selected at any of the 1st $n-k$ positions, and there remain $k-1$ positions to fill arbitrarily(the ones before the first zero and the $n-k+1$th positions are fixed). This yields the desired sum. Alternatively, we just have $\tbinom{n}{2}2^{n-2}$. Is this correct? – Shahab Aug 12 '13 at 13:03
• Not quite: $\binom{n}{2}2^{n-2}$ over-counts pretty badly, since the positions of the two 0's are not uniquely determined. Instead, see if you can count the number of sequences with exactly one 0 and exactly no 0's, and subtract from the total number of binary sequences. – Nick Peterson Aug 12 '13 at 13:05
• That would be $2^n-n-1$? – Shahab Aug 12 '13 at 13:08
• @Shahab That's right! – Nick Peterson Aug 12 '13 at 17:12
• @NickPeterson what was the motivation for using a binary sequence of length $n$? Why consider the position $n-k+1$? – pretzelman Aug 31 '15 at 18:06

Start with $$\sum_{k=1}^n x^k=\frac{x^{n+1}-x}{x-1}\tag{1}$$ then take the derivative and multitply by $x$: $$\sum_{k=1}^n kx^k=\frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2}\tag{2}$$ Subtract $(2)$ from $n$ times $(1)$ to get \begin{align} \sum_{k=1}^n(n-k)x^k &=\frac{nx^{n+2}-nx^{n+1}-nx^2+nx}{(x-1)^2}-\frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2}\\ &=\frac{x^{n+1}-nx^2+(n-1)x}{(x-1)^2}\tag{3} \end{align} Pluggng $x=2$ into $(3)$ yields $$\sum_{k=1}^n(n-k)2^k=2^{n+1}-2n-2\tag{4}$$

HINT: Let $S=\{1,2,\dots,n\}$. For each $k\in S$, $(n-k)2^{k-1}$ is the number of ways to pick any subset of $\{1,\dots,k-1\}$ and any one element of $\{k+1,k+2,\dots,n\}$. This is exactly the number of ways to pick a subset $A$ of $S$ such that $|A|\ge 2$, and the second-largest element of $A$ is $k$. Let $\mathscr{A}_k$ be the family of such subsets of $S$. If you pick a subset of $S$ of cardinality at least $2$, it belongs to a unique $\mathscr{A}_k$. Thus, the sum is the number of subsets of $S$ of cardinality at least $2$, which is ... ?

• $2^n-n-1$. Thanks. – Shahab Aug 12 '13 at 13:23
• @Shahab: That's right. You're welcome. – Brian M. Scott Aug 12 '13 at 13:24

If $f(x) = \sum_{k=1}^n k x^k$, and $g(x) = \sum_{k=1}^n (n-k) x^k$, then
\begin{align} f(x)x^{-n} &=\sum_{k=1}^n k x^{k-n}\\ &=\sum_{k=0}^{n-1} (n-k) x^{-k}\\ &=\sum_{k=0}^{n} (n-k) x^{-k}\\ &=n+\sum_{k=1}^{n} (n-k) x^{-k}\\ &=n+g(1/x)\\ \end{align}
so $f(1/x)x^n = n+g(x)$ or $g(x) = x^n f(1/x) - n$.