A Nonlinear Extension of Fibonacci Sequence
1Department of Mathematics, Goa University, Taleigaon Plateau, Goa, India
Abstract | |
1. | Introduction |
2. | Fibosenne Sequence {P(n)} |
3. | Some Congruence Properties of Fibosenne Sequence {P(n)} |
4. | Conclusion |
References |
Abstract
A new extension of Fibonacci sequence which yields a nonlinear second order recurrence relation is defined. Some identities and congruence properties for the new sequence are obtained.
Keywords: fibonacci sequence, nonlinear recurrence relation, congruence properties
Received July 01, 2016; Revised August 26, 2016; Accepted September 03, 2016
Copyright © 2016 Science and Education Publishing. All Rights Reserved.Cite this article:
- M. Tamba, Y.S. Valaulikar. A Nonlinear Extension of Fibonacci Sequence. Turkish Journal of Analysis and Number Theory. Vol. 4, No. 4, 2016, pp 109-112. http://pubs.sciepub.com/tjant/4/4/4
- Tamba, M., and Y.S. Valaulikar. "A Nonlinear Extension of Fibonacci Sequence." Turkish Journal of Analysis and Number Theory 4.4 (2016): 109-112.
- Tamba, M. , & Valaulikar, Y. (2016). A Nonlinear Extension of Fibonacci Sequence. Turkish Journal of Analysis and Number Theory, 4(4), 109-112.
- Tamba, M., and Y.S. Valaulikar. "A Nonlinear Extension of Fibonacci Sequence." Turkish Journal of Analysis and Number Theory 4, no. 4 (2016): 109-112.
Import into BibTeX | Import into EndNote | Import into RefMan | Import into RefWorks |
1. Introduction
T he well-known Fibonacci sequence F(n) is defined by
![]() | (1.1) |
is called the nth Fibonacci number. The Fibonacci sequence has been extended in many ways and it has many interesting properties and applications in different fields ([5, 6]). In recent years, Fibonacci numbers are also seen in many combinatorial problems ([1, 3]).
In this note, we present yet another extension of Fibonacci sequence and call it Fibosenne sequence defined by the relation
![]() | (1.2) |
where is the nth Fibonacci number. We call
the n th Fibosenne number in view of its form like Mersenne number
[4]. It is clear that
. We shall establish various relations for
in line with those of
. We shall also study some congruence properties of
.
2. Fibosenne Sequence {P(n)}
For , let
denote the
Fibosenne number. Then the following results follow immediately from definition (1.2) and from results on Fibonacci number
([2, 7]).
Proposition 2.1
1. For ,
![]() |
where are the roots of the equation
![]() |
2. For ,
satisfies the nonlinear second order recurrence relation,
![]() | (2.1) |
with initial conditions .
3. For ,
![]() |
Proof.
1. Follows from definition and Binet’s formula for
2. Follows from definition.
3. Follows from definition and
![]() |
The following properties can also be deduced easily. These properties are useful to find using the earlier Fibosenne numbers.
Proposition 2.2 We have
1.
2.
3. For
![]() |
4. For
5.
Proof
1. Using definition of and identity 18 for
given in ([2]), we get,
![]() |
Hence the result follows.
2. Using (1),
By recurrence relation (2.1), we see that
![]() |
Combining 1. and 2. obtained in this proof gives desired result.
3. We have for that
![]() |
(See [2] and [7]). Thus we arrive at the desired result.
4. Using the following identity and definition of result follows.
![]() |
The following results are concerning divisibility of
Proposition 2.3
1. For .
2. If .
3. If .
4. If is a prime such that
![]() |
Proof.
1. . Suppose
,
Then there is a prime
such that
divides both
and
. Hence by equation (2.1),
divides
. Inductively,
divides
, giving contradiction.
Proofs of (2)- (4) follows from the fact that, .
3. Some Congruence Properties of Fibosenne Sequence {P(n)}
In this section, we present some congruence properties of Fibosenne sequence. The following table gives Fibosenne numbers for .
A look at the Table 1 reveals that the last digit of P(n) follow the pattern 0113715, 113715, ... . Given , we have
and
. For
, the congruence properties of P(n) can be found by using the recurrence relation (2.1). For
, we show the cycles of
in Table 2.
Here we observe that P(n) modulo m show some pattern. After initial terms which we call “Base” there is periodic repetition of terms. We call it “Tail”. This suggests that there is a pattern for congruence residues, which is different from that of Fibonacci sequence. For all sequences, which show such a pattern for congruence modulo m, we define the Base length as the number of terms in the base and denote it by b(m), the base length of the sequence modulo m. Similarly, we define the Tail Period as the minimum number of terms repeating in the tail of the sequence modulo m and denote it by t(m). For example when , the sequence is 0, 1, 1,3,3,.... Here 0,1,1 is the base and 3,3,3,... the tail. There are three terms in the base and hence b(4)= 3 . In the tail number 3 repeats and so t(4)= 1. In the second column of Table 2, base is shown in brackets. If there are no initial terms forming base, then b(m) = 0 and the bracket is omitted. It is noteworthy that for m = 11, b(11) = 46 and t(11) =12.
From Table 2, for m = 10, the following result follows immediately.
Proposition 3.1. For
![]() |
The following result also from Table 2.
Proposition 3.2
1. For and
![]() |
2. For and
![]() |
For let
be the largest
such that
For example,
etc.
Proposition 3.3 For
, for
. In this case
and
Proof. For .
![]() | (3.1) |
Given considering the Fibonacci numbers
and the smallest residues
of the terms modulo
, it was observed ([9], Chap.VII) that the sequence
repeats after
term as are given in ([9]) which we tabulate here:
is called pisano period of
modulo
. From the definition of
, it is clear that
Lemma 3.4 For and
,
![]() |
Using this lemma we prove the following:
Proposition 3.5 For and
, we have
![]() |
and for some
then
![]() |
Proof. We have
![]() | (3.2) |
Notice that in Proposition 3.5, suggest that
is odd. The case when
is power of 2 is dealt in Proposition 3.3. When
is even, but not power of 2, we have the following:
Proposition 3.6 For and
, if
![]() |
where and
, for some
, then for
where
is independent of u. Here
.
Proof. We see for that
![]() | (3.3) |
where is the remainder when
is divided by
.
We have the following corollaries.
Corollary 3.7. For we have
![]() |
Proof. Follows from Proposition 3.5 as and taking
.
Corollary 3.8. For ,
![]() |
Proof. As so taking
Proposition 3.5,
When .
When .
Hence, by (1.2), for .
Similarly the congruence relations for can be obtained recursively.
Corollary 3.9. For
![]() |
Proof. As taking
and using Proposition 3.5 and proceeding as in the proof of Corollary 3.8 the result follows.
We have the following results on the tail period.
Proposition 3.10
1. If is an odd integer,then
and
, where
is Euler’s
- function. In particular, if
is prime, then
2. For
3. Let be an integer such that
then
Proof
1.
Thus the pattern in repeats after
terms. So
must be a multiple of
Also since the cycle repeats right from the beginning,
2. For
![]() |
3.
Using result (3) in Proposition 3.10, we have the following properties.
Proposition 3.11
1. For if
then
.
2. For if
then
.
3. If is the largest integer such that
and
for some prime
, then
, for all
4. If is a prime and
, then
.
5. If is a prime of the form
, then
6. If prime is of the form
and
, then
Proof
1. For if
Hence by Proposition 3.10 (3),
. Result now follows by ([8], Prop 3.5).
2. Follows as in (1) above from Proposition 3.10 (3) and ([8], Prop 3.7).
3. Follows as in (1) above from Proposition 3.10 (3) and ([8], Prop 3.8).
4. If is a prime and
, then
Then by Proposition 3.10 (3), . Hence
by ([8], Prop 3.11).
5. Follows as in (4) above from Proposition 3.10 (3) and ([8], Prop 3.12).
6. Follows as in (4) above from Proposition 3.10 (3) and ([8], Prop 3.13).
4. Conclusion
The new sequence defined using nonlinear second order recurrence relation has most of the identities satisfied by Fibonacci sequence. However the congruence properties of this sequence are different from those of Fibonacci sequence.
References
[1] | Z.Akyuz, S. Halici, On Some Combinatorial Identities involving the terms of generalized Fibonacci and Lucas sequences, Hacettepe Journal of Mathematics and Statistics, Volume 42 (4) (2013), 431-435. | ||
![]() | |||
[2] | A.T. Benjmin, J.J. Quinn, Proofs that really count: The Art of Combinatorial Proof, Mathematical Association of America, Washington, D.C., 2003. | ||
![]() | |||
[3] | A.T. Benjmin, J.J. Quinn, The Fibonacci Numbers Exposed More Discretely, Mathematics Magazine 76:3 (2003), 182-192. | ||
![]() | View Article | ||
[4] | D. Burton, Elementary Number Theory, 6th edition, Tata McGraw-Hill, 2006. | ||
![]() | |||
[5] | M. Edson, O. Yayenie, A new generalization of Fibonacci sequence and extended Binet's formula, Integers, Volume 9, Issue 6, Pages 639-654, ISSN (Print) 1867-0652. | ||
![]() | |||
[6] | J. Kappraff, G.W. Adamson, Generalized Binet Formulas, Lucas polynomials and Cyclic constants, Forma,19,(2004) 355-366. | ||
![]() | |||
[7] | M. Renault, The Fibonacci sequence under various moduli, Masters Thesis, 1996. | ||
![]() | |||
[8] | S. Vajda, Fibonacci and Lucas numbers and the Golden section: Theory and Applications, Dover Publications, 2008. | ||
![]() | |||