Double sum of binomial coefficients quotients

Question

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

Answer 1

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.