Question

Recurrence relations: Given this formula for Catalan numbers: sigma(n, k=1)( C[sub(k-1)] C[sub(n-k)] ), C[sub(0)] = 1 = C[sub(1)], C[sub(2)] = 2, what is C[sub(3)] thru 5?

For C[sub(2)] I put sigma(2, k=1)( C[sub(k-1)] C[sub(2-k)] ) = sigma(2,k=1)( 1 * 1 ) = C[sub(1)] + 1 = 1 + 1 = 2, check.
Then C[sub(3)] I put sigma(3, k=1)( C[sub(0)] C[sub(3-k)] ) = sigma(3,k=1)( 1 * 2 ) = 1 + 2 + 2 = 5, check.

Then C[sub(4)] doesn't check so I'm not sure if I'm even doing this right. sigma(4,k=1)( 1 * C[sub(3)] ) = sigma(4,k=1)(5) = 1 + 2 + 5 + 5 = 13. It's supposed to be 14. Where did I go wrong?

Answer 1

\[\sum_{k=1}^{n} C_{k-1}C_{n-k}\]
\(C_0=C_1=1\), \(C_2 =2\) what is \(C_3,C_4.C_5\), right?

Answer 2

yes

Answer 3

thanks..

Answer 4

If you can't type latex, show your work by Draw box below. I can't understand what you are doing.

Answer 5

can't draw in an initial post tho can you?

Answer 6

I think you missed the left hand side. it should be
\[C_{n+1}=\sum_{k=1}^{n} C_{k-1}C_{n-k}\]
right?

Answer 7

Nope just \(C_{n}\)

Answer 8

on a n x n grid

Answer 9

ok, let's do \(C_3\)
\[C_3 = \sum_{k=1}^{3} C_{k-1}C_{3-k}=C_0*C_2+C_1*C_1+C_2*C_0 = 1*2+1*1+2*1=5\]
And you are correct, :)

Answer 10

\(C_{2} = \sum\limits_{k=1}^2 C_{k-1} C_{2-k} = \sum\limits_{k=1}^2 C_{0}C_{1} = C_{1} + 1 * 1 = 2\)
checks, so does
\(C_{3} = \sum\limits_{k=1}^3 C_{k-1} C_{3-k} = \sum\limits_{k=1}^3 C_{0}C_{2} = C_{1} + C_{2} + 1 * 2 = 1 + 2 + 2 = 5\)

Right but then 4 does not work that way

Answer 11

Like my LaTeX??

Answer 12

yup, do C_4

Answer 13

\(C_{4} = \sum\limits_{k=1}^4 C_{k-1} C_{4-k} = \sum\limits_{k=1}^4 C_{0}C_{3} = C_{1} + C_{2} + C_{3} + 1 * 5 = 1 + 2 + 5 + 5 = 13\)
see? it's 14 though

Answer 14

:(

Answer 15

I got 14

Answer 16

but how

Answer 17

\[C_4 = \sum_{k=1}^{4} C_{k-1}C_{4-k}\\=C_0*C_3+C_1*C_2+C_2*C_0+C_3C_0\\ = 1*5+1*2+2*1+5*1=14\]

Answer 18

where'd you get all those combos? didn't do that in the previous iterations?

Answer 19

Look at the notation, that is "sum of". It means you replace k =1, n =4 + k =2, n=4 + k =3, n=4 + k =4 , n=4, then calculate

Answer 20

You have 2 terms, right? \(C_{k-1}\) and \(C_{4-k}\), so, just calculate one by one, times them together when k goes from 1 to 4. Then add the combos

Answer 21

ok