Generating function for Fibonacci-like sequence
$begingroup$
I have been reading the book Irresistible Integrals lately, and it inspired this problem.
For some constants $a,bin Bbb R$ we define the sequence $S(a,b)={e_n(a,b):ninBbb Z_{geq0}}$ by the recurrence
$$e_{n+2}(a,b)=r_{n+2}=ar_{n+1}+br_{n}qquad ninBbb N; ngeq2$$
With initial conditions $$r_0=r_1=1$$
We then immediately see that the Fibonacci numbers are given by the case
$${F_n}=S(1,1)$$
I have been struggling to find a closed form for
$$E(x;a,b)=R(x)=sum_{ngeq0}r_nx^n$$
Since $$F(x)=E(x;1,1)=frac{x}{1-x-x^2}$$
I have very little doubt that a general closed form exists.
My attempts:
$$r_{n+2}=ar_{n+1}+br_n$$
$$r_{n+2}x^n=ar_{n+1}x^n+br_nx^n$$
$$sum_{ngeq0}r_{n+2}x^n=asum_{ngeq0}r_{n+1}x^n+bR(x)$$
If I'm not mistaken,
$$sum_{ngeq0}r_{n+2}x^n=frac1{x^2}(R(x)-1-x)$$
and similarly
$$sum_{ngeq0}r_{n+1}x^n=frac1x(R(x)-1)$$
Since I fear I have made a really simple algebra mistake that I have failed to catch, I will show all of my steps.
$$frac1{x^2}(R(x)-1-x)=frac{a}x(R(x)-1)+bR(x)$$
$$R(x)-1-x=axR(x)-ax+bx^2R(x)$$
$$(1-ax-bx^2)R(x)=(1-a)x+1$$
$$R(x)=E(x;a,b)=frac{(1-a)x+1}{1-ax-bx^2}$$
But plugging in $a=b=1$ shows that I messed up, because
$$frac{1}{1-x-x^2}neqfrac{x}{1-x-x^2}$$
Did I do something wrong? What is the correct generating function $E(x;a,b)$ and how do you find it?
Thanks.
sequences-and-series elementary-number-theory power-series generating-functions fibonacci-numbers
$endgroup$
|
show 1 more comment
$begingroup$
I have been reading the book Irresistible Integrals lately, and it inspired this problem.
For some constants $a,bin Bbb R$ we define the sequence $S(a,b)={e_n(a,b):ninBbb Z_{geq0}}$ by the recurrence
$$e_{n+2}(a,b)=r_{n+2}=ar_{n+1}+br_{n}qquad ninBbb N; ngeq2$$
With initial conditions $$r_0=r_1=1$$
We then immediately see that the Fibonacci numbers are given by the case
$${F_n}=S(1,1)$$
I have been struggling to find a closed form for
$$E(x;a,b)=R(x)=sum_{ngeq0}r_nx^n$$
Since $$F(x)=E(x;1,1)=frac{x}{1-x-x^2}$$
I have very little doubt that a general closed form exists.
My attempts:
$$r_{n+2}=ar_{n+1}+br_n$$
$$r_{n+2}x^n=ar_{n+1}x^n+br_nx^n$$
$$sum_{ngeq0}r_{n+2}x^n=asum_{ngeq0}r_{n+1}x^n+bR(x)$$
If I'm not mistaken,
$$sum_{ngeq0}r_{n+2}x^n=frac1{x^2}(R(x)-1-x)$$
and similarly
$$sum_{ngeq0}r_{n+1}x^n=frac1x(R(x)-1)$$
Since I fear I have made a really simple algebra mistake that I have failed to catch, I will show all of my steps.
$$frac1{x^2}(R(x)-1-x)=frac{a}x(R(x)-1)+bR(x)$$
$$R(x)-1-x=axR(x)-ax+bx^2R(x)$$
$$(1-ax-bx^2)R(x)=(1-a)x+1$$
$$R(x)=E(x;a,b)=frac{(1-a)x+1}{1-ax-bx^2}$$
But plugging in $a=b=1$ shows that I messed up, because
$$frac{1}{1-x-x^2}neqfrac{x}{1-x-x^2}$$
Did I do something wrong? What is the correct generating function $E(x;a,b)$ and how do you find it?
Thanks.
sequences-and-series elementary-number-theory power-series generating-functions fibonacci-numbers
$endgroup$
$begingroup$
If $F_0=F_1=1$ then $sum_0^infty F_nx^n=frac1{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 17:55
$begingroup$
@LordSharktheUnknown So I did it right?
$endgroup$
– clathratus
Jan 7 at 17:58
$begingroup$
But you got $frac x{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 18:00
$begingroup$
@LordSharktheUnknown that's what the book gave me
$endgroup$
– clathratus
Jan 7 at 18:02
1
$begingroup$
@JeanMarie Less I think...
$endgroup$
– clathratus
Jan 7 at 18:06
|
show 1 more comment
$begingroup$
I have been reading the book Irresistible Integrals lately, and it inspired this problem.
For some constants $a,bin Bbb R$ we define the sequence $S(a,b)={e_n(a,b):ninBbb Z_{geq0}}$ by the recurrence
$$e_{n+2}(a,b)=r_{n+2}=ar_{n+1}+br_{n}qquad ninBbb N; ngeq2$$
With initial conditions $$r_0=r_1=1$$
We then immediately see that the Fibonacci numbers are given by the case
$${F_n}=S(1,1)$$
I have been struggling to find a closed form for
$$E(x;a,b)=R(x)=sum_{ngeq0}r_nx^n$$
Since $$F(x)=E(x;1,1)=frac{x}{1-x-x^2}$$
I have very little doubt that a general closed form exists.
My attempts:
$$r_{n+2}=ar_{n+1}+br_n$$
$$r_{n+2}x^n=ar_{n+1}x^n+br_nx^n$$
$$sum_{ngeq0}r_{n+2}x^n=asum_{ngeq0}r_{n+1}x^n+bR(x)$$
If I'm not mistaken,
$$sum_{ngeq0}r_{n+2}x^n=frac1{x^2}(R(x)-1-x)$$
and similarly
$$sum_{ngeq0}r_{n+1}x^n=frac1x(R(x)-1)$$
Since I fear I have made a really simple algebra mistake that I have failed to catch, I will show all of my steps.
$$frac1{x^2}(R(x)-1-x)=frac{a}x(R(x)-1)+bR(x)$$
$$R(x)-1-x=axR(x)-ax+bx^2R(x)$$
$$(1-ax-bx^2)R(x)=(1-a)x+1$$
$$R(x)=E(x;a,b)=frac{(1-a)x+1}{1-ax-bx^2}$$
But plugging in $a=b=1$ shows that I messed up, because
$$frac{1}{1-x-x^2}neqfrac{x}{1-x-x^2}$$
Did I do something wrong? What is the correct generating function $E(x;a,b)$ and how do you find it?
Thanks.
sequences-and-series elementary-number-theory power-series generating-functions fibonacci-numbers
$endgroup$
I have been reading the book Irresistible Integrals lately, and it inspired this problem.
For some constants $a,bin Bbb R$ we define the sequence $S(a,b)={e_n(a,b):ninBbb Z_{geq0}}$ by the recurrence
$$e_{n+2}(a,b)=r_{n+2}=ar_{n+1}+br_{n}qquad ninBbb N; ngeq2$$
With initial conditions $$r_0=r_1=1$$
We then immediately see that the Fibonacci numbers are given by the case
$${F_n}=S(1,1)$$
I have been struggling to find a closed form for
$$E(x;a,b)=R(x)=sum_{ngeq0}r_nx^n$$
Since $$F(x)=E(x;1,1)=frac{x}{1-x-x^2}$$
I have very little doubt that a general closed form exists.
My attempts:
$$r_{n+2}=ar_{n+1}+br_n$$
$$r_{n+2}x^n=ar_{n+1}x^n+br_nx^n$$
$$sum_{ngeq0}r_{n+2}x^n=asum_{ngeq0}r_{n+1}x^n+bR(x)$$
If I'm not mistaken,
$$sum_{ngeq0}r_{n+2}x^n=frac1{x^2}(R(x)-1-x)$$
and similarly
$$sum_{ngeq0}r_{n+1}x^n=frac1x(R(x)-1)$$
Since I fear I have made a really simple algebra mistake that I have failed to catch, I will show all of my steps.
$$frac1{x^2}(R(x)-1-x)=frac{a}x(R(x)-1)+bR(x)$$
$$R(x)-1-x=axR(x)-ax+bx^2R(x)$$
$$(1-ax-bx^2)R(x)=(1-a)x+1$$
$$R(x)=E(x;a,b)=frac{(1-a)x+1}{1-ax-bx^2}$$
But plugging in $a=b=1$ shows that I messed up, because
$$frac{1}{1-x-x^2}neqfrac{x}{1-x-x^2}$$
Did I do something wrong? What is the correct generating function $E(x;a,b)$ and how do you find it?
Thanks.
sequences-and-series elementary-number-theory power-series generating-functions fibonacci-numbers
sequences-and-series elementary-number-theory power-series generating-functions fibonacci-numbers
edited Jan 11 at 1:09
clathratus
asked Jan 7 at 17:53
clathratusclathratus
4,563337
4,563337
$begingroup$
If $F_0=F_1=1$ then $sum_0^infty F_nx^n=frac1{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 17:55
$begingroup$
@LordSharktheUnknown So I did it right?
$endgroup$
– clathratus
Jan 7 at 17:58
$begingroup$
But you got $frac x{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 18:00
$begingroup$
@LordSharktheUnknown that's what the book gave me
$endgroup$
– clathratus
Jan 7 at 18:02
1
$begingroup$
@JeanMarie Less I think...
$endgroup$
– clathratus
Jan 7 at 18:06
|
show 1 more comment
$begingroup$
If $F_0=F_1=1$ then $sum_0^infty F_nx^n=frac1{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 17:55
$begingroup$
@LordSharktheUnknown So I did it right?
$endgroup$
– clathratus
Jan 7 at 17:58
$begingroup$
But you got $frac x{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 18:00
$begingroup$
@LordSharktheUnknown that's what the book gave me
$endgroup$
– clathratus
Jan 7 at 18:02
1
$begingroup$
@JeanMarie Less I think...
$endgroup$
– clathratus
Jan 7 at 18:06
$begingroup$
If $F_0=F_1=1$ then $sum_0^infty F_nx^n=frac1{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 17:55
$begingroup$
If $F_0=F_1=1$ then $sum_0^infty F_nx^n=frac1{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 17:55
$begingroup$
@LordSharktheUnknown So I did it right?
$endgroup$
– clathratus
Jan 7 at 17:58
$begingroup$
@LordSharktheUnknown So I did it right?
$endgroup$
– clathratus
Jan 7 at 17:58
$begingroup$
But you got $frac x{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 18:00
$begingroup$
But you got $frac x{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 18:00
$begingroup$
@LordSharktheUnknown that's what the book gave me
$endgroup$
– clathratus
Jan 7 at 18:02
$begingroup$
@LordSharktheUnknown that's what the book gave me
$endgroup$
– clathratus
Jan 7 at 18:02
1
1
$begingroup$
@JeanMarie Less I think...
$endgroup$
– clathratus
Jan 7 at 18:06
$begingroup$
@JeanMarie Less I think...
$endgroup$
– clathratus
Jan 7 at 18:06
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
As Lord Shark the Unknown noted, your mistake is not in any of this algebraic manipulation, but rather in mixing up two common definitions of the Fibonacci sequence, only one of which gives a factor of $x$ in the numerator. Either way, sanity checks are always your friend. Expanding $frac{x}{1-x-x^2}$ as a power series clearly gives $x+cdots$; it can't start with a non-zero constant term, since it vanishes at $x=0$. But suppose we stick with that definition of $F_n$: then in the question's notation, ${F_{n+1}}=S(1,,1)$. In other words, your general result is consistent with the Fibonacci sanity check you attempted after all.
$endgroup$
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
1
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
1
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
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%2f3065283%2fgenerating-function-for-fibonacci-like-sequence%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$
As Lord Shark the Unknown noted, your mistake is not in any of this algebraic manipulation, but rather in mixing up two common definitions of the Fibonacci sequence, only one of which gives a factor of $x$ in the numerator. Either way, sanity checks are always your friend. Expanding $frac{x}{1-x-x^2}$ as a power series clearly gives $x+cdots$; it can't start with a non-zero constant term, since it vanishes at $x=0$. But suppose we stick with that definition of $F_n$: then in the question's notation, ${F_{n+1}}=S(1,,1)$. In other words, your general result is consistent with the Fibonacci sanity check you attempted after all.
$endgroup$
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
1
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
1
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
add a comment |
$begingroup$
As Lord Shark the Unknown noted, your mistake is not in any of this algebraic manipulation, but rather in mixing up two common definitions of the Fibonacci sequence, only one of which gives a factor of $x$ in the numerator. Either way, sanity checks are always your friend. Expanding $frac{x}{1-x-x^2}$ as a power series clearly gives $x+cdots$; it can't start with a non-zero constant term, since it vanishes at $x=0$. But suppose we stick with that definition of $F_n$: then in the question's notation, ${F_{n+1}}=S(1,,1)$. In other words, your general result is consistent with the Fibonacci sanity check you attempted after all.
$endgroup$
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
1
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
1
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
add a comment |
$begingroup$
As Lord Shark the Unknown noted, your mistake is not in any of this algebraic manipulation, but rather in mixing up two common definitions of the Fibonacci sequence, only one of which gives a factor of $x$ in the numerator. Either way, sanity checks are always your friend. Expanding $frac{x}{1-x-x^2}$ as a power series clearly gives $x+cdots$; it can't start with a non-zero constant term, since it vanishes at $x=0$. But suppose we stick with that definition of $F_n$: then in the question's notation, ${F_{n+1}}=S(1,,1)$. In other words, your general result is consistent with the Fibonacci sanity check you attempted after all.
$endgroup$
As Lord Shark the Unknown noted, your mistake is not in any of this algebraic manipulation, but rather in mixing up two common definitions of the Fibonacci sequence, only one of which gives a factor of $x$ in the numerator. Either way, sanity checks are always your friend. Expanding $frac{x}{1-x-x^2}$ as a power series clearly gives $x+cdots$; it can't start with a non-zero constant term, since it vanishes at $x=0$. But suppose we stick with that definition of $F_n$: then in the question's notation, ${F_{n+1}}=S(1,,1)$. In other words, your general result is consistent with the Fibonacci sanity check you attempted after all.
answered Jan 7 at 18:00
J.G.J.G.
27.1k22843
27.1k22843
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
1
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
1
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
add a comment |
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
1
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
1
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
$begingroup$
Thank you! I can see why they are called sanity checks
$endgroup$
– clathratus
Jan 7 at 18:03
1
1
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
@clathratus There's also a name for the error we caught this time.
$endgroup$
– J.G.
Jan 7 at 18:04
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
$begingroup$
Do you know if my general generating function is correct?
$endgroup$
– clathratus
Jan 7 at 18:07
1
1
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
$begingroup$
@clathratus It looks right, yes. Apart from me following your proof, we can verify its series begins $1+x$ as expected, which is enough to determine the rest of the series.
$endgroup$
– J.G.
Jan 7 at 18:12
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%2f3065283%2fgenerating-function-for-fibonacci-like-sequence%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$
If $F_0=F_1=1$ then $sum_0^infty F_nx^n=frac1{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 17:55
$begingroup$
@LordSharktheUnknown So I did it right?
$endgroup$
– clathratus
Jan 7 at 17:58
$begingroup$
But you got $frac x{1-x-x^2}$.
$endgroup$
– Lord Shark the Unknown
Jan 7 at 18:00
$begingroup$
@LordSharktheUnknown that's what the book gave me
$endgroup$
– clathratus
Jan 7 at 18:02
1
$begingroup$
@JeanMarie Less I think...
$endgroup$
– clathratus
Jan 7 at 18:06