Home > Cover Feature > On the Probability Distributions Induced by Integer Sequences Generated by Recurrence Relations with Positive Integer Coefficients

On the Probability Distributions Induced by Integer Sequences Generated by Recurrence Relations with Positive Integer Coefficients

Fibonacci Sequence

Fibonacci sequence, among the ocean of integer sequences, has caught the attention of professional mathematicians and amateurs alike, for over centuries. While on the one side, it is a treasure house of numerous interesting mathematical properties, on the other side, the applications of Fibonacci sequence are widespread, including that of fractal music, financial market trading etc. Fibonacci numbers are found in many biological settings and nature, like the number of petals in sunflower, spiral phyllotaxis of plants and so on.

The elements of the Fibonacci sequence are generated by the second order recurrence relation

$$ f_{n}=f_{n-1}+f_{n-2} $$

with the condition that $f_{0} = 0, f_{1} = 1$. It is also interesting to note that for a number $x$. to be a Fibonacci number, either $5x^{2} + 4$ or $5x^{2}-4$ must be a a perfect square.

The ratio

$$ {\rm \lim_{{\it n} \rightarrow \infty}} \dfrac{f_{n}+1}{f_{n}} $$

converges to the golden mean or the golden ratio $\varphi =\dfrac{1+\sqrt{5}}{2}$

The n-th Fibonacci number can be expressed in terms of the golden ratio as

$$ f_{n}= \dfrac{\varphi-(-\varphi^{-}n)}{\sqrt{5}} $$

In this work, we unfold yet another interesting result related to Fibonacci sequence from the perspective of discrete probability distributions generated by linear recurrence relations.

Abstract

The classical Fibonacci sequence is known to exhibit many fascinating properties. In this paper, we explore the Fibonacci sequence and integer sequences generated by second order linear recurrence relations with positive integer coeffcients from the point of view of probability distributions that they induce. We obtain the generalizations of some of the known limiting properties of these probability distributions and present certain optimal properties of the classical Fibonacci sequence in this context. In addition, we also look at the self linear convolution of linear recurrence relations with positive integer coefficients. Analysis of self linear convolution is focused towards locating the maximum in the resulting sequence. This analysis, also highlights the influence that the largest positive real root, of the “characteristic equation” of the linear recurrence relations with positive integer coefficients, has on the location of the maximum. In particular, when the largest positive real root is 2, the location of the maximum is shown to depend on whether the sequence length being odd or even.

Key words: Fibonacci sequence, recurrence relations, probability distribution, limiting properties, linear convolution

AMS subject classifications. 11B37, 11B39, 60C05, 60C09, 60F99

1  Introduction

Starting with any sequence $\{f[n]\}_{n\in \mathbb N}$ of positive real numbers, we can generate a probability distribution on $\{1; 2; : : : ;N\}$ for every $N \in \mathbb N$ as follows: Let $X$ be a random variable taking values $1; 2; : : : ;N$ such that

Starting with any sequence $\{f[n]\}_{n\in \mathbb N}$ of positive real numbers, we can generate a probability distribution on $\{1; 2; : : : ;N\}$ for every $N \in \mathbb N$ as follows: Let $X$ be a random variable taking values $1; 2; : : : ;N$ such that

$$ P(X=n) = \displaystyle{\frac{f[n]}{\displaystyle{\sum_{k=1}^N}f[k]}} $$

In particular, if $f[n]$ are all positive integers, then we can generate such probability distributions using only integers. In a recent work, Neal [1] has investigated such probability distributions arising out of the Fibonacci sequence and obtained some limiting properties of these distributions as $N \rightarrow \infty$.

While exploring integer sequences from the point of view of generating window functions in the context of designing digital filters for signal processing applications [2], we found some generalizations of Neal’s limiting properties for a class of integer sequences and an optimal property of the Fibonacci sequence in this class. In this paper, we present these results.

2  Probability Distributions Induced by Fibonacci Sequence

The classical Fibonacci sequence [3], [4], is the positive integer sequence $f[n]$ defined by the second order recurrence relation

\begin{equation} f[n] = f[n-1] + f[n-2]\tag{2.1}\label{2.1} \end{equation}

with initial conditions $f[1] = 1$, $f[2] = 1$. The ratio of successive terms of the Fibonacci sequence converges to the well known golden ratio $\varphi$, i.e.,

$$ \lim_{k \rightarrow \infty} \frac{f[k+1]}{f[k]} = \varphi = \displaystyle{\frac{1 + \sqrt5}{2}}\tag{2.2}\label{2.2} $$

For any positive integer $N$, consider the Fibonacci sequence, $f[1], f[2], \ldots, f[N]$, of length $N$. Using the Fibonacci sequence, we can define a discrete probability distribution as follows. We define the probability mass function as1

$$ p_{_{\bar{N}}}[1], p_{_{\bar{N}}}[2], \ldots, p_{_{\bar{N}}}[N] $$

\begin{equation} p_{_{\bar{N}}}(n) = \frac{f[n]}{\displaystyle{\sum_{k =1}^N f[k]}} \hspace{0.3in} \forall n = 1, 2, \ldots, N \tag{2.3}\label{2.3} \end{equation}

Let $\bar{X}$ be a random variable in $\{1,2, \ldots, N\}$ such that

\begin{equation} P(\bar{X} = n) = p_{_{\bar{N}}}(n); \hspace{0.3in} 1 \leq n\leq N.\tag{2.4}\label{2.4} \end{equation}

In his work, Neal [1] showed that, $E(\bar{X})$, the mean or expectation of $\bar{X}$, grows linearly as $N$ increases and hence

\begin{equation} \lim_{N\rightarrow \infty} E(\bar{X}) = \infty\tag{2.5}\label{2.5} \end{equation}

Similarly, let $\underline{X}$ be a random variable in $\{1,2, \ldots, N\}$, where the probabilities, $p_{_{\underline{N}}}[n]$, correspond to the Fibonacci sequence, of length $N$, in the decreasing order2. We define the probability mass function,

\begin{equation} P(\underline{X} = n) = \frac{f[N+1-n]}{\displaystyle{\sum_{k =1}^N f[k]}} = p_{_{\underline{N}}}(n) \hspace{0.2in} ; \hspace{0.2in} 1 \leq n\leq N.\tag{2.6}\label{2.6} \end{equation}

For such a random variable, $\underline{X}$, Neal [1] observed the following limiting properties:

\begin{equation} \lim_{N\rightarrow \infty} E(\underline{X}) = \varphi + 1\tag{2.7}\label{2.7} \end{equation}

\begin{equation} \lim_{N\rightarrow \infty} Var(\underline{X}) = 2\varphi + 1\tag{2.8}\label{2.8} \end{equation}

where $E(\underline{X})$ denotes the mean or expectation of $\underline{X}$ and $Var(\underline{X})$ denotes the variance of $\underline{X}$.

The aim of this paper, as mentioned earlier, is to show that such limiting properties are characteristic for integer sequences defined by linear recurrence relations , of any order, with positive integer coefficients. For the sake of simplicity, we shall first discuss the second order recurrence relation.

3 Second Order Recurrence Relations

Let $a$, $b$ be any two positive integers and consider the integer sequence defined by the second order recurrence relation

\begin{equation} f[n] = a f[n-1] + b f[n-2] \hspace{0.1in} {\rm where} \hspace{0.1in} f[1] = 1; f[2]= 1;\tag{3.1}\label{3.1} \end{equation}

The characteristic equation of this recurrence relation is given by

\begin{equation} r^2 – ar – b = 0.\tag{3.2}\label{3.2} \end{equation}

It is well known that the solution to this Eq.\eqref{3.2} is given by

\begin{equation*} f[n] = C[R(a,b)^n – R_s(a,b)^n] \end{equation*}

where,

\begin{equation*} R(a,b) = \displaystyle{\frac{a +\sqrt{a^2 + 4b}}{2}} \end{equation*}

is the positive real root. The other root of the equation is

\begin{equation*} R_s = – \frac{b}{R(a,b)} \end{equation*}

and

\begin{equation*} C = \displaystyle{\frac{1}{\sqrt{a^2 + 4b}}} \end{equation*}

We note that,

\begin{align} R(a,b) &\geq \varphi \hspace{0.1in} {\rm for all positive integers} \hspace{0.1in} a, b \tag{3.3}\label{3.3}\\ R(a,b) &= \varphi \hspace{0.1in}{\rm when}\hspace{0.1in} a = b = 1\tag{3.4}\label{3.4}\\ & \quad\quad {(\rm classical\, Fibonacci\, sequence)}\nonumber \end{align}

We further observe that the ratio of successive terms of this sequence converges to $R(a,b)$, i.e.,

\begin{equation} \lim_{k \rightarrow \infty} \frac{f[k+1]}{f[k]} = R(a,b)\tag{3.5}\label{3.5} \end{equation}

As in section 2, for any positive integer $N$, consider the above sequence, of length $N$, i.e.,

$$f[1],f[2], \ldots, f[N]$$

and define probability mass functions,

$$ p_{_{\bar{N}}}(n)[1],p_{_{\bar{N}}}(n)[2], \ldots, p_{_{\bar{N}}}(n)[N] $$

as

\begin{equation} p_{_{\bar{N}}}(n) = \frac{f[n]}{\displaystyle{\sum_{k =1}^N f[k]}} \hspace{0.3in} \forall n = 1, 2, \ldots, N\tag{3.6}\label{3.6} \end{equation}

Consider a random integer, $\bar{X}$, in $\{1,2, \ldots, N\}$, such that

\begin{equation} P(\bar{X} = n) = p_{_{\bar{N}}}(n)\tag{3.7}\label{3.7} \end{equation}

Similarly let $\underline{X}$ be a random variable in $\{1,2, \ldots, N\}$, (with probabilities corresponding to the decreasing sequence) such that,

\begin{equation} P(\underline{X} = n) = \frac{f[N+1-n]}{\displaystyle{\sum_{k =1}^N f[k]}} = p_{_{\underline{N}}}(n) \hspace{0.3in} \forall n = 1, 2, \ldots, N\tag{3.8}\label{3.8} \end{equation}

In the rest of the paper, for short, we shall denote $R(a,b)$ by $R$ and $R_S(a,b)$ by $R_S$.

4 The Main Theorems on the Limiting Properties

We prove the following limiting properties.

Analogous to eq.(\ref{2.5}), we have,

Theorem 1.

\begin{equation*} \lim_{N \rightarrow \infty} E(\bar{X}) = \infty \end{equation*}

Even though $E(\bar{X})$ grows as $N$ increases, its variance still converges. In fact, we have,

Theorem 2.

\begin{equation*} \lim_{N \rightarrow \infty} Var(\bar{X}) = \frac{R}{(R-1)^2} \end{equation*}

In the case of $\underline{X} $, both $E(\underline{X})$ and $Var(\underline{X})$ converge as $N \rightarrow \infty$ and the limit of $Var(\underline{X})$ is the same as that of $Var(\bar{X})$. We have, analogous to eq.(\ref{2.7}) and eq.(\ref{2.8}), the following limits.

Theorem 3.

\begin{equation}\nonumber \lim_{N \rightarrow \infty} E(\underline{X}) = \frac{R}{(R-1)} \end{equation}

Theorem 4.

\begin{equation}\nonumber \lim_{N \rightarrow \infty} Var(\underline{X}) = \frac{R}{(R-1)^2} \end{equation}

We, then, easily observe using these properties that when $a = b = 1$, the limits of Theorem.(1), Theorem.(2) and Theorem.(3) reduce to the limits, eq.(\ref{2.5}), eq.(\ref{2.7}), eq.(\ref{2.8}), obtained for the Fibonacci sequence, by Neal [1], described in section 2. Using eq.(\ref{3.3}) and eq.(\ref{3.4}), we can prove the following optimality properties of the Fibonacci sequence:

Theorem 5.

\begin{align*} \max{\left(\lim_{N\rightarrow \infty} E(\underline{X}): a, b \in \mathbb N \right)} &= \lim_{N \rightarrow \infty}\left(E(\underline{X}):a=b=1\right)\\ &= \varphi + 1 \end{align*}

Theorem 6.

\begin{align*} \max{\left (\lim_{N\rightarrow \infty}Var(\bar{X}): a,b \in \mathbb N\right)} &=\max{\left(\lim_{N\rightarrow \infty}Var(\underline{X}): a,b \in \mathbb N\right)}\\ &= \lim_{N \rightarrow \infty}\left(Var(\underline{X}):a=b=1\right)= 2\varphi + 1 \end{align*}

We now proceed to prove these theorems.

5 Some Notations Used in the Following Sections

In order to prove the aforesaid theorems, we make use of certain finite sums, presented in Appendix.A and Appendix.B. We list here, some of the notations used in the subsequent sections.

Increasing sequence Decreasing Sequence
$\bar{S} = \displaystyle{\sum_{n=1}^{N}}f[n]$ $\underline{S} = \displaystyle{\sum_{n=1}^{N}}f[N+1-n]$
$\bar{S}_1 = \displaystyle{\sum_{n=1}^{N}}n f[n]$ $\underline{S}_1 = \displaystyle{\sum_{n=1}^{N}}n f[N+1-n]$
$\bar{S}_2 = \displaystyle{\sum_{n=1}^{N}}n^2 f[n]$ $\underline{S}_2 = \displaystyle{\sum_{n=1}^{N}}n^2 f[N+1-n]$

6  Proofs of Theorems Related to Distributions Induced by Increasing Sequences

We look at the mean and variance of the random variable $\bar{X}$, defined as in section 2.

THEOREM 1:

\begin{equation*} \displaystyle{\lim_{N \rightarrow \infty}} E(\bar{X}) = \infty \end{equation*}

Proof :

We have,

\begin{equation} E(\bar{X}) = \frac{\bar{S}_1}{\bar{S}}\tag{6.1}\label{6.1} \end{equation}

Using eq.(\ref{B.8}) and eq.(\ref{B.6}), we get

\begin{align} E(\bar{X})&\sim \frac{(NR^{N+2}-(N+1)R^{N+1}+R)(R-1)}{(R-1)^2 R^{N+1}}\nonumber\\ &\sim \frac{NR-N-1}{R-1}\nonumber\\ \Rightarrow E(\bar{X}) &\sim N – \frac{1}{R-1}\tag{6.2}\label{6.2}\\ \nonumber E(\bar{X}) &\sim \mathcal{O}(N) \end{align}

Theorem 1, now follows from eq.(\ref{6.2}).

We also observe the following:

If we now define $\bar Y$ = $(N+1)- \bar{X}$, so that $\bar{Y}$ is also a random variable taking value 1, 2, 3, $\ldots$, $N$ and $\bar{X}$ has been in a sense centralized, then by eq.(\ref{6.2}),

\begin{equation*} E(\bar{Y}) \sim 1 + \frac{1}{R-1} = \frac{R}{R-1} \end{equation*}

Hence

\begin{equation*} \displaystyle{\lim_{N \rightarrow \infty}} E(\bar{Y}) = \frac{R}{R-1} \end{equation*}

This $\bar{Y}$ corresponds to $\underline{X}$, which we describe in sec.7.

THEOREM 2:

\begin{eqnarray*} \lim_{N \rightarrow \infty} Var(\bar{X}) = \frac{R}{(R -1)^2} \end{eqnarray*}

Proof :

We have,

\begin{equation} E(\bar{X}^2) = \frac{\bar{S}_2}{\bar{S}}\tag{6.3}\label{6.3} \end{equation}

Using eq.(\ref{B.10}) and eq.(\ref{B.6}), we get

\begin{equation} E(\bar{X}^2) \sim \frac{N^2(R-1)^2 – 2N(R-1) + R+1}{(R-1)^2}\tag{6.4}\label{6.4} \end{equation}

Using eq.(\ref{6.2}) and eq.(\ref{6.4}), we get

\begin{align*} Var(\bar{X})&= E(\bar{X}^2)-E(\bar{X})^2\nonumber \\ &\sim \frac{N^2(R-1)^2 – 2N(R-1) + R+1}{(R-1)^2}-\left(N – \frac{1}{R-1}\right)^2\nonumber\\ \Rightarrow \lim_{N \rightarrow \infty}Var(\bar{X})& = \frac{(R+1)-1}{(R-1)^2}\nonumber \end{align*}

Thus, we get the limit of the variance as,

\begin{equation} \lim_{N \rightarrow \infty}Var(\bar{X}) = \frac{R}{(R-1)^2}\tag{6.5}\label{6.5} \end{equation}

It is interesting to note from eq.(\ref{6.2}) and eq.(\ref{6.5}) that, even though the mean increases linearly as the length of the sequence, the variance converges, to a function of $R$.

7 Proofs of Theorems Related to Distributions Induced by Decreasing Sequences

In this section, we look at the probability distribution generated by reversing the sequence values. We recall that the probability of the random variable $\underline{X}$ taking a value $n$ was defined as,

\begin{equation} P(\underline{X} = n) =\frac{f[N+1-n]}{\displaystyle{\sum_{k=1}^{N}f[N+1-k]}} = p_{_{\underline{N}}}(n)\tag{7.1}\label{7.1} \end{equation}

THEOREM 3:

\begin{eqnarray*} \displaystyle{\lim_{N \rightarrow \infty}}E(\underline{X}) = 1 + \displaystyle{\frac{1}{R-1}} = \displaystyle{\frac{R}{R-1}} \end{eqnarray*}

Proof :

We have,

\begin{equation} E(\underline{X}) = \frac{\underline{S}_1}{\underline{S}}\tag{7.2}\label{7.2} \end{equation}

From eq.(\ref{B.13}), we get

\begin{align} E(\underline{X}) &= \frac{(N+1)\bar{S} – \bar{S}_1}{\bar{S}}\nonumber\\ &= (N+1) – \frac{\bar{S}_1}{\bar{S}}\nonumber\\ &\sim (N+1) – (N – \frac{1}{R-1}) \hspace{0.1in}{\rm by\hspace{0.1in} eq.(\ref{6.2}})\nonumber\\ \Rightarrow \lim_{N\rightarrow \infty}E(\underline{X}) &= 1 + \displaystyle{\frac{1}{R-1}} = \displaystyle{\frac{R}{R-1}}\tag{7.3}\label{7.3} \end{align}

THEOREM 4:

\begin{eqnarray*} \displaystyle{\lim_{N \rightarrow \infty}}E(\underline{X}^2) = 1 + \displaystyle{\frac{3R-1}{(R-1)^2}} \end{eqnarray*}

Proof :

\begin{equation} Var(\underline{X}) = E(\underline{X}^2) – E(\underline{X})^2\tag{7.4}\label{7.4} \end{equation}

Using eq.(\ref{B.14}) we first obtain $E(\underline{X}^2)$.

\begin{align} E(\underline{X}^2) &= \frac{\bar{S}_2}{\underline{S}} \nonumber\\ &\sim \frac{(N+1)^2\bar{S}}{\bar{S}} – \frac{2(N+1)\bar{S}_1}{\bar{S}} + \frac{\bar{S}_2}{\bar{S}}\nonumber\\ &\sim (N+1)^2 – 2(N+1)E(\bar{X}) +E(\bar{X}^2)\nonumber\\ &\sim (N+1)^2 – 2(N+1)\left(N-\frac{1}{R-1}\right) + \left(\frac{N^2(R-1)^2 – 2N(R-1)+(R+1)}{(R-1)^2}\right)\nonumber\\ &\sim \frac{(R-1)^2 +3R -1}{(R-1)^2}\nonumber \end{align}

\begin{equation} \Rightarrow \lim_{N \rightarrow \infty}E(\underline{X}^2) = 1 + \displaystyle{\frac{3R-1}{(R-1)^2}} \tag{7.5}\label{7.5} \end{equation}

From eq.(\ref{7.3}) and eq.(\ref{7.5}), we get

\begin{align} Var(\underline{X}) &= E(\underline{X}^2) – E(\underline{X})^2\nonumber\\ &\rightarrow 1 + \frac{3R-1}{(R-1)^2} – \frac{R^2}{(R-1)^2}\nonumber\\ \Rightarrow \lim_{N \rightarrow \infty}Var(\underline{X}) &= \frac{R}{(R-1)^2}\tag{7.6}\label{7.6} \end{align}

Thus, we find that, the limit of the variance of the probability distribution with probability defined by eq.(\ref{7.1}) to be a simple function $R$, the limit of the ratio of successive elements.

8 Mean and Variance of Discrete Probability Distributions Induced by Fibonacci Sequence

Now, we look at the probability distribution induced by the standard Fibonacci sequence. For such a distribution, we obtain the value of mean and variance,using eq.(\ref{6.2}) and eq.(\ref{7.5}) respectively, by using $a = 1 $, $b = 1$, and $R = \varphi$.

8.1  Distributions Induced by Increasing Sequence

By eq.(\ref{6.2}) and eq.(\ref{6.5}), we have

$$ E(\bar{X}) \sim \mathcal{O}(N) $$

and

\begin{align} \lim_{N \rightarrow \infty}Var(\bar{X}) &= \frac{R}{(R-1)^2} = \frac{\varphi}{(\varphi-1)^2}\nonumber\\ \Rightarrow \lim_{N \rightarrow \infty}Var(\bar{X}) &= 2\varphi+1\tag{8.1}\label{8.1} \end{align}

Neal [1] looks at the mean and variance of a Fibonacci distribution. It may be pointed out that the fact that the variance converges in this case was not observed by Neal. The above derivations show that, in this case, though the mean increases linearly as the length of the sequence, the variance converges to a simple function of the golden ratio $\varphi$.

8.2 Distributions Induced by Decreasing Sequence

By eq.(\ref{7.3}), we have

\begin{equation} \nonumber \displaystyle{\lim_{N \rightarrow \infty}}E(\underline{X}) = \displaystyle{\frac{R}{R-1}} = \varphi + 1 \end{equation}

From eq.(\ref{7.6}), we have

\begin{align} \displaystyle{\lim_{N \rightarrow \infty}}Var(\underline{X}) &= \frac{R}{(R-1)^2} =\frac{\varphi}{(\varphi-1)^2} \nonumber \\ \Rightarrow \displaystyle{\lim_{N \rightarrow \infty}}Var(\underline{X}) &= 2\varphi + 1\tag{8.2}\label{8.2} \end{align}

Comparing eq.(\ref{8.1}) and eq.(\ref{8.2}), we find that, in the case of the classical Fibonacci sequence, the variance of the distribution converges to the same value, irrespective of whether the probability values are increasing or decreasing.

In the following sections, we make a few observations and remarks related to the classical Fibonacci sequence.

9 Ratio of Variance to Mean

We observe the curious fact that, from Theorem.(1) and Theorem.(2),

\begin{equation} \lim_{N\rightarrow \infty} \frac{Var(\underline{X})}{E(\underline{X})} = \frac{1}{R-1}\tag{9.1}\label{9.1} \end{equation}

In the case $a = b = 1$, that is, in the case of the distribution induced by the Fibonacci sequence, since $R = \varphi$

\begin{equation} \lim_{N\rightarrow \infty} \frac{Var(\underline{X})}{E(\underline{X})} = \frac{1}{\varphi-1} = \varphi\tag{9.2}\label{9.2} \end{equation}

Thus the ratio of the variance of $\underline{X}$ to the expectation of $\underline{X}$ also converges to the Golden Ratio, $\varphi$.

10 Optimality Probabilistic Limit Properties of the Fibonacci Sequence

In this section, we establish certain optimal probabilistic limit properties of the classical Fibonacci sequence.

10.1 Mean

THEOREM 5:

\begin{equation*} \max{\left(\lim_{N\rightarrow \infty} E(\underline{X}): a, b \in \mathbb N\right)} = \lim_{N \rightarrow \infty}\left(E(\underline{X}) : a,b = 1\right) = \varphi + 1 \end{equation*}

Proof :

We know that

\begin{align} R &\geq \varphi\nonumber\\ \Rightarrow R-1 &\geq \varphi -1 \nonumber\\ \Rightarrow \frac{1}{R-1} &\leq \frac{1}{\varphi-1}\tag{10.1}\label{10.1} \end{align}

But $\varphi$ = $\displaystyle{\frac{1}{\varphi-1}}$.

Hence, from eq.(\ref{10.1}), we get

\begin{align} \frac{1}{R-1} \leq \varphi\nonumber\\ \Rightarrow 1 + \frac{1}{R-1} &\leq 1+\varphi\tag{10.2}\label{10.2}\\ \displaystyle{\frac{R}{R-1}} &\leq \varphi + 1 \nonumber\\ \Rightarrow \lim_{N\rightarrow \infty}\left(E(\underline{X}):a,b\in \mathbb N\right) &\leq \lim_{N\rightarrow \infty}\left(E(\underline{X}): a = b = 1\right)\tag{10.3}\label{10.3} \end{align}

Thus,

$\max{\left(\displaystyle{\lim_{N\rightarrow \infty}} E(\underline{X}): a, b \in \mathbb N\right)} = \displaystyle{\lim_{N \rightarrow \infty}}\left(E(\underline{X}) : a,b = 1\right) = \varphi + 1$

10.2  Variance

Among the family of distributions, induced by second order linear recurrence relations with positive integer coefficients, $a$ and $b$, the Fibonacci sequence gives the maximum limit for $Var(\underline{X})$, i.e.

THEOREM 6:

\begin{align} \max{\left(\lim_{N\rightarrow \infty} Var(\bar{X}): a,b \in \mathbb N\right)}&= \max{\left(\lim_{N\rightarrow \infty}Var(\underline{X}): a,b \in \mathbb N\right)}\tag{10.4}\label{10.4}\\ &= \lim_{N \rightarrow \infty}\left(Var(\underline{X}):a,b=1\right) = 2\varphi + 1\tag{10.5}\label{10.5} \end{align}

We prove this as follows:

Proof :

\begin{align} R &\ge \varphi\nonumber\\ \Rightarrow \frac{1}{R} &\le \frac{1}{\varphi}\nonumber\\ \Rightarrow -\frac{1}{R} &\ge – \frac{1}{\varphi}\nonumber\\ \Rightarrow 1-\frac{1}{R} &\ge 1 – \frac{1}{\varphi}\nonumber\\ \Rightarrow R\left(1-\frac{1}{R}\right)^2 &\ge \varphi\left(1 – \frac{1}{\varphi}\right)^2\nonumber\\ \Rightarrow \frac{1}{R\left(1-\frac{1}{R}\right)^2} &\le \frac{1}{\varphi\left(1 – \frac{1}{\varphi}\right)^2}\tag{10.6}\label{10.6} \end{align}

From eq.(\ref{10.6}), we get

\begin{align} \frac{R}{(R-1)^2} \le \frac{\varphi}{(\varphi-1)^2} = 2\varphi + 1\nonumber\\ \Rightarrow \frac{R}{(R-1)^2} &\le 2\varphi + 1\tag{10.7}\label{10.7}\\ \Rightarrow \lim_{N\rightarrow \infty} \left(Var(\underline{X}):a,b\in \mathbb N\right) &\leq \lim_{N\rightarrow \infty}\left(Var(\underline{X}): a = b = 1\right)\tag{10.8}\label{10.8} \end{align}

From eq.(\ref{10.8}), we conclude that the limit variance of discrete probability distributions, induced by decreasing sequence and generated using second order linear recurrence, is maximum for the one generated using Fibonacci sequence.

In the next section, we consider the probability distributions generated by higher order recurrence relation with positive integer coefficients.

11 Higher Order Recurrence Relation With Positive Integer Coefficients

From Section.6 and Section.7, one can observe that the mean and variance of the probability distributions, induced by general second order linear recurrence relation with positive integer coefficients, depend only on the largest positive real root, $R$, of the associated “characteristic equation”. It turns out that, even in the case of any other higher order recurrence relation with positive integer coefficients, it is the largest positive real root that determines the mean and variance. We now proceed to prove the same. Let

\begin{equation} f[n] = a_{n-1}f[n-1] + \ldots + a_{n-k}f[n-k] \hspace{0.3in} \forall a_i \in \mathbb{N}\tag{11.1}\label{11.1} \end{equation}

be a $k^{th}$ order recurrence relation. The characteristic equation of this recurrence relation is given by,

\begin{equation} f(x) = x^k – a_{n-1}x^{k-1}- \ldots – a_{n-k}\tag{11.2}\label{11.2} \end{equation}

Lemma 1.

Eq.(\ref{11.2}), has atleast one real positive root and if $\alpha$ is the largest positive real root, then all the other roots (real and complex) lie within the disc $|z| < \alpha$.

Using Lemma 1, it is easy to infer the following:

With $R = \alpha$,

  • The same asymptotic relations as in eq.(\ref{7.3}) and eq.(\ref{7.6}) hold.
  • The same limiting properties as in eq.(\ref{2.7}) and eq.(\ref{2.8}) hold.
  • The optimality properties of the Fibonacci sequence as in Theorem 5 and in Theorem 6 hold good. The reason is that, the largest positive real root, $\alpha > \varphi$, the golden ratio.

Thus, Theorem 5 can be generalized as

\begin{align*} &\max{\left(\lim_{N\rightarrow \infty} E(\underline{X}): a_i, i \in \mathbb N \right)}\\ &= \lim_{N \rightarrow \infty}\left(E(\underline{X}):a_1 = a_2 = 1, a_{i}=0, \forall i> 2\right)\\ &= \varphi + 1 \end{align*}

and Theorem 6 can be further generalized as

\begin{align*} &\max{\left(\lim_{N\rightarrow \infty}Var(\bar{X}): a_i, i \in \mathbb N\right)}\\ &= \max{\left(\lim_{N\rightarrow \infty}Var(\underline{X}): a_i, i \in \mathbb N\right)}\\ \nonumber &= \lim_{N \rightarrow \infty}\left(Var(\underline{X}):a_1=a_2=1, a_{i}=0,\forall i > 2\right) = 2\varphi + 1 \end{align*}

Now, we proceed to prove Lemma 1.

Proof :

By Descartes rule of signs, there exists a positive root. Since,

$ f(0) < 0$, $f(\infty) > 0$

Let $\alpha$ be the largest positive root.

11.1 α Is Simple Root

Claim: The root is simple.

Let $f(x)$ be as in eq.(\ref{11.2}). Since $\alpha$ is a root, we have

\begin{equation} \alpha^k – a_{n-1}\alpha^{k-1} + \ldots + a_{n-k} = 0\tag{11.3}\label{11.3} \end{equation}

Suppose, if $\alpha$ is a multiple root, then we must have

\begin{equation} f'(\alpha) = 0 \tag{11.4}\label{11.4} \end{equation}

\begin{equation} \Rightarrow k\alpha^{k-1}-(k-1)a_{n-1}\alpha^{k-2} + \ldots + a_{n-k+1} = 0\tag{11.5} \label{11.5} \end{equation}

Multiplying by $\alpha$, we get

\begin{align} &k\alpha^{k} – (k-1)a_{n-1}\alpha^{k-1} + \ldots + a_{n-k+1}\alpha = 0\nonumber\\ &\Rightarrow k\alpha^{k} = (k-1)a_{n-1}\alpha^{k-1} + \ldots + a_{n-k+1}\alpha\nonumber\\ &\Rightarrow \quad <\quad k\left( a_{n-1}\alpha^{k-1} + \ldots +a_{n-k+1}\alpha \right)\nonumber\\ &\Rightarrow \quad < \quad k\left( a_{n-1}\alpha^{k-1} + \ldots +a_{n-k+1}\alpha + a_{n-k}\right)\nonumber\\ &\Rightarrow \alpha^{k} < a_{n-1}\alpha^{k-1} + \ldots + a_{n-k+1}\alpha + a_{n-k}\nonumber\\ &\Rightarrow\alpha^{n} < \alpha^{n} \nonumber \end{align}

This contradicts eq.(\ref{11.3}). Hence $\alpha$ must be a simple root.

11.2 All Roots Lie Within Circle of Radius |α|

Now, we prove that all other roots of eq.(\ref{11.2}) lie within the circle of radius $\alpha$. Consider eq.(\ref{11.2}), the characteristic equation of the corresponding $k^{th}$ order recurrence relation with positive integer coefficients. Since $\alpha$ is a root,

\begin{equation*} f(\alpha) = 0 \end{equation*}

Also, we have

\begin{align} \displaystyle{\lim_{x\rightarrow \infty}} f(x) &= \infty \nonumber\\ \Rightarrow f(x) &\ge 0, \hspace{0.3in} \forall x \ge \alpha\tag{11.6}\label{11.6}\\ {\rm and}\hspace{0.1in} f(x) &> 0 \hspace{0.3in} \forall x > \alpha\tag{11.7}\label{11.7} \end{align}

Let $\beta$ be any root (real or complex) of eq.(\ref{11.2}). Clearly, $\beta$ cannot be zero, because,

\begin{equation}\nonumber f(0) = -a_{n-k} < 0 \end{equation}

Let $b$ = $|\beta|$.

Claim: $b$ $\le$ $\alpha$

Reason: Suppose $b$ $>$ $\alpha$.

Since $\beta$ is a root, we have

\begin{align*} f(\beta) = 0 \Rightarrow \beta^{k} &= a_{n-1}\beta^{k-1} + \ldots + a_{n-k}\beta^{n-k} \nonumber\\ \Rightarrow |\beta|^{k} &= |a_{n-1}\beta^{k-1} + \ldots + a_{n-k}\beta^{n-k}|\nonumber\\ \Rightarrow \beta^{k} &\leq a_{n-1}|\beta|^{k-1} + \ldots + a_{n-k}|\beta|^{n-k}\nonumber\\ \end{align*}

\begin{align} \Rightarrow \beta^{k}-a_{n-1}|\beta|^{k-1} – \ldots – a_{n-k}|\beta|^{n-k} &\leq 0 \nonumber\\ \Rightarrow b^{k}-a_{n-1}b^{k-1} – \ldots – a_{n-k}b^{n-k} &\leq 0 \nonumber\\ \Rightarrow f(b) &\leq 0\tag{11.8}\label{11.8} \end{align}

However, since $b$ $>$ $\alpha$, by eq.(\ref{11.7}), $f(b)$ $>$ 0. Thus, we get a contradiction and hence $b$ $\le$ $\alpha$.

Claim: $b$ = $\alpha$

Since $\beta$ is a root, we have,

\begin{align} \beta^k &= a_{n-1}\beta^{k-1} + \ldots + a_{n-k}\beta^{n-k}\nonumber\\ &\Rightarrow |\beta|^k = |a_{n-1}\beta^{k-1} + \ldots + a_{n-k}\beta^{n-k}|\nonumber \end{align}

Since we have assumed that $|\beta|$=$b$=$a$,

\begin{align*} \alpha^k &= |a_{n-1}\beta^{k-1}+ \ldots + a_{n-k}\beta^{n-k}| \end{align*}

\begin{align} a_{n-1}\alpha^{k-1}+ \ldots + a_{n-k} &= |a_{n-1}\beta^{k-1}+ \ldots + a_{n-k}| \hspace{0.1cm}{\rm by \hspace{0.1cm} eq.~(\ref{11.3})}\tag{11.9} \label{11.9}\\ a_{n-1}|\beta|^{k-1}+ \ldots + a_{n-k} &= |a_{n-1}\beta^{k-1}+ \ldots + a_{n-k}|\tag{11.10}\label{11.10} \end{align}

$\Rightarrow a_n-1\beta^{k-1}, \ldots, a_{n-k}$ are all complex numbers in the same direction.

$\Rightarrow a_{n-k}, a_{n-k+1} \beta$ are real positive

$\Rightarrow \beta$ is real positive

$\Rightarrow \beta = \alpha$.

Thus, based on the above claims, we find that

  • the only root on the circle $|z|$ = $\alpha$ is $z$ = $\alpha$ and there is no root outside this circle
  • all roots not equal to $\alpha$ are inside the circle $|z|$ = $\alpha$.

11.3 α is Strictly Greater Than the Golden Ratio φ

We prove that the largest positive real root of the characteristic equation, corresponding to higher order linear recurrence relation with integer coefficients, is greater than the golden ratio $\varphi$.

$$ \alpha^{k} = a_{n-1}\alpha^{k-1} + \ldots + a_{n-k}\alpha^{n-k} $$

Since all terms on the RHS are greater than 0

\begin{align} \Rightarrow \alpha^{k} &> a_{n-1}\alpha^{k-1} + a_{n-2}\alpha^{k-2}\nonumber \\ \Rightarrow \alpha^{2} &> a_{n-1}\alpha + a_{n-2}\nonumber \end{align}

As $a_{n-1}$, $a_{n-2}$ are positive integers, we see that,

\begin{align} \Rightarrow \alpha^{2} &> \alpha + 1\nonumber\\ \Rightarrow \alpha^{2} – \alpha – 1\ &> 0\tag{11.11}\label{11.11} \end{align}

From the fact that, $\varphi$, the golden ratio, is the largest positive root of $x^2-x-1 = 0$ and that $x^2-x-1 > 0$ for $x > \varphi$, it follows that $\alpha$ is always greater than $\varphi$.

12  Convergence in Distribution

It must be noted that the distribution $\{p_{_{\underline{N}}}(n)\}, 1 \leq n \leq N$, converges to a geometric distribution on $\mathbb N = \{1,2,3, \ldots\}$. More precisely, we have the following:

Let $Y$ be a random integer in $\mathbb N$, such that

\begin{equation} p(n) = P(Y=n) = \rho^n \left(\displaystyle{\frac{1-\rho}{\rho}}\right)\tag{12.1}\label{12.1} \end{equation}

where $\rho = \displaystyle{\frac{1}{R}}$. We have,

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}\rho^n} = \displaystyle{\frac{\rho}{1-\rho}}\tag{12.2}\label{eq-12.2} \end{equation}

and hence

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}n\rho^{n-1}} = \frac{\mathrm{d}}{\mathrm{d}\rho}\left(\displaystyle{\frac{\rho}{1-\rho}}\right) = \displaystyle{\frac{1}{(1-\rho)^2}} \end{equation*}

Thus,

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}n\rho^{n}} = \displaystyle{\frac{\rho}{(1-\rho)^2}} \end{equation*}

Consequently,

\begin{align} E(Y) = \displaystyle{\sum_{n=1}^{\infty}n\rho^{n}}\left(\displaystyle{\frac{1-\rho}{\rho}}\right) &= \displaystyle{\frac{\rho}{(1-\rho)^2}}\left(\displaystyle{\frac{1-\rho}{\rho}}\right)\nonumber\\ &= \displaystyle{\frac{1}{1-\rho}}\nonumber\\ &= \displaystyle{\frac{1}{1-\displaystyle{\left(\frac{1}{R}\right)}}}\nonumber\\ \Rightarrow E(Y) &= \displaystyle{\frac{R}{R-1}}\tag{12.3}\label{12.3} \end{align}

Similarly we can see that

\begin{equation} Var(Y^2) = \displaystyle{\frac{R}{(R-1)^2}}\tag{12.4}\label{12.4} \end{equation}

Thus, we see that,

\begin{align} \displaystyle{\lim_{N \rightarrow \infty}}E(\underline{X}) &= E(Y)\nonumber\\ \displaystyle{\lim_{N \rightarrow \infty}}Var(\underline{X}) &= Var(Y)\nonumber \end{align}

We now show that the random variable $\underline{X}$ converges to the random variable $Y$ in distribution.

We have for every $n \in \mathbb N$,

\begin{align} p_{_{\underline{N}}}(n) &\sim \left(\displaystyle{\frac{R^{N+1-n}}{R^{N+1}- R}}\right)(R-1)\nonumber\\ &= \left(\displaystyle{\frac{R^{-n}}{1-R^{-N}}}\right)(R-1)\nonumber\\ &= \left(\displaystyle{\frac{\rho^{n}}{1-\rho^{N}}}\right)\left(\displaystyle{\frac{1}{\rho}}-1\right)\nonumber\\ &= \left(\displaystyle{\frac{\rho^{n}}{1-\rho^{N}}}\right)\left(\displaystyle{\frac{1-\rho}{\rho}}\right)\nonumber \end{align}

Thus,

\begin{equation*} p_{_{\underline{N}}}(n) \sim \left(\displaystyle{\frac{\rho^{n}}{1-\rho^{N}}}\right)\left(\displaystyle{\frac{1-\rho}{\rho}}\right) \end{equation*}

Since $\displaystyle{\lim_{N \rightarrow \infty}}\rho^N = 0$ as $\rho = \displaystyle{\frac{1}{R}} < 1$, we have

\begin{equation} \displaystyle{\lim_{N \rightarrow \infty}}p_{_{\underline{N}}}(n) = \rho^{n}\left(\displaystyle{\frac{1-\rho}{\rho}}\right)\tag{12.5}\label{12.5} \end{equation}

From eq.(\ref{12.1}) and eq.(\ref{12.5}) we see that

\begin{equation} \displaystyle{\lim_{N \rightarrow \infty}}p_{_{\underline{N}}}(n) = p(n) \hspace{0.2in} \forall n \in \mathbb N\tag{12.6}\label{12.6} \end{equation}

and thus $\underline{X}$ converges to $Y$ in distribution.

13   Convergence of Moments

In the previous subsection, we observed that the distributions generated by second order linear recurrence relation converge to a geometric distribution, i.e.,

  • $\underline{X}$ converges to $Y$ in distribution and
  • $E(\underline{X})$ converges to $E(Y)$
  • $E(\underline{X}^2)$ converges to $E(Y^2)$ (and hence $Var(\underline{X})$ converges to $Var(Y)$).

Now, we prove that all the moments of $\underline{X}$ converge to the corresponding moment of $Y$, as $N \rightarrow \infty$.

Proof :

For any positive integer $k$, we have,

\begin{equation} E(\underline{X}^k) \sim \displaystyle{\frac{\displaystyle{\sum_{n=1}^{N}}n^k R^{N+1-n}}{\displaystyle{\sum_{n=1}^{N}}R^{N+1-n}}}\tag{13.1}\label{13.1} \end{equation}

We have,

\begin{equation} \displaystyle{\sum_{n=1}^{N}}R^{N+1-n} = \displaystyle{\frac{R^{N+1}-R}{R-1}}\tag{13.2}\label{13.2} \end{equation}

Also,

\begin{equation} \displaystyle{\sum_{n=1}^{N}}n^kR^{N+1-n} = R^{N+1}\displaystyle{\sum_{n=1}^{N}n^kR^{-n}}\tag{13.3}\label{13.3} \end{equation}

Substituting eq.(\ref{13.2}) and eq.(\ref{13.3}) in eq.(\ref{13.1}), we get

\begin{eqnarray} E(\underline{X}^k) &\sim& \left(\displaystyle{\frac{R^{N+1}\displaystyle{\sum_{n=1}^{N}n^kR^{-n}}}{R^{N+1}-R}}\right)(R-1)\nonumber\\ &=& \left(\displaystyle{\frac{R^{N+1}\displaystyle{\sum_{n=1}^{N}n^kR^{-n}}}{R^{N+1}(1-R^{-N})}}\right)(R-1)\nonumber\\ &=& \displaystyle{\frac{\displaystyle{\sum_{n=1}^{N}}n^k\rho^{n}}{1-R^{-N}}}\left(\frac{1-\rho}{\rho}\right)\nonumber \end{eqnarray}

Hence, as $N \rightarrow \infty$,

\begin{eqnarray} E(\underline{X}^k) &\longrightarrow& \displaystyle{\sum_{n=1}^{N}n^k\rho^{n}}\left(\frac{1-\rho}{\rho}\right) \hspace{0.2in} {\rm because}\hspace{0.2in} R^{-N}\rightarrow 0\nonumber\\ &=& E(Y^k)\nonumber \end{eqnarray}

Thus, we have for every non-negative integer $k$,

$E(\underline{X}^k) \longrightarrow E(Y^k),$

showing that all the moments of $\underline{X}$ converge to the corresponding moments of $Y$.

13.1  Limits of Moments in the Case of Classical Fibonacci Sequence

The moments of the probability distribution induced by classical Fibonacci sequence converge to a linear function of the Golden ratio, $\varphi$.

Proof :

We have,

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}}x^n = \displaystyle{\frac{x}{1-x}} \hspace{0.3in} {\rm for} \hspace{0.2in} |x| < 1. \end{equation*}

which on differentiation gives

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}}nx^{n-1} = \displaystyle{\frac{1}{(1-x)^2}}\tag{13.4}\label{13.4} \end{equation}

From eq.(\ref{13.4}), we get

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}}nx^{n} = \displaystyle{\frac{x}{(1-x)^2}}\tag{13.5}\label{13.5} \end{equation}

Then,

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}}nx^{n}\left(\displaystyle{\frac{1-x}{x}}\right) = \displaystyle{\frac{1}{(1-x)}}\tag{13.6}\label{13.6} \end{equation}

Similarly, differentiating eq.(\ref{13.5}), we get

\begin{eqnarray} \displaystyle{\sum_{n=1}^{\infty}}n^2x^{n-1} &=& \displaystyle{\frac{(1-x)^2 + 2x(1-x)}{(1-x)^4}}\nonumber\\ = \displaystyle{\frac{(1-x)+2x}{(1-x)^3}}&=& \displaystyle{\frac{1+x}{(1-x)^3}}\tag{13.7}\label{13.7} \end{eqnarray}

and hence,

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}}n^2x^{n} = \displaystyle{\frac{(1+x)x}{(1-x)^3}} \end{equation*}

and thus,

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}}n^2x^n\left(\frac{1-x}{x}\right) = \displaystyle{\frac{1+x}{(1-x)^2}}\tag{13.8}\label{13.8} \end{equation}

We shall now show, by induction, that in general, for any positive integer $k$,

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}}n^k x^n \left(\frac{1-x}{x}\right) = \displaystyle{\frac{P_{_{k-1}}(x)}{(1-x)^k}}\tag{13.9}\label{13.9} \end{equation}

where $P_{_{k-1}}(x)$ is a polynomial in $x$ of degree $k-1$.

We have from eq.(\ref{13.6}) and eq.(\ref{13.7}), that the result eq.(\ref{13.9}) is true for $k = 1$ and $k = 2$. Thus, it is enough to show that if eq.(\ref{13.9}) is true for some $k = r$, then it is also true for $k = r+1$. Suppose eq.(\ref{13.9}) is true for $k = r$, then

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}}n^r x^n \left(\frac{1-x}{x}\right) = \displaystyle{\frac{P_{_{r-1}}(x)}{(1-x)^r}} \end{equation*}

Hence, we get,

\begin{equation} \displaystyle{\sum_{n=1}^{\infty}}n^r x^n = \frac{xP_{_{r-1}}(x)}{(1-x)^r}\tag{13.10}\label{13.10} \end{equation}

On differentiating eq.(\ref{13.10}), we get,

\begin{align} \displaystyle{\sum_{n=1}^{\infty}}n^{r+1}x^{n-1} &= \frac{(1-x)^{r+1}\{P_{_{r-1}}(x)+P_{_{r-1}}'(x)\}+ xP_{_{r-1}}(x)r(1-x)^r}{(1-x)^{2r+2}}\nonumber\\ &= \frac{(1-x)\{P_{_{r-1}}(x) + xP_{_{r-1}}'(x)\}+ xP_{_{r-1}}(x)r}{(1-x)^{r+2}}\nonumber\\ &= \frac{P_{_r}(x)}{(1-x)^{r+2}}\tag{13.11}\label{13.11} \end{align}

where

\begin{equation} P_{_r}(x) = (1-x)\{P_{_{r-1}}(x) + xP_{_{r-1}}'(x)\} + xP_{_{r-1}}(x)r\tag{13.12}\label{13.12} \end{equation}

is a polynomial of degree $r$. From eq.(\ref{13.11}), we get,

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}}n^{r+1}x^n = \frac{xP_{_r}(x)}{(1-x)^{r+2}} \end{equation*}

and hence,

\begin{equation*} \displaystyle{\sum_{n=1}^{\infty}}n^{r+1}x^n\left(\frac{1-x}{x}\right) = \frac{P_{_r}(x)}{(1-x)^{r+1}} \end{equation*}

and thus proving that if eq.(\ref{13.9}) is true for $k = r$, then it is also true for $k = r+1$. Thus by induction, we get eq.(\ref{13.9}) is true for all $k$.

From eq.(\ref{13.9}), we get

\begin{align} E(Y^k) &= \displaystyle{\sum_{n=1}^{\infty}}n^k \rho^n \left(\frac{1-\rho}{\rho}\right)\nonumber\\ &= \frac{P_{_{k-1}}(\rho)}{(1-\rho)^{k}}\nonumber \end{align}

and hence

\begin{equation} \tag{13.13}\label{13.13} \displaystyle{\lim_{N \rightarrow \infty}}E(\underline{X}^k) = E(Y^k) = \displaystyle{\frac{P_{_{k-1}}(\rho)}{(1-\rho)^k}} \end{equation}

eq.(\ref{13.13}) is a rational function of $\rho$ and hence a rational function of $R$. In particular, for the classical Fibonacci sequence, we have

\begin{equation*} \displaystyle{\lim_{N \rightarrow \infty}} E(\underline{X}^k) = E(Y^k) = \frac{P_{_{k-1}}\left(\displaystyle{\frac{1}{\varphi}}\right)}{\left(1-\displaystyle{\frac{1}{\varphi}}\right)^k} \end{equation*}

Since $\displaystyle{\frac{1}{\varphi}} = \varphi-1$, we get

\begin{align} \displaystyle{\lim_{N \rightarrow \infty}} E(\underline{X}^k) = E(Y^k) &= \left(\frac{P_{_{k-1}}(\varphi-1)}{(\varphi-1)^k}\right)\varphi^k\nonumber\\ &= \varphi^{2k} P_{_{k-1}}(\varphi-1)\nonumber\\ &= Q(\varphi), \hspace{0.1in}{\rm a polynomial in}\hspace{0.1in} \varphi\tag{13.14} \label{13.14} \end{align}

But, since $\varphi^2 = \varphi + 1$, all powers $\varphi^j$ for $j\ge2$ can be expressed as linear polynomials in $\varphi$ and hence we get any polynomial in $\varphi$ can be rewritten as a linear polynomial in $\varphi$. Thus,

\begin{align} \displaystyle{\lim_{N \rightarrow \infty}} E(\underline{X}^k) &= E(Y)\tag{13.15}\label{13.15}\\ &= A_k\varphi + B_k\tag{13.16}\label{eq-13.16} \end{align}

We now provide a detailed analysis about the location of the maximum in the sequence resulting from self linear convolution of linear recurrence relations with positive integer sequences.

14   Linear Convolution of Linear Recurrence Relations With Themselves

In the previous sections, we proved certain optimal properties of the classical Fibonacci sequence among the general $k$-th order recurrence relations with positive integer coefficients, with respect to the discrete probability distributions that they induced. In this section we bring out another fascinating property of the classical Fibonacci sequence. Let $x_{_n}$ be a finite length integer sequence, of length $N$, generated by a $k$-th order recurrence relation with positive integer coefficients. The location of maxima in the sequence, $y_{_n}$ resulting from the linear convolution of $x_{_n}$ with itself, can be only one of the following:

  • 2$N$-1, when the largest positive real root of the “characteristic equation” is less than 2
  • 2$N$-1, when the largest positive real root of the “characteristic equation” is equal to 2 and the length even.
  • $2N$ when the largest positive real root is equal to 2 and the sequence length is odd.
  • $2N$ when the largest positive real root is greater than 2.

We prove the above in the following sections.

15  Some Notations and Definitions

As mentioned earlier, while investigating the use of integer sequences for window functions in digital filtering [2], we observed that most of the integer sequences generated by $k$-th order recurrence relations, with positive integer coefficients, are non-decreasing. However, conventional classical window functions are symmetric, bounded and smooth. Though, integer sequences, mentioned as above, are bounded for finite length, they are not symmetric. Hence to be used as window functions, integer sequences are symmetrized. However, this does not guarantee a smooth profile for most of the integer sequences. In order to get a smooth profile, we do one of the following:

  • Perform linear convolution after symmetrizing the integer sequence about, say, $N/2$.
  • Perform linear convolution of the non-decreasing integer sequence and then symmetrically extend the resulting sequence about its maximum.

While in the first case, for any finite length, $N$, one can symmetrize at half the length, the second case requires the location of maximum in the sequence resulting from the linear convolution. In the sections to follow, we obtain the location of maxima in the sequence resulting from the linear convolution of $x_{_n}$ with itself. In particular, we look at the family of sequences generated using $k$-th order linear recurrence relation. First, we look at the second order case and then generalize the result to higher order recurrence relations.

15.1 Notations

Let

\begin{align} x &= \{ x_{_n} \}_{n=1}^{^{N}}\tag{15.1}\label{15.1}\\ y &= \{y_{_n}\}_{n=2}^{^{2N}}\tag{15.2} \label{15.2}\\ x_{_n} &= ax_{_{n-1}} + bx_{_{n-2}}, \hspace{0.2in} \forall a,b \in \mathbb N\tag{15.3}\label{15.3} \end{align}

The “$characteristic$” equation of the above is given by

\begin{equation} x^2 – ax – b = 0\tag{15.4}\label{15.4} \end{equation}

The largest positive real root of the above equation is as below:

\begin{equation} R = a + \displaystyle{\frac{\sqrt{a^2+4b}}{2}}\tag{15.5}\label{15.5} \end{equation}

15.2  Definitions

The linear convolution of two sequences is given by

\begin{align} y_{_n} &= \displaystyle{\sum_{k=1}^{n-1}x_{_k} x_{_{n-k}}} \hspace{0.2in} 2 \leq n\leq N\tag{15.6}\label{15.6}\\ y_{_{N+j}} &= \displaystyle{\sum_{k=j}^{N}x_{_k} x_{_{N+j-k}}} \hspace{0.2in} 1 \leq j \leq N\tag{15.7}\label{15.7} \end{align}

For $2\leq n \leq N$, we have,

\begin{align} y_{_n} – y_{_{n-1}} &= \displaystyle{\sum_{k=1}^{n-1}}x_{_k}x_{_{n-k}} – \displaystyle{\sum_{k=1}^{n-2}}x_{_k}x_{_{n-1-k}}\tag{15.8}\label{15.8}\\ &= \displaystyle{\sum_{k=1}^{n-2}}x_{_k} (x_{_{n-k}}-x_{_{n-1-k}} )+ x_{_{n-1}}x_{_1}\tag{15.9}\label{15.9}\\ & > 0 \nonumber\\ \Rightarrow y_{_n} &> y_{_{n-1}} \hspace{0.2in} 1\leq n \leq N\tag{15.10}\label{15.10} \end{align}

From eq.(\ref{15.10}), we observe that the convolution sum is an increasing sequence for $1\leq n\leq N$.

Now we look at the eq.\ref{15.7}, for $j\geq 1$.

\begin{equation} y_{_{N+j}} – y_{_{N+j-1}} = \displaystyle{\sum_{k=j}^{N}}x_{_{k}}x_{_{N+j-k}} – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\tag{15.11}\label{15.11} \end{equation}

At this juncture, we revisit the general second order recurrence relation with positive integer coefficients, given in eq.(\ref{15.3}). We evaluate eq.(\ref{15.3}) for different possible values of $a$ and $b$ and hence compute the difference as in eq.(\ref{15.11}).

  1. $a = 1$
    1. $b = 1$
    2. $b = 2$
    3. $b > 2$
  2. $a >1$

16  a=1 , b =1 :

We look at case(Ai) that corresponds to $a = b = 1$. Eq.(\ref{15.3}), in this case, generates the elements of classical Fibonacci sequence. Eq.(\ref{15.3}) can be rewritten as

\begin{equation} x_{_n} = x_{_{n-1}} + x_{_{n-2}}\tag{16.1}\label{16.1} \end{equation}

$R$, the largest positive real root in the case of classical Fibonacci sequence corresponds to the golden ratio, $\varphi = \displaystyle{\left(\frac{1+\sqrt5}{2}\right)}$,

With the above conditions, eq.\ref{15.11} gives

\begin{align} y_{_{N+j}} – y_{_{N+j-1}} &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}x_{_{N+j-k}} – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\tag{16.2}\label{16.2}\\ &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}(x_{_{N+j-1-k}}+x_{_{N+j-2-k}}) – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\nonumber\\ &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}x_{_{N+j-2-k}} – x_{_{j-1}}x_{_N}\nonumber \end{align}

Suppose, $j \leq N-1$,

\begin{align*} y_{_{N+j}} – y_{_{N+j-1}} &\geq x_{_{N-1}}x_{_{j-1}} + x_{_N}x_{_{j-2}} – x_{_{j-1}}x_{_N}\nonumber\\ &= x_{_{N-1}}x_{_{j-1}} + x_{_N}(x_{_{j-1}}-x_{_{j-3}})- x_{_{j-1}}x_{_N}\nonumber\\ &= x_{_{N-1}}x_{_{j-1}} – x_{_{j-3}}x_{_N}\nonumber\\ &= x_{_{N-1}}(x_{_{j-2}}+x_{_{j-3}}) – x_{_{j-3}}(x_{_{N-1}}+x_{_{N-2}})\nonumber\\ &{\rm Rearranging the terms, we get}\nonumber\\ &= x_{_{N-1}}(x_{_{j-2}} – x_{_{j-3}}) + x_{_{j-3}}(x_{_{N-1}} – x_{_{N-2}})\nonumber \end{align*}

We find that the term on the right hand side, in the above equation is greater than 0. Hence

\begin{equation} y_{_{N+j}} – y_{_{N+j-1}} > 0\tag{16.3}\label{16.3} \end{equation}

From eq.(\ref{16.3}), we find the sequence $y_{_n}$ to be increasing for $1 \leq j \leq N-1$. The only pair of elements of $y_{_n}$ that needs to be compared are $y_{_{2N}}$ and $y_{_{2N-1}}$. From eq.(\ref{16.2}), we get For $N-1 \leq j \leq N$, the above corresponds to

\begin{align} y_{_{2N}} – y_{_{2N-1}} &= x_{_N}^2 – 2x_{_N}x_{_{N-1}}\tag{16.4}\label{16.4}\\ &= x_{_N}(x_{_N} – 2x_{_{N-1}})\nonumber\\\nonumber\\ &= x_{_N}(x_{_{N-2}}-x_{_{N-1}})\hspace{0.2in}{\rm since}\hspace{0.1in} x_{_N} = x_{_{N-1}} + x_{_{N-2}}\nonumber \end{align}

We know that $x_{{n}} < x_{_{n+1}}$, and hence, from the above equation, we have

\begin{equation} \Rightarrow y_{_{2N}} – y_{_{2N-1}}< 0 \tag{16.5}\label{16.5} \end{equation}

From eq.(\ref{16.5}), we find that $y_{_{2N}} < y_{_{2N-1}}$. Thus, in the sequence resulting from the linear convolution of finite length classical Fibonacci sequence with itself, the maximum is located at $2N-1$, where $N$ is the length of the sequence $x_{_n}$.

17  a=1, b = 2 :

Now, we explore what happens when $a=1, b=2$ in eq.(\ref{15.3}), as mentioned in case(Aii). The corresponding second order recurrence relation is as below:

\begin{equation} x_{_n} = x_{_{n-1}} + 2x_{{n-2}}\tag{17.1}\label{17.1} \end{equation}

In this case, the “$characteristic$” equation is $x^2 – x – 2 = 0$ and the largest positive root, $R$, is 2. To obtain the location of the maximum in the linear convolution of eq.\ref{17.1} with itself, we adopt the same procedure as classical Fibonacci sequence.

\begin{align} y_{_{N+j}} – y_{_{N+j-1}} &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}x_{_{N+j-k}} – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\nonumber\\ &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}(x_{_{N+j-1-k}}+2x_{_{N+j-2-k}}) – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\tag{17.2}\label{17.2}\\ &= \displaystyle{\sum_{k=j}^{N}}2x_{_{k}}x_{_{N+j-2-k}} \hspace{0.1in}- x_{_{j-1}}x_{_N}\tag{17.3}\label{17.3} \end{align}

Suppose, $j \leq N-1$,

\begin{align} y_{_{N+j}} – y_{_{N+j-1}}&\geq 2x_{_{N-1}}x_{_{j-1}} + x_{_N}x_{_{j-2}} – x_{_{j-1}}x_{_N}\nonumber\\ &\geq 2x_{_{N-1}}x_{_{j-1}} + x_{_N}(x_{_{j-1}}-2x_{_{j-3}})- x_{_{j-1}}x_{_N}\nonumber\\ &= 2x_{_{N-1}}x_{_{j-1}} – 2x_{_{j-3}}x_{_N}\nonumber\\ &= 2x_{_{N-1}}(x_{_{j-2}}+2x_{_{j-3}}) – 2x_{_{j-3}}(x_{_{N-1}}+2x_{_{N-2}})\nonumber \end{align}

Rearranging the terms, we get,

\begin{align} &= 2x_{_{N-1}}(x_{_{j-2}} – 2x_{_{j-3}}) + 4x_{_{j-3}}(x_{_{N-1}} – x_{_{N-2}})\nonumber\\ y_{_{N+j}} – y_{_{N+j-1}}&> 0\tag{17.4}\label{17.4} \end{align}

From eq.(\ref{17.4}), we find the sequence $y_{_n}$ to be an increasing one for $1 \leq j \leq N-1$. The only elements of $y_{_n}$ that need to be compared are $y_{_{2N}}$ and $y_{_{2N-1}}$. For $N-1 \leq j \leq N$, the above corresponds to

\begin{align} y_{_{2N}} – y_{_{2N-1}} &= x_{_N}^2 – 2x_{_N}x_{_{N-1}}\tag{17.5}\label{17.5}\\ &= x_{_N}(x_{_N} – 2x_{_{N-1}})\tag{17.6}\label{17.6} \end{align}

  • When $N$ is even, $x_{_N} < 2x_{_{N-1}}$ and hence $y_{_{2N-1}}$ is the maximum.
  • When $N$ is odd, $x_{_N} > 2x_{_{N-1}}$. Therefore, $y_{_{2N}}$ is maximum.

This can be easily proved by mathematical induction.

Proof :

Let $k$ = 2. With standard initial conditions 1, 1 one can observe that $f_2 < \frac{1}{2}f_3$ and $f_2 < 2f_1$.

Let $k$ = 4. The sequence elements with initial conditions 1, 1 turn out to be 1, 1, 3, 5. We observe that $f_4 < \frac{1}{2}f_5$ and $f_4 < 2f_3$.

For any $k$, we prove the following by induction.

\begin{equation} f_{_{2k}} < \min\{2f_{_{2k-1}}, \frac{1}{2}f_{_{2k+1}}\}\tag{17.7}\label{17.7} \end{equation}

Let eq.(\ref{17.7}) be true for $k$-1. So, we have

\begin{equation} f_{_{2k-2}} < \min\{2f_{_{2k-3}}, \frac{1}{2}f_{_{2k-1}}\}\tag{17.8}\label{17.8} \end{equation}

We now prove that eq.(\ref{17.7}) is true for $k$ i.e.,

\begin{equation*} f_{_{2k}} < \min\{2f_{_{2k-1}}, \frac{1}{2}f_{_{2k+1}}\} \end{equation*}

\begin{equation} f_{_{2k}} = f_{_{2k-1}} + 2f_{_{2k-2}}\tag{17.9}\label{17.9} \end{equation}

We know that from eq.(\ref{17.8}), $f_{_{2k-2}} < \frac{1}{2}f_{_{2k-1}}$

\begin{align} {\rm Hence} f_{_{2k}} &< f_{_{2k-1}} + f_{_{2k-1}}\nonumber\\ \Rightarrow f_{_{2k}} &< 2f_{_{2k-1}}\tag{17.10}\label{17.10} \end{align}

Similarly,

\begin{equation} f_{_{2k+1}} = f_{_{2k}} + 2f_{_{2k-1}}\tag{17.11}\label{17.11} \end{equation}

From eq.(\ref{17.10}), $f_{_{2k}} < 2f_{_{2k-1}}$

\begin{align} {\rm Hence}\quad f_{_{2k}} &< f_{_{2k+1}} - f_{_{2k}} \nonumber\\ \Rightarrow 2f_{_{2k}} &< f_{_{2k+1}}\nonumber\\ \Rightarrow f_{_{2k}} &< \frac{1}{2}f_{_{2k+1}}\tag{17.12}\label{17.12} \end{align}

Thus we find that, $f_{_{2k}} < \min\{2f_{_{2k-1}}, \frac{1}{2}f_{_{2k+1}}\}$. From this one can see that $y_{_n}$ has its maximum either at 2$N$-1 or 2$N$ depending on whether the sequence length is odd or even.

18  a=1, b > 2:

With $a=1, b > 2$ in eq.(\ref{15.3}), we look at case(Aiii). The corresponding second order recurrence relation is as below:

\begin{equation} x_{_n} = x_{_{n-1}} + bx_{{n-2}}\tag{18.1}\label{18.1} \end{equation}

In this case, the “$characteristic$” equation is $x^2 – x – b = 0$ and the largest positive root, $R$, greater than 2. We now proceed to obtain the location of the maximum in the linear convolution of eq.(\ref{18.1}) with itself.

\begin{align} y_{_{N+j}} – y_{_{N+j-1}} &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}x_{_{N+j-k}} – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\nonumber\\ &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}(x_{_{N+j-1-k}}+b x_{_{N+j-2-k}}) – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\nonumber\\ &= \displaystyle{\sum_{k=j}^{N}}bx_{_{k}}x_{_{N+j-2-k}} \hspace{0.1in}- x_{_{j-1}}x_{_N}\tag{18.2}\label{18.2} \end{align}

Suppose, $j \leq N-1$,

\begin{align} y_{_{N+j}} – y_{_{N+j-1}}&\geq bx_{_{N-1}}x_{_{j-1}} + b x_{_N}x_{_{j-2}} – x_{_{j-1}}x_{_N}\nonumber\\ &\geq bx_{_{N-1}}x_{_{j-1}} + b x_{_N}(x_{_{j-1}}- b x_{_{j-3}})- x_{_{j-1}}x_{_N}\nonumber\\ &= bx_{_{N-1}}x_{_{j-1}} – bx_{_{j-3}}x_{_N}\nonumber\\ &= bx_{_{N-1}}(x_{_{j-2}} + bx_{_{j-3}}) – b x_{_{j-3}}(x_{_{N-1}} + bx_{_{N-2}})\nonumber \end{align}

Rearranging the terms, we get,

\begin{align} &= bx_{_{N-1}}(x_{_{j-2}} – x_{_{j-3}}) + b^2x_{_{j-3}}(x_{_{N-1}} – x_{_{N-2}})\tag{18.3}\label{18.3}\\ y_{_{N+j}} – y_{_{N+j-1}}&> 0\tag{18.4}\label{18.4} \end{align}

From eq.(\ref{18.4}), we find the sequence $y_{_n}$ to be an increasing one for $1 \leq j \leq N-1$. The only elements of $y_{_n}$ that need to be compared are $y_{_{2N}}$ and $y_{_{2N-1}}$.

For $N-1 \leq j \leq N$, the above corresponds to

\begin{align} y_{_{2N}} – y_{_{2N-1}} &= x_{_N}^2 – 2x_{_N}x_{_{N-1}}\tag{18.5}\label{18.5}\\ &= x_{_N}(x_{_N} – 2x_{_{N-1}})\tag{18.6}\label{18.6}\\ &= x_{_N}(x_{_{N-1}}+ b x_{_{N-2}}- 2x_{_{N-1}})\tag{18.7}\label{18.7} \end{align}

Let us consider the sequence generated by eq.(\ref{18.1}), with $b=3$. The elements of the sequence, with initial values being 1, 1, are

1, 1, 4, 7, 19, 40, 97, $\ldots$

From the above, we find that $bx_{{n-2}}$ is always greater than $x_{{n-1}}$. Thus eq.\ref{18.7} is always positive. Hence, we find that $y_{_{2N}} > y_{_{2N-1}}$. Thus, the maximum is located at 2$N$ and not at 2$N-1$. A formal proof by induction can be obtained along the same lines of mathematical induction, as found in section.17.

a>1:

We now present the case when $a > 1$ and $b \in \mathbb N$, in eq.(\ref{15.3}).

\begin{align} y_{_{N+j}} – y_{_{N+j-1}} &= \displaystyle{\sum_{k=j}^{N}}x_{_{k}}x_{_{N+j-k}} – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\nonumber\\ &=\displaystyle{\sum_{k=j}^{N}}x_{_{k}}(a x_{_{N+j-1-k}}+b x_{_{N+j-2-k}}) – \displaystyle{\sum_{k=j-1}^{N}}x_{_k}x_{_{N+j-1-k}}\tag{18.8}\label{18.8}\\ &= \displaystyle{\sum_{k=j}^{N}}(a-1)x_{_{k}}x_{_{N+j-1-k}} + \displaystyle{\sum_{k=j}^{N}}bx_{_{k}}x_{_{N+j-2-k}} \hspace{0.1in}- x_{_{j-1}}x_{_N}\tag{18.9}\label{18.9} \end{align}

When $a >1$, the term $x_{_{j-1}}x_{_N}$ gets accounted for by $\displaystyle{\sum_{k=j}^{N}}(a-1)x_{_{k}}x_{_{N+j-1-k}}$, with $k=N$. The remaining terms are all positive. Hence $y_{_n}$ increases till $2N-1$. Now, we compare $y_{_{2N-1}}$ and $y_{_{2N}}$.

For $N-1 \leq j \leq N$, the above corresponds to

\begin{align} y_{_{2N}} – y_{_{2N-1}} &= x_{_N}^2 – 2x_{_N}x_{_{N-1}}\tag{18.10}\label{18.10}\\ &= x_{_N}(x_{_N} – 2x_{_{N-1}})\tag{18.11}\label{18.11}\\[.5cm] &= x_{_N}(a x_{_{N-1}}+ b x_{_{N-2}}- 2x_{_{N-1}})\tag{18.12}\label{18.12}\\ &= x_{_N}((a-2) x_{_{N-1}}+ b x_{_{N-2}})\tag{18.13}\label{18.13} \end{align}

With $a > 1$ and $b \in \mathbb N$, eq.(\ref{18.13}) is always positive. Hence $y(n)$ has its maximum at $y_{_{2N}}$.

19 Self Linear Convolution of Higher Order Linear Recurrence Relations With Integer Coefficients

In the previous section, we found that the sequence resulting from the self linear convolution of second order linear recurrence (with positive integer coefficients) has its maximum located at either 2$N$-1 or 2$N$ is determined by the

  • coefficients
  • and hence the largest positive real root.

It was proved that, when the largest positive real root was 2, the location of maximum is either 2$N$-1 or 2$N$, based on whether $N$, the length of $x_{_n}$, is even or odd.

It is also worth noting that this is true even in the case of self convolution of, $x_{_n} = a x_{_{n-1}}$, first order linear recurrence relation (with positive integer coefficients). In this case, if $a$ = 2, the largest positive real root is 2. $y_{_n}$ has its maximum at either 2$N$-1 or 2$N$ depending on whether the length $N$ is even or odd. However, when $a$ = 1, it can be easily proved that, the maximum of $y_{_n}$ is located at $N$.

Now, we look at the higher order recurrence relations with positive integer coefficients. Let

\begin{equation} x_{_n} = a_{_{n-1}}x_{_{n-1}} + \ldots + a_{_k}x_{_{n-k}} \hspace{0.3in} \forall a_{_i} \in \mathbb{N}\tag{19.1}\label{19.1} \end{equation}

be a higher order recurrence relation. On similar lines, as self linear convolution of the second order linear recurrence relation, one can establish that even in the case of higher order recurrence relations, there exist three cases, namely,

  • all the $a_{_i}$’s are 1. $y_{_n}$ is maximum at $n = 2N-1$
  • $a_{_i}$’s are 1 and $a_{_0}$ = 2. $y_{_n}$ is maximum at $n = 2N-1$ or $n = 2N$, depending on whether the length is even or odd
  • $a_{_i}$’s are greater than 1. $y_{_n}$ is maximum at $n = 2N$

20  Conclusion

In this work, on the one hand, we have explored and proved certain optimal probabilistic limit properties of Fibonacci sequence. We have proved that, among the distributions induced by $k^{th}$ order linear recurrence equations with positive integer coefficients, the limits of the mean and the variance are maximum for those generated by second order linear recurrence relation, corresponding to the Fibonacci sequence. We also found that the ratio of the variance to the mean, of the distribution induced by the Fibonacci sequence turns out to be golden ratio, $\varphi$. Moreover, for all such distributions, we have,

  • $\underline{X}$ converges to $Y$ in distribution
  • All the moments of $\underline{X}$ converge to the corresponding moments of $Y$
  • In the classical Fibonacci case, all moments of $\underline{X}$ converges to linear function of the golden ratio, $\varphi$.

Besides proving certain optimal probabilistic limit properties, we also analyzed the second order linear recurrence relation with positive integer coefficients, from the point of view of self linear convolution. We established that the sequence resulting from the self linear convolution of any higher order linear recurrence relation with integer coefficients, can have its maximum either at 2$N$ or 2$N$-1. A more interesting observation in this regard is that when the largest positive real root of such recurrence relations is 2, the location of maximum depends on whether the sequence length of $x_{_n}$ is odd or even.

Appendix A.

Some Preliminaries.

We list some of the identities used in this paper in the following sections.

\begin{equation*} G(x) = \displaystyle{\sum_{n=1}^{N}}x^n = x+x^2+\ldots+x^N = \displaystyle{\frac{x^{N+1}-x}{x-1}}\tag{A.1}\label{A.1} \end{equation*}

Let $G'(x)$ be the derivative of $G(x)$. We have,

\begin{align*} G'(x) = 1+2x+\ldots+Nx^{N-1} &= \displaystyle{\frac{(x-1)\{(N+1)x^{N}-1\}- (x^{N+1}-x)}{(x-1)^2}}\\ &= \displaystyle{\frac{(N+1)x^{N+1}-x-(N+1)x^{N}+1-x^{N+1}+x}{(x-1)^2}}\\ &= \displaystyle{\frac{Nx^{N+1}-(N+1)x^N + 1}{(x-1)^2}} \end{align*}

Hence, we get,

\begin{align*} xG'(x) = \displaystyle{\sum_{n=1}^{N}}nx^n &= x+2x^2+\ldots+ Nx^N \nonumber\\ &=\displaystyle{\frac{Nx^{N+2}-(N+1)x^{N+1}+x}{(x-1)^2}}\tag{A.2}\label{A.2} \end{align*}

From this we get,

\begin{equation*} (xG'(x))’ = 1+2^2x+\ldots+N^2x^{N-1}\tag{A.3}\label{A.3} \end{equation*}

which by eq.(\ref{A.2}) is

\begin{align*} &\nonumber(xG'(x))’ \\ &= \displaystyle{\frac{(x-1)^2\{N(N+2)x^{N+1}-(N+1)^2x^N+1\}-2(x-1)\{Nx^{N+2}-(N+1)x^{N+1}+x\}}{(x-1)^4}}\\ \nonumber&= \displaystyle{\frac{(x-1)\{N(N+2)x^{N+1}-(N+1)^2x^N+1\}-2\{Nx^{N+2}-(N+1)x^{N+1}+x\}}{(x-1)^3}}\\ \nonumber&= \displaystyle{\frac{N^2\{x^{N+2}-2x^{N+1}+x^N\}+ N\{-2x^{N+1}+2x^N\}+\{x^{N+1}+x^N+x+1\}}{(x-1)^3}} \end{align*}

and hence,

\begin{align*} &\nonumber x(xG'(x))’\\ &= \displaystyle{\sum_{n=1}^{N}}n^2x^n \\ &= \displaystyle{\frac{N^2\{x^{N+3}-2x^{N+2}+x^{N+1}\}+ N\{-2x^{N+2}+2x^{N+1}\}+\{x^{N+2}+x^{N+1}+x^2+x\}}{(x-1)^3}}\tag{A.4}\label{A.4} \end{align*}

Appendix B.

Useful Finite Sums.

In this section, we obtain the expressions for some of the finite sums relevant to the work presented in this paper.

B.1. $\displaystyle{\sum_{n=1}^Nf[n]}$

Let $\bar{S}$ be the sum of the sequence $f[n]$ defined as

\begin{equation} \bar{S} =\displaystyle{\sum_{n=1}^N f[n]} = \displaystyle{\sum_{n=1}^N \frac{1}{\sqrt{a^2 + 4b}}(R^n – R_S^n)}\tag{B.1}\label{B.1} \end{equation}

From eq.(\ref{A.1}), we get

\begin{equation} G(R) = R + R^2 + R^3 + \ldots + R^N =\displaystyle{ \sum_{n=1}^N R^n = \frac{R^{N+1}- R}{R-1}}\tag{B.2}\label{B.2} \end{equation}

\begin{equation} G(R_S) = R_S + R_S^2 + R_S^3 + \ldots + R_S^N = \displaystyle{\sum_{n=1}^N R_S^n = \frac{R_S^{N+1}- R_S}{R_S-1}}\tag{B.3}\label{B.3} \end{equation}

Substituting eq.(\ref{B.2}) and eq.(\ref{B.3}) eq.(\ref{B.1}), we get,

\begin{align} \bar{S} =& \displaystyle{\frac{1}{\sqrt{a^2 + 4b}}}\displaystyle{\sum_{n=1}^N{(G(R) – G(R_S))}}\nonumber\\ = & \displaystyle{\frac{1}{\sqrt{a^2 + 4b}}} \left(\displaystyle{\frac{R^{N+1}- R}{R-1}} – \displaystyle{\frac{R_S^{N+1}- R_S}{R_S-1}}\right)\tag{B.4}\label{B.4} \end{align}

We have,

\begin{align} \nonumber R^2 &= \displaystyle{\frac{2a^2+4b+2a\sqrt{a^2+4b}}{4}}\\ \nonumber \Rightarrow R^2 &> b\\ \Rightarrow |\frac{R_S}{R}| &= \frac{b}{R^2} < 1\tag{B.5}\label{B.5} \end{align}

Hence, taking $R^{N+1}$ common from eq.(\ref{B.4}), we see that,

\begin{equation} \bar{S} \sim \displaystyle{\frac{1}{\sqrt{a^2 + 4b}}}\left( \frac{R^{N+1}}{R-1}\right)\tag{B.6}\label{B.6} \end{equation}

B.2. $\displaystyle{\sum_{n=1}^{N}n f[n]}$

Let $\bar{S}_1$ be defined as

\begin{equation} \bar{S}_1 = \displaystyle{\sum_{n=1}^N nf[n]}\tag{B.7}\label{B.7} \end{equation}

\begin{align} \bar{S}_1 &= \displaystyle{\sum_{n=1}^N nf[n]} \nonumber\\ &= \frac{1}{\sqrt{a^2 + 4b}} \displaystyle{\sum_{n=1}^N{(n R^n – n(R_S)^n)}}\nonumber \end{align}

By eq.(\ref{A.2}), we get

\begin{equation} \displaystyle{\sum_{n=1}^N }nR^n = \frac{NR^{N+2}-(N+1)R^{N+1}+R}{(R-1)^2}\tag{B.8}\label{B.8} \end{equation}

We can get a similar expression involving the other root $R_S$. Using the fact that the absolute value of the ratio of $R_S$ and $R$ is less than 1, we obtain

\begin{equation} \bar{S}_1 \sim \frac{1}{\sqrt{a^2 + 4b}}\left(\frac{NR^{N+2}-(N+1)R^{N+1}+R}{(R-1)^2}\right)\tag{B.9}\label{B.9} \end{equation}

B.3. $\displaystyle{\sum_{n=1}^{N}n^2 f[n]}$.

Let $\bar{S}_2$ be defined as

\begin{equation} \bar{S}_2 = \displaystyle{\sum_{n=1}^{N}n^2 f[n]}\tag{B.10}\label{B.10} \end{equation}

Using eq.(\ref{A.4}) we get

\begin{equation*} \bar{S}_2 \sim \frac{N^2\{R^{N+3}-2R^{N+2}+R^{N+1}\}+N\{-2R^{N+2}+2R^{N+1}\}+ \{R^{N+2}+R^{N+1}+R^2+R\}}{(R-1)^3}\tag{B.11}\label{B.11} \end{equation*}

B.4. $\displaystyle{\sum_{n=1}^{N}f[N+1-n]}$.

Let $\underline{S}$ be defined as

\begin{align} \underline{S} &= \displaystyle{\sum_{n=1}^{N}f[N+1-n]}\tag{B.12}\label{B.12}\\ {\rm Clearly,} \hspace{0.3in} \bar{S} = \displaystyle{\sum_{n=1}^{N}f[n]} &= \displaystyle{\sum_{n=1}^{N}f[N+1-n]} = \underline{S}\tag{B.13}\label{B.13} \end{align}

Thus the sum $\underline{S}$ = $\bar{S}$ , where $\bar{S}$ is as in eq.(\ref{B.6}).

B.5. $\displaystyle{\sum_{n=1}^{N}nf[N+1-n]}$.

Let $\underline{S}_1$ denote $\displaystyle{\sum_{n=1}^{N}nf[N+1-n]}$

\begin{align} &\underline{S}_1 = \displaystyle{\sum_{n=1}^{N}nf[N+1-n]}\nonumber\\ &= -\displaystyle{\sum_{n=1}^{N}(-n)f[N+1-n]}\nonumber\\ &= – \displaystyle{\sum_{n=1}^{N}(N+1-n)f[N+1-n]} + (N+1)\displaystyle{\sum_{n=1}^{N}f[N+1-n]}\nonumber\\ &= – \displaystyle{\sum_{k=1}^{N}kf[k] + (N+1)\bar{S}}\nonumber\\ &\Rightarrow \underline{S}_1 = (N+1)\bar{S} – \bar{S}_1\tag{B.14}\label{B.14} \end{align}

B.6. $\displaystyle{\sum_{n=1}^{N}n^2f[N+1-n]}$.

Let $\underline{S}_2$ be defined as

\begin{align} &\underline{S}_2 = \displaystyle{\sum_{n=1}^{N}n^2f[N+1-n]}\nonumber\\ &= \displaystyle{\sum_{n=1}^{N}(N+1-n)^2f[n]}\nonumber\\ &= (N+1)^2 \displaystyle{\sum_{n=1}^Nf[n]} – 2(N+1)\displaystyle{\sum_{n=1}^N nf[n]} + \displaystyle{\sum_{n=1}^N n^2f[n]}\nonumber\\ &\Rightarrow \underline{S}_2 = (N+1)^2\bar{S} -2(N+1)\bar{S}_1 + \bar{S}_2\tag{B.15}\label{B.15} \end{align}

where $\bar{S}_1$ and $\bar{S}_2$ are as in eq.(\ref{B.7}) and in eq.(\ref{B.9}) respectively.

References

  • [1]   D. K. Neal, Limits of Mean and Variance of a Fibonacci Distribution, Math. Scientist 34, 2009, pp. 25-29.

  • [2]    Arulalan Rajan, Some applications of Integer sequences in signal processing and their implications on performance and architecture, PhD thesis, Indian Institute of Science, September 2011.

  • [3]    N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Ed.2008, published electronically at

    http://oeis.org/A000045

  • [4]   S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover, 2008.

Leave a Comment:

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.