Fibonacci Series

The Fibonacci sequence is defined as follows: the first term is 0, the second term is 1, and every subsequent term is the sum of the two terms that…

The Fibonacci sequence is defined as follows: the first term is 0, the second term is 1, and every subsequent term is the sum of the two terms that immediately precede it. Formally: fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n ≥ 2. Given a non-negative integer `n`, return the value of the nth Fibonacci number.

- `0 <= n <= 35` - The answer always fits in a 32-bit signed integer for all valid inputs.

Example 1: input n = 6; output 8. The sequence from index 0 is: 0, 1, 1, 2, 3, 5, 8. The term at index 6 is 8.

Example 2: input n = 9; output 34. The sequence from index 0 is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. The term at index 9 is 34.

Example 3: input n = 0; output 0. By definition the 0th Fibonacci number is 0.

Category: Math. Topic: math. Difficulty: Easy. Patterns: recursion, dynamic-programming.