ON FIBO N A C C I SEQUENCE A N D ITS EXTENSIO NS
THESIS SUBMITTED FOR THE AWARD OF THE DEGREE OF
DOCTOR OF PHILOSOPHY
IN THE FACULTY OF NATURAL SCIENCES
GOA UNIVERSITY
5 I K 5 _
P h A / F f b
BY
C H A N D R A K A N T N A G N A TH P H A D T E
DEPARTMENT OF MATHEMATICS GOA UNIVERSITY
DECLARATION
I, the undersigned, hereby declare that the thesis titled "On Fibonacci Se
quence a n d Its E xtensions" has been completed by me and has not pre
viously formed the basis for the award of any diploma, degree, or any other similar titles.
Chandrakant N Phadte Taleigao Plateau-Goa
24-06-2016
/\\\ Sw^e,S VlcI Cor^tck<,KS “We. CV'A S H C - V I'LsA e\y-«cv «-* y-wi .
CERTIFICATE
This is to certify that Mr. Chandrakant Nagnath Phadte has successfully com
pleted the thesis entitled "On Fibonacci Sequence and Its Extensions"
for the degree of Doctor of Philosophy in Mathematics under my guidance during the period 2012-2016 and to the best of my knowledge it has not pre
viously formed the basis of award of any degree or diploma in Goa University or elsewhere.
Guide, Associate Professor Department of Mathematics Heaa7x)epartment of Mathematics
Goa University
ACKNOWLEDGEMENT
I wish to express my most sincere gratitude to Dr. S.P. Pethe, former vis
iting Professor, Department of Mathematics, Goa University. He suggested the problem under taken for this study. The guidance, support and immense mathematical knowledge that I received from Dr. S. P. Pethe while working on my thesis has been greatly appreciated. I would like to thank Dr. Y. S.
Valaulikar for his guidance and friendship from the first day I arrived in the department. I am especially grateful for his time and effort. I am very much thankful to Principal P. M. Bhende for the inspiration and encouragement given to me. My thanks are also due to Dr. M. Tamba, Lecturer, Department of Mathematics, Goa University. I would also like to thank the faculty and the non-teaching staff of the Department of Mathematics, Goa University for their selfless service.
Lastly I would also like to thank my family who always helped me when I needed it.
Contents
1 Introduction 1
2 Literature Review 4
2.1 Introduction... 4
2.2 Binet Form ula... 7
2.3 Plethora of Fibonacci Identities:... 9
2.4 Generating F u n c tio n ... 11
2.5 Various Extensions of Fibonacci Sequence ...12
2.5.1 Horadam’s Extension... 12
2.5.2 Fibonacci Polynom ials... 15
2.5.3 Fibonacci Function by Francis P a rk e r...15
2.5.4 Extension due to Horadam and Shannon ...16
2.5.5 Elmore’s E x ten sio n ... 16
2.5.6 Extension by J.E.Walton and A.F. H o r a d a m ...17
2.5.7 Extension to Complex Fibonacci N u m b e rs... 18
2.5.8 Extension to Tribonacci N um bers... 20
2.5.9 Extension of Fibonacci sequence using Generalized Cir cular F u n ctio n s...20
2.6 Fibonacci Numbers and Binomial Coefficients... 24
2.7 Divisibility properties of Fibonacci N u m b ers... 29
3 Pseudo Fibonacci Sequence 31
3.1 Introduction... 31
3.2 Some Fundamental Identities of {gn} ... 32
3.3 A Generalization to a new Sequence {Gn} ... 40
3.4 Some Fundamental Identities of Gn ... 43
3.5 E x a m p le s ...59
3.6 Properties of {Gn} using Matrices ... 61
3.7 Another Generalization... 67
3.8 Use of Generalized Circular Functions... 69
3.9 Some Identities of Hn( x )... 72
4 Pseudo Tribonacci Sequence 78 4.1 Introduction...78
4.2 Some identities of {Jn} ...81
4.3 Use of E-Operator ... 91
4.4 Generalization of {Jn} ... 93
5 Pseudo Fibonacci Polynomials 95 5.1 Introduction... 95
5.2 Some Fundamental Identities of gn( x , t )... 99
5.3 Pseudo Fibonacci Polynomial in two v a ria b le s... 105
6 Congruence Properties of Gn 110 6.1 Introduction...110
6.2 Some Identities 112 6.3 Modular P ro p erties...114
SUM M ARY 119
LIST OF PUBLICATIONS/COM M UNICATIONS 119
BIBLIOGRAPHY 119
C hapter 1
Introduction
Fibonacci Sequence have intrigued Mathematicians for years. Generalized Fi
bonacci Sequence can be noticed in many fields like computer algorithms, cryptography, optical network, probability theory and so on. There are many studies in literature that are concerned about the general sequences of second order. For example the Lucas sequence, Jacobsthal sequence, k - Fibonacci sequence, etc. [24], [20],[4].
The main objective of this research is to study the well known Fibonacci se
quence and its identities with the intention of generalizing the results to a gen
eral sequence defined by second order non-homogeneous recurrence relation. It is well known th at the Fibonacci retracement play an important part in stock trading. It is natural to expect that the non homogeneous recurrence relation associated with Fibonacci relation will also be useful in the stock analysis es
pecial when the non homogeneous term is oscillatory. W ith this application in mind the non homogeneous relation of the type gn+2 = gn+1 + 9n + Atn was formed, where A is a non zero constant and t is some fixed constant. The sequence generated by this relation is named as pseudo Fibonacci sequence indicating th at the new sequence is like Fibonacci sequence and hence should
exhibit the properties /identities in line with those of Fibonacci sequence. The main part of the research involves in exploring the generalizations of Fibonacci Sequence in this direction and obtaining a more generalized sequence together with its different identities. The richness of the results in generalization work prompted our investigation on this topic.
In this thesis an attempt is made to develop the theory of generalizations of Fibonacci sequence by introducing non homogeneous term and also by chang
ing the seed values. The thesis is divided into six chapters with Chapter 1 introducing the topic and describing the thesis. Chapter 2 opens with rabbit problem. After defining the Fibonacci sequence, it deals with a survey of var
ious important properties and main generalizations of this sequence. In short, this chapter is a survey of existing literature on Fibonacci sequence and its extensions.
In Chapter 3, we have introduced a new generalization {<?„}, of the Fibonacci sequence, defined by non homogeneous recurrence relation and called it pseudo Fibonacci sequence. This sequence is further extended to obtain another gen
eralization {Gn} • The various identities of these sequences are stated and proved in section (3.4), (3.5). In section (3.10), further generalization of {G„}
with its properties are discussed. Few results are verified by means of examples in section(3.11).
In chapter 4, the third order non-homogeneous recurrence relation has been studied to extend our concepts to Tribonacci sequence.
2
In chapter 5, another extension of Fibonacci sequence that gives rise to a new class of Fibonacci polynomials has been discussed. Some identities of these newly obtained pseudo Fibonacci polynomials are proposed and proved.
Chapter 6 contains pseudo Fibonacci sequence modulo m, a positive integer with the intentions of generalizing result to sequence obtained from pseudo Fibonacci sequence. This mainly involves in investigating the periodicity of the new sequence after modding out by m.
Finally, a brief summary of the work done is presented together with the future plans. The thesis ends with a Bibliography.
3
C hapter 2
Literature R eview
2.1 In tro d u ctio n
The Fibonacci sequence of numbers is named after its promoter the Italian mathematician, Leonardo Pisano also known as Fibonacci. In his book “Liber Abacci” meaning book of calculation or book of counting, published in 1202, he discussed the problem of rabbit regeneration. In relation with the generation of rabbits he posed the following problem. Suppose each month the female of a pair of rabbits gives birth to a pair of rabbits (of different sexes). Two months later the female of new pair gives birth to a pair of rabbits. What is the number of pairs of rabbits at the end of the year if there was one pair of rabbit in the beginning of the year?.
At the end of the first month there will be 2 pairs of rabbits. At the end of second month just one of these two pairs will have offspring and so the number of pairs of rabbits will be 3. At the end of the third month the original pair of rabbit as well as the pair born at the end of first month will have offspring and so the number of pairs of rabbits will be 5.
Let Fn be the number of pairs of rabbits at the end of nth month. At the end
4
of (n + l) th month there will be Fn pairs of old rabbits and as many pairs of new rabbits as there were pairs of rabbits at the end of (n — l)th month, that is F„_i. Mathematically this can be written as
■^n+1 — Fn + Fn-1.
As we have F\ — 1, F2 = 1, it follows that F3 = 2, F4 = 3, F5 = 5 and so on.
In particular, at the end of one year the number of rabbits equals to Fi2 — 233.
If the total number of rabbits for different months is listed one after other, it gives rise to a sequence of numbers as
1,1,2,3,5,8,13,21,34,55,...
This sequence of numbers is known as Fibonacci Sequence. Here every term of the sequence is obtained by adding the preceding two consecutive numbers.
We take one more problem which is structurally similar to Fibonacci’s rabbit problem [Tucker, 1980,pp. 112-113].
Consider a staircase having n steps. One can climb it by taking one step or two steps to begin with. How many ways can be there to climb the staircase?
Let us say there are Sn ways to climb the staircase. When one starts to climb, he takes one step or two to begin with. If he takes one step then there are Sn_ i steps to continue climbing the remaining n — 1 steps. If he takes two steps then there remains Sn- 2 ways to climb the steps.
Hence,
Sn = S, 1 + <Sn-2
are the possibilities to continue climbing the remaining n — 1 steps. This relation is equivalent to above mentioned equation. Here Si — 1 and S2 — 2.
This is again a Fibonacci sequence shifted by one term.
S n — F n + l-
In India, the discovery of these numbers was done much earlier in the 6th century, in connection with Sanskrit Prosody. Much of the emphasis was laid to study the effect in mixing the long (L) syllables with the short (S), giving different patterns of L and S within a given fixed length resulting in Fibonacci numbers. Paramanand Sing [16] mentions that Acharya Pingala (possibly 500 BC) was the first Mathematician to know these numbers. It is said that Acharya Virahanka (6th century AD) was the first Indian Mathematician to give a written representation of so called Fibonacci numbers between 600 to 800 A.D. The search of relation of these numbers was continued in Indian po
etry even after Acharya Hemachandra [1088 -1173 ].
Presently in most of the cases Fibonacci sequence is defined as follows:
D efinition The Fibonacci Sequence {Fn} is defined by the recurrence rela
tion
Fn = Fn_1 +F„_2, n > 2 (2.1)
with initial values (or seed values)
F0 = 0 and Fx = 1. (2.2)
2.2 B in e t Formula
Any term of {.F„} can be given by the recurrence relation (2.1). It will be a tedious task to calculate Fn for large value of n. However, it would be easy to calculate n th Fibonacci number directly if one knows the formula for Fn.
In 1843, Jacques Philippe - Marie Binet designed a formula for nth term of the sequence. Binet formula provides a method for computing any Fibonacci number Fn in terms of its index n without listing the previous (n — l)th terms of the sequence. Let a and ft be the roots of x2 — x — 1 = 0. Then by the standard linear difference equation method, the solution of (2.1) is given by
Fn = Cla n + c2£n, (2.3)
a — (3 Substituting c\ and C2 in (2.3), we get
f3 — a
Fn = <xn - p n a - 0 ’
(2.4) where ci and c2 are to be obtained from initial conditions (2.2). Thus we get
f
C\ + c2 = 0 era + c2/d = 1.
On solving above equations we get
1 , 1
C\ —--- and c2 =
(2.5) which is called Binet formula.
Note that a = 1 +0 5 and 0 - — -— are the roots of x 2 - x - 1 = 0 7
corresponding to the recurrence relation (2.1).
Also
a + /3 = l, a — (3 = V5, a(3 = —1. (2.6) Binet Formula can be used to find the sum of many series connected with Fibonacci numbers. One can illustrate this with the following example:
To find the sum of series
F3 + ^6 + Fg + ... + F3n, we have
i*3 + FIs + ... + F 3n
a 3 - (3Z a 6 - p a 3n - (33n
v/5 + V5 y/S
= -\={a3 + a 6 + ... + cc3n - (33 - /36 - ... - /?3n]
v 5
1 a 3n+3 — a 3 /33n+3- / 3 3
“ v/5l a 3 - 1 £3 - 1 Since
a 3 — l = a + a:2 — l = a + a + l = 2a, similarly,
P3 - l = 2(3.
Hence,
F3 + Fe + ... + F3n — ^ = [ —
,3n+3 a /33n+3 _
2a 2 (3
V5
a 3n+2 _ Q 2 _ 03n+2 + £ 2
_ 1 3n+2 _ £ 3„+2 a 2_£2
_ 2 V5 x/5
— g [-^3n+2 - M2]
F'An+2 ~ 1
2
Binet Formula has been used to prove different identities in chapters 2 and 3 ahead.
2.3 P le th o r a o f F ib on acci Identities:
The sequence of Fibonacci numbers possesses a number of interesting and important properties. The following are some simple properties of {F„}.
a) The sum of the first n Fibonacci numbers is the Fibonacci numbers two further of n minus 1.
± F k = Fn+2 - l . fc=0
b) The total of consecutive even positioned Fibonacci numbers is equal to the Fibonacci number one further along the sequence minus 1.
y Fzk = Fzn+i — i-
*:=0
c) The total of consecutive odd positioned Fibonacci numbers is equal to the Fibonacci number that follows the last odd number in the sum.
y Fzk—i = Fin- k=1
9
d) The total of the squares of first n Fibonacci numbers is the product of last number and the next Fibonacci number in the sequence.
tfe ~ FnFn+1, fc=0
e) The sum of the products of consecutive Fibonacci numbers is either the square of a Fibonacci number or Square of a Fibonacci number m in u s 1.
n+i F%+1, when n is odd,
k=2 F„+i — 1, when n is even.
*
f) The sum of squares of two consecutive Fibonacci numbers is equal to the Fibonacci number in the sequence whose position number is the sum of their position numbers.
F„ + Fl+1 = F2n+1-
g) For any four consecutive terms from Fibonacci sequence, difference of squares of the two middle terms is the product of two outer terms.
n + l F l = Fn-iF rn + 2 -
h) The product of two alternative terms of Fibonacci sequence is the square of the middle term between them plus 1 or minus 1.
Fn-iF n+i
F% + 1, if n is even, F% — 1, if n is odd.
i) The difference of the squares of two alternate Fibonacci numbers is the Fibonacci number in the sequence whose position number is the sum of their
10
position numbers.
j) A Fibonacci number Fmn is divisible by a Fibonacci number Fm.
In other words if p is divisible by q then Fp is divisible by Fq where m, n, p and q are positive integers.
k) The sum of any ten consecutive Fibonacci numbers is divisible by 11.
l) Fn+m = FnFm+i -h Fn—iFm, Tn, n > 1.
All the above properties can be easily proved by mathematical induction.
2.4 G en era tin g F u n ction
Generating function for the sequence a0,a i,a 2, ... is the function whose power series representation an is the coefficient of xn. Generating function establishes the connectivity between function of real variable and sequence of numbers.
They are often expressed in closed form by some expression.
The generating function for the Fibonacci sequence is given by
R.T. Harsen [5] has generalized this result by the relation Fm 4" Fm—\X
1 — x — X2
OO
E{x) = Y , F nxn/ n!,
n = 0
which can be expressed in terms of a, f3 as
p a x _ p fix
2.5 V arious E x ten sio n s o f F ib on acci Sequence
Many have extended Fibonacci sequence in different ways. In doing so, some of them have changed the initial values where as others altered the recurrence relation. Here we give some of the extensions of {Fn}.
2.5.1 H oradam ’s E xtension
One of the most widely used extension of Fibonacci that was given by A.F.
Horadam [8], [7]. He defined the extended Fibonacci Sequence as follows:
Let {W„} be a sequence defined by
W„ = Wn(a, b,p, q) = pWn-1 - qWn, n > 2 where p and q are arbitrary integers with Wo = a and W\ — b.
We observe th at {W„} reduces to the Fibonacci sequence {Fn} when p — 1, q — —l and a = 0, b = 1. i.e.,
Fn = Wn( 0,1, 1,-1).
Another form of generating function for Fibonacci sequence is Exponen
tial G e n era tin g function given by
It is very interesting to see that Wn(a,b,p, q) itself can be modified to give other forms of sequences. Some of its special cases can be seen in the following table:
a b P q
1 Integers 0 1 2 l
2 Odd numbers 1 3 2 l
4 Geometric Progression 1 r r+1 r
6 Fermat’s Sequence 1 3 3 2
7 Fermat’s Sequence 2 3 3 2
8 Lucas Sequence 2 1 1 -1
Table A: Special cases of Horadam’s Sequence Binet Formula for Wn is given by
(2.9) here
/ — 2(6 — a/3), m = 2(6 — aa), d = a — /3 (2.10) where a , /3 are the distinct roots of x2 — px + q = 0.
Note that a + (3 = p and a/3 = q.
R em ark: For p = 1, q = - 1 and a = 0,6 = 1 equation (2.10) reduces to Wn = Fn = an — /?"
a - / ? ’ where a and /? are the roots o f x 2 — a: — 1 = 0.
P ro p e rtie s o f Wn(a, b;p,q):
13
Wn(a, b;p, q) has very interesting properties which can be easily proved by us
ing Binet Formula. Some of its properties are listed below:
1 Z W k = Wn+2 ~ b ~ ( p ~ 1)(Wn+1 - a)
k=o p — q — 1 ’
*
o ^ xxr (1 + ? ) ( ^2n+2 ~ o) - (Pq)(W2n+1 - W .X) I , yy2k —---5— ——rr5---,
k=o p2 - (q + l) 2
o ^ xxt p(w2n+2 - a) - q(l + q){W2n+i - W -1)
'' 2fc+l o / i i\2 *
k=o p2 - (q + l)2
where IFlj = pa
4. E ( - i m k=0
k u , _ (P + l ) [ ( - l ) nWn+i + a] - b + ( -1 )n+lWn+2 p - q - l
5. E ( - lW n' kWk+1Wk = ^ ^ — ^ ,
k=o P
6. W„+r = Wru n - qWr-iU n-i = WnUr - qWn- XUr. u where Un = Wn(0 ,1 \p,q).
7. W 2 = Wn+xWn. x - e q n~l where e — q[bW-X — a2].
T heorem 1. The generating function for {W„} is given by W (x) = a + {b — ap)x
1 — px — qx2 (2.11)
Note: For a = 0,6 = 1 and p = l,q = -1 , equation (2.11) reduces to generating function of {F„} as given in (2.7).
14
The exponential generating Wn is given by
E ( x ) ^ [ leax - me0x}. (2.12) Note: For p = 1, q — —1, o = 0, b = 1 and l = 2, m = 2, above reduces to
which is the exponential generating function for Fn as derived in the section (2.4).
2.5.2 Fibonacci Polynom ials
One of the generalizations of Fibonacci numbers is Fibonacci polynomials.
These polynomials are defined by the recurrence relation similar to Fibonacci numbers. Fibonacci Polynomial is defined as follows:
Definition: The nth Fibonacci Polynomial Fn(x) is defined by the relation Fn(x) = xF(n-\){x) + F(n_2){x) with F0(x) = 0, Fi(x) = 1.
Fibonacci polynomial reduces to Fibonacci numbers when x — 1. i.e., F„(l) = Fn where Fn is the Fibonacci number.
2.5.3 Fibonacci Function by Francis Parker
Francis Parker [15] studied another form of Fibonacci polynomial called Fi
bonacci function and is defined by
F(x) = a cos(nir)a x
~ 7 E
(2.13)
15
Here a is the larger of the two roots. Observe that for x — n, F(n) = an — cos(rar)a n
a n _ (_l)»(_l)-»0»
V5 a n - / 3 n
V5 • Thus F(x) reduces to Fn when x — n.
2.5.4 E xtension due to Horadam and Shannon
Horadam and Shannon [10] extended (2.14) by defining the Fibonacci curve as follows:
fyX _ ®
F(x) = ---j=---. Here F{x) reduces to Fn when x — n.
V5
2.5.5 E lm ore’s Extension
Elmore [3] used the concept of derivatives of function to extend the Fibonacci sequence as follows:
gdX _
Let F0(x) = ---j=— , where a and ft are the roots of x2 — x — 1 = 0.
V5
Define successively F\(x), F2(x), Fs(x). . . by
Fi(x) = Fq(x) =
F2(x) = Fq(x) =
aeax - Pe13*
7E ’
a2eax — P2ePx
In general,
/ ^ n meax — BmePx
Fm(x) = Fim)(x) = - --- ^ ---, m > 1.
16
We observe that Fm+1(x) - Fm(x) + Fm_1(x), when x = 0, Fm(0) - Fm. Thus Fn(x) is another extension of Fn.
Taking a, /? as the roots of x2 — px + q = 0 and using similar process we define
, a n e ™ - p n e f!x
Fn(x) = --- ---, where d — a - /3.
We easily see that F*(x) - pF*_x(x) - qF*_2(x). In this case F*(0) = F*
where F0* = 0, F* = 1, but F* = pF*_x - qF,n - 2 -
2.5.6 E xtension by J.E.W alton and A .F . Horadam
J.E.Walton and A.F. Horadam [28] generalized Fibonacci function by using Elmore’s concept as follows:
Let Go(x) = \leax — me^xj
where a , /3 , l and m are as in (2.10) and p = 1, q — —1.
Define successively Gi, G2, ... by
G ^ x) = G'q(x) = [laeax - m ^ x] , G2(x) = Gq(x) = [lc?eax - m ^ x\ , In general,
G„(x) = Gj,”>(x) = [/a"e“ - m /S V *], It can be easily seen that when p = 1 , q = — 1,
Go(0) = a = Wo, Gj(0) = b = Wx and in general G„(0) = [lan - m/3n] = Wn(a, b; 1, -1).
17
Horadam [9] extended the Fibonacci numbers to complex number field by defining them as F* = Fn + iFn+\ . Berzsenyi [2] defined this by taking dif
ferent approach as a set of complex numbers at Gaussian integers and called them as Gaussian Fibonacci numbers. He defined them as follows:
Let n and m be a non negative integer. The Gaussian Fibonacci numbers F (n,m ) are defined as F (n ,m) = J2 (T)ikFn- k where (n, m) = n + im are the Gaussian integers and Fj are the (real) Fibonacci numbers. He proved that F(n,m ) = F (n — 1, m) + F(n — 2,m ), n > 2. This relation implies that any adjacent triplets on the horizontal line possesses a Fibonacci type recurrence relation. In 1981, Harman [6] elaborated Berzsenyi’s idea and defined another set of complex numbers by using the Fibonacci recurrence relation. He defined them as follows:
Let (n, m) = n+ im . where n ,m E Z. The complex Fibonacci numbers denoted by G (n,m) are those which satisfy
(7(0,0) = 0, (7(0,1) = i, (7(1,0) = 1, (7(1,1) = 1 + i, G{n + 2, m) = G(n + 1, m) + G(n, m), and
(7(n,m + 2) = G (n,m + 1) + G{n,m).
The initial values and the recurrence relations are sufficient to specify uniquely the value of G(n, m) and for each (n, m) in the plane. It is easy to see that G(n, 0) = Fn and (7(0, m) - iFm.
Harman’s definition has three fold advantages over Berzsenyi’s as given below:
2.5.7 E xtension to Complex Fibonacci Numbers
1-In Berzsenyi’s definition any adjacent horizontal triplets in the plane satisfy the Fibonacci recurrence relation where as in Harman’s definition any horizon
tal and vertical triplets are same.
2. Horadam’s Complex Fibonacci numbers F* come as a special case for Har
man’s. Indeed, F* = G(n, 1).
3. Harman was able to prove some new summation identities for {Fn}. Pethe [18], in collaboration with Horadam extended Harman’s idea to define Gen
eralized Gaussian Fibonacci numbers. They again denoted these numbers by G(n, m) and defined them at the Gaussian integers (n, m) as follows:
Let Pi, Pi be two fixed non zero real numbers. Define
(7(0, 0) = 0, (7(0,1) = i, G( 1,0) = 1, (7(1,1) = P2 + iPi with the conditions G(n -f 2, m) = PiG(n + 1, m) — qiG(n, m), and
(7(n, m + 2) = P2G(n, m + 1) — g2(7(n, m).
Using this extension of Harman’s definition they were able to obtain vari
ous summation identities involving the combination of Fibonacci numbers and polynomials, Pell numbers and polynomials and Chebyshev polynomials of the second kind.For example it is proved that:
G(n + 2k + s ,m + 2k + s) = bp( 1 + i) E { - i y q (2k~^Un+j +sUm+j+s2k j=i
+apq2 E (—l)JV 2fe-j)Un+j_2k 2+sUm+j_i-t-s + q2kG(n + s,m + s) j=i
where s = 0 or 1, and Un — VFn(0, l;p, q).
Putting different values for p, q, a and b, we get various identities involving the Fibonacci numbers, the Pell numbers and polynomials etc.
19
Fibonacci numbers can be extended to Tribonacci numbers as follows:
Definition: Tribonacci numbers sequence Sn is defined by
Sn = PlSn-l + P2*Sn—2 + P3Sn-3i (2-14)
where n > 3 and Pi,P2,P3 are arbitrary integers. Many scholars studied this se
quence by taking different initial conditions. Shanon and Horadam [22] studied this sequence by taking following three sets of conditions.
2.5.8 E xtension to Tribonacci Numbers
So — 0, Si — 1, S2 — Pi, (2.15) So = 1, Si = 0, S2 = P21 (2.16) S0 = 0, Si = 0, S2 = Pz- (2.17) Denote the {S„} with condition (2.16) by {S*}.
One can observe that for Pi = 1,P2 = 1 and pz = 0, {S'*} reduces to {Fn} .
2.5.9 E xten sion of Fibonacci sequence using General
ized Circular Functions
The generalized circular functions are defined by Mikusinsky [12] as follows:
Let
oo f n r + j
J ^ (nr + j)\
oo -fnr+ j
NrJ® " 5 (nr + i ) !’
j = 0,1, •••, r — 1; r > l (2.18) j — 0,1, —,r — 1; r > l . (2.19) 20
Note that
NitQ(t) = el, N2,o(t) = cosht, N2ti(t) = sinht and Mifl(t)= e~l, M2fi(t)= cost, M2>1(t)= sint.
These functions are studied by Mikusinski and proved some of their basic properties. Further studies of these functions are found in Pethe and Sharma [17],
Results for generalized circular functions
Differentiating (2.18) and (2.19) term by term with respect to t, it can be easily seen that
Mr,j-p(t), 0 < p < j, Mr,r+j— p(t)> 0 — J ^ V — 'C-
(2.20)
JvffW =
Nr,j-p(t), 0 < p < j,
Nr,r+j—p(t')i 0 — 3<~ 3 <• P — T- Particularly in (2.21) note that
JV$<t) = Nr,o(t).
(2.21)
In general
Further note that
N $ )(t) = Nr<Q(t ) ,n > l . (2.22)
Nr,o(0) = N $ \0) = 1
21
Observe that from (2.21) for a fixed value of r the functions consti
tute a fundamental system of differential equations.
y (r) + Y = 0 (2.23)
such that
M-j}(0) = 6pj , (p ,j = 0,1,..., r - 1). (2.24) S.P. Pethe and C.N. Phadte [19], studied generalized Fibonacci functions using the property of circular functions. They defined it as follows:
Definition: Let
Po(x) = ^ [ l N Tfi(a*x) - mNrfi(l3*x)] (2.25) where r is a positive integer and
a* = a 1/r,p* = P1/r, (2.26)
a, 13 being distinct roots of x 2 — px + q = 0 and Z, m, and d are as defined in (2.10). Note th at a + 13 = p, a{3 = q.
A sequence of generalized Fibonacci function {Pn(a;)} is defined as follows:
Pi(x) = Por)(x), P2(x) = Pq t){x), and in general,
Pn(x) = P t \ ^ , n > l . Then from (2.25) we get
Pi(x) = ^ [ la N rto{a*x) - m/3Nrfi{j3*x)}
22
A(x) = ^ [ l a 2Nrfi(a*x) - m/32Nrfi(/3*x)}
In general, Pn(x) = -^[lanNrfi(a*x) - mPnNrt0(/]*x)].
Observe that for r = 1, a* = a, /3* = /3 and Nrfi(t) = Nlfi(t) = el with p = 1, q = — 1 and r = 1, becomes
P"(X) = 2^ a "e"* “ mfine^x] = Gn(x). We have the following.
Theorem 2. Pn(x) satisfies the recurrence relation
Pn{x) = pPn_j(x) - qPn_2{x). (2.27) For simplicity , let QntT(l,a ‘,x) = lanNrfl(a*x) with the corresponding ex
pression for Qn,r(m,/3; x).
Note that Pn(x) = '^j\Qn,r(l>&]X') Qn,r(pi> fi] x')}.
The various identities of Pn(x) are listed below:
i) E Pk(x) = Pn+2^ ~ P l^ ~ (p ~ 1)[p"+i(x) ~ Afo)]
f / , xfc P /_% (P + l)[po(i) + (—l)n+2Pn+1 (x)] - Pi (a:) + ( - l ) n+1Pn+2(x)
n j - M i j n W - (p + g + 1)
iii).Pn_i(x)Pn+1(x) - P 2(x) = Q n ,r ( J i X^Qn^r^TTl, /9, x)
iv) -P„ {x)E*+1 (x)-q Pn-i (x)F£ (x) eaXQn+sAh x) - e/3XQ n + s , r ( m , fi\ x) 2d
\ t~i / \ n* / \ r> /■ \ rr>*/ \ &aVQn+s,r(l> U) A* QnjrS,r{m‘i U) v).Pn(u)E*s+1(v) - gP„_i(n)P;(n) = ---—---
i).P„2(x) - gPn2_: (x) = --- ^ ---
23
vii).p2+1(x ) _ q2Pl_l {x ) = ER h S l' a;x>> Ql,r(m,P;x)]
4 q
Viu).Pn+1- s(x)Pn+1+s(x)-P Z+1{x) = lQ n + lA ^ x )Q n + lA ™ ,M ] l2 <* ' F <**0 °]
4 a?
ix)-P„(x)P„+l+t(x)-P„-,(x)P„+i+nl(x) = {p« A ‘,*;x)P*Arn,l}-,x)(a- P‘){a‘+M ft 4 (Pqs
All these properties can be proved by using Binet formula.
2.6 F ib o n a cci N u m b ers and B in o m ia l Coeffi
cien ts
There is an interesting connection between Fibonacci numbers and Binomial coefficients [26]. We get the following pattern if Binomial coefficients are ar
ranged in a triangular arrays as follows:
/
V
/ \ / \
1 1
v0 M1)
M M M
\° A 1 A 2;
/ \ (
_\ V1 / v2;
\
/
( . \ V 0 /
( . \ ( . \ V 1 A 2 /
/ \
v 3 / ( . \ v 4 /
Table B: Binomial coefficient in triangular array Above pattern is also called Pascal Triangle which is listed below:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Table C: Pascal Triangle
We left align the above triangular arrangement can be listed as below.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Table D: Triangular array of numbers
Lines connecting the number of triangular array shown in Table D are called ascending diagonals. We observe that the sum o f th e num bers on th e ascending diagonals are Fibonacci num bers. We prove this fact as follows:
It can be observed that each of the first two ascending diagonals consists of number 1. i.e., Fq and F\. In order to prove the result, because of the relation (2.1), it is sufficient to show that the sum of all numbers making up (n — 2)th and (n — l) th diagonal of the triangular array is equal to the sum of numbers lying on the nth diagonal.
The (n — 2)th diagonal consists of the numbers
n-3 \ ' (n-3)/2 ^
0 , V 1 ,
*•*?
v (n-3)/2 , if n is odd and
\ ( \ ( , , , \
n-3 n-4 (n-4)/2
0 , 1
< 1 > ^ (n-4)/2 J if n is even.
The (n — l) tfl diagonal consists of the numbers
n-2 \ I n F / \
(n-2)/2 0 >
?
, 1 y
’"J
to "to
if n is even.
The (n — \ ) th diagonal consists of the numbers
/ N / \
n-2 n-3
. 0 y
>
, 1 y
' (n-l)/2 ' , (n-3)/2 t if n is odd. Hence,
the sum of numbers of the (n - l) th and (n - 2)tfc diagonals is
/ \ (
n-l n-2
+
\ 0 , < 1
+ ... + (
\
(n + l)/2
(n-3)/2
\ / \
(n-l)/2
+
(n-l)/2
if n is odd and
M *
n-2 ^
+ ...+
/ \
(n+2)/2
+
/ \
(n)/2
° J V 1 , ^ (n"4)/2 y ^ (n-2)/2 j if n is even. We use the fact that
V
w
= 1
and
( \ ( \ (
k k k+ 1
+ —
< < i ^ i + 1 J i+ 1
The sums that are obtained are the numbers that lie on the nth diagonal of the triangular array if n is odd or even. This proves the theorem. British mathe
matician Ron Knott [31] provided interesting insights into Fibonacci numbers.
He found Fibonacci numbers as the sum of “rows” in the Pascal triangle. The arrangement of numbers by drawing Pascal triangle with all the rows moved
over by one place shows the Fibonacci numbers as the sums of columns shown in the table below:
Table E: Fibonacci numbers as sums of columns
Pascal’s triangle is drawn with all rows moved over by one place. It clearly shows the Fibonacci numbers as sums of columns as shown in the last row.
2.7 D iv isib ility p rop erties o f F ibonacci N um b ers
Here we list some results on divisibility of Fibonacci numbers. Divisibility of Fibonacci numbers is important when we try to study the periodicity of the sequence.
T heorem 3. I f n is divisible by m then Fn is divisible by Fm.
Proof. Let n be divisible by m. Then n = mmi, where mi is a positive integer < n. We prove the theorem by induction on mj.
If mi = 1 then n = m and the result is obivious. Assume that the result holds for mi = k. Therefore, Fmk is divisible by Fm. Now consider Fm(fc+i). Using property (1) of section (2.3), we get
Fm(k+1) = FmkFm+1 + Fjnh—iFfn,.
The right hand side of this equation is divisible by Fm. This proves the theo
rem. ^
T h eorem 4. : Consecutive Fibonacci numbers are relatively prime, i.e., [F„,F„+i] = 1.
Proof. If Fn and Fn+\ have same common divisor d > 1 then
Fn+1—Fn = Fn_! is divisible by d. We can prove by induction that F„_2, Fn_3,...
and finally Fo is divisible by d > 1. This contradiction proves the theorem. □ The following properties are easy to prove.
(a) A Fibonacci number F„ is even if and only if n is divisible by 3.
(b) A Fibonacci number Fn is divisible by 3 if and only if n is divisible by 4.
(c) A Fibonacci number Fn is divisible by 4 if and only if n is divisible by 6. (d) A Fibonacci number Fn is divisible by 5 if and only if n is divisible by 5.
(e) A Fibonacci number Fn is divisible by 7 if and only if n is divisible by 8. (f) There is no Fibonacci number that gives the remainder 4 on division by 8
and also there is no even Fibonacci number divisible by 17.
Chapter 3
Pseudo Fibonacci Sequence
3.1 In tro d u ctio n
It is well known that Fibonacci sequence has been generalized in many ways to generate a new sequence. These generalizations are based on either changing the coefficients in the homogeneous recurrence relation defining the Fibonacci sequence or by changing the initial or seed values. In this chapter we define a new sequence using a non homogeneous recurrence relation which gives rise to a generalized Fibonacci Sequence. We call this sequence as pseudo Fibonacci sequence.
D efinition: The Pseudo Fibonacci Sequence {gn} is defined as the sequence satisfying the following non-homogeneous recurrence relation.
fl'n+2 = 9n+1 + 9n + A tn, n > 0 and t 7^ 0, CHI, Pi (3-1) with go = 0 and g\ = 1. Here t is a fixed parameter for the relation (3.1) . The first few terms of {#„} are:
g2 = l + A, g3 = 2 + A + At, g4 = 3 + 2A + At + A t2 and so on.
Observe that each pseudo Fibonacci number is such that its first term is a Fibonacci number and remaining terms form a polynomial in t with coefficient
A times a Fibonacci number, pseudo Fibonacci Numbers for negative indices are given by the non-homogeneous relation <?_„ = 9 - n+2 — 9-n+1 — At~n.
As in case of all the extensions of Fibonacci sequence, we can obtain Binet type formula for pseudo Fibonacci sequence in the usual way.
Binet ty p e form ula for {gn} is given by
9n = ci a? + c2/?" + ptn, (3.2) where ai and Pi are the roots of characteristic equation x 2 — x — 1 = 0. The constants Ci, c2 and p are
_ [(1 - p { t - P i ) } _ \p(t - a i) ~ 1] A
1 a i - Pi 2 a i - Pi ’ (t2 - t - 1 ) '
Binet type formula is useful in developing the theory of pseudo Fibonacci sequence. We shall use it in the subsequent sections of this chapter to obtain various identities.
3.2 S o m e F u n d am en tal Id en tities o f {gn}
Many interesting identities may be derived for the sequence {gn]- Some of the identities are given below.
i) T he G e n e ra tin g Function of {^n} is given by
Z (x) = , ^ + 1~2V provided |t| < 1.
(1 - t)(l - x - x 2)
Proof. Let Z{x) = £ gnxn. Then, fc=0
z {x) = go + g\x + g2x 2 + ... + gkxk + ...
xZ{x) = g0x + gi x2 + g2x 3 + ... + gkxk+1 + ...
(1 + x )Z (x ) = g0x + (gx + g0)x + (g2 + g i)x2 + ... + (gk + gk_lXk + ...
= 9o + (92 ~ A )x + (g3 - at)x2 + ... + (gk+1 - Atfe_1)xk 4- ...
OO
x ( l + x ) Z ( x ) = go + g2x 2 + g3x 3 + ... + gk+1xk+1 + ... - A Y ^ i k 0
OO
= z(x) - g i x - A j 2 t k-
Since go — 0 and pi = 1, we get, Z(x){x2 + x — 1) = —g\x — £ tk.
k= 0
Hence
Z(x) =
x + 1
1 - 1 (1 — X — X2) ’
x(l — t) + 1
(1 — t){ 1 — X — X2), provided |t| < 1.
ii) E gk = gn+2 - gl - A E t l
k=0 k=0
Proof The recurrence relation (3.1) can be written as
□
9k = 9k+2 — 9k+1 — Atk.
Adding up the equations for k = 0,1, ...,n term by term, we obtain
n n+2 n+1 n
fc=0 fc=2 fc=l fc=0
n ^ n n
= ( E 9 k - g o ~ f f i+ gn+1 + gn+2) - ( E 9k - go + gn+\) - A E
*=0 fe=0 k=0
n
= 9n+2 - fl-l ~ A 5 3 <*•
k=Q
Hence the result. □
hi) E g2k -l = g2n ~ g-2 - A £ t 2k~2.
k=0 k=0
Proof. From equation (3.1) we write
92k—1 = 92k ~ 92k~2 ~ At2k~2.
Adding up the equations for k = 0,1,..., n term by term, we obtain
5 3 92k—1 = 5 3 52k ~ 5 3 £,2k-2 - a 5 3 i2fe-2,
fc=0 k=0 k=0 fc=0
= 5> * ~ n£ g 2 k - A ± t 2k- 2,
fc= 0 fc= —1 fc= 0
= l?2n - 9 - 2 - A E ^ fe~2- fe=0
□
iv) E g2k = g2n+l - g-1 - A E t 2k_1.
k=0 k=0
Proof. Recurrence relation (3.1.1) can be written as
a j.2n—l 92n = 92n+1 ~ 92n-1 ~ At
R e p e a ted u se o f t h e ab ove eq u a tio n for k = 0 , 1 , 2 ,n a n d su m m in g up lead s to,
X^ 92k = 5 3 92k+i — ^2 52fc-i — A ^2 i 2fe~ \
fc=0 fc=0 k—o k=0
— XT 92k+i — X I 52*1+1 ~ A X ] i 2fe_1,
k=0 k——1 *=0
= 92n+\ ~ 9\ ~ A j 2 t 2k~l ■
*:=0
□
V) E g 3 k -2 = 2 {gSn - g —3 + A ( 1 + t ) E t 3k~3 }.
k=0 0
Proof. F rom t h e recurrence re la tio n (3 .1 ) w e w rite,
29n — 9n+2 — 9n- 1 + A t” X( l + t) . (3-4)
For n = - 2 , 25_2 = 50 - 5-3 + A t~ 3( l + 1), For n = 1, 2gx = gz - g0 + A t ° ( l 4 - 1), For n = 4, 2g4 = 5e ~ 53 + A t3( l + 1), . . . For n = k, 2gk = 5fc+2 - gk-i + A t fc-1( l + i).
A d d in g th e le ft h a n d sid e term s a n d righ t h and sid e te rm s separately, w e g e t 2 E 53fc—2 = E 53k ~ E 53*: + A (1 + t) E ^ ' 3-
k=0 fc=0 * = - l 0
H ence,
E 93k—2 = \{93n — 5 -3 + A (1 + 1) E t 3/5~3}-
k=o o
□
Vi) E g3k-l = |{g3n+l - g—2 + A(1 + t) E t 3k_2}-
k=0 0
Proof. R e p e a te d u se o f eq u a tio n (3 .4 ) for k = 0 , 1 , 2 , . . . , n gives th e follow ing eq u ation s.
For n = -1, 2g_! = ^ - g_2 4- A r 2( l + f), For n = 2, 2g2 = - 5 i + A*x( l + i ) , For n = 5, 2g5 = g7 - g 4 + At*(l 4 -1), . . .
For n = k, 2gk = gk+2 ~ 9k-i + A**-1( 1 4-1).
A d d in g th e le ft h a n d sid e term s a n d righ t h and sid e te rm s separately, w e get
2 E 93k-1 = E 53*+i — 2 93k—2 + A(1 + i) E*3fe-2-
k=0 fc=0 fc=0 0
H ence,
E 93k-\ — 2{93n+l — 9-2 + A (l 4- t) E ^ 3*- 2 }- □
fc=0 o
Vii). E g3k = §{g3n+2 ~ g-1 + A(1 + t) E t 3k_1}.
k= 0 0
Proof. R e p e a te d u se o f eq u ation (3 .1 ) for k = 0 , 1 , 2 , . . . , n giv es th e follow in g eq u ations.
For n = 0, 2g0 = 92- 9-1 + A*_ 1 ( l 4 -1), For n = 3, 2g3 = 95~ 92+ At2( 1 4 - 1), For n = 6, 2g& — g&- g^ + At5( 1 4-t), . . .
For n = k, 2gk = gk+2 - gk- 14- A t fc_1( l 4-1).
A d d in g th e le ft h a n d sid e term s a n d right hand sid e te rm s separately, w e g et 2 E 93k = ~ 9 - l + 93n+2 + A (1 4 -1)E t3k~l .
k=0 0
H ence,
E 93k = \{g3n+2 - g-i + A( 1 4- 1) E*3*'1}.
k=0 0
□
viii) £ © g n -k = g2n - p[t2n - (1 + t) “], where p = -- ^
k=0 ' — t — 1
Proof. Using Binet type formula (3.2), we get
= ci(l + m )" + c2( 1 + &)" + p{ 1 + t)n
= cia?" + c2^ n + pt2n - pt2n + p( 1 + f)n
= 92n-p\t*n - ( l + t ) n}.
ix) E (k)g3k = 2n(g2n - p t 2n) + p ( l + t 3)n, k=0 v /
Proo/. Here we use the relation a f + 1 = 2a2 which is obtained from charac
teristic equation a 2 = au + 1. We have
= c i ( i + a i r +0 2(1+ p i t+p( i + t3r
= c1(2a2)n + c2(2/32r + p ( l + t 3r
= 2 n ( Cla 2n + c2P ln + p t 2n) - 2np t 2n + p ( 1 + t 3)n
= 2ng2 n - 2 np t 2 n + p ( l + t 3)n
= 9 2 n - p [ t 2 n - ( l + t n
l n — fe
Hence the result.
□
where p = A
t 2 - t - 1'
□
S im ilarly, w e h ave th e fo llow in g result.
x). E (k)g4k = 3n(g2n - p t2n) + p (l + t4)n], k=0 '
w here p = —---.
v t 2 - t - 1
Proof. T h e p r o o f is sim ilar t o th e a b o v e ex cep t th a t w e u se th e relation, a f + 1 = 3 a \.
t ( * ) s « = t ( * ) ( C l < + ^ + pt«)
=Cl( i + a i r+ C2( i + f i r +p(i + t4r
= ci (3a2)" + c2(3 01Y + p(l + t4T
= 3"(Cla 2n + c2Pin + pt2n) - 3npt2n + p{ 1 + t4r
= T g 2n - 3 npt2n+ p (l + t4)n.
H ence th e re su lt.
□
w h ere T n = E t 2k+1
k=0 Proof. W e p ro v e th is result b y m e th o d o f induction.
R e su lt h o ld s tr u e for n = 1.
A ssu m e t h a t it is tr u e for all v a lu es o f k from 1 to n i.e .,
n—1
„ M " +1 + 9n+ltn - 1 - A E t2k+1]
E 9ktk~l = --- fc"°
fc=0 (t2 + t - 1)
N ow t o p ro v e th a t it is tru e for n = k + 1 i.e., to p rove
E 9ktk~l k=0
[9n+itn+2 + gn+2t n+1 - 1 - A £ t2k+1]
_______________________ fe=0____
(t2 + 1 - 1)
C onsider
n+l n
£ 9ktk~x = £ 9ktfc_1 + 9n+ltn
fc=0 k=0
n—1 [9ntn+1 + 9ntn ~ 1 ~ A E t2k+1]
k=0
(i2 + 1 - 1) + 9 n + l t n
n—1
[</n*n+1 + s„+1r - 1 - i E t2k+1] + gn+1tn( f + t - 1) fc=0
(t2 + i — 1)
n—1
[ ( S n * " + 1 + 5 n + l< n + 1 ) + 5 n + l< n + 2 - l - A Y , t 2 k + l ]
k=0 (i2+ t - l )
n— 1
[Sn+2*n+1 - A t2n+1 + 5n+l<n+2 - 1 - A E t 2k+1]
_______________________________ fc=0____
i f + t - 1)
H ence, E 9kt‘
k=0
fc-1 _ \gn+1t n+2 + gn+2t n+1 - 1 - ATn\
(t2 + t - 1)
T h is c o m p le te s th e proof.
□
Xii) E gk = gngn+l - A E gktk
k=0 k=0
Proof. L et u s p rove it b y in d u c tio n over n. For n = 1, id e n tity (xii) tak es th e form So + 9i = 9i92 ~ A(gQt~x + S i ) , w h ich is true.
A ssu m e t h a t it is tr u e for n — k i.e .,
£S fc = SnSn+i ~ A j 2 9 k t k X-
fc= 0 fc=0
(3.5)
We now prove that (3.5) is true for n — k + 1.
Adding g^+1 to both sides of the above equation gives
n+l n
Y 9k = gn9n+1 - A J 2 + 9n+l
k=0 k=0
n
= 9n+l[9n + 9n+l] — A ^ S f c ^ ” 1 fe=0
= 9n+l[9n+2 ~ A tn] ~ A J 2 9ktk~X k=0
n+1
~ 9n+l9n+2 ~ A ^ gktk~X, k=0
which proves that identity (xii) holds true for n = k + 1.
This completes the proof. □
3.3 A G en eralization to a new Sequence {Gn}
In this section, the sequence {gn} is extended to a generalized form defining a new sequence {Gn}. It is defined as follows:
Definition: A generalized pseudo Fibonacci Sequence {Gn} is the sequence satisfying the following non-homogeneous recurrence relation.
Gn+2 = pGn+i — qGn + A tn, n > 0, A ± 0 and (3.6) with
Go = a and Gi = b. (3.7)
Here a, b, p, q are arbitrary integers and a, /3 are the roots of x 2 — px + q = 0 . First few generalised pseudo Fibonacci numbers are given below:
Go = a, G\ = b,
G2 = (pb — qa) + A,
G3 = (p2b — pqa — qb) + Ap + A t,
G4 = (p36 - p2qa - 2pg6 + #2a) + A(p2 - ^) + ylip + At2, and
G5 = (p46 - p3ga - 3p2qb+2q2a + q2b) +A(p*~ 2pq) + At(p2 - q)p+At2p + At3.
Observe that each generalized pseudo Fibonacci number Gn, n > 2 consists of two parts. The first part contains expression in p, q, a ,b and the second part is a polynomial in t whose coefficients are A times the terms in p and q. This is shown in the following tables.
n Expression
2 pb — qa
3 p2b — pqa — qb 4 p3b — 2pqb — p2qa + q2a 5 p4b — 3p2qb + q2b — p3qa + 2q2a
6 p5b — 4p3qb — p4qa + 3 q2a + 2 q2 Table F : First part of G„
n A to At3 A t4 At5 At6
2 1
3 P 1
4 p2 - q P 1
5 p3 — 2pq p2 - q p 1
6 p4 - 3p2q + q2 p3 — 2pq p2 — q P 1
Table G: Second part of Gn, n ^ 2
From the above tables it can be concluded that Gm, the mth term of gen
eralized pseudo Fibonacci sequence is given by Gm = Wm(a,b;p,q) + A £ Wfe(0,
k=1
where Wm is m th term of the extended Fibonacci sequence or Horadams se
quence listed in Chapter 1. section (2.5.1). Thus we have TO— 1
T heorem 5. Form > 2, the term Gm — Wm(a, b-,p, q)+A £ VFfe(0, l;p, k=1
of the sequence {Gm} satisfy the non-homogeneous recurrence relation Gm+2 = pGm+1 — qGm + Atm.
Proof. Consider
’E1 Wk{ 0,1 ;p, q)tm~k+1 = Wxtm + W2tm~x + W3tm~2 + ... + Wm+i k=1
=Wxtm + (pWl - qWo)tm~l + (pW2 - qWi)tm~2 4-... + (pWm - qWm-1)
=Witm + p(W 1tm~1 + W2tm~2 + ... + Wm) - q{Wotm- 1 + W itm~2 + ... + Wm-1)
TO . TO—1 ,
=Wi*m + p £ Wfe(0, - g £ W*(0,
fc=l fc=o
That is, m+l
*=i
£
£ Wk(0 ,l;p ,q )tm- k+1) =m m—1
+ p £ w*(0,1; p, g)tm- fc - g 53 h m o, i ; p, g ) r- fc- 1 (3.8)
fc=l fe=0
Now
fc=i
Gm+2 = Wm+2(a, 6;p, q) + A £ m+l
wk(
0,1;p, q)tm~k+1.k=l Using equations (3.6) and (3.8),
Gm+2 = pWm+i(o, b;p, q) - qWm(a, b;p, 9) + Ap 53 Wk{0,1; p, q)tm~k k=1
m—1
- g 4 £ Wlfe(0, l ; p , g ) r- fc- 1 + A W
= p[Wm+i(a, b;p,q) + A £ Wfc*m" fc]
fc=i
TO—1
- g[W(a, 6;p, g) + A 53 Wfc(0, l;p , g)*”1- * ' 1] + At"
k=0
—pGm+1 — gGm + -df”
Hence the theorem.
□
3.4 S o m e F undam ental Id en tities o f Gn
In this section we obtain some fundamental identities {Gn} which are useful in further development of the subject.
(i) B in et T y p e Formula: Let the homogeneous relation corresponding to the equation (3.6) be given by
Hn+2 = pHn+1 - qHn (3.9)
If a and j3 be the roots of x2 — px + q = 0, the characteristic equation of (3.9), then
with the initial conditions as of Gn, i.e. Hq = a and H\ — b.
a —P + d „ _ p - d
2 ’ P 2 (3.10)
where d = y/p2 — 4q ^ 0. Note that
a + = p, a (3 = q, a — (3 = d. (3-H) We now obtain the Binet type formula of generalized pseudo Fibonacci sequence.
T h eo rem 6. For every n E N , th e B inet ty p e formula of G P F Sequence is given by
Gn = Cia" + c2/3n + z tn, (3.12) w here
(b — a/?) — z(t — P) (aa — b) — z(a — t) Ci — --- , c2 = —
a —13 a — j3
A t2 - p t + q
(3.13) Proof. Let G ^ = ztn be the particular solution of (3.6), hence
z tn+2 = zptn+1 — zqtn + A tn, which gives 2 = —--- . t2 —pt + q Hence particular solution is
Atn
t2 —pt + q (3.14)
C1 + C2 = z — a and Cia + c2fi — b — zt.
Solving these equations for c\ and c2 , we get, Using initial conditions we get,
(b — aft) — z{t — P) _ (aa — b) — z(a — t)
a — [3 ’ °2 a — (3
Hence solution of (3.9) is
(3.15)
HW = c1cr + c20 n (3.16)
and the general solution of (3.6) is given by Gn = H W + GW = Ci a" + c2pn + ztn
which is as required. □
Note that
C1+C2 = a—z, ci— C2 = ((2b—ap)—z(2t—p))d~1, C1C2 = edT2 (3.17) where e = abp — b2 — a2q — z{bp — 2bt — 2aq + atp + A}. Gn in terms of Un can be given as
Gn - bU„ - aqUn- 2 + (ztn - ztUn- 1 + zqUn- 2) Qn+1 _ ftn+1
where Un = --- -— is the generalized Fibonacci number [7] which a — p
satisfies the recurrence relation
Un+2 — pUn+i qUn.
