# Combinatorial proof of $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$

Give a combinatorial proof for this identity for non-negative integer $$k$$ and $$n$$ such that $$0 \leq k < n$$ $$\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$$

My attempt: I tried to reduce this identity. Since $$k,n$$ are nonnegative integer and $$k then I can change the upper limit into

$$\sum_{j=0}^{n-1} \binom{n}{j} =2^n-1 \quad \text{and} \quad \sum_{j=0}^{n-1} \binom{n-1-j}{n-1-j}2^j = \sum_{j=0}^{n-1} 2^j ~.$$

So, I just need to show $$\sum_{j=0}^{n-1} 2^j =2^n-1$$ using combinatorial proof. Am I right? I really need helps

## 1 Answer

Big hint

$$\sum_{j=0}^k\binom{n}j$$ counts subsets of $$\{1,2,\dots,n\}$$ with at most $$k$$ elements. Such a subset is missing at least $$n-k$$ elements. Arrange the missing elements in a sorted list, so the first element in the list is the smallest missing element. For how many such subsets is the $$(n-k)^{th}$$ entry of the list of missing elements equal to $$n-j$$?

Further explanation, just shy of a full solution:

If a subset satisfies this condition, then the element $$n-j$$ is missing, and among the elements $$\{1,2,\dots,n-j-1\}$$, exactly $$n-k-1$$ are missing. The elements above $$n-j$$ are either included or excluded, arbitrarily.

Here is an illustration for $$n=5,k=3$$. We represent subsets as a string of zeroes and ones. The $$(n-k)^{th}$$ smallest, i.e. second smallest, missing element is highlighted in red. $$\begin{array}{c|c|c|c} \binom{5-1-0}{3-0} & \binom{5-1-1}{3-1}2 & \binom{5-1-2}{3-2}2^2 & \binom{5-1-3}{3-3}2^3 \\\hline 1110\color{red}0 & 110\color{red}00 &10\color{red}000 &0\color{red}0000 \\ 1101\color{red}0 & 110\color{red}01 &10\color{red}001&0\color{red}0001 \\ 1011\color{red}0 & 101\color{red}00 &10\color{red}010&0\color{red}0010 \\ 0111\color{red}0 & 101\color{red}01 &10\color{red}011&0\color{red}0011 \\ & 011\color{red}00 &01\color{red}000&0\color{red}0100 \\ & 011\color{red}01&01\color{red}001&0\color{red}0101 \\ & &01\color{red}010&0\color{red}0110 \\ & &01\color{red}011&0\color{red}0111 \end{array}$$

• How could we say 'Such a subset is missing at least n−k elements.' @Mike Earnest – SutMar Apr 11 at 4:02
• @SutMar There are $n$ elements total, and at most $k$ of them are in the subset, so at least $n-k$ are missing from the subset (this is what I mean by “missing”). – Mike Earnest Apr 11 at 4:18