Periodicity of Generalized Fibonacci-like Sequences
“Dianet”, Laboratory of Digital Technologies, Moscow, RussiaAbstract
Generalized Fibonacci-like sequences appear in finite difference approximations of the Partial Differential Equations based upon replacing partial differential equations by finite difference equations. This paper studies properties of the generalized Fibonacci-like sequence Fn+2=A+BFn+1+CFn. It is shown that this sequence is periodic with period T>2, if C= -1, |B|<2.
Keywords: generalized fibonacci-like sequence, periodicity, discrete dynamical system, PDE, graph, network, digital space
Copyright © 2017 Science and Education Publishing. All Rights Reserved.Cite this article:
- Alexander V. Evako. Periodicity of Generalized Fibonacci-like Sequences. Applied Mathematics and Physics. Vol. 5, No. 1, 2017, pp 11-18. https://pubs.sciepub.com/amp/5/1/2
- Evako, Alexander V.. "Periodicity of Generalized Fibonacci-like Sequences." Applied Mathematics and Physics 5.1 (2017): 11-18.
- Evako, A. V. (2017). Periodicity of Generalized Fibonacci-like Sequences. Applied Mathematics and Physics, 5(1), 11-18.
- Evako, Alexander V.. "Periodicity of Generalized Fibonacci-like Sequences." Applied Mathematics and Physics 5, no. 1 (2017): 11-18.
Import into BibTeX | Import into EndNote | Import into RefMan | Import into RefWorks |
At a glance: Figures
1. Introduction
Fibonacci sequences have attracted attention of scientists from different fields. Fibonacci numbers are widely used in many areas from applied mathematics to physics. The Fibonacci sequence, Lucas sequence, Pell sequence and periodic generalized Fibonacci sequences modulo m have been intensively studied for many years. Over the last decades, numerous useful theoretical results have been obtained in this field (see, e.g., [1, 10, 15, 17, 21, 22]).
In this paper, we introduce and study a new generalization of Fibonacci-like sequences; we are interested in the periodicity of the Fibonacci-like sequence.
The essential fact is that finite difference PDE equations on discrete domains contain generalized Fibonacci-like sequences as basic elements of these equations, and knowledge of features of these sequences plays an important role in analyzing properties computational solutions of PDE such as the period and the frequency of oscillations.
Finite difference approximations of the PDE are based upon replacing partial differential equations by finite difference equations [13, 18]. In the past decades, computational solutions of PDE on various domains including non-orientable surfaces such as a Moebius strip and a Klein bottle have been studied by scientists from different fields. The study was derived from obvious practical and science background. In physics, a considerable interest has emerged in studying lattice models on non-orientable surfaces as new challenging unsolved lattice-statistical problems and as a realization and testing of predictions of the conformal field theory (see, e.g., [12]). Many important technical and physical properties of non-orientable structural elements can be described by solutions of partial differential equations (PDE), where a non-orientable space serves as a domain. A problem exists in description of electronic and nuclear motions in nano-technology structures and biological networks. Modeling blood flow through a capillary network or road traffic requires a system of differential equations on a graph or network . Since analytic solutions of PDE can be obtained only in simple geometric regions, for practical problems, it is more reasonable to use computational or numerical solutions. It can be done by implementing as domains graphs, networks and digital spaces, which are discreet counterparts of continuous spaces, and by transferring PDE from a continuous area into discrete one. A review of works devoted to partial differential equations on networks and graphs can be found in [4, 14, 16].
The material to be presented in Section 2 begins with the investigation of properties of a periodic continuous function , where . It is shown that if is periodic with period then .
In section 3, we study properties of the sequence, which is defined by recurrence relation with , where A, B C, a and b are real numbers. We show that if then is periodic with the period .
Section 4 presents numerical examples of periodic Fibonacci-like sequences and gives examples of application of Fibonacci-like sequences to the numerical solutions of the wave equation on the graph containing two vertices and on the graph containing sixteen vertices and presenting a non-orientable Klein bottle, which is an important object of study in physics. Using properties of Fibonacci-like sequences, we show that the period of oscillations on the two-point graph is T=13.9. Oscillations at different points of the Klein bottle are also periodic.
2. Periodicity of Fibonacci-like Continuous Functions
In a numerical solution of the one-dimensional wave equation by the finite difference method, the spatial domain and the temporal domain are replaced by a set of mesh points, the second-order derivatives can be replaced by central differences [4, 13, 14, 16]. The solution of the wave equation is replaced by the mesh function, which approximates the exact solution at the mesh points. The obtained discretization scheme has the form , where .
Note that the solution is periodic in time. Using this formula, consider properties of periodic continuous function f(x) on domain R provided that .
Theorem 1
Let f(x) be a continuous function on domain R, and let
(1) |
for any . If f(x) is a periodic function with period then , , .
Proof.
Let f(x) is periodic with period . Consider the Fourier series representing f(x).
(2) |
Using (2), it is easy to see that
where
(3) |
(4) |
(5) |
Since
then for any n, coefficients c0, cn and dn are equal to zero.
(6) |
Let n=1.
As f(x) is periodic with basic period then and/or , which means that
(7) |
Suppose that , i.e., . It follows from (7) that Therefore, . Hence,
(8) |
Let n>1.
For the same reason as above, if then , if then and/or . Note that if
Finally, find a0 from equation (3). Notice that .
Thus, if and then f(x) is periodic with basic period and .
(9) |
where if . This completes the proof.
Theorem 2
Let f(x) be a continuous periodic function on domain R with period, and for any ,
Then if .
if .
Proof
Let k is even, i.e., k=2n and . Then
This means that in (9),
Let k is odd, i.e., k=2n+1 and . Then and Since , then by (7), . Therefore,
(10) |
It follows from (10) that . This completes the proof.
We now outline a correspondence between the number B and the period T of function , where . Let’s investigate this question graphically. The graph is shown in Figure 1. Obviously, .
3. Periodic generalized Fibonacci-like Sequences
Periodic generalized Fibonacci sequences modulo m have been studied in a number of papers (see e.g. [9, 11, 19, 21]). In this section, we consider the periodic generalized Fibonacci sequence
(11) |
In sequence (11), and are real numbers. In particular, and can be integer. The results of this section are directly deduced from the previous section. The following theorems are a direct consequence of theorems 1 and 2.
Theorem 3
Let , be a sequence of real numbers, If then is a periodic sequence with period,
(12) |
Proof.
Consider the function where . Then for .
According to theorem 1, if , then f(x) is periodic with period , . . Therefore, sequence is also periodic with period . This completes the proof.
Consider a special case when the period T=1, 2.
Theorem 4
Let , be a sequence of real numbers, .
If then is a periodic sequence with period , .
If then is a periodic sequence with period ,
Let f(x) be a continuous periodic function on domain R, and .
If the period of f(x) then by theorem 2. Therefore, .
If the period of f(x) then by theorem 2. Therefore, . This completes the proof.
4. Numerical Examples
In this Section, we consider examples of the periodic generalized Fibonacci sequence and its applications to numerical solution of the wave equation on graphs.
4.1. Numerical Examples of Periodic Fibonacci-like Sequencesfor .
Example 1
First, consider the case, when coefficient B is close to 2. Let . Then . In Figure 2, the sequence profile Fn, , is plotted for n=1,…50. The plot illustrates the periodicity of Fn with period , as it follows from formulas (12) , . For the first n=0,1,…13, the terms of Fn are given in Table 1.
Example 2
In this case, take the following constants: . Then . In Figure 3, we have plotted the sequence profile Fn, , at n=1,…20. The plot shows that Fn is periodic with period T=6. According to (12), , . For the first n=0,1,…13, the terms of Fn are shown in Table 2.
Example 3
Consider the case, when . Then . In Figure 4, the profile Fn, , is plotted for n=1,…20. Fn is periodic with period T=4, as it follows from (12). For the first n=0,1,…13, the terms of Fn are given Table 3.
Example 4
Let . Then . The profile of Fn for n=1,…20 is shown in Figure 5. Fn, , is periodic with period , as it follows from formulas , .
For the first n=0,1,…13, the terms of Fn are given in Table 4.
Example 5
Choose . Then . In Figure 6, we have plotted the sequence profile Fn, , at n=1,…20. The plot shows that Fn is periodic with period T=2.51. According to (12), For the first n=0,1,…13, the terms of sequence Fn are given in Table 5.
As it was mentioned above, finite difference approximations of the PDE are based upon replacing partial differential equations by finite difference equations using Taylor approximations [18]. Consider a hyperbolic PDE with two spatial independent variables.
where Using a standard two-dimensional spatial orthogonal grid H with points , the forward difference formula for the derivative with respect to t, and the central difference formula for the second derivatives with respect to x and y, we obtain the following equivalent finite deference equation
(13) |
where . By construction, grid H is a graph, in which point is adjacent to points and The nearest neighborhood (ball) of point is the subgraph containing and points and . Using these notations, equation (13) can be written as the following.
(14) |
where .
The set (14) can be applied to a general graph G(V, W) with the set of points V=(v1, v2,...vs) and the set of edges W = ((vрvq),....), where is the ball of point , p=1,...s. Set (14) is similar to the set of differential equations on a graph investigated by A. I. Volpert in [20].
The wave equation defined below is a special case of hyperbolic equation (14) if the following condition holds
(15) |
The solution of this equation should be analogous the solution of the wave equation in the continuous case. It should be associated with oscillations of the function at points of G and the wave propagation.
There is considerable amount of literature devoted to the study of different approaches to digital lines, surfaces and spaces used by researchers. Traditionally, a digital image has a graph structure (see [2, 3, 5]). A digital space G is a simple undirected graph G=(V,W) where V=(v1,v2,...vn,…) is a finite or countable set of points, and W = ((vрvq),....) is a set of edges. The induced subgraph containing point v and all points adjacent to v is called the ball of point v in G. Graphs that are digital counterparts of continuous n-dimensional manifolds were studied in [5, 6, 7, 8]. Consider the numerical solutions of the initial value problem for the wave equation on a graph . We will see that periodic Fibonacci-like sequences are basic elements of this equation.
Example 6. Numerical solution of the initial value problem on a connected graph G with two points.
Consider a connected graph consisting of two adjacent points depicted in Figure 7(a). According to (15)
(16) |
Let and . Then for any n>1. For set (16) we have two sequences
(17) |
According to theorem 3, sequence (17) is the generalized Fibonacci-like sequence with . Since , and , then . Therefore, sequence (17) is periodic with period , as it follows from (12). For the same reason, is periodic with the same period T. Define coefficients in equation (16) in the following way; . Initial values are given as , . Therefore, , .
The period of oscillations is . The solution of the initial value problem at points 1 and 2 for t=1,…50 is displayed in Figure 7(b), which illustrates the time behavior of the values of function f. Figure 7(b) presents oscillations at points 1 and 2.
Example 7. Numerical solution of the initial value problem on the digital Klein bottle.
A Klein bottle is an object of investigation in many fields. In physics [12], a Klein bottle attracted attention in studying lattice models on non-orientable surfaces A digital 2D Klein bottle K depicted in Figure 8(a) consists of sixteen points. The nearest neighborhood O(vk) of every point vk is a digital 1-sphere containing six points. Topological properties of K are similar to topological properties of its continuous counterpart. For example, the Euler characteristic and the homology groups of a continuous and a digital Klein bottle are the same ([7] and [8]). Consider the solution of equation (15) on K. One can check directly that all sequences in set (15) are periodic generalized Fibonacci-like sequences. Define coefficients in the following way. If points vp and vk are adjacent then =0.01and ckk=0.94 for k=1,…16. Initial values are given as =3, =3. In Figure 8(b), numerical solutions at points 1 and 3 of the of the initial value problem are plotted at time t=1,…100. Two lines show oscillations with period T>2.
5. Conclusion
In connection with computational methods for approximating the solutions of partial differential equations, the generalized Fibonacci-like sequence with , where A, B, C, a and b are real numbers is investigated. It is shown that if then is periodic with the period . If period , then
If period and then , . Numerical examples of periodic Fibonacci-like sequences, and periodic numerical solutions of the wave equation on graphs are presented.
Competing Interests
The author declares that he has no competing interests.
Acknowledgements
The author has got no financial or any other support from any person, fund, organization, etc.
References
[1] | Badshah, V.H., Teeth, M.S. and Dar, M.M., ‘Generalized Fibonacci-Like Sequence and its Properties”, Int. J. Contemp. Math. Sciences,7(24) (2012) 1155-1164. | ||
In article | |||
[2] | Bai, Y., Han, X., Prince, J., Digital Topology on Adaptive Octree Grids. Journal of Mathematical Imaging and Vision. 34(2) (2009) 165-184. | ||
In article | View Article PubMed PubMed | ||
[3] | Eckhardt, U. and Latecki, L., Topologies for the digital spaces Z2 and Z3. Computer Vision and Image Understanding, 90 (2003) 295-312. | ||
In article | View Article | ||
[4] | Evako, A., “Solution of a Parabolic Partial Differential Equation on Digital Spaces: A Klein Bottle, a Projective Plane, a 4D Sphere and a Moebius Band”, International Journal of Discrete Mathematics, https://www.sciencepublishinggroup.com/j/dmath, in press | ||
In article | |||
[5] | Evako, A., Kopperman, R. and Mukhin, Y., Dimensional properties of graphs and digital spaces. Journal of Mathematical Imaging and Vision, 6 (1996) 109-119. | ||
In article | View Article | ||
[6] | Evako, A., Classification of digital n-manifolds. Discrete Applied Mathematics. 181 (2015) 289-296. | ||
In article | View Article | ||
[7] | Ivashchenko, A., Representation of smooth surfaces by graphs. Transformations of graphs which do not change the Euler characteristic of graphs. Discrete Mathematics, 122 (1993) 219-233. | ||
In article | View Article | ||
[8] | Ivashchenko, A., Contractible transformations do not change the homology groups of graphs. Discrete Mathematics, 126 (1994) 159-170. | ||
In article | View Article | ||
[9] | Falcon, S. and Plaza, A.,” k-Fibonacci sequences modulo m”, Chaos, Solitons and Fractals”, 41 (2009) 497-504. | ||
In article | View Article | ||
[10] | Koshy, T., Fibonacci and Lucas Numbers with Applications, Wiley, New York, 2001. | ||
In article | View Article | ||
[11] | Li, H-C., “ Complete and reduced residue systems of second-order recurrences modulo p”, Fibonacci Quart., 38 (2000) 272-281. | ||
In article | |||
[12] | Lu, W. T. and Wu, F. Y., Ising model on nonorientable surfaces: Exact solution for the Moebius strip and the Klein bottle. Phys. Rev., E 63 (2001) 026107. | ||
In article | View Article PubMed | ||
[13] | Morton, K.W. and Mayers, D.E., Numerical Solution of Partial Differential Equations, An Introduction. Cambridge University Press, 2005. | ||
In article | View Article | ||
[14] | Pokornyi, Y. and Borovskikh, A., “Differential equations on networks (Geometric graphs)”, Journal of Mathematical Science, 119 (6) (2004) 691-718. | ||
In article | View Article | ||
[15] | Schork, M., “Generalized Heisenberg algebras and k-generalized Fibonacci numbers”, J. Phys. A: Math. Theor., 40 (2007). 4207-4214. | ||
In article | View Article | ||
[16] | Shu, T.L. and Chen, G., “Oscillations of Second-Order Nonlinear Partial Difference Equations”, Rocky Mountain J. Math., 34(2) (2004) 699-711. | ||
In article | View Article | ||
[17] | Singh, M., Gupta, Y.K. and Sikhwal, O., “Generalized Fibonacci – Lucas sequence its Properties”, Global Journal of Mathematical Analysis, 2 (3) (2014) 160-168. | ||
In article | View Article | ||
[18] | Smith, G.D., Numerical solution of partial differential equations: finite difference methods (3rd ed.), Oxford University Press, 1985. | ||
In article | |||
[19] | Tuwankotta, J.M.,” Two aspects of a generalized Fibonacci sequence”, J. Indones. Math. Soc., 21(1) (2015). 1-17. | ||
In article | |||
[20] | Vol’pert, A., Differential equations on graphs. Mat. Sb. (N. S.), 88 (130) (1972) 578-588. | ||
In article | |||
[21] | Wall, D.D., “Fibonacci series modulo m”, Amer. Math. Monthly, 67 (1960).525-532. | ||
In article | |||
[22] | Walton, J.E. and Horadam, A.F., “Some Aspects of Generalized Fibonacci Sequence”, The Fibonacci Quaterly, 12 (3) (1974). 241-250. | ||
In article | |||