1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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


    User Avatar
    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


    User Avatar
    Science Advisor

    Click on that to see the code. You don't need a "math writing program" on your own computer.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook