WordGPT

Binet's formula: Fibonacci numbers in closed form

Exercise Ā· Level 4 (Hard)

Find F₁₀ without listing the sequence, using the golden ratio.

Fn=φnāˆ’Ļˆn5F_n=\frac{\varphi^n-\psi^n}{\sqrt5}

wordgptpro.com

Solution 1/2

  1. Try Fn=xnF_n=x^n in Fn=Fnāˆ’1+Fnāˆ’2F_n=F_{n-1}+F_{n-2}. Dividing by xnāˆ’2x^{n-2} gives x2=x+1x^2=x+1, with roots φ=1+52\varphi=\tfrac{1+\sqrt5}{2} and ψ=1āˆ’52\psi=\tfrac{1-\sqrt5}{2}. So any combination Aφn+BψnA\varphi^n+B\psi^n satisfies the recurrence.

wordgptpro.com

Solution 2/2

  1. Match F0=0F_0=0 and F1=1F_1=1: A+B=0A+B=0 and Aφ+Bψ=1A\varphi+B\psi=1, so A=āˆ’B=15A=-B=\tfrac1{\sqrt5} (since Ļ†āˆ’Ļˆ=5\varphi-\psi=\sqrt5):

    Fn=φnāˆ’Ļˆn5F_n=\frac{\varphi^n-\psi^n}{\sqrt5}
    (1)
  2. Since ∣ψ∣<1|\psi|<1, the second term is tiny, and FnF_n is the nearest whole number to φn/5\varphi^n/\sqrt5. For n=10n=10: φ10=122.99…\varphi^{10}=122.99\ldots, divided by 5\sqrt5 that is 55.003655.0036:

    F10=55F_{10}=55
    (2)
AnswerF10=55F_{10}=55

wordgptpro.com

Need a hint?

Look for solutions of the form xⁿ of Fā‚™ = Fₙ₋₁ + Fₙ₋₂. That gives x² = x + 1.

Binet's formula gives F₁₀ = 55 as the nearest integer to φ¹⁰/√5 ā‰ˆ 55.0036.

How to work it out

  1. Try Fn=xnF_n=x^n in Fn=Fnāˆ’1+Fnāˆ’2F_n=F_{n-1}+F_{n-2}. Dividing by xnāˆ’2x^{n-2} gives x2=x+1x^2=x+1, with roots φ=1+52\varphi=\tfrac{1+\sqrt5}{2} and ψ=1āˆ’52\psi=\tfrac{1-\sqrt5}{2}. So any combination Aφn+BψnA\varphi^n+B\psi^n satisfies the recurrence.

  2. Match F0=0F_0=0 and F1=1F_1=1: A+B=0A+B=0 and Aφ+Bψ=1A\varphi+B\psi=1, so A=āˆ’B=15A=-B=\tfrac1{\sqrt5} (since Ļ†āˆ’Ļˆ=5\varphi-\psi=\sqrt5):

    Fn=φnāˆ’Ļˆn5F_n=\frac{\varphi^n-\psi^n}{\sqrt5}
    (1)
  3. Since ∣ψ∣<1|\psi|<1, the second term is tiny, and FnF_n is the nearest whole number to φn/5\varphi^n/\sqrt5. For n=10n=10: φ10=122.99…\varphi^{10}=122.99\ldots, divided by 5\sqrt5 that is 55.003655.0036:

    F10=55F_{10}=55
    (2)
LaTeX source of the formulas on this page
\[ F_{10}=55 \]
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5} \]

Questions

What is the answer to: Binet's formula: Fibonacci numbers in closed form?

Binet's formula gives F₁₀ = 55 as the nearest integer to φ¹⁰/√5 ā‰ˆ 55.0036.

What is the key idea?

A linear recurrence is solved by powers of the roots of its characteristic equation.

Is there a hint?

Look for solutions of the form xⁿ of Fā‚™ = Fₙ₋₁ + Fₙ₋₂. That gives x² = x + 1.

Related problems

More algebra problems

    Binet's formula: Fibonacci numbers in closed form: answer and solution | WordGPT