binomial coefficient identity $\sum_{k=0}^n {n\choose k}\sum_{j=0}^{k-1}{{n-1}\choose j}=2^{2n-2}$

Question

While trying to solve a probability question about a coin flip game, I arrived at the expression $\sum_{k=0}^n {n\choose k}\sum_{j=0}^{k-1}{{n-1}\choose j}.$ Computing this sum for several low values of $n$ suggested that it summed to $2^{2n-2}$, suggesting there is an identity:

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

However I was not able to prove the identity by means of the Pascal recurrence relation, the Chu-Vandermonde identity $\sum_{k=0}^r {m\choose k}{n\choose {r-k}}={{m+n}\choose r}$, nor the $\sum_{k=0}^n{n\choose k} = (1+1)^n=2^n$ identity from the binomial theorem.

Can I get a hint how to proceed?

Answer 1

This is similar to the proof by darij grinberg in the other thread but the formula there looks slightly different.

Let $$S=\sum_{k=0}^n {n\choose k}\sum_{j=0}^{k-1}{{n-1}\choose j}$$ be the original sum. Then $$S=\sum_{k=0}^n{n\choose k}\left[2^{n-1}-\sum_{j=k}^{n-1}{{n-1}\choose j}\right]$$ $$=\sum_{k=0}^n {n\choose k}\cdot 2^{n-1}-\sum_{k=0}^n{n\choose k}\sum_{j=k}^{n-1}{{n-1}\choose j}$$ $$=2^n\cdot 2^{n-1}-\sum_{k=0}^n{n\choose {n-k}}\sum_{j=k}^{n-1}{{n-1}\choose j}$$ $$=2^{2n-1}-\sum_{k’=0}^n{n\choose k’}\sum_{j=n-k’}^{n-1}{{n-1}\choose j}~({\rm with~}n-k=k’)$$ $$=2^{2n-1}-\sum_{k’=0}^n{n\choose k’}\sum_{j=n-k’}^{n-1}{{n-1}\choose {n-1-j}}$$ $$=2^{2n-1}-\sum_{k’=0}^n{n\choose k’}\sum_{j’=0}^{k’-1}{{n-1}\choose j’}~({\rm with~}n-1-j=j’)$$ $$=2^{2n-1}-S,$$ hence $$2S=2^{2n-1}~{\rm and~so~}S=2^{2n-2},$$ as required.

Answer 2

$$ \begin{align} &\sum_{k=0}^n\binom{n}{k}\sum_{j=0}^{k-1}\binom{n-1}{j}\\ &=\sum_{k=0}^n\left[\binom{n-1}{k-1}+\binom{n-1}{k}\right]\sum_{j=0}^{k-1}\binom{n-1}{j}\tag{1a}\\ &=\sum_{k=0}^{n-1}\sum_{j=0}^k\binom{n-1}{k}\binom{n-1}{j}+\sum_{k=0}^{n-1}\sum_{j=0}^{k-1}\binom{n-1}{k}\binom{n-1}{j}\tag{1b}\\ &=\sum_{j=0}^{n-1}\sum_{k=j}^{n-1}\binom{n-1}{k}\binom{n-1}{j}+\sum_{k=0}^{n-1}\sum_{j=0}^{k-1}\binom{n-1}{k}\binom{n-1}{j}\tag{1c}\\ &=\sum_{k=0}^{n-1}\sum_{j=k}^{n-1}\binom{n-1}{k}\binom{n-1}{j}+\sum_{k=0}^{n-1}\sum_{j=0}^{k-1}\binom{n-1}{k}\binom{n-1}{j}\tag{1d}\\ &=\sum_{k=0}^{n-1}\sum_{j=0}^{n-1}\binom{n-1}{k}\binom{n-1}{j}\tag{1e}\\ &=\left[\sum_{k=0}^{n-1}\binom{n-1}{k}\right]^2\tag{1f}\\[9pt] &=2^{2n-2}\tag{1g} \end{align} $$ Explanation:
$\text{(1a):}$ $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ (Pascal's Identity)
$\text{(1b):}$ substitute $k\mapsto k+1$ in the left sum
$\text{(1c):}$ swap the order of summation in the left sum
$\text{(1d):}$ swap $j$ and $k$ in the left sum
$\text{(1e):}$ combine the inner sums
$\text{(1f):}$ this is the product of two identical sums
$\text{(1g):}$ $\sum\limits_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1}$

Answer 3

We seek to evaluate

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

This is

$$\sum_{k=0}^n {n\choose k} [z^k] \frac{z}{1-z} \sum_{j\ge 0} {n-1\choose j} z^j = \sum_{k=0}^n {n\choose k} [z^k] \frac{z}{1-z} (1+z)^{n-1} \\ = \sum_{k=0}^n {n\choose k} [z^{n-k}] \frac{z}{1-z} (1+z)^{n-1} = [z^n] \frac{z}{1-z} (1+z)^{n-1} \sum_{k=0}^n {n\choose k} z^k \\ = [z^n] \frac{z}{1-z} (1+z)^{n-1} (1+z)^n = [z^{n-1}] \frac{1}{1-z} (1+z)^{2n-1} \\ = \sum_{q=0}^{n-1} [z^{n-1-q}] \frac{1}{1-z} [z^q] (1+z)^{2n-1} = \sum_{q=0}^{n-1} {2n-1\choose q} = \frac{1}{2} 2^{2n-1} = 2^{2n-2}.$$