Results 1 to 4 of 4

Thread: 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
    12,028
    Thanks
    849
    Hello, taylor1234!

    $\displaystyle \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: .$\displaystyle (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 $\displaystyle A$ of all functions $\displaystyle f: \{1,2, \cdots , n \} \longrightarrow \{a,b,c\}.$ clearly $\displaystyle |A|=3^n.$ now we'll find $\displaystyle |A|$ in a different way: for any $\displaystyle 0 \leq k \leq n$ let $\displaystyle A_k$ be the set of all $\displaystyle f \in A$ such that

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

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

    and $\displaystyle A = \bigcup_{k=0}^n A_k.$ thus $\displaystyle |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
    678
    Thanks
    1
    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 $\displaystyle \sum_{k=0}^n |A(k)|$ = 3^n.

    What is |A(k)|. It simply is $\displaystyle \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: Apr 3rd 2011, 03:22 PM
  2. Combinatorial proof
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Sep 30th 2010, 12:33 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Aug 18th 2010, 04:08 AM
  4. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 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