Results 1 to 8 of 8

Math Help - Combinatorial Proof

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    Combinatorial Proof

    Provide a combinatorial proof of the following identity:

    \tbinom{n}{2}+\tbinom{n+1}{2}=n^2

    I can provide an algebraic proof of the above identity. It is rather straight forward. But I have no idea how can I provide a "combinatorial" proof for the above identity! Please help!

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    May not be a best answer but here is an attempt

    Consider a set A with 'n' elements, A = {a1,a2.....,an}
    Consider a set B with 'n+1' elements, B = A + {x} = {a1,a2.....,an,x} - Here 'x' will have a special meaning for us.

    Now you RHS = n^2 is simply the number of ways you can arrange 'n' elements from set A in 2 seats. repititions are allowed.

    Now there is another way to count the same.
    Select two elements from set B. i.e. (n+1)C2 ways.
    Here in a selection, if we get element 'x' in the selection we interpret is as a repeat. So, for us {x,a1} gets mapped to {a1,a1}
    But here we have missed a few cases for e.g. we counted {a1,a2} but did not count {a2,a1} [as we are using only selections]. So we need to add that
    Now note the order will not matter when there is a repeatition. So excluding element 'x' there are nC2 selection. Which need to added to get the final answer.

    So we get
    (n+1)C2 + nC2 = n^2

    It is easy to check that any pair like (a,b) is counted same number of times in LHS and RHS.
    if a = b;
    RHS count = 1
    Now this pair can't come in the second selection, so it is counted only once (as {a,x} order doesn' matter)
    similarly you can show if a<>b each is counted twice.

    Hope this helps - maybe someone can show a more elegant way to put it though.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Infact you can give a better argument by breaking the arrangement in two cases
    (1) Repeat
    (2) No repeat

    (1) can be done in nC1 ways.
    (2) = 2. nC2
    so n^2 = nC1 + 2. nC2
    and simplify from here
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Here is another approach.

    Consider the set of ordered pairs (x, y) where x and y are integers with 1 \leq x \leq n and 1 \leq y \leq n. There are n^2 ordered pairs in the set.

    Break the set into two subsets: (1) those with x < y and (2) those with y \geq x.

    Subset (1) contains \binom{n}{2} ordered pairs.

    In subset (2), we have y \geq x, which is equivalent to x-1 < y since x and y are integers. So we have 0 \leq x-1 < y \leq n, and there are \binom{n+1}{2} possible ordered pairs.

    So...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    A question:

    What is binomial expression that should be instead of ****

    when ****=n^k

    You understand me?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1
    Quote Originally Posted by Also sprach Zarathustra View Post
    A question:
    What is binomial expression that should be instead of ****
    when ****=n^k
    You understand me?
    I cannot say that I do understand your question.
    But this is true:
    n^k  = \sum\limits_{j = 0}^k {\binom{k}{j} \left( {n - 1} \right)^j } .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Also sprach Zarathustra View Post
    A question:

    What is binomial expression that should be instead of ****

    when ****=n^k

    You understand me?
    In addition to Plato's answer, another possible expression is

    \sum_{i=0}^k i! \; S(k,i) \binom{n}{i} = n^k

    where S(k,i) is a Sterling number of the second kind.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by lpd View Post
    Provide a combinatorial proof of the following identity:

    \tbinom{n}{2}+\tbinom{n+1}{2}=n^2

    I can provide an algebraic proof of the above identity. It is rather straight forward. But I have no idea how can I provide a "combinatorial" proof for the above identity! Please help!

    Thanks!
    \binom{n}{2} is the number of selections of 2 from n.

    \binom{n+1}{2} is the number of selections of 2 from n+1.

    Before we bring in that extra term, there are \binom{n}{2} selections.

    When we bring in that extra term, there are an additional "n" selections of 2,
    since that extra term can be paired with any of the original n,
    along with all the original pairs.

    Hence \binom{n+1}{2}=\binom{n}{2}+n

    Therefore, the question is, is 2\binom{n}{2}+n=n^2\ ?

    n^2=n(n)=n(n-1+1)=n(n-1)+n

    2\binom{n}{2}=n(n-1)\ ?

    For pairs of 2, the number of arrangements is twice the number of selections etc..
    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 Discrete Math Forum
    Replies: 6
    Last Post: July 4th 2010, 08:02 PM
  3. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 12:20 PM
  4. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 05:43 PM
  5. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 17th 2008, 04:40 PM

Search Tags


/mathhelpforum @mathhelpforum