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.
Can someone help please?
 A: Hint:
How many binary sequences of length $n$ contain at least two 0's, with the second 0 occurring in position $n-k+1$?
A: 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}
$$
A: 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 ... ?
A: A comment on robjohn's answer:
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$.
