Results 1 to 5 of 5

Math Help - Bijective Proof

  1. #1
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85

    Bijective Proof

    Don't know if this is in the right section but....

    I need to write up a bijective proof of this:

    n+1 \choose{k+1}  = \sum_{m=k}^{n} m \choose{k}

    I don't understand how that equals. I need to write up a little story to explain it like... if you're planning a party for n people but you want to make sure you don't miss anyone, so you add +1 persons to it and you need to order k amount of pizza, but don't want to not have too little pizza so you add +1 pizzas which would be the same as.... the other side of the equation.

    Please help!
    Nicole
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    The bijective thing has kinda thrown me off but here's how it's proved...
    (Although I suppose equality is a bijection so... I dunno)

    Use induction.

    Base case. m=k

    {k \choose{k}} = {{k+1} \choose{k+1}} holds as both equal 1 so we have our inductive case.

    Assume that it is true for n (>k), i.e, assume that.

    \sum_{m=k}^n {m \choose{k}} = {n+1 \choose{k+1}}

    Now prove for the case n+1, i.e. show that...

    \sum_{m=k}^{n+1} {m \choose{k}} = {(n+1)+1 \choose{k+1}} = {n+2 \choose{k+1}}

    Now we have,

    \sum_{m=k}^{n+1} {m \choose{k}} = \sum_{m=k}^n {m \choose{k}} + {{n+1} \choose{k}} = {n+1 \choose{k+1}} + {{n+1} \choose{k}}

    Now just expand using {n \choose k} = \frac{n!}{k!\,(n-k)!} and it should come out to be {n+2 \choose{k+1}}. Hence the relationship holds for all n \geq k.

    (If you get stuck on the last part, look up Pascal's Rule).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member thaopanda's Avatar
    Joined
    Sep 2009
    From
    Worcester, Massachusetts
    Posts
    85
    well, a bijective proof is pretty much a proof that you give through just words. My professor wanted us to do that, only instead of just explaining it, kind of put a story to it...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    Posts
    95
    Here is a hint,

    if you want to do a bijection proof I recommend finding a sets A and X_k,X_{k+1},..,.X_n such that X_i \cap X_j = \emptyset whenever i \neq j and A = \bigcup_{i} X_i with |X_i | = \binom{i}{k} and |A|=\binom{n+1}{k+1}, i.e. use a counting argument, your set A should be the number of ways to do something and your sets X_i should be different disjoint cases you can break the counting process into. Once you have these sets the bijection you want can be taken from your counting argument in a straightforward fashion.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    Posts
    95
    ok let me give you a stronger hint.

    Lets start off by proving the identity

    <br /> <br />
\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}<br /> <br />


    To do this consider how to breakdown counting the left hand side into two disjoint sets that correspond on the right hand side:

    <br /> <br />
\underbrace{ \overbrace{ \Box \Box \ldots \Box \Box } ^k }_n <br /> <br />

    the boxes represent each of the n items and each box can have value 0 or 1 depending on if the item is chosen or not, and we must have that exactly k of the boxes are 1's and n-k are 0's.

    <br /> <br />
\begin{matrix}<br />
\underbrace{ \overbrace{ \Box \Box \ldots \Box \Box } ^k }_n <br />
\end{matrix}<br />
=<br />
\begin{matrix}<br />
1\underbrace{ \overbrace{\Box \Box \ldots \Box \Box } ^{k-1} }_{n-1}  + <br />
0\underbrace{ \overbrace{\Box \Box \ldots \Box \Box } ^{k} }_{n-1}<br />
\end{matrix}<br />

    where I hope you can see why in the first term on the RHS we must choose k-1 1's and the second term we must choose k (this is because the first one is set to 1 in the first and 0 on the second.)

    So this is the counting argument.

    It should be clear and trivial how to construct the bijection from this counting argument, and your prof/teacher shouldn't force you to do it, this argument should suffice. If you really had to construct the bijection, then you would need to define the sets that the map acts on, which would be easiest by defining binary sequences of 0's and 1's of length n, n-1 with k,k-1 one's as appropriate. The map then you construct would come directly from the counting arguement and would be clearly a bijection by the same argument.

    So for your case I hope you can see that this is just a repeated application on this simple counting argument.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 27th 2010, 11:11 PM
  2. Bijective Equivalence relation proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: December 16th 2009, 10:23 AM
  3. bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 12th 2009, 01:09 PM
  4. Bijective function proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 23rd 2009, 04:35 PM
  5. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 2nd 2009, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum