Finding a closed form for coefficients in $x^3n=x_0left(a_nx+b_n+frac c_nxright)$ The 2019 Stack Overflow Developer Survey Results Are InFinding the closed form for a sequenceFinding the closed form solution of a third order recurrence relation with constant coefficientsClosed form for integral $int_0^pi left[1 - r cosleft(phiright)right]^-n phi ,rm dphi$Closed form for $int_-1^1fraclnleft(2+x,sqrt3right)sqrt1-x^2,left(2+x,sqrt3right)^ndx$Prove that positive $x,y$ satisfy $left(frac11+xright)^2+left(frac11+yright)^2gefrac11+xy$.Iterated means $a_n+1=sqrta_n fracb_n+c_n2$, $b_n+1$ and $c_n+1$ similar, closed form for general initial conditions?Closed form for the limit of the iterated sequence $a_n+1=fracsqrt(a_n+b_n)(a_n+c_n)2$A known closed form for Borchardt mean (generalization of AGM) - why doesn't it work?Closed form of $x_n+1 =frac12left(x_n-frac1x_nright)$ with $x_0 neq 0,1$Find the closed form of $u_n+1=a_nu_n+b_n$
Why couldn't they take pictures of a closer black hole?
Why didn't the Event Horizon Telescope team mention Sagittarius A*?
What is the meaning of Triage in Cybersec world?
Ubuntu Server install with full GUI
How do I free up internal storage if I don't have any apps downloaded?
Mathematics of imaging the black hole
What is the motivation for a law requiring 2 parties to consent for recording a conversation
Did Scotland spend $250,000 for the slogan "Welcome to Scotland"?
writing variables above the numbers in tikz picture
How to translate "being like"?
How to obtain a position of last non-zero element
Geography at the pixel level
"as much details as you can remember"
How to charge AirPods to keep battery healthy?
What does Linus Torvalds mean when he says that Git "never ever" tracks a file?
What is this business jet?
How to notate time signature switching consistently every measure
Is it correct to say the Neural Networks are an alternative way of performing Maximum Likelihood Estimation? if not, why?
Get name of standard action overriden in Visualforce contorller
How do you keep chess fun when your opponent constantly defeats?
Is it ethical to upload a automatically generated paper to a non peer-reviewed site as part of a larger research?
If a sorcerer casts the Banishment spell on a PC while in Avernus, does the PC return to their home plane?
Worn-tile Scrabble
How to type a long/em dash `—`
Finding a closed form for coefficients in $x^3n=x_0left(a_nx+b_n+frac c_nxright)$
The 2019 Stack Overflow Developer Survey Results Are InFinding the closed form for a sequenceFinding the closed form solution of a third order recurrence relation with constant coefficientsClosed form for integral $int_0^pi left[1 - r cosleft(phiright)right]^-n phi ,rm dphi$Closed form for $int_-1^1fraclnleft(2+x,sqrt3right)sqrt1-x^2,left(2+x,sqrt3right)^ndx$Prove that positive $x,y$ satisfy $left(frac11+xright)^2+left(frac11+yright)^2gefrac11+xy$.Iterated means $a_n+1=sqrta_n fracb_n+c_n2$, $b_n+1$ and $c_n+1$ similar, closed form for general initial conditions?Closed form for the limit of the iterated sequence $a_n+1=fracsqrt(a_n+b_n)(a_n+c_n)2$A known closed form for Borchardt mean (generalization of AGM) - why doesn't it work?Closed form of $x_n+1 =frac12left(x_n-frac1x_nright)$ with $x_0 neq 0,1$Find the closed form of $u_n+1=a_nu_n+b_n$
$begingroup$
Consider,
$$
x^3=x+1
$$
Let $x_0$ be a solution to the above equation. Now consider $x^3n$. For $n=2$ we have:
$$
x^6=(x+1)^2
$$
$$
=x^2+2x+1
$$
$$
=xleft(x+2+frac 1xright)
$$
$$
=x_0left(x+2+frac 1xright)
$$
For $n=3$ we have:
$$
x^9=(x+1)^3
$$
$$
=x^3+3x^2+3x+1
$$
$$
=3x^2+4x+2
$$
$$
=xleft(3x+4+frac 2xright)
$$
$$
=x_0left(3x+4+frac 2xright)
$$
Similarly for $n=4$ we have:
$$
x^12=x_0left(7x+9+frac 5xright)
$$
In general we have:
$$
x^3n=x_0left(a_nx+b_n+frac c_nxright),
$$
Where,
$$
a_n+1=a_n+b_n, a_2=1,
$$
$$
b_n+1=a_n+b_n+c_n, b_2=2,
$$
$$
c_n+1=a_n+c_n, c_2=1.
$$
My question is: is there a closed form for $a_n,b_n$ and $c_n$?
Any help would be appreciated.
algebra-precalculus closed-form recursion
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
$endgroup$
add a comment |
$begingroup$
Consider,
$$
x^3=x+1
$$
Let $x_0$ be a solution to the above equation. Now consider $x^3n$. For $n=2$ we have:
$$
x^6=(x+1)^2
$$
$$
=x^2+2x+1
$$
$$
=xleft(x+2+frac 1xright)
$$
$$
=x_0left(x+2+frac 1xright)
$$
For $n=3$ we have:
$$
x^9=(x+1)^3
$$
$$
=x^3+3x^2+3x+1
$$
$$
=3x^2+4x+2
$$
$$
=xleft(3x+4+frac 2xright)
$$
$$
=x_0left(3x+4+frac 2xright)
$$
Similarly for $n=4$ we have:
$$
x^12=x_0left(7x+9+frac 5xright)
$$
In general we have:
$$
x^3n=x_0left(a_nx+b_n+frac c_nxright),
$$
Where,
$$
a_n+1=a_n+b_n, a_2=1,
$$
$$
b_n+1=a_n+b_n+c_n, b_2=2,
$$
$$
c_n+1=a_n+c_n, c_2=1.
$$
My question is: is there a closed form for $a_n,b_n$ and $c_n$?
Any help would be appreciated.
algebra-precalculus closed-form recursion
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
$endgroup$
$begingroup$
The only way I know to approach this is the method of solving simultaneous recurrence relations covered in my combinatorics textbook. (For those curious: Applied Combinatorics, Sixth Edition by Alan Tucker: it's in section 7.5, example 5, on page 313.) The issue being, this is a very nontrivial calculation, and concerns the use of generating functions throughout. [cont.]
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
I tried solving it just to get the generating function for your $a_n$ terms and that in itself took several pages of scratch work (haven't even tried the other two yet) - which I'm not confident in because it's messy and there's a lot of painful algebra involved in this one, so there's plenty of room for error. Plus it all feels like it might fruitless if you're not familiar with such topics. I'm not going to say it's the only method, but it's the only one that I know of off-hand.
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
2
$begingroup$
What I would try is computing $a_n$, $b_n$, and $c_n$ by computer program up to, say, n=12 and plug each sequence independently into the OEIS.
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:12
1
$begingroup$
a is oeis.org/A095263, b is oeis.org/A052921 and c is oeis.org/A181984
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:24
$begingroup$
The PARI program is ? a=[0,0,0,0,0,0,0,0,0,0,0,0]; b=a; c=a; ? a[1]=1; b[1]=2; c[1]=1; ? for (n=1, 11, a[n+1]=a[n]+b[n]; b[n+1]=a[n]+b[n]+c[n]; c[n+1]=a[n]+c[n]);
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:29
add a comment |
$begingroup$
Consider,
$$
x^3=x+1
$$
Let $x_0$ be a solution to the above equation. Now consider $x^3n$. For $n=2$ we have:
$$
x^6=(x+1)^2
$$
$$
=x^2+2x+1
$$
$$
=xleft(x+2+frac 1xright)
$$
$$
=x_0left(x+2+frac 1xright)
$$
For $n=3$ we have:
$$
x^9=(x+1)^3
$$
$$
=x^3+3x^2+3x+1
$$
$$
=3x^2+4x+2
$$
$$
=xleft(3x+4+frac 2xright)
$$
$$
=x_0left(3x+4+frac 2xright)
$$
Similarly for $n=4$ we have:
$$
x^12=x_0left(7x+9+frac 5xright)
$$
In general we have:
$$
x^3n=x_0left(a_nx+b_n+frac c_nxright),
$$
Where,
$$
a_n+1=a_n+b_n, a_2=1,
$$
$$
b_n+1=a_n+b_n+c_n, b_2=2,
$$
$$
c_n+1=a_n+c_n, c_2=1.
$$
My question is: is there a closed form for $a_n,b_n$ and $c_n$?
Any help would be appreciated.
algebra-precalculus closed-form recursion
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
$endgroup$
Consider,
$$
x^3=x+1
$$
Let $x_0$ be a solution to the above equation. Now consider $x^3n$. For $n=2$ we have:
$$
x^6=(x+1)^2
$$
$$
=x^2+2x+1
$$
$$
=xleft(x+2+frac 1xright)
$$
$$
=x_0left(x+2+frac 1xright)
$$
For $n=3$ we have:
$$
x^9=(x+1)^3
$$
$$
=x^3+3x^2+3x+1
$$
$$
=3x^2+4x+2
$$
$$
=xleft(3x+4+frac 2xright)
$$
$$
=x_0left(3x+4+frac 2xright)
$$
Similarly for $n=4$ we have:
$$
x^12=x_0left(7x+9+frac 5xright)
$$
In general we have:
$$
x^3n=x_0left(a_nx+b_n+frac c_nxright),
$$
Where,
$$
a_n+1=a_n+b_n, a_2=1,
$$
$$
b_n+1=a_n+b_n+c_n, b_2=2,
$$
$$
c_n+1=a_n+c_n, c_2=1.
$$
My question is: is there a closed form for $a_n,b_n$ and $c_n$?
Any help would be appreciated.
algebra-precalculus closed-form recursion
algebra-precalculus closed-form recursion
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
edited Apr 6 at 5:54
Awe Kumar Jha
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
asked Apr 6 at 5:46
Awe Kumar JhaAwe Kumar Jha
633113
633113
$begingroup$
The only way I know to approach this is the method of solving simultaneous recurrence relations covered in my combinatorics textbook. (For those curious: Applied Combinatorics, Sixth Edition by Alan Tucker: it's in section 7.5, example 5, on page 313.) The issue being, this is a very nontrivial calculation, and concerns the use of generating functions throughout. [cont.]
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
I tried solving it just to get the generating function for your $a_n$ terms and that in itself took several pages of scratch work (haven't even tried the other two yet) - which I'm not confident in because it's messy and there's a lot of painful algebra involved in this one, so there's plenty of room for error. Plus it all feels like it might fruitless if you're not familiar with such topics. I'm not going to say it's the only method, but it's the only one that I know of off-hand.
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
2
$begingroup$
What I would try is computing $a_n$, $b_n$, and $c_n$ by computer program up to, say, n=12 and plug each sequence independently into the OEIS.
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:12
1
$begingroup$
a is oeis.org/A095263, b is oeis.org/A052921 and c is oeis.org/A181984
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:24
$begingroup$
The PARI program is ? a=[0,0,0,0,0,0,0,0,0,0,0,0]; b=a; c=a; ? a[1]=1; b[1]=2; c[1]=1; ? for (n=1, 11, a[n+1]=a[n]+b[n]; b[n+1]=a[n]+b[n]+c[n]; c[n+1]=a[n]+c[n]);
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:29
add a comment |
$begingroup$
The only way I know to approach this is the method of solving simultaneous recurrence relations covered in my combinatorics textbook. (For those curious: Applied Combinatorics, Sixth Edition by Alan Tucker: it's in section 7.5, example 5, on page 313.) The issue being, this is a very nontrivial calculation, and concerns the use of generating functions throughout. [cont.]
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
I tried solving it just to get the generating function for your $a_n$ terms and that in itself took several pages of scratch work (haven't even tried the other two yet) - which I'm not confident in because it's messy and there's a lot of painful algebra involved in this one, so there's plenty of room for error. Plus it all feels like it might fruitless if you're not familiar with such topics. I'm not going to say it's the only method, but it's the only one that I know of off-hand.
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
2
$begingroup$
What I would try is computing $a_n$, $b_n$, and $c_n$ by computer program up to, say, n=12 and plug each sequence independently into the OEIS.
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:12
1
$begingroup$
a is oeis.org/A095263, b is oeis.org/A052921 and c is oeis.org/A181984
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:24
$begingroup$
The PARI program is ? a=[0,0,0,0,0,0,0,0,0,0,0,0]; b=a; c=a; ? a[1]=1; b[1]=2; c[1]=1; ? for (n=1, 11, a[n+1]=a[n]+b[n]; b[n+1]=a[n]+b[n]+c[n]; c[n+1]=a[n]+c[n]);
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:29
$begingroup$
The only way I know to approach this is the method of solving simultaneous recurrence relations covered in my combinatorics textbook. (For those curious: Applied Combinatorics, Sixth Edition by Alan Tucker: it's in section 7.5, example 5, on page 313.) The issue being, this is a very nontrivial calculation, and concerns the use of generating functions throughout. [cont.]
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
The only way I know to approach this is the method of solving simultaneous recurrence relations covered in my combinatorics textbook. (For those curious: Applied Combinatorics, Sixth Edition by Alan Tucker: it's in section 7.5, example 5, on page 313.) The issue being, this is a very nontrivial calculation, and concerns the use of generating functions throughout. [cont.]
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
I tried solving it just to get the generating function for your $a_n$ terms and that in itself took several pages of scratch work (haven't even tried the other two yet) - which I'm not confident in because it's messy and there's a lot of painful algebra involved in this one, so there's plenty of room for error. Plus it all feels like it might fruitless if you're not familiar with such topics. I'm not going to say it's the only method, but it's the only one that I know of off-hand.
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
I tried solving it just to get the generating function for your $a_n$ terms and that in itself took several pages of scratch work (haven't even tried the other two yet) - which I'm not confident in because it's messy and there's a lot of painful algebra involved in this one, so there's plenty of room for error. Plus it all feels like it might fruitless if you're not familiar with such topics. I'm not going to say it's the only method, but it's the only one that I know of off-hand.
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
2
2
$begingroup$
What I would try is computing $a_n$, $b_n$, and $c_n$ by computer program up to, say, n=12 and plug each sequence independently into the OEIS.
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:12
$begingroup$
What I would try is computing $a_n$, $b_n$, and $c_n$ by computer program up to, say, n=12 and plug each sequence independently into the OEIS.
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:12
1
1
$begingroup$
a is oeis.org/A095263, b is oeis.org/A052921 and c is oeis.org/A181984
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:24
$begingroup$
a is oeis.org/A095263, b is oeis.org/A052921 and c is oeis.org/A181984
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:24
$begingroup$
The PARI program is ? a=[0,0,0,0,0,0,0,0,0,0,0,0]; b=a; c=a; ? a[1]=1; b[1]=2; c[1]=1; ? for (n=1, 11, a[n+1]=a[n]+b[n]; b[n+1]=a[n]+b[n]+c[n]; c[n+1]=a[n]+c[n]);
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:29
$begingroup$
The PARI program is ? a=[0,0,0,0,0,0,0,0,0,0,0,0]; b=a; c=a; ? a[1]=1; b[1]=2; c[1]=1; ? for (n=1, 11, a[n+1]=a[n]+b[n]; b[n+1]=a[n]+b[n]+c[n]; c[n+1]=a[n]+c[n]);
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We derive generating functions for the recurrence relation:
beginalign*
a_n+1&=a_n+b_ntag1\
b_n+1&=a_n+b_n+c_nqquadqquad (ngeq 2)tag2\
c_n+1&=a_n+c_ntag3\
a_2&=1,b_2=2,c_2=1\
endalign*
Let $A(x)=sum_ngeq 2 a_nx^n, B(x)=sum_ngeq 2 b_nx^n, C(x)=sum_ngeq 2 c_n x^n$.
We obtain from (1)
beginalign*
sum_ngeq 2a_n+1x^n&=sum_ngeq 2a_nx^n+sum_ngeq 2b_nx^n\
frac1xsum_ngeq 3a_nx^n&=A(x)+B(x)\
A(x)-x^2&=xA(x)+xB(x)\
colorblue(1-x)A(x)-xB(x)&colorblue=x^2tag4\
endalign*
Since (3) and (1) have the same structure and initial condition, we get
beginalign*
colorblue(1-x)C(x)-xA(x)&colorblue=x^2qquadqquadqquadqquadtag5\
endalign*
The relationship (2):
beginalign*
sum_ngeq 2b_n+1x^n&=sum_ngeq 2left(a_n+b_n+c_nright)x^n\
frac1xsum_ngeq 3b_nx^n&=A(x)+B(x)+C(x)\
B(x)-2x^2&=xA(x)+xB(x)+xC(x)\
colorblue(1-x)B(x)-xA(x)-xC(x)&colorblue=2x^2tag6
endalign*
We take (4) - (6) and derive from them the generating functions.
beginalign*
(1-x)A(x)-xB(x)&=x^2\
-xA(x)+(1-x)C(x)&=x^2\
-xA(x)+(1-x)B(x)-xC(x)&=2x^2
endalign*
Solving the equations above we obtain
beginalign*
colorblueA(x)&colorblue=fracx^21-3x+2x^2-x^3\
&=x^2 + 3 x^3 + 7 x^4 + 16 x^5 + 37 x^6 + 86 x^7+cdots\
colorblueB(x)&colorblue=frac1-xxA(x)-x\
&=2 x^2 + 4 x^3 + 9 x^4 + 21 x^5 + 49 x^6 + 114 x^7 +cdots\
colorblueC(x)&colorblue=fracx1-xA(x)+fracx^21-x\
&=x^2 + 2 x^3 + 5 x^4 + 12 x^5 + 28 x^6 + 65 x^7+cdots
endalign*
where the expansion was done with some help of Wolfram Alpha.
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
$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
);
);
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%2f3176696%2ffinding-a-closed-form-for-coefficients-in-x3n-x-0-lefta-nxb-n-frac-c-n%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$
We derive generating functions for the recurrence relation:
beginalign*
a_n+1&=a_n+b_ntag1\
b_n+1&=a_n+b_n+c_nqquadqquad (ngeq 2)tag2\
c_n+1&=a_n+c_ntag3\
a_2&=1,b_2=2,c_2=1\
endalign*
Let $A(x)=sum_ngeq 2 a_nx^n, B(x)=sum_ngeq 2 b_nx^n, C(x)=sum_ngeq 2 c_n x^n$.
We obtain from (1)
beginalign*
sum_ngeq 2a_n+1x^n&=sum_ngeq 2a_nx^n+sum_ngeq 2b_nx^n\
frac1xsum_ngeq 3a_nx^n&=A(x)+B(x)\
A(x)-x^2&=xA(x)+xB(x)\
colorblue(1-x)A(x)-xB(x)&colorblue=x^2tag4\
endalign*
Since (3) and (1) have the same structure and initial condition, we get
beginalign*
colorblue(1-x)C(x)-xA(x)&colorblue=x^2qquadqquadqquadqquadtag5\
endalign*
The relationship (2):
beginalign*
sum_ngeq 2b_n+1x^n&=sum_ngeq 2left(a_n+b_n+c_nright)x^n\
frac1xsum_ngeq 3b_nx^n&=A(x)+B(x)+C(x)\
B(x)-2x^2&=xA(x)+xB(x)+xC(x)\
colorblue(1-x)B(x)-xA(x)-xC(x)&colorblue=2x^2tag6
endalign*
We take (4) - (6) and derive from them the generating functions.
beginalign*
(1-x)A(x)-xB(x)&=x^2\
-xA(x)+(1-x)C(x)&=x^2\
-xA(x)+(1-x)B(x)-xC(x)&=2x^2
endalign*
Solving the equations above we obtain
beginalign*
colorblueA(x)&colorblue=fracx^21-3x+2x^2-x^3\
&=x^2 + 3 x^3 + 7 x^4 + 16 x^5 + 37 x^6 + 86 x^7+cdots\
colorblueB(x)&colorblue=frac1-xxA(x)-x\
&=2 x^2 + 4 x^3 + 9 x^4 + 21 x^5 + 49 x^6 + 114 x^7 +cdots\
colorblueC(x)&colorblue=fracx1-xA(x)+fracx^21-x\
&=x^2 + 2 x^3 + 5 x^4 + 12 x^5 + 28 x^6 + 65 x^7+cdots
endalign*
where the expansion was done with some help of Wolfram Alpha.
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
$endgroup$
add a comment |
$begingroup$
We derive generating functions for the recurrence relation:
beginalign*
a_n+1&=a_n+b_ntag1\
b_n+1&=a_n+b_n+c_nqquadqquad (ngeq 2)tag2\
c_n+1&=a_n+c_ntag3\
a_2&=1,b_2=2,c_2=1\
endalign*
Let $A(x)=sum_ngeq 2 a_nx^n, B(x)=sum_ngeq 2 b_nx^n, C(x)=sum_ngeq 2 c_n x^n$.
We obtain from (1)
beginalign*
sum_ngeq 2a_n+1x^n&=sum_ngeq 2a_nx^n+sum_ngeq 2b_nx^n\
frac1xsum_ngeq 3a_nx^n&=A(x)+B(x)\
A(x)-x^2&=xA(x)+xB(x)\
colorblue(1-x)A(x)-xB(x)&colorblue=x^2tag4\
endalign*
Since (3) and (1) have the same structure and initial condition, we get
beginalign*
colorblue(1-x)C(x)-xA(x)&colorblue=x^2qquadqquadqquadqquadtag5\
endalign*
The relationship (2):
beginalign*
sum_ngeq 2b_n+1x^n&=sum_ngeq 2left(a_n+b_n+c_nright)x^n\
frac1xsum_ngeq 3b_nx^n&=A(x)+B(x)+C(x)\
B(x)-2x^2&=xA(x)+xB(x)+xC(x)\
colorblue(1-x)B(x)-xA(x)-xC(x)&colorblue=2x^2tag6
endalign*
We take (4) - (6) and derive from them the generating functions.
beginalign*
(1-x)A(x)-xB(x)&=x^2\
-xA(x)+(1-x)C(x)&=x^2\
-xA(x)+(1-x)B(x)-xC(x)&=2x^2
endalign*
Solving the equations above we obtain
beginalign*
colorblueA(x)&colorblue=fracx^21-3x+2x^2-x^3\
&=x^2 + 3 x^3 + 7 x^4 + 16 x^5 + 37 x^6 + 86 x^7+cdots\
colorblueB(x)&colorblue=frac1-xxA(x)-x\
&=2 x^2 + 4 x^3 + 9 x^4 + 21 x^5 + 49 x^6 + 114 x^7 +cdots\
colorblueC(x)&colorblue=fracx1-xA(x)+fracx^21-x\
&=x^2 + 2 x^3 + 5 x^4 + 12 x^5 + 28 x^6 + 65 x^7+cdots
endalign*
where the expansion was done with some help of Wolfram Alpha.
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
$endgroup$
add a comment |
$begingroup$
We derive generating functions for the recurrence relation:
beginalign*
a_n+1&=a_n+b_ntag1\
b_n+1&=a_n+b_n+c_nqquadqquad (ngeq 2)tag2\
c_n+1&=a_n+c_ntag3\
a_2&=1,b_2=2,c_2=1\
endalign*
Let $A(x)=sum_ngeq 2 a_nx^n, B(x)=sum_ngeq 2 b_nx^n, C(x)=sum_ngeq 2 c_n x^n$.
We obtain from (1)
beginalign*
sum_ngeq 2a_n+1x^n&=sum_ngeq 2a_nx^n+sum_ngeq 2b_nx^n\
frac1xsum_ngeq 3a_nx^n&=A(x)+B(x)\
A(x)-x^2&=xA(x)+xB(x)\
colorblue(1-x)A(x)-xB(x)&colorblue=x^2tag4\
endalign*
Since (3) and (1) have the same structure and initial condition, we get
beginalign*
colorblue(1-x)C(x)-xA(x)&colorblue=x^2qquadqquadqquadqquadtag5\
endalign*
The relationship (2):
beginalign*
sum_ngeq 2b_n+1x^n&=sum_ngeq 2left(a_n+b_n+c_nright)x^n\
frac1xsum_ngeq 3b_nx^n&=A(x)+B(x)+C(x)\
B(x)-2x^2&=xA(x)+xB(x)+xC(x)\
colorblue(1-x)B(x)-xA(x)-xC(x)&colorblue=2x^2tag6
endalign*
We take (4) - (6) and derive from them the generating functions.
beginalign*
(1-x)A(x)-xB(x)&=x^2\
-xA(x)+(1-x)C(x)&=x^2\
-xA(x)+(1-x)B(x)-xC(x)&=2x^2
endalign*
Solving the equations above we obtain
beginalign*
colorblueA(x)&colorblue=fracx^21-3x+2x^2-x^3\
&=x^2 + 3 x^3 + 7 x^4 + 16 x^5 + 37 x^6 + 86 x^7+cdots\
colorblueB(x)&colorblue=frac1-xxA(x)-x\
&=2 x^2 + 4 x^3 + 9 x^4 + 21 x^5 + 49 x^6 + 114 x^7 +cdots\
colorblueC(x)&colorblue=fracx1-xA(x)+fracx^21-x\
&=x^2 + 2 x^3 + 5 x^4 + 12 x^5 + 28 x^6 + 65 x^7+cdots
endalign*
where the expansion was done with some help of Wolfram Alpha.
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
$endgroup$
We derive generating functions for the recurrence relation:
beginalign*
a_n+1&=a_n+b_ntag1\
b_n+1&=a_n+b_n+c_nqquadqquad (ngeq 2)tag2\
c_n+1&=a_n+c_ntag3\
a_2&=1,b_2=2,c_2=1\
endalign*
Let $A(x)=sum_ngeq 2 a_nx^n, B(x)=sum_ngeq 2 b_nx^n, C(x)=sum_ngeq 2 c_n x^n$.
We obtain from (1)
beginalign*
sum_ngeq 2a_n+1x^n&=sum_ngeq 2a_nx^n+sum_ngeq 2b_nx^n\
frac1xsum_ngeq 3a_nx^n&=A(x)+B(x)\
A(x)-x^2&=xA(x)+xB(x)\
colorblue(1-x)A(x)-xB(x)&colorblue=x^2tag4\
endalign*
Since (3) and (1) have the same structure and initial condition, we get
beginalign*
colorblue(1-x)C(x)-xA(x)&colorblue=x^2qquadqquadqquadqquadtag5\
endalign*
The relationship (2):
beginalign*
sum_ngeq 2b_n+1x^n&=sum_ngeq 2left(a_n+b_n+c_nright)x^n\
frac1xsum_ngeq 3b_nx^n&=A(x)+B(x)+C(x)\
B(x)-2x^2&=xA(x)+xB(x)+xC(x)\
colorblue(1-x)B(x)-xA(x)-xC(x)&colorblue=2x^2tag6
endalign*
We take (4) - (6) and derive from them the generating functions.
beginalign*
(1-x)A(x)-xB(x)&=x^2\
-xA(x)+(1-x)C(x)&=x^2\
-xA(x)+(1-x)B(x)-xC(x)&=2x^2
endalign*
Solving the equations above we obtain
beginalign*
colorblueA(x)&colorblue=fracx^21-3x+2x^2-x^3\
&=x^2 + 3 x^3 + 7 x^4 + 16 x^5 + 37 x^6 + 86 x^7+cdots\
colorblueB(x)&colorblue=frac1-xxA(x)-x\
&=2 x^2 + 4 x^3 + 9 x^4 + 21 x^5 + 49 x^6 + 114 x^7 +cdots\
colorblueC(x)&colorblue=fracx1-xA(x)+fracx^21-x\
&=x^2 + 2 x^3 + 5 x^4 + 12 x^5 + 28 x^6 + 65 x^7+cdots
endalign*
where the expansion was done with some help of Wolfram Alpha.
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
edited Apr 7 at 21:34
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
answered Apr 7 at 21:01
Markus ScheuerMarkus Scheuer
64.1k460152
64.1k460152
add a comment |
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%2f3176696%2ffinding-a-closed-form-for-coefficients-in-x3n-x-0-lefta-nxb-n-frac-c-n%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
$begingroup$
The only way I know to approach this is the method of solving simultaneous recurrence relations covered in my combinatorics textbook. (For those curious: Applied Combinatorics, Sixth Edition by Alan Tucker: it's in section 7.5, example 5, on page 313.) The issue being, this is a very nontrivial calculation, and concerns the use of generating functions throughout. [cont.]
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
$begingroup$
I tried solving it just to get the generating function for your $a_n$ terms and that in itself took several pages of scratch work (haven't even tried the other two yet) - which I'm not confident in because it's messy and there's a lot of painful algebra involved in this one, so there's plenty of room for error. Plus it all feels like it might fruitless if you're not familiar with such topics. I'm not going to say it's the only method, but it's the only one that I know of off-hand.
$endgroup$
– Eevee Trainer
Apr 6 at 6:10
2
$begingroup$
What I would try is computing $a_n$, $b_n$, and $c_n$ by computer program up to, say, n=12 and plug each sequence independently into the OEIS.
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:12
1
$begingroup$
a is oeis.org/A095263, b is oeis.org/A052921 and c is oeis.org/A181984
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:24
$begingroup$
The PARI program is ? a=[0,0,0,0,0,0,0,0,0,0,0,0]; b=a; c=a; ? a[1]=1; b[1]=2; c[1]=1; ? for (n=1, 11, a[n+1]=a[n]+b[n]; b[n+1]=a[n]+b[n]+c[n]; c[n+1]=a[n]+c[n]);
$endgroup$
– Jaume Oliver Lafont
Apr 6 at 6:29