Recurrences 2.1 Finding a recurrence Ideally, we could find a formula for the number of professors in the world in a given year Then we could determine the year in which all N faculty positions are filled. Let f(n) be the number of professors during year n. To develop some intuition about the problem, we can compute values of this function for small n by hand f(0)=0 No CS professors; the dark ages f 1 new professor; too busy to train a student. f(2)=1 1 old professor; now training a student f 3)=2 1 new prof, 1 old prof; new prof too busy, old prof training f (4)=3 1 new prof, 2 old profs; new prof too busy, both old profs training f(5)=5 2 new profs, 3 old profs f(6)=8 3 new profs, 5 old profs In general, the number of professors in year n is equal to the number of professors last ear plus the number of new hires. The number of professors last year is f(n-1). The number of new hires is equal to the number of professors two years ago, f(n-2), since each of these professors trained a student last year. These observations give the following recurrence equation for the number of professors f(1)=1 f(m)=∫(n-1)+f(-2)(n≥2) This is the familiar Fibonacci recurrence. Looking back, the values of f(n) that we computed by hand are indeed the first few Fibonacci numbers. Fibonacci numbers arise in all sorts of applications. Fibonacci himself introduced the numbers in 1202 to study rabbit reproduction. Fibonacci numbers also appear, oddly enough, in the spiral patterns on the faces of sunflowers. And the input numbers that make Euclids GCD algorithm require the greatest number of steps are consecutive Fibonacci numbers. So how bi f(n)anyway? could many Fiona lbers as we like using the recurrence but it would be much nicer to find a closed form 2.2 Solving the recurrence Solving the Fibonacci recurrence is easy because the recurrence is linear (Well,"ea the sense that you can learn the technique in one lecture: discovering it actually took six6 Recurrences 2.1 Finding a Recurrence Ideally, we could find a formula for the number of professors in the world in a given year. Then we could determine the year in which all N faculty positions are filled. Let f(n) be the number of professors during year n. To develop some intuition about the problem, we can compute values of this function for small n by hand. f(0) = 0 No CS professors; the dark ages. f(1) = 1 1 new professor; too busy to train a student. f(2) = 1 1 old professor; now training a student. f(3) = 2 1 new prof, 1 old prof; new prof too busy, old prof training. f(4) = 3 1 new prof, 2 old profs; new prof too busy, both old profs training f(5) = 5 2 new profs, 3 old profs f(6) = 8 3 new profs, 5 old profs In general, the number of professors in year n is equal to the number of professors last year plus the number of new hires. The number of professors last year is f(n − 1). The number of new hires is equal to the number of professors two years ago, f(n − 2), since each of these professors trained a student last year. These observations give the following recurrence equation for the number of professors: f(0) = 0 f(1) = 1 f(n) = f(n − 1) + f(n − 2) (n ≥ 2) This is the familiar Fibonacci recurrence. Looking back, the values of f(n) that we computed by hand are indeed the first few Fibonacci numbers. Fibonacci numbers arise in all sorts of applications. Fibonacci himself introduced the numbers in 1202 to study rabbit reproduction. Fibonacci numbers also appear, oddly enough, in the spiral patterns on the faces of sunflowers. And the input numbers that make Euclid’s GCD algorithm require the greatest number of steps are consecutive Fibonacci numbers. So how big is f(n) anyway? Of course, we could compute as many Fibonacci numbers as we like using the recurrence, but it would be much nicer to find a closed form. 2.2 Solving the Recurrence Solving the Fibonacci recurrence is easy because the recurrence is linear. (Well, “easy” in the sense that you can learn the technique in one lecture; discovering it actually took six