Generalization of Fibonacci using Generating Functions

Question

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.

Answer 1

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