Combinatorial Proof (Argument) for $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^{k} \binom{n-1-j}{k-j} 2^j$

Question

Give a combinatorial proof for: $$\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^{k} \binom{n-1-j}{k-j} 2^j$$

Answer 1

Let $S_m$ be a set of all sequences $(a_1, a_2, \ldots , a_m)$ such that $a_i\in\{0,1\}$ for all $i\in\{1,2\ldots, m\}$. It's clear that $|S_n|=2^n$. Then, it's easy to see that $\binom{n}{j}$ equals to number of the elements $(a_1, a_2, \ldots, a_n)$ of a set $S_n$ such that among $a_i$ there exactly $j$ 'ones'. Therefore, sum $\sum\limits_{j=0}^{k} \binom{n}{j}$ equals to number of elements of $S_n$ that has at most $k$ 'ones'. Denote set of elements of $S_n$ that has at most $k$ 'ones' as $T$. We proved that $|T|=\sum\limits_{j=0}^{k} \binom{n}{j}$.

On the other hand, we can count number of elements of $T$ in the following way. Every sequence $\overline{a}=(a_1,a_2,\ldots, a_n)\in T$ has at least $n-k$ 'zeros'. For every sequence $\overline{a}\in T$ let $s(\overline{a})$ be the position of $n-k$-th 'zero' in sequence $\overline{a}$. Note that $n-k\leq s(\overline{a})\leq n$ for all $\overline{a}\in T$. Now, consider number of sequences $\overline{a}$ in $T$ such that $s(\overline{a})=n-j$ for sime fixed $0\leq j\leq k$. Among $a_1, a_2, \ldots, a_{s(\overline{a})-1}$ there exactly $n-k-1$ 'zeros', so there $\binom{s(\overline{a})-1}{n-k-1}=\binom{n-j-1}{n-k-1}=\binom{n-j-1}{k-j}$ options for subsequence $a_1, a_2, \ldots, a_{s(\overline{a})-1}$. Then, $a_{s(\overline{a})}=1$ and for $i>s(\overline{a})$ term $a_i\in \{0,1\}$ (there no condition for it), so there $2^j$ options for subsequence $a_{s(\overline{a})}, \ldots, a_n$. Hence, for fixed $0\leq j\leq k$ there exactly $\binom{n-1-j}{k-j} 2^j$ elements $\overline{a}$ in $T$ with property $s(\overline{a})=n-j$. Thus, $|T|=\sum\limits_{j=0}^{k}\binom{n-1-j}{k-j} 2^j$. Since $|T|=\sum\limits_{j=0}^{k} \binom{n}{j}$ we obtain that $$ \sum_{j=0}^{k} \binom{n}{j}=\sum_{j=0}^{k}\binom{n-1-j}{k-j} 2^j, $$ as desired.