Bereken het aantal functieaanroepen

Laten we een klassiek voorbeeld van recursie bekijken: de rij van Fibonacci, bestaande uit niet-negatieve gehele getallen beginnend bij 0, waarbij elk element \(F(n)\) gelijk is aan de som van de twee voorgaande: 0, 1, 1, 2, 3, 5, 8, 13, 21, .... Je krijgt een functie die een tuple teruggeeft met het \(n\)-de element van de rij en het aantal aanroepen van fib() dat daarvoor is gebruikt:

def fib(n):

  if n < 2:
    return (n, 1)

  fib1 = fib(n-1)
  fib2 = fib(n-2)

  return (fib1[0] + fib2[0], fib1[1] + fib2[1] + 1)

Hoeveel aanroepen van fib() zijn er nodig om het \(15^{de}\) en \(20^{ste}\) element van de rij te berekenen?