Basecamp
Sign in
Mmedv

Fibonacci numbers

The Fibonacci sequence is one of the most well-known sequences in mathematics and computer science. It is named after the Italian mathematician Leonardo of Pisa, also known as Fibonacci.

https://en.wikipedia.org/wiki/Fibonacci\_number

The Fibonacci numbers f_n = f(n) form a sequence where each number after the first two is equal to the sum of the two preceding ones.

They are defined by the following recurrence relation:

f(n)= \begin{cases} 0, \text{if } n=0 \\ 1, \text{if } n=1 \\ f(n-1)+f(n-2), \text{if } n \ge 2 \end{cases}

Thus, we have:

f_0 = 0, f_1 = 1, \\ f_n = f_{n-1} + f_{n-2}

The Fibonacci sequence therefore begins as:

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

Each term is obtained by adding the two previous terms.

Example. Compute Fibonacci numbers using an array.

The following program fills an integer array such that fib[i] = f_i, where f_i is the -th Fibonacci number. It then prints the value for a given input .

#include <stdio.h>

int i, n, fib[47];

int main(void)
{
  scanf("%d",&n);

  fib[0] = 0; fib[1] = 1;
  for(i = 2; i <= n; i++)
    fib[i] = fib[i-1] + fib[i-2];

  printf("%d\n",fib[n]);
  return 0;
}
C++

The largest Fibonacci number that can be stored in the int data type is:

f_{46} = 1836311903

The largest Fibonacci number that can be stored in the long long data type is:

f_{92} = 7540113804746346429

For computing Fibonacci numbers with index n > 92, standard integer types are no longer sufficient due to overflow. In such cases, arbitrary-precision arithmetic must be used, such as the BigInteger type (or equivalent big number libraries in programming languages that do not support built-in large integers).

Example. Compute the -th Fibonacci number using a recursive function.

The following program implements a direct recursive definition of the Fibonacci sequence. The function returns the -th Fibonacci number according to the recurrence relation.

#include <stdio.h>

int n;

int fib(int n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n-1) + fib(n - 2);
}

int main(void)
{
  scanf("%d",&n);
  printf("%d\n",fib(n));
  return 0;
}
C++

Example. Compute the -th Fibonacci number using recursion with memoization.

The following program implements a recursive solution enhanced with memoization to avoid redundant computations. Previously computed values are stored in an array, so each Fibonacci number is calculated at most once.

#include <stdio.h>
#include <string.h>
 
int n, fib[46];
 
int f(int n)
{
  // base cases
  if (n == 0) return 0;
  if (n == 1) return 1;

  // if fib[n] has already been computed, return it 
  if (fib[n] != -1) return fib[n]; 

  // otherwise compute and store (memoize) the result
  return fib[n] = f(n-1) + f(n - 2);
}
 
int main(void)
{
  scanf("%d",&n);

  // initialize memoization array:
  // fib[i] = -1 indicates that the value has not been computed yet 
  memset(fib,-1,sizeof(fib));

  printf("%d\n",f(n));
  return 0;
}
C++

This approach significantly improves efficiency compared to plain recursion. While the naive recursive solution has exponential complexity, memoization reduces the time complexity to , since each state is evaluated only once.

Java code

import java.util.*;

public class Main
{
  static int fib[] = new int[46];    
  
  static int f(int n)
  {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (fib[n] != -1) return fib[n];
    return fib[n] = f(n-1) + f(n - 2);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Arrays.fill(fib, -1);
    System.out.println(f(n));     
    con.close();
  }
}
Java

Prove the following properties of Fibonacci numbers:

f_0 + f_1 + f_2 + f_3 + ... + f_n = f_{n+2} - 1

► Base case n = 0: f_0 = f_2 - 1. This is true since 0 = 1 - 1.

Inductive step. Assume that:

f_0 + f_1 + f_2 + f_3 + ... + f_{n-1} = f_{n+1} - 1

Then:

f_0 + f_1 + f_2 + f_3 + ... + f_n = (f_0 + f_1 + f_2 + f_3 + ... + f_{n-1}) + f_n = \\ (f_{n+1} - 1) + f_n = f_{n+2} - 1
f_1 + f_3 + f_5 + ... + f_{2n-1} = f_{2n}

► Base case n = 1: f_1 = f_2, which holds since .

Inductive step. Assume:

f_1 + f_3 + f_5 + ... + f_{2n-1} = f_{2n}

Then:

f_1 + f_3 + ... + f_{2n+1} = (f_1 + f_3 + ... + f_{2n-1}) + f_{2n+1} = \\ f_{2n} + f_{2n+1} = f_{2n+2}
f_2 + f_4 + f_6 + ... + f_{2n} = f_{2n+1} - 1

► Base case n = 1: f_2 = f_3 - 1. This is true since 1 = 2 - 1.

Inductive step. Assume:

f_2 + f_4 + f_6 + ... + f_{2n} = f_{2n+1} - 1

Then:

f_2 + f_4 + ... + f_{2n+2} = (f_2 + f_4 + ... + f_{2n}) + f_{2n+2} = \\ (f_{2n+1} - 1) + f_{2n+2} = f_{2n+3} - 1
f_0^2 + f_1^2 + f_2^2 + ... + f_n^2 = f_n \cdot f_{n+1}

► Base case n = 0: f_0^2 = f_0 \cdot f_1. This is true since 0 = 0 \cdot 1.

Inductive step. Assume:

f_0^2 + f_1^2 + f_2^2 + ... + f_{n-1}^2 = f_{n-1} \cdot f_n

Then:

f_0^2 + f_1^2 + f_2^2 + ... + f_n^2 = (f_0^2 + f_1^2 + f_2^2 + ... + f_{n-1}^2) + f_n^2 = \\ (f_{n-1} \cdot f_n) + f_n^2 = f_n \cdot (f_{n-1} + f_n) = f_n \cdot f_{n+1}

NO two one's in a row

Find the number of sequences of length , consisting only of zeros and ones, that do not have two one's in a row.

Let be the number of sequences consisting of and of length that do not have two one's in a row.

If the first number in the sequence is , then starting from the second place we can build f(n - 1) sequences.

If the first number in the sequence is , then second number must be . In this case, starting from the third position, we can build f(n - 2) sequences.

We have Fibonacci numbers with base cases f(1) = 2, f(2) = 3.

List of problems

6

Comments2