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


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

  • $\begingroup$ How could we say 'Such a subset is missing at least n−k elements.' @Mike Earnest $\endgroup$ – SutMar Apr 11 at 4:02
  • $\begingroup$ @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”). $\endgroup$ – Mike Earnest Apr 11 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.