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.

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:

Thus, we have:

The Fibonacci sequence therefore begins as:

Each term is obtained by adding the two previous terms.

Example. Compute Fibonacci numbers using an array.

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

#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;
}

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

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

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 $n$-th Fibonacci number using a recursive function.

The following program implements a direct recursive definition of the Fibonacci sequence. The function $fib(n)$ returns the $n$-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;
}

Example. Compute the $n$-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;
}

This approach significantly improves efficiency compared to plain recursion. While the naive recursive solution has exponential complexity, memoization reduces the time complexity to $O(n)$, 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();
  }
}

Prove the following properties of Fibonacci numbers:

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

Inductive step. Assume that:

Then:

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

Inductive step. Assume:

Then:

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

Inductive step. Assume:

Then:

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

Inductive step. Assume:

Then:

NO two one's in a row

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

Let $f(n)$ be the number of sequences consisting of $0$ and $1$ of length $n$ that do not have two one's in a row.

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

If the first number in the sequence is $1$, then second number must be $0$. 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

• 4730. Fibonacci

• 263. Three ones

• 2421. Fibonacci numbers

• 1250. Fibonacci problem again

• 8295. Fibonacci string generation

• 5103. Koza Nostra

• 5091. Explosive containers

• 5092. Honeycomb

• 7438. Binary password

• 9558. Flags

• 4469. Domino

• 2292. Fibonacci number

• 12317. Field modulo

• 12318. Sum in Field

• 12483. Fibonacci fever