The binominal theorem is: .
Here is the row of the Pascal Triangle.
Now let . See what you get.
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
Let and let . Then, we can think of this as saying " is how many subsets of there are. Well, how many are there for ? Well, it is how many ways I can choose items from items, and so . How aboust subsets with one element? Using the same logic it is . Thus, to get how many subsets with elements I only need compute . Thus, to get the number of all subsets of it is
Thus, . So, let's see if we can find a recurrence relation for . To do this we must only relate the number of subsets of to . So, let's do it:
We can partition into two blocks; namely those that contain (call them ) and those that don't ( ). So, how many things are in ? Well, it's all the subsets I can make out of elements of . But, as the way I wrote the RHS side indicates this is clearly all the subsets I can make which contain elements only from . But, we called this number . So what about ? Well, since all of these subsets contain elements of we see in particular that each set contains only elements of or contains elements of and . Clearly the number of sets we can form using only is . The latter can be thought about as taking one of the subsets of and uniting it with . Thus, there are of those. Thus, ....or does it! Notice that included the number of ALL subsets of including . But, all of the sets in must contain and so we can't count . Thus, the number of things in is .
Thus, since we have that .
Thus, remembering that we are done. Since proving that and implies that is trivial.