Results 1 to 5 of 5

Math Help - sum of (n+1)th row pascal triangle proof

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    39

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by 234578 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Have you ever used a cannon when a flyswatter will work well?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Use pascal's triangle to expand
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 27th 2009, 12:33 PM
  2. Pascal's Triangle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 1st 2008, 11:02 AM
  3. Pascal's triangle
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 4th 2008, 09:37 PM
  4. Pascal's Triangle
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 31st 2007, 07:12 AM
  5. Pascal's Triangle.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 27th 2006, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum