Mixing
Combinatorics - Catalan numbers recursive function proof by induction help
$begingroup$
I'm trying to prove that $$C_n = sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number).
For $n=1$ this is true.
Assume it is true for $n=k$:
$$C_k = sum_{i=0}^{k-1} C_iC_{k-i-1}$$
Now we just need to show that $$C_{k+1} = sum_{i=0}^{k} C_iC_{k-i}$$
And here I'm stuck. I can't understand how to use our assumption.
Friendly reminder: $C_r = frac{1}{r+1} {2r choose r}$ for all $ 0leq r$
combinatorics recurrence-relations induction catalan-numbers
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
$endgroup$
add a comment |
$begingroup$
I'm trying to prove that $$C_n = sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number).
For $n=1$ this is true.
Assume it is true for $n=k$:
$$C_k = sum_{i=0}^{k-1} C_iC_{k-i-1}$$
Now we just need to show that $$C_{k+1} = sum_{i=0}^{k} C_iC_{k-i}$$
And here I'm stuck. I can't understand how to use our assumption.
Friendly reminder: $C_r = frac{1}{r+1} {2r choose r}$ for all $ 0leq r$
combinatorics recurrence-relations induction catalan-numbers
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
$endgroup$
2
$begingroup$
What is your definition of Catalan's numbers?
$endgroup$
– Pedro Tamaroff♦
Mar 3 '15 at 21:50
1
$begingroup$
Check out en.wikipedia.org/wiki/Catalan_number#Fifth_proof.
$endgroup$
– Doris
Jan 27 at 20:03
$begingroup$
@PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number.
$endgroup$
– Felix Marin
Jan 30 at 6:18
add a comment |
$begingroup$
I'm trying to prove that $$C_n = sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number).
For $n=1$ this is true.
Assume it is true for $n=k$:
$$C_k = sum_{i=0}^{k-1} C_iC_{k-i-1}$$
Now we just need to show that $$C_{k+1} = sum_{i=0}^{k} C_iC_{k-i}$$
And here I'm stuck. I can't understand how to use our assumption.
Friendly reminder: $C_r = frac{1}{r+1} {2r choose r}$ for all $ 0leq r$
combinatorics recurrence-relations induction catalan-numbers
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
$endgroup$
I'm trying to prove that $$C_n = sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number).
For $n=1$ this is true.
Assume it is true for $n=k$:
$$C_k = sum_{i=0}^{k-1} C_iC_{k-i-1}$$
Now we just need to show that $$C_{k+1} = sum_{i=0}^{k} C_iC_{k-i}$$
And here I'm stuck. I can't understand how to use our assumption.
Friendly reminder: $C_r = frac{1}{r+1} {2r choose r}$ for all $ 0leq r$
combinatorics recurrence-relations induction catalan-numbers
combinatorics recurrence-relations induction catalan-numbers
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
asked Nov 19 '13 at 22:04
Oria GruberOria Gruber
6,53732462
6,53732462
2
$begingroup$
What is your definition of Catalan's numbers?
$endgroup$
– Pedro Tamaroff♦
Mar 3 '15 at 21:50
1
$begingroup$
Check out en.wikipedia.org/wiki/Catalan_number#Fifth_proof.
$endgroup$
– Doris
Jan 27 at 20:03
$begingroup$
@PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number.
$endgroup$
– Felix Marin
Jan 30 at 6:18
add a comment |
2
$begingroup$
What is your definition of Catalan's numbers?
$endgroup$
– Pedro Tamaroff♦
Mar 3 '15 at 21:50
1
$begingroup$
Check out en.wikipedia.org/wiki/Catalan_number#Fifth_proof.
$endgroup$
– Doris
Jan 27 at 20:03
$begingroup$
@PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number.
$endgroup$
– Felix Marin
Jan 30 at 6:18
2
2
$begingroup$
What is your definition of Catalan's numbers?
$endgroup$
– Pedro Tamaroff♦
Mar 3 '15 at 21:50
$begingroup$
What is your definition of Catalan's numbers?
$endgroup$
– Pedro Tamaroff♦
Mar 3 '15 at 21:50
1
1
$begingroup$
Check out en.wikipedia.org/wiki/Catalan_number#Fifth_proof.
$endgroup$
– Doris
Jan 27 at 20:03
$begingroup$
Check out en.wikipedia.org/wiki/Catalan_number#Fifth_proof.
$endgroup$
– Doris
Jan 27 at 20:03
$begingroup$
@PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number.
$endgroup$
– Felix Marin
Jan 30 at 6:18
$begingroup$
@PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number.
$endgroup$
– Felix Marin
Jan 30 at 6:18
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are many different definitions of the Catalan numbers that make different properties clearer. One is as the number of ways to parenthesize the product $x_1 x_2 dots x_{n+1}$, which makes the relation you want to prove obvious. From that you can show that the generating function $sum C_n x^n$ is the solution of a quadratic equation in $x$ and has a formula involving the square root of some function like $frac{1}{1-x}$ (probably not exactly that, but similar). Then the binomial theorem for exponent $1/2$ tells you a formula for the generating function coefficients and shows this definition is equivalent to the numerical one.
To start from the definition at the end of the question, the formula for the numbers, and prove the recursion looks like a potentially complicated combinatorial problem. I don't think this is the way it would normally be done except for the sake of sport or its evil twin, student exercises.
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
$endgroup$
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
2
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f573810%2fcombinatorics-catalan-numbers-recursive-function-proof-by-induction-help%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are many different definitions of the Catalan numbers that make different properties clearer. One is as the number of ways to parenthesize the product $x_1 x_2 dots x_{n+1}$, which makes the relation you want to prove obvious. From that you can show that the generating function $sum C_n x^n$ is the solution of a quadratic equation in $x$ and has a formula involving the square root of some function like $frac{1}{1-x}$ (probably not exactly that, but similar). Then the binomial theorem for exponent $1/2$ tells you a formula for the generating function coefficients and shows this definition is equivalent to the numerical one.
To start from the definition at the end of the question, the formula for the numbers, and prove the recursion looks like a potentially complicated combinatorial problem. I don't think this is the way it would normally be done except for the sake of sport or its evil twin, student exercises.
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
$endgroup$
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
2
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
add a comment |
$begingroup$
There are many different definitions of the Catalan numbers that make different properties clearer. One is as the number of ways to parenthesize the product $x_1 x_2 dots x_{n+1}$, which makes the relation you want to prove obvious. From that you can show that the generating function $sum C_n x^n$ is the solution of a quadratic equation in $x$ and has a formula involving the square root of some function like $frac{1}{1-x}$ (probably not exactly that, but similar). Then the binomial theorem for exponent $1/2$ tells you a formula for the generating function coefficients and shows this definition is equivalent to the numerical one.
To start from the definition at the end of the question, the formula for the numbers, and prove the recursion looks like a potentially complicated combinatorial problem. I don't think this is the way it would normally be done except for the sake of sport or its evil twin, student exercises.
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
$endgroup$
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
2
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
add a comment |
$begingroup$
There are many different definitions of the Catalan numbers that make different properties clearer. One is as the number of ways to parenthesize the product $x_1 x_2 dots x_{n+1}$, which makes the relation you want to prove obvious. From that you can show that the generating function $sum C_n x^n$ is the solution of a quadratic equation in $x$ and has a formula involving the square root of some function like $frac{1}{1-x}$ (probably not exactly that, but similar). Then the binomial theorem for exponent $1/2$ tells you a formula for the generating function coefficients and shows this definition is equivalent to the numerical one.
To start from the definition at the end of the question, the formula for the numbers, and prove the recursion looks like a potentially complicated combinatorial problem. I don't think this is the way it would normally be done except for the sake of sport or its evil twin, student exercises.
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
$endgroup$
There are many different definitions of the Catalan numbers that make different properties clearer. One is as the number of ways to parenthesize the product $x_1 x_2 dots x_{n+1}$, which makes the relation you want to prove obvious. From that you can show that the generating function $sum C_n x^n$ is the solution of a quadratic equation in $x$ and has a formula involving the square root of some function like $frac{1}{1-x}$ (probably not exactly that, but similar). Then the binomial theorem for exponent $1/2$ tells you a formula for the generating function coefficients and shows this definition is equivalent to the numerical one.
To start from the definition at the end of the question, the formula for the numbers, and prove the recursion looks like a potentially complicated combinatorial problem. I don't think this is the way it would normally be done except for the sake of sport or its evil twin, student exercises.
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
edited Nov 19 '13 at 22:45
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
answered Nov 19 '13 at 22:23
zyxzyx
31.6k33699
31.6k33699
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
2
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
add a comment |
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
2
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
$begingroup$
Haha spot on. I am trying to prove this for student exercise. And yeah it must be done via induction.
$endgroup$
– Oria Gruber
Nov 19 '13 at 22:25
2
2
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
$begingroup$
I see it is supposed to use an induction. Given that the formula is correct, there has to be a way of giving an induction proof, and it probably is not difficult (after doing it) but not as enlightening as just learning some of the other meanings of the Catalan numbers. Books and Wikipedia should list the standard ones: parentheses, binary trees, I forget the rest.
$endgroup$
– zyx
Nov 19 '13 at 22:28
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f573810%2fcombinatorics-catalan-numbers-recursive-function-proof-by-induction-help%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
What is your definition of Catalan's numbers?
$endgroup$
– Pedro Tamaroff♦
Mar 3 '15 at 21:50
1
$begingroup$
Check out en.wikipedia.org/wiki/Catalan_number#Fifth_proof.
$endgroup$
– Doris
Jan 27 at 20:03
$begingroup$
@PedroTamaroff I guess there is just one definition. Isn't it ?. Catalan Number.
$endgroup$
– Felix Marin
Jan 30 at 6:18