1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – coffeemath Aug 12 '13 at 12:32
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Aug 12 '13 at 12:33
  • $\begingroup$ @GerryMyerson: The question specifically asks for using the sum rule. $\endgroup$ – Shahab Aug 12 '13 at 12:34
  • $\begingroup$ Then maybe you had better tell us what "the sum rule" is! $\endgroup$ – Gerry Myerson Aug 12 '13 at 12:36
  • $\begingroup$ See this post for ideas. $\endgroup$ – David Mitra Aug 12 '13 at 12:36
3
$\begingroup$

Hint:

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Shahab Aug 12 '13 at 13:03
  • $\begingroup$ 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. $\endgroup$ – Nick Peterson Aug 12 '13 at 13:05
  • $\begingroup$ That would be $2^n-n-1$? $\endgroup$ – Shahab Aug 12 '13 at 13:08
  • $\begingroup$ @Shahab That's right! $\endgroup$ – Nick Peterson Aug 12 '13 at 17:12
  • $\begingroup$ @NickPeterson what was the motivation for using a binary sequence of length $n$? Why consider the position $n-k+1$? $\endgroup$ – pretzelman Aug 31 '15 at 18:06
2
$\begingroup$

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} $$

$\endgroup$
2
$\begingroup$

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 ... ?

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.