Clarifying one the related formulas of Binomial Theorem. Can someone please clarify this formula, I don't really understand, I know the LHS is to count the number of subsets with a maximum of j elements from a set of n elements, but the RHS I just don't understand even with the book's clarification.
$$\sum_{j=0}^k{n\choose{j}}=\sum^k_{j=0}{n-j-1\choose{k-j}}2^j$$
Ty.
 A: You can prove the formula by induction but if you want to understand it look at the Pascal's triangle. The LHS is the sum of first $k+1$ terms in the $n^{\rm th}$ row (counting the rows from $0$) whereas the RHS is the sum of the terms running diagonally from the zeroth term in the $(n-k-1)^{\rm st}$ row to the $k^{\rm th}$ term of the $(n-1)^{st}$ row, weighted appropriately by the powers of $2$.
Now, we can reduce one sum to the other by the repeated use of the fact that when $0 < l < m$ we have $${m \choose l} = {m-1 \choose l-1} + {m-1 \choose l},$$
i.e. the sum of any term not on the boundary is obtained by summing the two terms above it. In this manner, we multiply the sum by $2$ each time we move up one level (because each term above contributes both to the left and to the right in the next level), in the end leaving just the sum over the two sides of the triangle (as determined by the diagonal and original row) multiplied by the powers of $2$. If we can get rid of the left-hand side we are done but that's simple because all the terms on the boundary of the Pascal's triangle are $1$ and summing over all the powers of $2$ there gives us precisely $2^k$ as the last term of the sum on the RHS.
A: I think that you meant to say that the lefthand side is the number of subsets of an $n$-element set that have at most $k$ elements, not at most $j$ elements. The fact that you were looking at it that way suggests that you might want a combinatorial explanation rather than an algebraic one. I found one, but it’s a little involved.
For $m\in\Bbb Z^+$ let $[m]=\{1,2,\ldots,n\}$. Suppose that $n,k\in\Bbb Z^+$, and $0\le k\le n$.

Proposition. If $S\subseteq[n]$, and $|S|\le k$, there is exactly one $j\in\{0,1,\ldots,k\}$ such that $$|S\cap[n-j-1]|=k-j\tag{1}$$ and $n-j\notin S$. $(1)$ just says that exactly $k-j$ members of $S$ are smaller than $n-j$.
Proof. Let $J=\{j\in\{0,1,\ldots,k\}:n-j\notin S\}$; $|\{0,1,\ldots,k\}|=k+1>|S|$, so $J\ne\varnothing$. Let $\ell=k+1-|S|$; clearly $|J|\ge\ell>0$. Thus, there is a $j\in J$ such that $|[j]\cap J|=\ell$: $j$ is the $\ell$-th member of $J$ counting up from the smallest element of $J$. Thus, the set $$\{n,n-1,n-2,\ldots,n-j\}\tag{2}$$ contains exactly $\ell$ members of $[n]\setminus S$. The set in $(2)$ has cardinality $j+1$, it contains $$j+1-\ell=j+1-(k+1-|S|)=|S|-(k-j)$$ members of $S$, and the other $k-j$ members of $S$ are therefore smaller than $n-j$. If $j\,'\in J\setminus\{j\}$, the set $\{n,n-1,\ldots,n-j\,'\}$ does not contain exactly $\ell$ members of $[n]\setminus S$ and hence does not contain exactly $|S|-(k-j\,')$ members of $S$, and the number of elements of $S$ smaller than $n-j\,'$ is therefore not $k-j\,'$. Thus, $j$ is the unique element of $\{0,1,\ldots,k\}$ with the desired properties. In the sequel I’ll denote this element by $j_S$. $\dashv$

Now consider the $j$ term on the righthand side of the identity, $$\binom{n-j-1}{k-j}2^j\;;$$ I claim that it gives the number of $S\subseteq[n]$ such that $|S|\le k$ and $j_S=j$. Since for each subset of $S$ of $[n]$ of cardinality at most $k$ there is a unique $j\in\{0,1,\ldots,k\}$ such that $j_S=j$, proving this claim would show that the righthand side also just counts those subsets of $[n]$.
To prove the claim, suppose that $S\subseteq[n]$, $|S|\le k$, and $j_S=j$. Then the definition of $j_S$ ensures that $S$ has exactly $k-j$ elements in $[n-j-1]$; these $k-j$ elements smaller than $n-j$ can be chosen in $\binom{n-j-1}{k-j}$ ways. The definition of $j_S$ also ensures that $n-j\notin S$, so the rest of $S$ can be any subset of the $j$-element set $\{n,n-1,n-2,\ldots,n-j+1\}$, and there are $2^j$ such subsets. Thus, there are $\binom{n-j-1}{k-j}2^j$ sets $S\subseteq[n]$ such that $|S|\le k$ and $j_S=j$, as claimed.
