• Support PF! Buy your school textbooks, materials and every day products Here!

Proofs involving Catalan Numbers

  • Thread starter saubbie
  • Start date
13
0
1. Homework Statement

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. Homework 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!
 

Answers and Replies

HallsofIvy
Science Advisor
Homework Helper
41,738
898
I would start by writing down the definition of Catalan numbers!
 
13
0
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.
 
HallsofIvy
Science Advisor
Homework Helper
41,738
898
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.
 

Related Threads for: Proofs involving Catalan Numbers

  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
830
Replies
3
Views
2K
Replies
4
Views
1K
Replies
1
Views
756
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
4
Views
1K
Top