Originally Posted by

**234578** prove that the sum from j=1 to j=n of combinatorial(n, j) is 2^n.

so basicially i have to prove that the sum of the (n+1)th row of pascal's triangle is 2^n. I have tried using induction on n and the definition of combinatiorial(n,j) = n!/[j!(n-j)!] but I keep getting stuck. If someone could provide guidance as to how I should approach this problem it would be more helpful than a straight solution because I am trying to solve problems as practice for an exam

Here's how I like to think about it.

Let $\displaystyle \Omega_n=\{1,\cdots,n\}$and let $\displaystyle f(n)=\text{card }\mathcal{P}(\Omega_n)$. Then, we can think of this as saying "$\displaystyle f(n)$ is how many subsets of $\displaystyle \Omega_n$ there are. Well, how many are there for $\displaystyle 0$? Well, it is how many ways I can choose $\displaystyle 0$ items from $\displaystyle n$ items, and so $\displaystyle n\choose 0$. How aboust subsets with one element? Using the same logic it is $\displaystyle n\choose 1$. Thus, to get how many subsets with $\displaystyle 1\leqslant k\leqslant n$ elements I only need compute $\displaystyle n\choose k$. Thus, to get the number of all subsets of $\displaystyle \Omega_n$ it is

$\displaystyle \text{number of subsets with zero elements}+\cdots+\text{number of subsets with }n\text{ elements}$$\displaystyle ={n\choose 0}+\cdots+{n\choose n}=f(n)$.

Thus, $\displaystyle f(n)=\text{card }\mathcal{P}(\Omega_n)=\sum_{j=0}^{n}{n\choose j}$. So, let's see if we can find a recurrence relation for $\displaystyle n$. To do this we must only relate the number of subsets of $\displaystyle \Omega_{n+1}$ to $\displaystyle \Omega_n$. So, let's do it:

We can partition $\displaystyle \mathcal{P}(\Omega_{n+1})$ into two blocks; namely those that contain $\displaystyle n+1$ (call them $\displaystyle B_1$) and those that don't ($\displaystyle B_2$). So, how many things are in $\displaystyle B_1$? Well, it's all the subsets I can make out of elements of $\displaystyle \Omega_{n+1}=\Omega_{n}\cup\{n+1\}$. But, as the way I wrote the RHS side indicates this is clearly all the subsets I can make which contain elements only from $\displaystyle \Omega_n$. But, we called this number $\displaystyle f(n)$. So what about $\displaystyle B_2$? Well, since all of these subsets contain elements of $\displaystyle \Omega_{n+1}=\Omega_n\cup\{n+1\}$ we see in particular that each set contains only elements of $\displaystyle \{n+1\}$ or contains elements of $\displaystyle \Omega_n$ and $\displaystyle \{n+1\}$. Clearly the number of sets we can form using only $\displaystyle \{n+1\}$ is $\displaystyle 1$. The latter can be thought about as taking one of the subsets of $\displaystyle \Omega_n$ and uniting it with $\displaystyle \{n+1\}$. Thus, there are $\displaystyle f(n)$ of those. Thus, $\displaystyle B_2=f(n)+1$....or does it! Notice that $\displaystyle f(n)$ included the number of ALL subsets of $\displaystyle \Omega_n$ including $\displaystyle \varnothing$. But, all of the sets in $\displaystyle B_2$ must contain $\displaystyle n+1$ and so we can't count $\displaystyle \varnothing$. Thus, the number of things in $\displaystyle B_2$ is $\displaystyle f(n)+1-1=f(n)$.

Thus, since $\displaystyle B_1\cup B_2=\mathcal{P}(\Omega_{n+1}),B_1\cap B_2=\varnothing$ we have that $\displaystyle f(n+1)=\text{card }\mathcal{P}(\Omega_{n+1})=\text{card }B_1+\text{card }B_2=f(n)+f(n)=2f(n)$.

Thus, remembering that $\displaystyle f(n)=\sum_{j=0}^{n}{n\choose j}$ we are done. Since proving that $\displaystyle f(n+1)=2f(n)$ and $\displaystyle f(0)=\sum_{j=0}^{0}{0\choose j}=\text{card }\mathcal{P}(\Omega_0)=1$ implies that $\displaystyle f(n)=2^n$ is trivial.