# Thread: sum of (n+1)th row pascal triangle proof

1. ## sum of (n+1)th row pascal triangle proof

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

2. The binominal theorem is: $\left( {x + y} \right)^n = \sum\limits_{k = 0}^n {\binom{n}{k}x^{n - k} y^k }$.
Here $\sum\limits_{k = 0}^n {\binom{n}{k}}=\binom{n}{0}+\binom{n}{1}+\binom{n} {2}+\cdots+\binom{n}{n}$ is the $(n+1)^{th}$ row of the Pascal Triangle.
Now let $x=1~\&~y=1$. See what you get.

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

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

Thus, $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 $n$. To do this we must only relate the number of subsets of $\Omega_{n+1}$ to $\Omega_n$. So, let's do it:

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

Thus, since $B_1\cup B_2=\mathcal{P}(\Omega_{n+1}),B_1\cap B_2=\varnothing$ we have that $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 $f(n)=\sum_{j=0}^{n}{n\choose j}$ we are done. Since proving that $f(n+1)=2f(n)$ and $f(0)=\sum_{j=0}^{0}{0\choose j}=\text{card }\mathcal{P}(\Omega_0)=1$ implies that $f(n)=2^n$ is trivial.

4. Have you ever used a cannon when a flyswatter will work well?

5. Originally Posted by Plato
Have you ever used a cannon when a flyswatter will work well?
Aren't you the proponent of "don't plug and chug...actually think!". While what I did was way more than the problem probably intended I think it was more insightful. Anyways, I don't think nor do I care if the OP uses this for their homework (though they probably shouldn't!!!), I just want them to learn.