Results 1 to 4 of 4

Math Help - Combinatorial Proof

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    10

    Combinatorial Proof

    1 + (n choose 1)*2 + (n choose 2)*4 + . . . + (n choose n-1)*2^n-1 + (n choose n)*2^n = 3^n

    Try to find a combinatorial proof
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,678
    Thanks
    610
    Hello, taylor1234!

    \text{Prove that: }\;1 + {n\choose1}\cdot2 + {n\choose2}\cdot2^2 + {n\choose3}\cdot2^3 + \hdots + {n\choose n}\cdot2^n \;=\; 3^n

    This probably doesn't qualify as a "combinatorial proof", but . . .

    . . Note that the left side of the equation is: . (1 + 2)^n
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    consider the set A of all functions f: \{1,2, \cdots , n \} \longrightarrow \{a,b,c\}. clearly |A|=3^n. now we'll find |A| in a different way: for any 0 \leq k \leq n let A_k be the set of all f \in A such that

    |f^{-1}\{a\}|=k. that means those f \in A are in A_k that map exactly k elements of \{1,2, \cdots , n \} to a. there are \binom{n}{k} ways to choose k elements of a set with n elements. also, for any

    set I \subseteq \{1,2, \cdots , n \} with |I|=k there are 2^{n-k} functions f \in A with f^{-1}\{a\} = I. therefore |A_k|=\binom{n}{k}2^{n-k}. on the other hand, it is clear that A_i \cap A_j = \emptyset for all i \neq j

    and A = \bigcup_{k=0}^n A_k. thus |A|=\sum_{k=0}^n |A_k|= \sum_{k=0}^n \binom{n}{k}2^{n-k}=\sum_{k=0}^n \binom{n}{k}2^k and the proof is complete.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    To put whatever NonCommAlg said in a different way (a little non-abstract, I would say)

    Consider 'n' different balls and 3 different urns. We can put the balls in these urns in 3^n ways. That makes the RHS of your equation.

    Now consider another way to count the same.

    Let A(k) = Number of ways to put 'k' balls in first two urns and rest in 3rd urn. k ranges from 0 to n.
    A(k) form mutually exclusive and exhaustive events. Hence \sum_{k=0}^n |A(k)| = 3^n.

    What is |A(k)|. It simply is \binom{n}{k}2^k. Select k balls first and then put k balls in 2 urns.
    Hence the result.

    Please Note: My definition ok A(k), though similar in construct, is not equaly to how NonCommAlg defined it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 3rd 2011, 03:22 PM
  2. Combinatorial proof
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 30th 2010, 12:33 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 18th 2010, 04:08 AM
  4. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 12:20 PM
  5. combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 30th 2008, 02:13 PM

Search Tags


/mathhelpforum @mathhelpforum