I have been reading the book Irresistible Integrals lately, and it inspired this problem.
For some constants $a,b\in \Bbb R$ we define the sequence $S(a,b)=\{e_n(a,b):n\in\Bbb Z_{\geq0}\}$ by the recurrence $$e_{n+2}(a,b)=r_{n+2}=ar_{n+1}+br_{n}\qquad n\in\Bbb N; n\geq2$$ 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_{n\geq0}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_{n\geq0}r_{n+2}x^n=a\sum_{n\geq0}r_{n+1}x^n+bR(x)$$ If I'm not mistaken, $$\sum_{n\geq0}r_{n+2}x^n=\frac1{x^2}(R(x)-1-x)$$ and similarly $$\sum_{n\geq0}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}\neq\frac{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.
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.