How to prove the following formula?

$$\sum_{j=0}^{n-1} \sum_{k=0}^{j} \frac{{n}\choose{k}}{{n-1}\choose{j}} = 2^{n-1}\sum_{j=0}^{n-1} \frac{1}{{n-1}\choose{j}}$$

I tried induction and manipulating the binomial coefficients but couldn't prove it. I also tried to write the term $2^{n-1}$ as $\sum_{k=0}^{n-1} {{n-1}\choose{k}}$. That's a nice structure at least: sum of the binomial coefficients times the sum of their reciprocals. But how do we "cut" the inner sum at $j$ and turn $n-1$ in the numerator into $n$?


Notice that

$$ \sum_{k=0}^{j} \binom{n}{k} = 2^n - \sum_{k=j+1}^{n} \binom{n}{k} = 2^n - \sum_{k=j+1}^{n} \binom{n}{n-k} \stackrel{(k\to n-k)}{=} 2^n - \sum_{k=0}^{n-1-j} \binom{n}{k}. $$

Plugging this back,

$$ = \sum_{j=0}^{n-1} \frac{\sum_{k=0}^{j} \binom{n}{k}}{\binom{n-1}{j}} = \sum_{j=0}^{n-1} \frac{2^n - \sum_{k=0}^{n-j-1} \binom{n}{k}}{\binom{n-1}{n-1-j}} \stackrel{(j\to n-1-j)}{=} \sum_{j=0}^{n-1} \frac{2^n - \sum_{k=0}^{j} \binom{n}{k}}{\binom{n-1}{j}}. $$

Therefore the result follows by averaging the left-hand side and the right-hand side.


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.