1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics problem help

  1. Jun 29, 2011 #1

    Mentallic

    User Avatar
    Homework Helper

    1. The problem statement, all variables and given/known data
    I need to show that [tex]{^{2n}}C_n[/tex] is an even number.


    2. Relevant equations
    [tex]{^n}C_k=\frac{n!}{k!(n-k)!}[/tex]


    3. The attempt at a solution
    It was simple to convert the expression into factorials, but from there I really am stuck.

    [tex]\frac{(2n)!}{(n!)^2}=\frac{2n(2n-1)(2n-2)...(n+2)(n+1)}{n(n-1)(n-2)...2\cdot1}[/tex]

    To show that it is even I would need to somehow cancel out the denominator, but I have had no such luck in doing so.
     
  2. jcsd
  3. Jun 29, 2011 #2
    Re: Combinatorics

    You have a 2 at the beginning of the expanded expression of (2n)!/(n!)2; won't that be enough to show that it's even?
     
  4. Jun 29, 2011 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Re: Combinatorics

    Have you tried proof by induction?
     
  5. Jun 29, 2011 #4

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Re: Combinatorics

    Think of Pascal's Triangle.

    ehild
     
  6. Jun 29, 2011 #5

    Mentallic

    User Avatar
    Homework Helper

    Re: Combinatorics

    No, because we need to show that the rest of the expression is an integer, and we haven't done so due to the fraction involved.

    I'll give it a go.

    Yes I was thinking maybe rather than algebraic manipulations, this question just needs a good old logical explanation as to why it must be true.

    I'll get back to editing this when I've tried more things out.
     
  7. Jun 30, 2011 #6
    Re: Combinatorics

    Wow, with those 4 words of advice, I solved this in about a minute! :smile:

    For another hint, Mentallic, remember the properties
    [tex]
    \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
    [/tex]
    and
    [tex]
    \binom{n}{k} = \binom{n}{n-k}.
    [/tex]

    It should fall right out!
     
  8. Jun 30, 2011 #7

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Re: Combinatorics

    But it took me about half an hour to find these four words. :wink:

    ehild
     
  9. Jun 30, 2011 #8

    Mentallic

    User Avatar
    Homework Helper

    Re: Combinatorics

    Oh wow I wish I remembered the first equality. For a question in an exam that doesn't provide us with something like "use the equality ..." but it instead prefers to tell me that tan=sin/cos, I feel like I just got slapped in the face.

    [tex]\binom{2n}{n}=\binom{2n-1}{n}+\binom{2n-1}{n-1}[/tex]

    [tex]\binom{2n-1}{n-1}=\binom{2n-1}{2n-1-(n-1)}=\binom{2n-1}{n}[/tex]

    Therefore

    [tex]\binom{2n}{n}=2\binom{2n-1}{n}[/tex]

    But all valid binomials are integers, thus it is even.

    Some wise words indeed :wink:


    As for the proof by induction, I had some trouble along the way, and I'm unsure of what 'excuse' to use.

    Assume [tex]\binom{2n}{n}=2a, a\in Z[/tex]

    and now prove [tex]\binom{2n+2}{n+1}=2b, b\in Z[/tex]

    [tex]\binom{2n+2}{n+1}=\frac{(2n+2)(2n+1)(2n)!}{(n+1)n!(n+1)n!}[/tex]
    [tex]=\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}[/tex]

    Now all I can say at this point is that [tex]\binom{2n}{n}[/tex] is some integer, so I need to show that [tex]\frac{(2n+2)(2n+1)}{(n+1)^2}[/tex] is even for all integers n.

    [tex]\frac{(2n+2)(2n+1)}{(n+1)^2}=2\left(\frac{2n+1}{n+1}\right)[/tex]

    And from this point I'm unsure, but I was also able to convert it into the form

    [tex]=2\left(2-\frac{1}{n+1}\right)[/tex] and from this expression, it's quite clear that it is going to not be true, so I must have done something wrong.
     
  10. Jun 30, 2011 #9

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Re: Combinatorics

    You know that an element in the Pascal triangle is the sum of the two elements above it. And the triangle is symmetric.
    The 2N line has odd number of elements, and that in question is just in the middle so the two other elements above it are equal.

    ehild
     

    Attached Files:

  11. Jun 30, 2011 #10

    I like Serena

    User Avatar
    Homework Helper

    Re: Combinatorics

    Hi Mentallic! :smile:

    Aren't you forgetting your induction assumption?
    That is:
    [tex]\binom{2n}{n}=2a, a\in Z[/tex]
    which is even?
     
  12. Jun 30, 2011 #11

    Mentallic

    User Avatar
    Homework Helper

    Re: Combinatorics

    That route would seem like such an easy way out, I would need to prove that both numbers above it are equal, no?

    Oh, right :biggrin: It doesn't really change anything though, because I still need to show that the other factor is an integer and it clearly isn't. It's obvious that I went wrong somewhere along the way, yet I can't see where.
     
  13. Jun 30, 2011 #12

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Re: Combinatorics

    Those two elements above are 2n-1Cn-1 and 2n-1Cn, are not they? Are not they the same? (Anyway, the Pascal triangle is symmetric.)

    ehild
     
  14. Jun 30, 2011 #13

    I like Serena

    User Avatar
    Homework Helper

    Re: Combinatorics

    I checked your formula which is correct, so you didn't go wrong along the way.
    However, you're left with proving that (n+1) divides [itex]\binom{2n}{n}[/itex], which is not immediately obvious. You can probably do it with full induction. :tongue2:
     
  15. Jun 30, 2011 #14

    Mentallic

    User Avatar
    Homework Helper

    Re: Combinatorics

    Oh yes of course, and the fact that Pascal's triangle is symmetrical is nailed down once more :smile:
    By they way, are they not? :wink:

    If I were to expand the binomial, where exactly would I be using my inductive hypothesis?
     
  16. Jun 30, 2011 #15

    Gib Z

    User Avatar
    Homework Helper

    Re: Combinatorics

    For every way to choose n objects from 2n, there exists a complementary choice (the other n objects).
     
  17. Jun 30, 2011 #16

    I like Serena

    User Avatar
    Homework Helper

    Re: Combinatorics

    Dunno. I tried it for a little while, but I don't see yet how to do this with full induction. :(
     
  18. Jun 30, 2011 #17

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    Re: Combinatorics

    You simplified it too much. Try writing it like
    [tex]\begin{pmatrix}2n \\ n\end{pmatrix} = \frac{2n!}{n! n!} = \frac{2n (2n-1)!}{n(n-1)! n!}=\cdots[/tex]
     
  19. Jul 7, 2011 #18
    Re: Combinatorics

    wow genius solution!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics problem help
  1. Help on combinatorics (Replies: 3)

  2. Combinatorics Problem (Replies: 3)

  3. Combinatorics problem (Replies: 2)

Loading...