“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Fibonacci Sequence

Algorithms

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

Definition

The Fibonacci sequence is defined as:

F_{0} = 0, F_{1} = 1

F_{n} = F_{n - 1} + F_{n - 2} for n \geq 2

Dynamic Programming Approach

Using dynamic programming, we can compute Fibonacci numbers efficiently in $O (n)$ time with $O (1)$ space using an optimized approach.

Implementation

def fibonacci(n, optimized=True):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    if optimized:
        # Space-Optimized Approach
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b
    else:
        # Full List Approach
        fib = [0] * (n + 1)
        fib[1] = 1
        for i in range(2, n + 1):
            fib[i] = fib[i - 1] + fib[i - 2]
        return fib[n]

# Example usage:
print(fibonacci(10))  # Output: 55 (optimized by default)
print(fibonacci(10, optimized=False))  # Output: 55 (using full list)

Try First

Each prompt asks a checkable question about the working code or math above — predict an output, derive a sign, state an invariant, find a bug. Commit to an answer before clicking "reveal." That commitment is the whole point: if your answer matched, you understand the piece you were looking at; if it didn't, that's the part worth re-reading.

invariant

At the top of iteration k of the optimized loop (so just before the assignment runs), what do a and b hold? Phrase your answer in terms of

F

. Be precise about indices — the loop starts at k = 2.

predict

Without running the code, predict fibonacci(20). Use Binet's closed form:

F (n) = \frac{φ ^{n} - ψ ^{n}}{5}

where

φ = (1 + 5) /2 \approx 1.618

and

ψ = (1 - 5) /2 \approx - 0.618

. For n = 20, the

ψ^{n}

term is tiny — about 5·10^-5 — so rounding

φ^{20} / 5

should give the answer. Now: at what n does floating-point error start producing the wrong integer?

why does this work

Compute F(n) mod 7 for n = 0, 1, 2, ..., 20 and write out the sequence. You'll find it repeats with a period (the Pisano period for m = 7). Why is the existence of some period — for any modulus m — guaranteed? The argument should come from the structure of the recurrence, and a counting bound on the possible states it can be in.

find the bug

I changed a, b = b, a + b to a, b = b, max(a, b). The code still runs and still returns a number. What does it now compute, and for what input would you actually want this algorithm?

equivalence

Show that

(1110)^{n} = (F (n + 1) F (n) F (n) F (n - 1))

. What does this matrix identity buy you computationally over the linear loop above?

hint

Prove by induction on n. The base case is n = 1; the inductive step uses one matrix multiplication and the Fibonacci recurrence.

Hack This

The code above works. Don't reinvent it — pull it into an editor, run it, and try the modifications below. Each one is small. Each one will change the behavior in a specific way; the question is which way.

trivial

The Fibonacci recurrence runs both directions: rearranging

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

gives

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

. So F(-1) = 1, F(-2) = -1, F(-3) = 2, F(-4) = -3, F(-5) = 5 — the magnitudes match the positive side, but the signs alternate. Modify the optimized function to accept negative n and return the right value. Then: why does the sign alternate specifically in that pattern? Predict the sign of F(-100) without computing it.

hint

The alternation pattern is dictated by the closed form. With

ψ = (1 - 5) /2

being negative,

ψ^{n}

flips sign with every step of n — and on the negative side, the

ψ^{n}

term dominates rather than vanishes.

trivial

Change the initialization to a, b = 2, 1. The recurrence is unchanged but the sequence becomes the Lucas numbers: 2, 1, 3, 4, 7, 11, 18, 29, 47, .... Verify by running. Then: what's the closed form? It uses the same

φ

and

ψ

as Binet — only the coefficients change. Find them.

small

Generalize the rolling pair to compute

a_{n} = p \cdot a_{n - 1} + q \cdot a_{n - 2}

for arbitrary integer p, q. With p = q = 1 you get Fibonacci. With p = 2, q = 1 you get Pell numbers (0, 1, 2, 5, 12, 29, ...). With p = 1, q = 2 you get the Jacobsthal numbers (0, 1, 1, 3, 5, 11, 21, ...). What's the growth rate of the generalized sequence as a function of p, q? When is the growth rate even real?

small

Define T(n) = T(n-1) + T(n-2) + T(n-3) with T(0) = 0, T(1) = 0, T(2) = 1. Modify the optimized code to compute it. You'll need more state — the rolling pair becomes a rolling triple. The growth rate is the tribonacci constant

η \approx 1.839

(replacing the golden ratio). Predict T(20) using

T (n) \approx C \cdot η^{n}

(the constant

C \approx 0.18

), then verify.

hint

Three variables: a, b, c = 0, 0, 1. Each step: a, b, c = b, c, a + b + c. Return c (with appropriate handling for small n). For n = 20, the prediction

0.18 \cdot 1.83 9^{20}

gives roughly 35,890 — close to the true value 35,890. (Yes, exactly. The leading coefficient and constant are both close enough that rounding lands on the integer.)

medium

Implement fib_log(n) using the matrix identity from the Under-the-Hood probe:

M^{n}

where

M = (1110)

, computed via repeated squaring (use Python's ** for ints but write the 2×2 matrix power yourself). Verify it against the linear loop for n = 0..50. Then run it with n = 10^18 mod (10^9 + 7) — a problem that would take longer than the heat death of the universe with the linear loop, and a few microseconds here. Compare its asymptotic cost to the Pisano-period approach. Which one wins, and for what kind of input?

hint

Matrix exponentiation is O(log n) regardless of modulus. The Pisano-period approach is O(period(m)) to find the period, then O(n mod period(m)) to compute. For small m the period is tiny and Pisano dominates. For large m (especially prime m), the period can approach m and the matrix approach wins.

medium

Compute fibonacci(10**8) % 1000 using the existing optimized loop. Time it. Now modify the loop to take the modulus inside the loop body — a, b = b, (a + b) % 1000 — and time that. Why is the second version dramatically faster, even though both do the same number of iterations? What's the running magnitude of b in each case at iteration 10^7?

hint

Python ints are arbitrary precision. By iteration 10^7 the value of b in the unmodded version has about

1 0^{7} \cdot lo g_{10} (φ) \approx 2.1 \cdot 1 0^{6}

digits. Each addition of two such numbers is O(digits) — turning the loop from O(n) primitive operations into O(n²) bit operations. The modded version keeps every value below 1000, so each addition is actually constant-time.