Generating function for Fibonacci-like sequence












1












$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.










share|cite|improve this question











$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
















1












$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.










share|cite|improve this question











$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














1












1








1





$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.










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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


















  • $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










1 Answer
1






active

oldest

votes


















2












$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.






share|cite|improve this answer









$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











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


















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









2












$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.






share|cite|improve this answer









$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
















2












$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.






share|cite|improve this answer









$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














2












2








2





$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.






share|cite|improve this answer









$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.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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


















  • $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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅