summation - Double sum of binomial coefficients quotients

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

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.