Find the initial condition and recurrence relation for Fibonacci sequence and solve it.

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.

The Fibonacci sequence is defined by the following recurrence relation:

F(n) = F(n-1) + F(n-2)

And the initial conditions are:

F(0) = 0, F(1) = 1

Here's how the Fibonacci sequence starts:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The Fibonacci sequence is used in computer science, mathematics, and even in nature, where patterns reflecting the sequence are found in the arrangement of leaves on a stem or the scales of a pineapple.

To solve the Fibonacci sequence, you can use a recursive function, which calls itself with smaller values until it reaches the base case. Here's a simple Python function that does this:

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

However, this function is not efficient because it does a lot of repeated work. For example, to compute fibonacci(5), it first computes fibonacci(4) and fibonacci(3). But to compute fibonacci(4), it needs to compute fibonacci(3) and fibonacci(2), so fibonacci(3) is computed twice. This redundancy gets worse for larger inputs.

A more efficient solution is to use dynamic programming, which stores the results of subproblems so that each one is only solved once. Here's a Python function that does this:

def fibonacci(n):
    fib = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

This function uses a list fib to store the Fibonacci numbers as they are computed. The list is initialized with the base cases fib[0] = 0 and fib[1] = 1, and the rest of the list is filled in by the loop. The function returns the nth Fibonacci number.

This function runs in O(n) time and uses O(n) space. If you only care about the nth Fibonacci number and not the entire sequence up to n, you can reduce the space usage to O(1) by only keeping track of the last two Fibonacci numbers:

def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

This function runs in O(n) time and uses O(1) space.