Dtjytyk

Was it really inappropriate to write a pull request for the company I interviewed with?

Custom javascript not working

What is the purpose of a disclaimer like "this is not legal advice"?

Align equations with text before one of them

How spaceships determine each other's mass in space?

Quitting employee has privileged access to critical information

ESPP--any reason not to go all in?

What is "desert glass" and what does it do to the PCs?

Should I use HTTPS on a domain that will only be used for redirection?

Paper published similar to PhD thesis

Replacing tantalum capacitor with ceramic capacitor for Op Amps

What does "rhumatis" mean?

Is divide-by-zero a security vulnerability?

Iron deposits mined from under the city

Sundering Titan and basic normal lands and snow lands

How to make sure I'm assertive enough in contact with subordinates?

What is a term for a function that when called repeatedly, has the same effect as calling once?

Why is there an extra space when I type "ls" on the Desktop?

When to use the term transposed instead of modulation?

What's the best tool for cutting holes into duct work?

Can a space-faring robot still function over a billion years?

Are Wave equations equivalent to Maxwell equations in free space?

Is "cogitate" an appropriate word for this?

New invention compresses matter to produce energy? or other items? (Short Story)

Generating Function For Catalan Numbers Type Sequence

How do you find generating function?Generating function of shifted Catalan NumbersGenerating function satisfying a second degree equationGenerating Function for 2-Associated Stirling Numbers of the Second KindFinding the generating function for the Catalan number sequenceCatalan numbers generating functionCatalan numbers formula derivationExpress C(x) through A(x) and B(x), where C(x), A(x), B(x), are generating functions of sequences $c_{n}$, $a_{n}$, $b_{n}$ respectivelyFind a generating function and a closed form for the sequence $c_{n+1} = sum_{i=0}^{n}c_i$Generating function for the Catalan numbersSequence $rightarrow$ Generating function simple practice problems

2

$begingroup$

I've been working my way through an old post, but I don't think the solution offered can be correct.

The question is;

Find the generating function (within a choice of sign) for:
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\c_0=1, ;c_1=3$$

I think this recurrence relation generates the numbers
$$1, 3, 12, 66, 408, 2712, ...$$

The solution offered is;

Let $$g(x)=sum_{nge 0}c_nx^n$$ be the ordinary generating function for the sequence. Then the standard formula for the Cauchy product of two summations yields

$$big(g(x)big)^2=left(sum_{nge 0}c_nx^nright)^2=sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=frac12sum_{nge 0}c_{n+1}x^n;,$$

and multiplication by $2x$ gives us

$$2xbig(g(x)big)^2=xsum_{nge 0}c_{n+1}x^n=sum_{nge 1}c_nx^n=g(x)-c_0;.$$

This is a quadratic in $g(x)$, so it can straightforwardly be solved for $g(x)$.

From this I've deduced that
$$g(x)=frac{1-sqrt(1-8x)}{4x}$$

I've gone through this proof carefully and can't see an error but I know from Wolfram Alpha that it does not generate the numbers I was expecting. It also makes no use of the fact that $c_1 = 3$ which can't be right.
I think the correct generating function is;
$$GF=frac{1-sqrt(1-8x-8x^2)}{4x}$$
but can't see how to obtain this.
It generates the numbers I was expecting and is in Sloan : https://oeis.org/search?q=1%2C3%2C12%2C66%2C408&language=english&go=Search

FYI : The original post, from 2013, is here : How do you find generating function?

For anyone interested in The Catalan Numbers, this would be a good 'one step on' question so if anyone can spot where the glitch is, I think it would be most useful.

sequences-and-series elementary-number-theory generating-functions catalan-numbers cauchy-product

share|cite|improve this question

asked 17 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

add a comment | 

2

$begingroup$

I've been working my way through an old post, but I don't think the solution offered can be correct.

The question is;

Find the generating function (within a choice of sign) for:
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\c_0=1, ;c_1=3$$

I think this recurrence relation generates the numbers
$$1, 3, 12, 66, 408, 2712, ...$$

The solution offered is;

Let $$g(x)=sum_{nge 0}c_nx^n$$ be the ordinary generating function for the sequence. Then the standard formula for the Cauchy product of two summations yields

$$big(g(x)big)^2=left(sum_{nge 0}c_nx^nright)^2=sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=frac12sum_{nge 0}c_{n+1}x^n;,$$

and multiplication by $2x$ gives us

$$2xbig(g(x)big)^2=xsum_{nge 0}c_{n+1}x^n=sum_{nge 1}c_nx^n=g(x)-c_0;.$$

This is a quadratic in $g(x)$, so it can straightforwardly be solved for $g(x)$.

From this I've deduced that
$$g(x)=frac{1-sqrt(1-8x)}{4x}$$

I've gone through this proof carefully and can't see an error but I know from Wolfram Alpha that it does not generate the numbers I was expecting. It also makes no use of the fact that $c_1 = 3$ which can't be right.
I think the correct generating function is;
$$GF=frac{1-sqrt(1-8x-8x^2)}{4x}$$
but can't see how to obtain this.
It generates the numbers I was expecting and is in Sloan : https://oeis.org/search?q=1%2C3%2C12%2C66%2C408&language=english&go=Search

FYI : The original post, from 2013, is here : How do you find generating function?

For anyone interested in The Catalan Numbers, this would be a good 'one step on' question so if anyone can spot where the glitch is, I think it would be most useful.

sequences-and-series elementary-number-theory generating-functions catalan-numbers cauchy-product

share|cite|improve this question

asked 17 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

add a comment | 

$begingroup$

I've been working my way through an old post, but I don't think the solution offered can be correct.

The question is;

Find the generating function (within a choice of sign) for:
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\c_0=1, ;c_1=3$$

I think this recurrence relation generates the numbers
$$1, 3, 12, 66, 408, 2712, ...$$

The solution offered is;

Let $$g(x)=sum_{nge 0}c_nx^n$$ be the ordinary generating function for the sequence. Then the standard formula for the Cauchy product of two summations yields

$$big(g(x)big)^2=left(sum_{nge 0}c_nx^nright)^2=sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=frac12sum_{nge 0}c_{n+1}x^n;,$$

and multiplication by $2x$ gives us

$$2xbig(g(x)big)^2=xsum_{nge 0}c_{n+1}x^n=sum_{nge 1}c_nx^n=g(x)-c_0;.$$

This is a quadratic in $g(x)$, so it can straightforwardly be solved for $g(x)$.

From this I've deduced that
$$g(x)=frac{1-sqrt(1-8x)}{4x}$$

I've gone through this proof carefully and can't see an error but I know from Wolfram Alpha that it does not generate the numbers I was expecting. It also makes no use of the fact that $c_1 = 3$ which can't be right.
I think the correct generating function is;
$$GF=frac{1-sqrt(1-8x-8x^2)}{4x}$$
but can't see how to obtain this.
It generates the numbers I was expecting and is in Sloan : https://oeis.org/search?q=1%2C3%2C12%2C66%2C408&language=english&go=Search

FYI : The original post, from 2013, is here : How do you find generating function?

For anyone interested in The Catalan Numbers, this would be a good 'one step on' question so if anyone can spot where the glitch is, I think it would be most useful.

sequences-and-series elementary-number-theory generating-functions catalan-numbers cauchy-product

share|cite|improve this question

asked 17 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

share|cite|improve this question

asked 17 hours ago

Martin HansenMartin Hansen

12711

share|cite|improve this question

asked 17 hours ago

Martin HansenMartin Hansen

12711

asked 17 hours ago

Martin HansenMartin Hansen

12711

asked 17 hours ago

Martin HansenMartin Hansen

12711

2 Answers
2

active

oldest

votes

2

$begingroup$

The trouble seems to be in this step:
$$
sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=
frac12sum_{nge 0}c_{n+1}x^n.tag{*}
$$
It is true that
$$
sum_{k=0}^nc_kc_{n-k}=frac12 c_{n+1},
$$
but only for $nge1$. The constant term in (*) is $c_0^2 = 1$, which is not $frac12 c_1 = frac32$.

Taking this into account, one instead finds
$$
g(x)^2 = frac12sum_{nge 0}c_{n+1}x^n - frac12,
$$
and the resulting quadratic is
$$
2x(g(x))^2 = g(x) - x - 1.
$$
One of the solutions of this quadratic is exactly the result you expected.

By the way, to find the error I found it helpful to write out the low-order terms of $g(x)$ and $g(x)^2$. Those terms are where the complications are typically found in generating function problems.

share|cite|improve this answer

answered 17 hours ago

FredHFredH

1,073612

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for a quick response; I'm going to look at it very carefully after work finishes later, (following your advice), but it's the sort of small but very annoying error that I knew had to be in there somewhere.
  $endgroup$
  – Martin Hansen
  17 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've gone over this and am thoroughly satisfied with the argument now. I've added a note to the old post to point it here, and have also added a small further clarification here of exactly why the original six year old post derived a wrong answer.
  $endgroup$
  – Martin Hansen
  9 hours ago
  
  
  

  
  
  
  

add a comment | 

0

$begingroup$

Thanks so much for your answer FredH. I agree with what you say.

Thinking about it some more, and to clarify for anyone looking at this later on, the key step was moving from
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\$$
to
$$sum_{k=0}^{n}c_k c_{n-k}=frac{c_n+1}{2};;;n=1,2,3,4,dots\$$
This needed this to be valid for $n=0,1,2,3,4,...$ in order to make the substitution to carry the main thread of the argument onward.
So, clearly great care must be taken over such extensions to include $n=0$.

share|cite|improve this answer

answered 9 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

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
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3138866%2fgenerating-function-for-catalan-numbers-type-sequence%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

The trouble seems to be in this step:
$$
sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=
frac12sum_{nge 0}c_{n+1}x^n.tag{*}
$$
It is true that
$$
sum_{k=0}^nc_kc_{n-k}=frac12 c_{n+1},
$$
but only for $nge1$. The constant term in (*) is $c_0^2 = 1$, which is not $frac12 c_1 = frac32$.

Taking this into account, one instead finds
$$
g(x)^2 = frac12sum_{nge 0}c_{n+1}x^n - frac12,
$$
and the resulting quadratic is
$$
2x(g(x))^2 = g(x) - x - 1.
$$
One of the solutions of this quadratic is exactly the result you expected.

By the way, to find the error I found it helpful to write out the low-order terms of $g(x)$ and $g(x)^2$. Those terms are where the complications are typically found in generating function problems.

share|cite|improve this answer

answered 17 hours ago

FredHFredH

1,073612

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for a quick response; I'm going to look at it very carefully after work finishes later, (following your advice), but it's the sort of small but very annoying error that I knew had to be in there somewhere.
  $endgroup$
  – Martin Hansen
  17 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've gone over this and am thoroughly satisfied with the argument now. I've added a note to the old post to point it here, and have also added a small further clarification here of exactly why the original six year old post derived a wrong answer.
  $endgroup$
  – Martin Hansen
  9 hours ago
  
  
  

  
  
  
  

add a comment | 

2

$begingroup$

The trouble seems to be in this step:
$$
sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=
frac12sum_{nge 0}c_{n+1}x^n.tag{*}
$$
It is true that
$$
sum_{k=0}^nc_kc_{n-k}=frac12 c_{n+1},
$$
but only for $nge1$. The constant term in (*) is $c_0^2 = 1$, which is not $frac12 c_1 = frac32$.

Taking this into account, one instead finds
$$
g(x)^2 = frac12sum_{nge 0}c_{n+1}x^n - frac12,
$$
and the resulting quadratic is
$$
2x(g(x))^2 = g(x) - x - 1.
$$
One of the solutions of this quadratic is exactly the result you expected.

By the way, to find the error I found it helpful to write out the low-order terms of $g(x)$ and $g(x)^2$. Those terms are where the complications are typically found in generating function problems.

share|cite|improve this answer

answered 17 hours ago

FredHFredH

1,073612

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks for a quick response; I'm going to look at it very carefully after work finishes later, (following your advice), but it's the sort of small but very annoying error that I knew had to be in there somewhere.
  $endgroup$
  – Martin Hansen
  17 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've gone over this and am thoroughly satisfied with the argument now. I've added a note to the old post to point it here, and have also added a small further clarification here of exactly why the original six year old post derived a wrong answer.
  $endgroup$
  – Martin Hansen
  9 hours ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

The trouble seems to be in this step:
$$
sum_{nge 0}left(sum_{k=0}^nc_kc_{n-k}right)x^n=
frac12sum_{nge 0}c_{n+1}x^n.tag{*}
$$
It is true that
$$
sum_{k=0}^nc_kc_{n-k}=frac12 c_{n+1},
$$
but only for $nge1$. The constant term in (*) is $c_0^2 = 1$, which is not $frac12 c_1 = frac32$.

Taking this into account, one instead finds
$$
g(x)^2 = frac12sum_{nge 0}c_{n+1}x^n - frac12,
$$
and the resulting quadratic is
$$
2x(g(x))^2 = g(x) - x - 1.
$$
One of the solutions of this quadratic is exactly the result you expected.

By the way, to find the error I found it helpful to write out the low-order terms of $g(x)$ and $g(x)^2$. Those terms are where the complications are typically found in generating function problems.

share|cite|improve this answer

answered 17 hours ago

FredHFredH

1,073612

$endgroup$

share|cite|improve this answer

answered 17 hours ago

FredHFredH

1,073612

answered 17 hours ago

FredHFredH

1,073612

answered 17 hours ago

FredHFredH

1,073612

0

$begingroup$

Thanks so much for your answer FredH. I agree with what you say.

Thinking about it some more, and to clarify for anyone looking at this later on, the key step was moving from
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\$$
to
$$sum_{k=0}^{n}c_k c_{n-k}=frac{c_n+1}{2};;;n=1,2,3,4,dots\$$
This needed this to be valid for $n=0,1,2,3,4,...$ in order to make the substitution to carry the main thread of the argument onward.
So, clearly great care must be taken over such extensions to include $n=0$.

share|cite|improve this answer

answered 9 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

add a comment | 

0

$begingroup$

Thanks so much for your answer FredH. I agree with what you say.

Thinking about it some more, and to clarify for anyone looking at this later on, the key step was moving from
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\$$
to
$$sum_{k=0}^{n}c_k c_{n-k}=frac{c_n+1}{2};;;n=1,2,3,4,dots\$$
This needed this to be valid for $n=0,1,2,3,4,...$ in order to make the substitution to carry the main thread of the argument onward.
So, clearly great care must be taken over such extensions to include $n=0$.

share|cite|improve this answer

answered 9 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

add a comment | 

$begingroup$

Thanks so much for your answer FredH. I agree with what you say.

Thinking about it some more, and to clarify for anyone looking at this later on, the key step was moving from
$$c_{n+1} = 2sum_{k=0}^{n}c_k c_{n-k},;;;n=1,2,3,4,dots\$$
to
$$sum_{k=0}^{n}c_k c_{n-k}=frac{c_n+1}{2};;;n=1,2,3,4,dots\$$
This needed this to be valid for $n=0,1,2,3,4,...$ in order to make the substitution to carry the main thread of the argument onward.
So, clearly great care must be taken over such extensions to include $n=0$.

share|cite|improve this answer

answered 9 hours ago

Martin HansenMartin Hansen

12711

$endgroup$

share|cite|improve this answer

answered 9 hours ago

Martin HansenMartin Hansen

12711

answered 9 hours ago

Martin HansenMartin Hansen

12711

answered 9 hours ago

Martin HansenMartin Hansen

12711