Fibonacci Calculator

Enter n to find the nth Fibonacci number.

A whole number from 0 to 10 000.

Try

Result

You enteredF50F_{50}

F50=12586269025\displaystyle F_{50} = 12586269025

Number of digits

11\displaystyle 11

Ratio to the previous

1.618034\displaystyle 1.618034
Show the work
  1. Fibonacci recurrence

    Each Fibonacci number is the sum of the two before it, starting from F0=0F_0 = 0 and F1=1F_1 = 1.

    Using Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}

    0,  1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  …0,\; 1,\; 1,\; 2,\; 3,\; 5,\; 8,\; 13,\; 21,\; 34,\; 55,\; 89,\; \dots
  2. Fast doubling

    Adding up 5050 terms one by one is slow for a large nn. Fast doubling instead reads the binary digits of nn from the left and, for each digit, jumps from FkF_k and Fk+1F_{k+1} to the pair for 2k2k or 2k+12k+1; that takes only about 66 doublings.

    Using F2k=Fk(2Fk+1−Fk)F2k+1=Fk2+Fk+12F_{2k} = F_k\left(2F_{k+1} - F_k\right) \quad F_{2k+1} = F_k^{2} + F_{k+1}^{2}

    50=110010250 = 110010_{2}
  3. Binet's formula as a check

    For a large nn the term ψn\psi^n is far too small to matter, so FnF_n is almost exactly φn/5\varphi^n / \sqrt{5}. That gives about 1.25863 times 10 to the power 10, which matches the leading digits 125862 of the answer.

    Using Fn=φn−ψn5F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

    F50≈φ505≈1.25863×1010F_{50} \approx \frac{\varphi^{50}}{\sqrt{5}} \approx 1.25863 \times 10^{10}
  4. Result

    So F50=12586269025F_{50} = 12586269025.

Worked examples