# Generalization of Fibonacci using Generating Functions

I have been trying to work through the beginning of Generating Functionology. In the first chapter, the author mentions that it is possible to using generating functions to solve for a Fibonacci-like sequence ($a_{n+1}=a_n+a_{n-1}$) where we have $a_b, a_c$ such that b and c are not adjacent integers. The books goes on to solve a more difficult problem, but I wanted to try it for that problem in particular.

Following the method in the book, I have $a_{n+1}=a_n+a_{n-1}, (a_b, a_c, n \geq 1)$ So we know two specific values of the sequence, but they are not necessarily adjacent, and we know the sequence is defined for all values greater than or equal to 1. Naturally, $A(x)= \sum_{n \geq 1} a_n * x^n$.

Following the next step, we have that $\sum_{n \geq 1} a_n * x^n = A(x)/x - a_1$ We also have that $\sum_{n \geq 1} a_n * x^n + \sum_{n \geq 1}^{???} a_{n-1} * x^n = A(x)+A(x)*x+a_0x$. Clearly, from here it should not be too difficult to work form here.

My issue come from the (???) section. At that point in the sequence, we are requiring the evaluation of $a_0$. In fact, we require it later as well. But I described the sequence without defining $a_0$. It is outside the scope.

Am I mis-defining my problem, solving incorrectly, or doing something entirely different that is incorrect? Thank you very much.

• Your generating functions should have a constant term (usually denoted $a_0$). You might find it simpler to work with $A(x) = \sum_{n \geq 0} a_n x^n$ and the recurrence $a_{n+2} = a_{n+1} + a_n$ for $n \geq 0$. – Austin Mohr Jun 30 '14 at 4:10
• O.K. That seems to work a lot nicer. Now I don't have any undefined terms. However, I now need to figure out what (the new) $a_0,a_1$ are. Do you have a suggestion as to why the first method didn't work? Is this the point where you create a finite sum with bounds at b and c to solve for the other sum? – Thoth19 Jun 30 '14 at 4:25
• I'm not sure what you mean by "figure out $a_0$ and $a_1$. They can be any constants you wish. For the classical Fibonacci numbers, $a_0 = a_1 = 1$ by definition. If you wanted to take $a_0 = 100$ and $a_1 = 250$, then you get a new Fibonacci-like sequence with different initial conditions. – Austin Mohr Jun 30 '14 at 18:20
• As for why the first approach didn't work, you should always prefer to start your sequence at $a_0$ unless you have a particularly compelling reason not to do so. Your generating function will then be $a_0x^0 + a_1x^1 + a_2x^2 + \cdots$, so the index and the exponent line up nicely. – Austin Mohr Jun 30 '14 at 18:24
• I understand your question now. It probably does merit a separate question, as it is really a question about recurrence relations and not generating functions. (By the way, generatingfunctionology is a great text to learn from.) – Austin Mohr Jun 30 '14 at 21:58

Let $a_{n+1}=a_n+a_{n-1} (n\geq 1)$ and $a_M,a_N$ given boundary values $(0\leq M < N)$.

In order to respect the information of the boundary values $a_M$ and $a_N$ we need a generating function which makes use of them. Therefore, we define

$$A_{M,N}(x)=\sum_{n=M}^{N}a_nx^n$$

Following the recipe according to section 1.4 from Wilf's Generatingfunctionology we get

\begin{align*} \sum_{n=M+1}^{N-1}a_{n+1}x^n-\sum_{n=M+1}^{N-1}a_{n}x^n-\sum_{n=M+1}^{N-1}a_{n-1}x^n&=0\\ \frac{1}{x}\sum_{n=M+1}^{N-1}a_{n+1}x^{n+1}-\sum_{n=M+1}^{N-1}a_{n}x^n-x\sum_{n=M+1}^{N-1}a_{n-1}x^{n-1}&=0\\ \frac{1}{x}\sum_{n=M+2}^{N}a_{n}x^{n}-\sum_{n=M+1}^{N-1}a_{n}x^n-x\sum_{n=M}^{N-2}a_{n}x^{n}&=0\\ \end{align*}

Now we can use $A_{M,N}(x)$ to get

\begin{align*} \frac{1}{x}\left(A_{M,N}(x)-a_{M+1}x^{M+1}-a_Mx^M\right)-\left(A_{M,N}(x)-a_{M}x^{M}-a_Nx^N\right)&\\ \quad-x\left(A_{M,N}(x)-a_{N-1}x^{N-1}-a_Nx^N\right)&=0\\ \end{align*}

and after some rearrangement we get \begin{align*} \left(1-x-x^2\right)A_{M,N}(x)&=(1-x)x^Ma_M+x^{M+1}a_{M+1}\tag{1}\\ &-x^{N+1}a_{N-1}-(1+x)x^{N+1}a_N \end{align*} with the unknowns $a_{M+1}$ and $a_{N-1}$.

Note: Observe, that the calculation in section 1.4 is somewhat simpler. This is due to the fact, that the given boundary values in Wilf's example are $u_0=u_N=0$ and so they vanish. But we have to calculate based upon the given values $a_M$ and $a_N$ in order to determine the unknowns $a_{M+1}$ and $a_{N-1}$.

We use the same technique as in section 1.4 and calculate the zeros $x_0=-\frac{1-\sqrt{5}}{2}$ and $x_1=-\frac{1+\sqrt{5}}{2}$ of the quadratic equation $x^2+x-1=(x-x_0)(x-x_1)$ in $(1)$. (Please note, that $x_0=-r_{-}$ and $x_1=-r_{+}$ in Wilf's example.) Substituting therefore $x_0$ and $x_1$ in $(1)$ we get two linear equations in the two unknowns $a_{M+1}$ and $a_{N-1}$.

\begin{align*} x_0^{M+1}a_{M+1}-x_0^{N+1}a_{N-1}&=-(1-x_0)x_0^Ma_M+x_0^Na_N\\ x_1^{M+1}a_{M+1}-x_1^{N+1}a_{N-1}&=-(1-x_1)x_1^Ma_M+x_1^Na_N\\ \end{align*}

Solving these equations by consequently using $1+x_0=x_1, 1+x_1=x_0, x_0x_1=-1, x_0+x_1=-1$ and $x_1-x_0=-\sqrt{5}$ gives

\begin{align*} \left(x_1^{N-M}+x_0^{N-M}\right)a_{M+1}&=\left(x_1^{N-M+1}-x_0^{N-M+1}\right)a_M+\left(x_1^{N-M}-x_0^{N-M}\right)a_M\\ &+(-1)^{N-M+1}(x_1-x_0)a_N\tag{2}\\ \left(x_1^{N-M}+x_0^{N-M}\right)a_{N-1}&=(x_1-x_0)a_M-\left(x_1^{N-M-1}-x_0^{N-M-1}\right)a_N\tag{3}\\ \end{align*}

and finally by substituting for $x_0$ and $x_1$

\begin{align*} a_{M+1}&=\frac{-\frac{1}{2}\left(1+\sqrt{5})^{N-M+1}-(1-\sqrt{5})^{N-M+1}\right)a_M+2^{N-M}\sqrt{5}a_N}{(1+\sqrt{5})^{N-M}-(1-\sqrt{5})^{N-M}}+a_M\\ a_{N-1}&=\frac{(-2)^{N-M}\left(-\sqrt{5}\right)a_M+2\left((1+\sqrt{5})^{N-M-1}-(1-\sqrt{5})^{N-M-1}\right)a_N}{(1+\sqrt{5})^{N-M}-(1-\sqrt{5})^{N-M}} \end{align*}

Note: If we assume $a_M,a_N$ being ordinary Fibonacci numbers we could use the explicit formula for them (see e.g. Wilf's section $3$, formula $(1.3.3)$)

\begin{align*} a_n=\frac{(-1)^n}{\sqrt{5}}\left(x_1^n-x_0^n\right)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) \end{align*}

and so additionally derive the following recursion formulas from $(2)$ and $(3)$ for $0 \leq M<N$:

\begin{align*} a_{N-M}a_{M+1}&=(a_{N-M}-a_{N-M+1})a_M+a_N\\ a_{N-M}a_{N-1}&=(-1)^{N-M-1}a_M+a_{N-M-1}a_N \end{align*}

Added 2014-07-04: Some additional information according to the comment of thoth19

Note: Please note that the main task of the calculation above is showing which Ansatz could be used in order to solve the boundary value problem similar to Wilf's section $1.4$. The benefit thereby is mainly to derive consecutive sequence elements to calculate elements near the boundaries $a_M$ and $a_N$. If we want to find a proper generating function of generalized Fibonacci numbers, we should not proceed with the generating function $A_{M,N}(x)$ but we should instead use a different approach.

Let's assume we start with given $a_M$ and $a_N$. If we are interested in the natural domain of a generating function for the generalized Fibonacci sequence, we should keep in mind, that the recursion formula

$$a_{n+1}=a_n+a_{n-1}\qquad\qquad(n\geq 1)$$

has as natural domain $n\geq 1$. So, the generalized Fibonacci sequence wants to start with $a_0, a_1$, etc.

Therefore I suggest the following approach:

• find a generating function $A(x)=\sum_{n\geq 0}a_nx^n$ based upon the unknowns $a_0$ and $a_1$
• determine the general coefficient $a_n$ in terms of $a_0$ and $a_1$
• express $a_M$ and $a_N$ in terms of the unknowns $a_0$ and $a_1$ according to the step above
• solve the two linear equations above to determine $a_0$ and $a_1$

The benefit thereby is, that we do not need to cope with the rather complicated GF $A_{M,N}(x)$ which is only due to the artificial circumstance of already known $a_M$ and $a_N$. If we normalise the approach to the natural domain of the recurrence formula and work with $a_0$ and $a_1$ instead everything becomes much easier and we'll gain a better insight.

Two hints (hopefully correctly calculated):

First step: \begin{align*} \sum_{n\geq1}a_{n+1}x^n&=\sum_{n\geq 1}a_{n}x^n+\sum_{n\geq1}a_{n-1}x^n\\ &...\\ A(x)&=\frac{a_0+(a_1-a_0)x}{(1+x_1x)(1+x_0x)} \end{align*}

Second step: \begin{align*} a_n=\frac{(-1)^n}{\sqrt{5}}\left(a_1(x_1^n-x_0^n)+a_0(x_1^{n-1}-x_0^{n-1})\right) \end{align*}

Final Note to your question: GF mostly useless? No, indeed! Generating functions are an important instrument which provides often deep insights, which could otherwise be hardly found. But, we have to think about which GF is most suitable for our needs! To emphasize this aspect you could look at point $3$ of my answer to this question about IEP, which is also based upon Wilf's Generatingfunctionology (section $4.2$)

Btw: You can find another kind of generalisation of Fibonacci numbers at the end of my answer to this question

• Thank you so much for writing this all out for me. Slightly confused from the point "If we use the explicit formula for...." on. Which explicit formula is that? is that the Fibonacci formula generalized formula? In the last box, is that meant to be multiplication between $a_{n-m}$ and $a_{m+1}$? Additionally, what is the final GF? Or is the fact that you have the explicit form, mean the GF is mostly useless? Again, thank you so much. – Thoth19 Jul 3 '14 at 22:04
• @Thoth19: I've updated the text, which caused some confusion. Hopefully it's better understandable now. ... and yes, this recurrence relation contains multiplications of Fibonacci numbers. I've added some notes to clarify your question about GF. Best regards. – Markus Scheuer Jul 4 '14 at 16:58