Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233... is...

 

Transcribed Image Text:

Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233... is defined by the recurrence relation F = 1, F = 1, Fk = Fk-1 + Fk. (a) Show that the Fibonacci sequence taken modulo a positive integer n must be periodic, i.e., it repeats itself after a finite number of terms. (b) Let (n) denote the period of the Fibonacci sequence modulo n. For example, (3) the Fibonacci sequence taken modulo 3 repeats itself after eight terms: 1, 1, 2, 0, 2, 2, 1, 3, 1, 1.... (c) Let m and n be positive integers satisfying ged(m, n) common multiple of T(m) and (n). Recall that the - 1 = 8, since 1. Show that (mn) is the least NOTE: The function (n) is called the Pisano period. Other interesting things can be proven about it, such as the fact T(n) is always even for n > 2. No closed form formula for (n) is currently known. This means that a complete answer to the question Dr. Murray posed about matrices modulo n is also unknown! Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233... is defined by the recurrence relation F = 1, F = 1, Fk = Fk-1 + Fk. (a) Show that the Fibonacci sequence taken modulo a positive integer n must be periodic, i.e., it repeats itself after a finite number of terms. (b) Let (n) denote the period of the Fibonacci sequence modulo n. For example, (3) the Fibonacci sequence taken modulo 3 repeats itself after eight terms: 1, 1, 2, 0, 2, 2, 1, 3, 1, 1.... (c) Let m and n be positive integers satisfying ged(m, n) common multiple of T(m) and (n). Recall that the - 1 = 8, since 1. Show that (mn) is the least NOTE: The function (n) is called the Pisano period. Other interesting things can be proven about it, such as the fact T(n) is always even for n > 2. No closed form formula for (n) is currently known. This means that a complete answer to the question Dr. Murray posed about matrices modulo n is also unknown!