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!

Proofs involving Catalan Numbers

  1. Apr 7, 2008 #1
    1. The problem statement, all variables and given/known data

    I need to prove two things about the Catalan numbers. The first is that Cn is odd iff n=(2^k)-1 for some positive integer k.

    The second is that given the matrix A defined by the rule a(i,j)=C(i+j), prove that det A=1. I have not covered determinants in my linear class yet, so I do not have any idea what to do with this one.

    2. Relevant equations



    3. The attempt at a solution

    I am assuming that both proceed by induction. The first one seems to be more direct, but I am really lost as to how to proceed with both. Any help or suggestions is greatly appreciated. Thanks a lot!
     
  2. jcsd
  3. Apr 7, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I would start by writing down the definition of Catalan numbers!
     
  4. Apr 7, 2008 #3
    Sorry. The Catalan numbers are 1,1,2,5,14,42,... given by the formula Cn=(1/(n+1))*2n choose n. With 2n choose n equal to (2n)!/(n!n!). Sorry for the bad form, I don't have any math writing program.
     
  5. Apr 7, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    That's
    [tex]\frac{1}{n+1}\frac{(2n)!}{n!n!}[/tex]
    Click on that to see the code. You don't need a "math writing program" on your own computer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?