A QUARTERLY PUBLICATION OF ACCS
On the Probability Distributions Induced by Integer Sequences Generated by Recurrence Relations with Positive Integer Coefficients

ARULALAN RAJAN, Electronic Design and Technology, Indian Institute of Science, Bangalore.
R. VITTAL RAO, Department of Electronic systems Engg., (DESE) at the Indian Institute of Science, Bangalore.
H. S. JAMADAGNI, (DESE) at IISc
ASHOK RAO, Electronics Design and Technology, IISc Bangalore

## 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

fn = fn-1 + fn-2

with the condition that f0=0,f1=1. It is also interesting to note that for a number x. to be a Fibonacci number, either 5x2+4  or 5x2−4 must be a a perfect square.

The ratio

converges to the golden mean or the golden ratio

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

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   of positive real numbers, we can generate a probability distribution on {1;2;:::;N} for every N∈N as follows: Let X be a random variable taking values 1;2;:::;N such that

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

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→∞.

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

f[n]=f[n−1]+f[n−2]

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 φ, i.e.,

For any positive integer N, consider the Fibonacci sequence, f[1],f[2],…,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

pN  [1], pN [2],….., pN  [N]

pËN(n)=f[n]N∑k=1f[k]∀n=1,2,…,N

Let ËX be a random variable in {1,2,…,N} such that

P(ËX=n)=pËN(n);1≤n≤N.

In his work, Neal [1] showed that, E(ËX), the mean or expectation of ËX, grows linearly as N increases and hence

limN→∞E(ËX)=∞

Similarly, let X_ be a random variable in {1,2,…,N}, where the probabilities, pN_[n], correspond to the Fibonacci sequence, of length N, in the decreasing order2. We define the probability mass function,

P(X_=n)=f[N+1−n]N∑k=1f[k]=pN_(n);1≤n≤N.

For such a random variable, X_, Neal [1] observed the following limiting properties:

limN→∞E(X_)=φ+1

limN→∞Var(X_)=2φ+1

where E(X_) denotes the mean or expectation of X_ and Var(X_) denotes the variance of 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

f[n]=af[n−1]+bf[n−2]wheref[1]=1;f[2]=1;

The characteristic equation of this recurrence relation is given by

r2–ar–b=0.

It is well known that the solution to this Eq.(3.2) is given by

f[n]=C[R(a,b)n–Rs(a,b)n]

where,

R(a,b)=a+√a2+4b2

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

Rs=–bR(a,b)

and

C=1√a2+4b

We note that,

R(a,b)≥φforallpositiveintegersa,bR(a,b)=φwhena=b=1(classicalFibonaccisequence)

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

limk→∞f[k+1]f[k]=R(a,b)

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

f[1],f[2],…,f[N]

and define probability mass functions,

pËN(n)[1],pËN(n)[2],…,pËN(n)[N]

as

pËN(n)=f[n]N∑k=1f[k]∀n=1,2,…,N

Consider a random integer, ËX, in {1,2,…,N}, such that

P(ËX=n)=pËN(n)

Similarly let X_ be a random variable in {1,2,…,N}, (with probabilities corresponding to the decreasing sequence) such that,

P(X_=n)=f[N+1−n]N∑k=1f[k]=pN_(n)∀n=1,2,…,N

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

## 4 The Main Theorems on the Limiting Properties

We prove the following limiting properties.

Analogous to eq.(2.5), we have,

Theorem 1.

Even though E(ËX) grows as N increases, its variance still converges. In fact, we have,

Theorem 2.

In the case of X_, both E(X_) and Var(X_) converge as N→∞ and the limit of Var(X_) is the same as that of Var(ËX). We have, analogous to eq.(2.7) and eq.(2.8), the following limits.

Theorem 3.

Theorem 4.

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.(2.5), eq.(2.7), eq.(2.8), obtained for the Fibonacci sequence, by Neal [1], described in section 2. Using eq.(3.3) and eq.(3.4), we can prove the following optimality properties of the Fibonacci sequence:

Theorem 5.

max(limN→∞E(X_):a,b∈N)=limN→∞(E(X_):a=b=1)=φ+1

Theorem 6.

max(limN→∞Var(ËX):a,b∈N)=max(limN→∞Var(X_):a,b∈N)=limN→∞(Var(X_):a=b=1)=2φ+1

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
ËS=N∑n=1f[n] S_=N∑n=1f[N+1−n]
ËS1=N∑n=1nf[n] S_1=N∑n=1nf[N+1−n]
ËS2=N∑n=1n2f[n] S_2=N∑n=1n2f[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 ËX, defined as in section 2.

THEOREM 1:

limN→∞E(ËX)=∞

Proof :

We have,

E(ËX)=ËS1ËS

Using eq.(B.8) and eq.(B.6), we get

E(ËX)∼(NRN+2−(N+1)RN+1+R)(R−1)(R−1)2RN+1∼NR−N−1R−1⇒E(ËX)∼N–1R−1E(ËX)∼O(N)

Theorem 1, now follows from eq.(6.2).

We also observe the following:

If we now define ËY = (N+1)−ËX, so that ËY is also a random variable taking value 1, 2, 3, …, N and ËX has been in a sense centralized, then by eq.(6.2),

E(ËY)∼1+1R−1=RR−1

Hence

limN→∞E(ËY)=RR−1

This ËY corresponds to X_, which we describe in sec.7.

THEOREM 2:

limN→∞Var(ËX)=R(R−1)2

Proof :

We have,

E(ËX2)=ËS2ËS

Using eq.(B.10) and eq.(B.6), we get

E(ËX2)∼N2(R−1)2–2N(R−1)+R+1(R−1)2

Using eq.(6.2) and eq.(6.4), we get

Var(ËX)=E(ËX2)−E(ËX)2∼N2(R−1)2–2N(R−1)+R+1(R−1)2−(N–1R−1)2⇒limN→∞Var(ËX)=(R+1)−1(R−1)2

Thus, we get the limit of the variance as,

limN→∞Var(ËX)=R(R−1)2

It is interesting to note from eq.(6.2) and eq.(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 X_ taking a value n was defined as,

P(X_=n)=f[N+1−n]N∑k=1f[N+1−k]=pN_(n)

THEOREM 3:

limN→∞E(X_)=1+1R−1=RR−1

Proof :

We have,

E(X_)=S_1S_

From eq.(B.13), we get

E(X_)=(N+1)ËS–ËS1ËS=(N+1)–ËS1ËS∼(N+1)–(N–1R−1)byeq.(6.2)⇒limN→∞E(X_)=1+1R−1=RR−1

THEOREM 4:

limN→∞E(X_2)=1+3R−1(R−1)2

Proof :

Var(X_)=E(X_2)–E(X_)2

Using eq.(B.14) we first obtain E(X_2).

E(X_2)=ËS2S_∼(N+1)2ËSËS–2(N+1)ËS1ËS+ËS2ËS∼(N+1)2–2(N+1)E(ËX)+E(ËX2)∼(N+1)2–2(N+1)(N−1R−1)+(N2(R−1)2–2N(R−1)+(R+1)(R−1)2)∼(R−1)2+3R−1(R−1)2

⇒limN→∞E(X_2)=1+3R−1(R−1)2

From eq.(7.3) and eq.(7.5), we get

Var(X_)=E(X_2)–E(X_)2→1+3R−1(R−1)2–R2(R−1)2⇒limN→∞Var(X_)=R(R−1)2

Thus, we find that, the limit of the variance of the probability distribution with probability defined by eq.(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.(6.2) and eq.(7.5) respectively, by using a=1, b=1, and R=φ.

### 8.1  Distributions Induced by Increasing Sequence

By eq.(6.2) and eq.(6.5), we have

E(ËX)∼O(N)

and

limN→∞Var(ËX)=R(R−1)2=φ(φ−1)2⇒limN→∞Var(ËX)=2φ+1

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

### 8.2 Distributions Induced by Decreasing Sequence

By eq.(7.3), we have

limN→∞E(X_)=RR−1=φ+1

From eq.(7.6), we have

limN→∞Var(X_)=R(R−1)2=φ(φ−1)2⇒limN→∞Var(X_)=2φ+1

Comparing eq.(8.1) and eq.(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),

limN→∞Var(X_)E(X_)=1R−1

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

limN→∞Var(X_)E(X_)=1φ−1=φ

Thus the ratio of the variance of X_ to the expectation of X_ also converges to the Golden Ratio, φ.

## 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:

max(limN→∞E(X_):a,b∈N)=limN→∞(E(X_):a,b=1)=φ+1

Proof :

We know that

R≥φ⇒R−1≥φ−1⇒1R−1≤1φ−1

But φ = 1φ−1.

Hence, from eq.(10.1), we get

1R−1≤φ⇒1+1R−1≤1+φRR−1≤φ+1⇒limN→∞(E(X_):a,b∈N)≤limN→∞(E(X_):a=b=1)

Thus,

max(limN→∞E(X_):a,b∈N)=limN→∞(E(X_):a,b=1)=φ+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(X_), i.e.

THEOREM 6:

max(limN→∞Var(ËX):a,b∈N)=max(limN→∞Var(X_):a,b∈N)=limN→∞(Var(X_):a,b=1)=2φ+1

We prove this as follows:

Proof :

R≥φ⇒1R≤1φ⇒−1R≥–1φ⇒1−1R≥1–1φ⇒R(1−1R)2≥φ(1–1φ)2⇒1R(1−1R)2≤1φ(1–1φ)2

From eq.(10.6), we get

R(R−1)2≤φ(φ−1)2=2φ+1⇒R(R−1)2≤2φ+1⇒limN→∞(Var(X_):a,b∈N)≤limN→∞(Var(X_):a=b=1)

From eq.(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

f[n]=an−1f[n−1]+…+an−kf[n−k]∀ai∈N

be a kth order recurrence relation. The characteristic equation of this recurrence relation is given by,

f(x)=xk–an−1xk−1−…–an−k

Lemma 1.

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

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

With R=α,

• The same asymptotic relations as in eq.(7.3) and eq.(7.6) hold.
• The same limiting properties as in eq.(2.7) and eq.(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, α>φ, the golden ratio.

Thus, Theorem 5 can be generalized as

max(limN→∞E(X_):ai,i∈N)=limN→∞(E(X_):a1=a2=1,ai=0,∀i>2)=φ+1

and Theorem 6 can be further generalized as

max(limN→∞Var(ËX):ai,i∈N)=max(limN→∞Var(X_):ai,i∈N)=limN→∞(Var(X_):a1=a2=1,ai=0,∀i>2)=2φ+1

Now, we proceed to prove Lemma 1.

Proof :

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

f(0)<0, f(∞)>0

Let α be the largest positive root.

### 11.1 α Is Simple Root

Claim: The root is simple.

Let f(x) be as in eq.(11.2). Since α is a root, we have

αk–an−1αk−1+…+an−k=0

Suppose, if α is a multiple root, then we must have

f′(α)=0

⇒kαk−1−(k−1)an−1αk−2+…+an−k+1=0

Multiplying by α, we get

kαk–(k−1)an−1αk−1+…+an−k+1α=0⇒kαk=(k−1)an−1αk−1+…+an−k+1α⇒<k(an−1αk−1+…+an−k+1α)⇒<k(an−1αk−1+…+an−k+1α+an−k)⇒αk<an−1αk−1+…+an−k+1α+an−k⇒αn<αn

This contradicts eq.(11.3). Hence α must be a simple root.

### 11.2 All Roots Lie Within Circle of Radius |α|

Now, we prove that all other roots of eq.(11.2) lie within the circle of radius α. Consider eq.(11.2), the characteristic equation of the corresponding kth order recurrence relation with positive integer coefficients. Since α is a root,

f(α)=0

Also, we have

limx→∞f(x)=∞⇒f(x)≥0,∀x≥αandf(x)>0∀x>α

Let β be any root (real or complex) of eq.(11.2). Clearly, β cannot be zero, because,

f(0)=−an−k<0

Let b = |β|.

Claim: b ≤ α

Reason: Suppose b > α.

Since β is a root, we have

f(β)=0⇒βk=an−1βk−1+…+an−kβn−k⇒|β|k=|an−1βk−1+…+an−kβn−k|⇒βk≤an−1|β|k−1+…+an−k|β|n−k

⇒βk−an−1|β|k−1–…–an−k|β|n−k≤0⇒bk−an−1bk−1–…–an−kbn−k≤0⇒f(b)≤0

However, since b > α, by eq.(11.7), f(b) > 0. Thus, we get a contradiction and hence b ≤ α.

Claim: b = α

Since β is a root, we have,

βk=an−1βk−1+…+an−kβn−k⇒|β|k=|an−1βk−1+…+an−kβn−k|

Since we have assumed that |β|=b=a,

αk=|an−1βk−1+…+an−kβn−k|

an−1αk−1+…+an−k=|an−1βk−1+…+an−k|byeq. (11.3)an−1|β|k−1+…+an−k=|an−1βk−1+…+an−k|

⇒an−1βk−1,…,an−k are all complex numbers in the same direction.

⇒an−k,an−k+1β are real positive

⇒β is real positive

⇒β=α.

Thus, based on the above claims, we find that

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

### 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 φ.

αk=an−1αk−1+…+an−kαn−k

Since all terms on the RHS are greater than 0

⇒αk>an−1αk−1+an−2αk−2⇒α2>an−1α+an−2

As an−1, an−2 are positive integers, we see that,

⇒α2>α+1⇒α2–α–1 >0

From the fact that, φ, the golden ratio, is the largest positive root of x2−x−1=0 and that x2−x−1>0 for x>φ, it follows that α is always greater than φ.

## 12  Convergence in Distribution

It must be noted that the distribution {pN_(n)},1≤n≤N, converges to a geometric distribution on N={1,2,3,…}. More precisely, we have the following:

Let Y be a random integer in N, such that

p(n)=P(Y=n)=ρn(1−ρρ)

where ρ=1R. We have,

∞∑n=1ρn=ρ1−ρ

and hence

∞∑n=1nρn−1=ddρ(ρ1−ρ)=1(1−ρ)2

Thus,

∞∑n=1nρn=ρ(1−ρ)2

Consequently,

E(Y)=∞∑n=1nρn(1−ρρ)=ρ(1−ρ)2(1−ρρ)=11−ρ=11−(1R)⇒E(Y)=RR−1

Similarly we can see that

Var(Y2)=R(R−1)2

Thus, we see that,

limN→∞E(X_)=E(Y)limN→∞Var(X_)=Var(Y)

We now show that the random variable X_ converges to the random variable Y in distribution.

We have for every n∈N,

pN_(n)∼(RN+1−nRN+1−R)(R−1)=(R−n1−R−N)(R−1)=(ρn1−ρN)(1ρ−1)=(ρn1−ρN)(1−ρρ)

Thus,

pN_(n)∼(ρn1−ρN)(1−ρρ)

Since limN→∞ρN=0 as ρ=1R<1, we have

limN→∞pN_(n)=ρn(1−ρρ)

From eq.(12.1) and eq.(12.5) we see that

limN→∞pN_(n)=p(n)∀n∈N

and thus 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.,

• X_ converges to Y in distribution and
• E(X_) converges to E(Y)
• E(X_2) converges to E(Y2) (and hence Var(X_) converges to Var(Y)).

Now, we prove that all the moments of X_ converge to the corresponding moment of Y, as N→∞.

Proof :

For any positive integer k, we have,

E(X_k)∼N∑n=1nkRN+1−nN∑n=1RN+1−n

We have,

N∑n=1RN+1−n=RN+1−RR−1

Also,

N∑n=1nkRN+1−n=RN+1N∑n=1nkR−n

Substituting eq.(13.2) and eq.(13.3) in eq.(13.1), we get

E(X_k)∼(RN+1N∑n=1nkR−nRN+1−R)(R−1)=(RN+1N∑n=1nkR−nRN+1(1−R−N))(R−1)=N∑n=1nkρn1−R−N(1−ρρ)

Hence, as N→∞,

E(X_k)â¶N∑n=1nkρn(1−ρρ)becauseR−N→0=E(Yk)

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

E(X_k)â¶E(Yk),

showing that all the moments of 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, φ.

Proof :

We have,

∞∑n=1xn=x1−xfor|x|<1.

which on differentiation gives

∞∑n=1nxn−1=1(1−x)2

From eq.(13.4), we get

∞∑n=1nxn=x(1−x)2

Then,

∞∑n=1nxn(1−xx)=1(1−x)

Similarly, differentiating eq.(13.5), we get

∞∑n=1n2xn−1=(1−x)2+2x(1−x)(1−x)4=(1−x)+2x(1−x)3=1+x(1−x)3

and hence,

∞∑n=1n2xn=(1+x)x(1−x)3

and thus,

∞∑n=1n2xn(1−xx)=1+x(1−x)2

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

∞∑n=1nkxn(1−xx)=Pk−1(x)(1−x)k

where Pk−1(x) is a polynomial in x of degree k−1.

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

∞∑n=1nrxn(1−xx)=Pr−1(x)(1−x)r

Hence, we get,

∞∑n=1nrxn=xPr−1(x)(1−x)r

On differentiating eq.(13.10), we get,

∞∑n=1nr+1xn−1=(1−x)r+1{Pr−1(x)+P′r−1(x)}+xPr−1(x)r(1−x)r(1−x)2r+2=(1−x){Pr−1(x)+xP′r−1(x)}+xPr−1(x)r(1−x)r+2=Pr(x)(1−x)r+2

where

Pr(x)=(1−x){Pr−1(x)+xP′r−1(x)}+xPr−1(x)r

is a polynomial of degree r. From eq.(13.11), we get,

∞∑n=1nr+1xn=xPr(x)(1−x)r+2

and hence,

∞∑n=1nr+1xn(1−xx)=Pr(x)(1−x)r+1

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

From eq.(13.9), we get

E(Yk)=∞∑n=1nkρn(1−ρρ)=Pk−1(ρ)(1−ρ)k

and hence

limN→∞E(X_k)=E(Yk)=Pk−1(ρ)(1−ρ)k

eq.(13.13) is a rational function of ρ and hence a rational function of R. In particular, for the classical Fibonacci sequence, we have

limN→∞E(X_k)=E(Yk)=Pk−1(1φ)(1−1φ)k

Since 1φ=φ−1, we get

limN→∞E(X_k)=E(Yk)=(Pk−1(φ−1)(φ−1)k)φk=φ2kPk−1(φ−1)=Q(φ),apolynomialinφ

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

limN→∞E(X_k)=E(Y)=Akφ+Bk

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 xn 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, yn resulting from the linear convolution of xn with itself, can be only one of the following:

• 2N-1, when the largest positive real root of the “characteristic equation” is less than 2
• 2N-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 xn 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

x={xn}Nn=1y={yn}2Nn=2xn=axn−1+bxn−2,∀a,b∈N

The “characteristic” equation of the above is given by

x2–ax–b=0

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

R=a+√a2+4b2

### 15.2  Definitions

The linear convolution of two sequences is given by

yn=n−1∑k=1xkxn−k2≤n≤NyN+j=N∑k=jxkxN+j−k1≤j≤N

For 2≤n≤N, we have,

yn–yn−1=n−1∑k=1xkxn−k–n−2∑k=1xkxn−1−k=n−2∑k=1xk(xn−k−xn−1−k)+xn−1x1>0⇒yn>yn−11≤n≤N

From eq.(15.10), we observe that the convolution sum is an increasing sequence for 1≤n≤N.

Now we look at the eq.15.7, for j≥1.

yN+j–yN+j−1=N∑k=jxkxN+j−k–N∑k=j−1xkxN+j−1−k

At this juncture, we revisit the general second order recurrence relation with positive integer coefficients, given in eq.(15.3). We evaluate eq.(15.3) for different possible values of a and b and hence compute the difference as in eq.(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.(15.3), in this case, generates the elements of classical Fibonacci sequence. Eq.(15.3) can be rewritten as

xn=xn−1+xn−2

R, the largest positive real root in the case of classical Fibonacci sequence corresponds to the golden ratio, φ=(1+√52),

With the above conditions, eq.15.11 gives

yN+j–yN+j−1=N∑k=jxkxN+j−k–N∑k=j−1xkxN+j−1−k=N∑k=jxk(xN+j−1−k+xN+j−2−k)–N∑k=j−1xkxN+j−1−k=N∑k=jxkxN+j−2−k–xj−1xN

Suppose, j≤N−1,

yN+j–yN+j−1≥xN−1xj−1+xNxj−2–xj−1xN=xN−1xj−1+xN(xj−1−xj−3)−xj−1xN=xN−1xj−1–xj−3xN=xN−1(xj−2+xj−3)–xj−3(xN−1+xN−2)Rearrangingtheterms,weget=xN−1(xj−2–xj−3)+xj−3(xN−1–xN−2)

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

yN+j–yN+j−1>0

From eq.(16.3), we find the sequence yn to be increasing for 1≤j≤N−1. The only pair of elements of yn that needs to be compared are y2N and y2N−1. From eq.(16.2), we get For N−1≤j≤N, the above corresponds to

y2N–y2N−1=x2N–2xNxN−1=xN(xN–2xN−1)=xN(xN−2−xN−1)sincexN=xN−1+xN−2

We know that xn<xn+1, and hence, from the above equation, we have

⇒y2N–y2N−1<0

From eq.(16.5), we find that y2N<y2N−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 xn.

## 17  a=1, b = 2 :

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

xn=xn−1+2xn−2

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

yN+j–yN+j−1=N∑k=jxkxN+j−k–N∑k=j−1xkxN+j−1−k=N∑k=jxk(xN+j−1−k+2xN+j−2−k)–N∑k=j−1xkxN+j−1−k=N∑k=j2xkxN+j−2−k−xj−1xN

Suppose, j≤N−1,

yN+j–yN+j−1≥2xN−1xj−1+xNxj−2–xj−1xN≥2xN−1xj−1+xN(xj−1−2xj−3)−xj−1xN=2xN−1xj−1–2xj−3xN=2xN−1(xj−2+2xj−3)–2xj−3(xN−1+2xN−2)

Rearranging the terms, we get,

=2xN−1(xj−2–2xj−3)+4xj−3(xN−1–xN−2)yN+j–yN+j−1>0

From eq.(17.4), we find the sequence yn to be an increasing one for 1≤j≤N−1. The only elements of yn that need to be compared are y2N and y2N−1. For N−1≤j≤N, the above corresponds to

y2N–y2N−1=x2N–2xNxN−1=xN(xN–2xN−1)

• When N is even, xN<2xN−1 and hence y2N−1 is the maximum.
• When N is odd, xN>2xN−1. Therefore, y2N is maximum.

This can be easily proved by mathematical induction.

Proof :

Let k = 2. With standard initial conditions 1, 1 one can observe that f2<12f3 and f2<2f1.

Let k = 4. The sequence elements with initial conditions 1, 1 turn out to be 1, 1, 3, 5. We observe that f4<12f5 and f4<2f3.

For any k, we prove the following by induction.

f2k<min{2f2k−1,12f2k+1}

Let eq.(17.7) be true for k-1. So, we have

f2k−2<min{2f2k−3,12f2k−1}

We now prove that eq.(17.7) is true for k i.e.,

f2k<min{2f2k−1,12f2k+1}

f2k=f2k−1+2f2k−2

We know that from eq.(17.8), f2k−2<12f2k−1

Hencef2k<f2k−1+f2k−1⇒f2k<2f2k−1

Similarly,

f2k+1=f2k+2f2k−1

From eq.(17.10), f2k<2f2k−1

Hencef2k<f2k+1−f2k⇒2f2k<f2k+1⇒f2k<12f2k+1

Thus we find that, f2k<min{2f2k−1,12f2k+1}. From this one can see that yn has its maximum either at 2N-1 or 2N depending on whether the sequence length is odd or even.

## 18  a=1, b > 2:

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

xn=xn−1+bxn−2

In this case, the “characteristic” equation is x2–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.(18.1) with itself.

yN+j–yN+j−1=N∑k=jxkxN+j−k–N∑k=j−1xkxN+j−1−k=N∑k=jxk(xN+j−1−k+bxN+j−2−k)–N∑k=j−1xkxN+j−1−k=N∑k=jbxkxN+j−2−k−xj−1xN

Suppose, j≤N−1,

yN+j–yN+j−1≥bxN−1xj−1+bxNxj−2–xj−1xN≥bxN−1xj−1+bxN(xj−1−bxj−3)−xj−1xN=bxN−1xj−1–bxj−3xN=bxN−1(xj−2+bxj−3)–bxj−3(xN−1+bxN−2)

Rearranging the terms, we get,

=bxN−1(xj−2–xj−3)+b2xj−3(xN−1–xN−2)yN+j–yN+j−1>0

From eq.(18.4), we find the sequence yn to be an increasing one for 1≤j≤N−1. The only elements of yn that need to be compared are y2N and y2N−1.

For N−1≤j≤N, the above corresponds to

y2N–y2N−1=x2N–2xNxN−1=xN(xN–2xN−1)=xN(xN−1+bxN−2−2xN−1)

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

1, 1, 4, 7, 19, 40, 97, …

From the above, we find that bxn−2 is always greater than xn−1. Thus eq.18.7 is always positive. Hence, we find that y2N>y2N−1. Thus, the maximum is located at 2N and not at 2N−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∈N, in eq.(15.3).

yN+j–yN+j−1=N∑k=jxkxN+j−k–N∑k=j−1xkxN+j−1−k=N∑k=jxk(axN+j−1−k+bxN+j−2−k)–N∑k=j−1xkxN+j−1−k=N∑k=j(a−1)xkxN+j−1−k+N∑k=jbxkxN+j−2−k−xj−1xN

When a>1, the term xj−1xN gets accounted for by N∑k=j(a−1)xkxN+j−1−k, with k=N. The remaining terms are all positive. Hence yn increases till 2N−1. Now, we compare y2N−1 and y2N.

For N−1≤j≤N, the above corresponds to

y2N–y2N−1=x2N–2xNxN−1=xN(xN–2xN−1)=xN(axN−1+bxN−2−2xN−1)=xN((a−2)xN−1+bxN−2)

With a>1 and b∈N, eq.(18.13) is always positive. Hence y(n) has its maximum at y2N.

## 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 2N-1 or 2N 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 2N-1 or 2N, based on whether N, the length of xn, is even or odd.

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

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

xn=an−1xn−1+…+akxn−k∀ai∈N

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 ai’s are 1. yn is maximum at n=2N−1
• ai’s are 1 and a0 = 2. yn is maximum at n=2N−1 or n=2N, depending on whether the length is even or odd
• ai’s are greater than 1. yn 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 kth 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, φ. Moreover, for all such distributions, we have,

• X_ converges to Y in distribution
• All the moments of X_ converge to the corresponding moments of Y
• In the classical Fibonacci case, all moments of X_ converges to linear function of the golden ratio, φ.

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 2N or 2N-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 xn is odd or even.

Appendix A.

Some Preliminaries.

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

G(x)=N∑n=1xn=x+x2+…+xN=xN+1−xx−1

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

G′(x)=1+2x+…+NxN−1=(x−1){(N+1)xN−1}−(xN+1−x)(x−1)2=(N+1)xN+1−x−(N+1)xN+1−xN+1+x(x−1)2=NxN+1−(N+1)xN+1(x−1)2

Hence, we get,

xG′(x)=N∑n=1nxn=x+2x2+…+NxN=NxN+2−(N+1)xN+1+x(x−1)2

From this we get,

(xG′(x))′=1+22x+…+N2xN−1

which by eq.(A.2) is

(xG′(x))′=(x−1)2{N(N+2)xN+1−(N+1)2xN+1}−2(x−1){NxN+2−(N+1)xN+1+x}(x−1)4=(x−1){N(N+2)xN+1−(N+1)2xN+1}−2{NxN+2−(N+1)xN+1+x}(x−1)3=N2{xN+2−2xN+1+xN}+N{−2xN+1+2xN}+{xN+1+xN+x+1}(x−1)3

and hence,

x(xG′(x))′=N∑n=1n2xn=N2{xN+3−2xN+2+xN+1}+N{−2xN+2+2xN+1}+{xN+2+xN+1+x2+x}(x−1)3

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. N∑n=1f[n]

Let ËS be the sum of the sequence f[n] defined as

ËS=N∑n=1f[n]=N∑n=11√a2+4b(Rn–RnS)

From eq.(A.1), we get

G(R)=R+R2+R3+…+RN=N∑n=1Rn=RN+1−RR−1

G(RS)=RS+R2S+R3S+…+RNS=N∑n=1RnS=RN+1S−RSRS−1

Substituting eq.(B.2) and eq.(B.3) eq.(B.1), we get,

ËS=1√a2+4bN∑n=1(G(R)–G(RS))=1√a2+4b(RN+1−RR−1–RN+1S−RSRS−1)

We have,

R2=2a2+4b+2a√a2+4b4⇒R2>b⇒|RSR|=bR2<1

Hence, taking RN+1 common from eq.(B.4), we see that,

ËS∼1√a2+4b(RN+1R−1)

B.2. N∑n=1nf[n]

Let ËS1 be defined as

ËS1=N∑n=1nf[n]

ËS1=N∑n=1nf[n]=1√a2+4bN∑n=1(nRn–n(RS)n)

By eq.(A.2), we get

N∑n=1nRn=NRN+2−(N+1)RN+1+R(R−1)2

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

ËS1∼1√a2+4b(NRN+2−(N+1)RN+1+R(R−1)2)

B.3. N∑n=1n2f[n].

Let ËS2 be defined as

ËS2=N∑n=1n2f[n]

Using eq.(A.4) we get

ËS2∼N2{RN+3−2RN+2+RN+1}+N{−2RN+2+2RN+1}+{RN+2+RN+1+R2+R}(R−1)3

B.4. N∑n=1f[N+1−n].

Let S_ be defined as

S_=N∑n=1f[N+1−n]Clearly,ËS=N∑n=1f[n]=N∑n=1f[N+1−n]=S_

Thus the sum S_ = ËS , where ËS is as in eq.(B.6).

B.5. N∑n=1nf[N+1−n].

Let S_1 denote N∑n=1nf[N+1−n]

S_1=N∑n=1nf[N+1−n]=−N∑n=1(−n)f[N+1−n]=–N∑n=1(N+1−n)f[N+1−n]+(N+1)N∑n=1f[N+1−n]=–N∑k=1kf[k]+(N+1)ËS⇒S_1=(N+1)ËS–ËS1

B.6. N∑n=1n2f[N+1−n].

Let S_2 be defined as

S_2=N∑n=1n2f[N+1−n]=N∑n=1(N+1−n)2f[n]=(N+1)2N∑n=1f[n]–2(N+1)N∑n=1nf[n]+N∑n=1n2f[n]⇒S_2=(N+1)2ËS−2(N+1)ËS1+ËS2

where ËS1 and ËS2 are as in eq.(B.7) and in eq.(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.

Current Issue

Issue 1
25 March, 2022
Browse by Categories