Recursion and Periodicity

Standard

One of the simplest recursive formula that I can think of is the one which generates the Fibonacci sequence, $F_{n+1} = F_n +F_{n-1}, n\geq 1$ with $F_0 = F_1=1$. So, I will illustrate a following general concept about recursions using Fibonacci sequence.

A sequence generated by a recursive formula is periodic modulo k, for any positive integer k greater than 1.

I find this fact very interesting because it means that a sequence which is strictly increasing when made bounded using the modulo operation (since it will allow only limited numbers as the output of recursion relation), will lead to a periodic cycle.

Following are the first 25 terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025.

And here are few examples modulo k, for k=2,3,4,5,6,7,8

As you can see, the sequence repeats as soon as 1,0 appears. And from here actually one can see why there should be a periodicity.

For the sequence to repeat, what we need is a repetition of two consecutive values (i.e. the number of terms involved in the recursive formula) in the sequence of successive pairs. And for mod k, the choices are limited, namely k^2.  Now, all we have to ensure is that “1,0” should repeat. But since consecutive pairs can’ repeat (as per recursive formula) the repetition of “1,0” must occur within the first k^2.

For rigorous proofs and its relation to number theory, see: http://math.stanford.edu/~brianrl/notes/fibonacci.pdf

Fibonacci, Chebyshev and Ramsey

Standard

Pascal’s triangle has long and celebrated history, see this TedEd video:

What makes it more interesting is its relations with various domains of Mathematics (if you don’t understand the three relations discussed, refer Wikipedia). Here I will point few such connections:

1. Fibonacci Numbers: I believe that this is the most celebrated observation from pascal’s triangle. To see the jungle of Equations involved, visit http://www.maplesoft.com/applications/view.aspx?SID=3617&view=html

2. Chebyshev Polynomial: We can find coefficients of Chebyshev Polynomial using pascal’s triangle. See- http://mathpages.com/home/kmath304.htm

3. Ramsey Number: Upper bound of Ramsey Number can be found using Pascal’s triangle, for more details refer : https://plus.maths.org/content/friends-and-strangers