A Nonlinear Extension of Fibonacci Sequence

M. Tamba, Y.S. Valaulikar

Turkish Journal of Analysis and Number Theory

A Nonlinear Extension of Fibonacci Sequence

M. Tamba1,, Y.S. Valaulikar1

1Department of Mathematics, Goa University, Taleigaon Plateau, Goa, India

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.

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.

Table 2. Cycles of P(n) (mod m), b(m), t(m), 2≤m≤10

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:

Table 3. Values of π(m) for 2≤m≤30

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.
In article      
 
[2]  A.T. Benjmin, J.J. Quinn, Proofs that really count: The Art of Combinatorial Proof, Mathematical Association of America, Washington, D.C., 2003.
In article      
 
[3]  A.T. Benjmin, J.J. Quinn, The Fibonacci Numbers Exposed More Discretely, Mathematics Magazine 76:3 (2003), 182-192.
In article      View Article
 
[4]  D. Burton, Elementary Number Theory, 6th edition, Tata McGraw-Hill, 2006.
In article      
 
[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.
In article      
 
[6]  J. Kappraff, G.W. Adamson, Generalized Binet Formulas, Lucas polynomials and Cyclic constants, Forma,19,(2004) 355-366.
In article      
 
[7]  M. Renault, The Fibonacci sequence under various moduli, Masters Thesis, 1996.
In article      
 
[8]  S. Vajda, Fibonacci and Lucas numbers and the Golden section: Theory and Applications, Dover Publications, 2008.
In article      
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn