Evaluating $\sum_{i=0}^{n}\sum_{j=0}^{i-1}\binom{n}{i}\binom{n-1}{j}$

Question

During a question in probability theory, I was required to evaluate the following double-sum:

$$S=\sum_{i=0}^{n}\sum_{j=0}^{i-1}\binom{n}{i}\binom{n-1}{j}$$

Where $2\leq n\in\mathbb{N}$. According to the book, $S=4^{n-1}$. I am not very familiar of how to work with this kind of sums, usually I just use the Binomial Theorem . I have always had hard times computing this kind of sums, especially because 100% of the time they are merely a small part of the general question (they are not the main part).

Thanks!

Answer 1

Key observation is that $\sum \binom{n}{i} = 2^n$ and $\binom{n}{r} = \binom{n}{n-r}$.

Now in your sum, just take first coefficient outside the summation, as it is constant for inner sum:

$$\sum_{i=0}^{n}\binom{n}{i}\sum_{j=0}^{i-1}\binom{n-1}{j}$$

Now notice that inner sum can be simplified using the fact that $\binom{n}{r} = \binom{n}{n-r}$. To better visualise, try writing some of the terms:

$$S = \color{red}{\binom{n}{0}\left[0\right]}+\color{blue}{\binom{n}{1}\left[\binom{n-1}{0}\right]} + \binom{n}{2}\left[\binom{n-1}{0}+\binom{n-1}{1}\right] + ... + \\ \binom{n}{n-2}\left[\binom{n-1}{0}+..\binom{n-1}{n-3}\right]+\color{blue}{\binom{n}{n-1}\left[\binom{n-1}{0}+..\binom{n-1}{n-2}\right]} + \color{red}{\binom{n}{n}\left[\binom{n-1}{0}+...\binom{n-1}{n-1}\right]}$$

Combine the like terms, $$S = \color{red}{\binom{n}{0}\left[0\right]}+\color{blue}{\binom{n}{1}\left[\binom{n-1}{0}\right]} + \binom{n}{2}\left[\binom{n-1}{0}+\binom{n-1}{1}\right] + ... + \\ \binom{n}{2}\left[2^{n-1}-\binom{n-1}{0}-\binom{n-1}{1}\right]+\color{blue}{\binom{n}{1}\left[2^{n-1}-\binom{n-1}{0}\right]} + \color{red}{\binom{n}{0}\left[2^{n-1}\right]}$$

This leads to your answer

Answer 2

As for a combinatorial proof:

Imagine a bucket with $n-1$ white balls and a single black ball.

First, choose some number $i$ ranging from $0$ to $n$ of balls from the larger bucket. If the black ball was included, then paint the white balls that you pulled yellow and leave the others white. Otherwise, paint the white balls that you did not pull yellow leaving the others white.

Next, from the $n-1$ not-black balls choose some number $j$ ranging from $0$ to $i-1$ of the balls. If the black ball was pulled in the previous step then add blue paint to the balls you just pulled which will cause a ball if previously painted yellow to turn green as the paints mix. Otherwise, add blue paint to the balls you didn't pull.

Now... at the end of this, each of the $n-1$ originally white balls will be one of four colors: white, yellow, blue, or green corresponding to whether they were painted in neither round, the first round only, the second round only, or both rounds.

Convince yourself why we have not overcounted any scenario.

Compare this count to had we just individually picked up each ball and decided what color to make it in sequence.