1 EPEpisodes
Transcript
Episode 1 · From recurrence to Binet, with n=25 and n=30
Maya: Here’s a small wonder: a rule that only adds two earlier numbers can lead to a formula with powers, square roots, and the golden ratio. Today, we’re going from Fibonacci’s recurrence to Binet’s formula. Oren: Starting with the familiar bit? Maya: Yes. F1 equals 1. F2 equals 1. And Fn equals F n minus 1 plus F n minus 2. Each new term is the sum of the previous two. Oren: Like a family budget where this month depends on the last two receipts. Maya: Exactly. Now, repeated growth often suggests powers. So we try a solution that behaves like t to the n. The recurrence then gives t squared equals t plus 1. Oren: And that’s where the golden ratio walks in. Maya: Right. The two roots are phi, approximately 1.618033988..., and psi, approximately negative 0.618033988.... Binet’s formula is: Fn equals open parenthesis phi to the n minus psi to the n close parenthesis divided by square root of 5. Oren: So for a particular n, it’s just plug in, calculate, and round? Maya: Calmly, yes. Raise phi and psi to that n, subtract, divide by square root of 5, then round. For n equals 25, phi to the 25th is 167,761.00, while psi to the 25th is roughly negative 0.00000596. The result is F25 equals 75,025. Oren: Tiny second term. Almost gone. Maya: By n equals 30, psi to the 30th is roughly negative 0.00000537, and phi to the 30th is 1,860,498.00. Dividing gives F30 equals 832,040. Oren: So phi is the dominant growth pattern. Maya: Precisely. The recurrence behaves like multiplication by phi. Thanks for listening.