One of the simplest recursive formula that I can think of is the one which generates the Fibonacci sequence, with . 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
You must be logged in to post a comment.