Home » Python » Python programs

Python | Program to calculate n-th term of a Fibonacci Series

Here, we are going to learn how to calculate the n-th term of a Fibonacci series using python program?
Submitted by Sanjeev, on March 30, 2019

Python program to calculate n-th term of Fibonacci series with the help to two approaches (there are many approaches to calculate n-th term).

Description:

1. First Approach: Dynamic Programming
   In this approach, we calculate all the terms of Fibonacci series up to n and if we need to calculate any other term which is smaller than n, then we don’t have to calculate it again.
2. Second Approach: By Formula
   In this approach we calculate the n-th term of Fibonacci series with the help of a formula.

    Formula:
    phi = ( 1 + sqrt(5) ) / 2
    An = phin/ sqrt(5)

Example:

    Input:
    for n = 5
    for n = 8

    Output:
    a5  = 5
    a8 = 21

Procedure: Dynamic Programming Approach

    L[0] = 0, L[1] = 1
    For loop from 2 to n+1
        L[i] = L[i-1] + L[i -2]
    End of for

As you may observe that we are also storing each calculated value, so we can also use them later if necessary.

This is the benefit of Dynamic Programming over Recursion.

Python code to calculate n-th term of a Fibonacci series

def dynamic_fibonacci(n):
    '''
    This function will calculate fobonacci
    series with the help of dynamic
    programming.
    '''
    l = [0]*(n+1)
    l[0] = 0
    l[1] = 1
    for i in range(2, n+1):
        l[i] = l[i-1] + l[i-2]

    return l

    # Time complexity O(n)


def fibonacci_by_formula(n):
    '''
    This function will calculate n-th
    term of fibonacci series with the
    help of a formula.
    '''
    from math import sqrt
    
    phi = (1 + sqrt(5))/2

    fib = round(pow(phi, n)/sqrt(5))

    return fib

    # Time complexity O(1)

def main():
    n = 8
    lst = dynamic_fibonacci(n)
    x = fibonacci_by_formula(n)

    print('By Dynamic Programming:',lst[n])
    print()
    print('By Formula:',x)

main()

Output

By Dynamic Programming: 21

By Formula: 21