56. Fibonacci number

EasyProgramFree10 points

The Fibonacci numbers start 0, 1 and continue with the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, …. Write fib n, the n-th of them, counting from fib 0 = 0.

The hidden tests go up to n = 90, so the answer has to be computed in a number of steps that grows with n, not with the answer.

Examples

  1. Input: fib 0Output: 0
  2. Input: fib 1Output: 1
  3. Input: fib 2Output: 1
  4. Input: fib 10Output: 55

Submitting also runs 5 hidden tests.

Constraints

  • 0 ≤ n ≤ 90.
  • The direct definition fib (n + 2) = fib (n + 1) + fib n makes about 2ⁿ calls and runs out of time.
Solution.lean
Loading editor…

Run checks your code against the examples and your custom inputs and records nothing. Submit also runs the hidden tests, confirms the axioms your proof uses and records the result. Each uses one compiler check.

ReadyLn 1, Col 1Lean 4
Draft saved in this browser