Number Patterns and Sequences Explained — Fibonacci, Catalan, Triangular for Interviews [LC 96, Google, Meta]

Algorithm Statement#

A reference of the most interview-relevant integer sequences and their identities:

1. Fibonacci: $F(n) = F(n-1) + F(n-2)$, $F(0) = 0$, $F(1) = 1$.
2. Triangular: $T_n = \binom{n+1}{2} = \frac{n(n+1)}{2}$.
3. Catalan: $C_n = \frac{1}{n+1}\binom{2n}{n}$, with the recurrence $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$.
4. Lucas: $L(n) = L(n-1) + L(n-2)$, $L(0) = 2$, $L(1) = 1$.
5. Pell: $P(n) = 2 P(n-1) + P(n-2)$, $P(0) = 0$, $P(1) = 1$.

Constraints typical:

• $1 \le n \le 10^5$ for direct DP.
• $1 \le n \le 10^{18}$ for matrix exponentiation or closed forms.

Examples:

F(10) = 55
T(10) = 55
C(5)  = 42         (LC 96 BST count for n = 5)
L(10) = 123

Why This Problem Matters#

Interview problems are often disguised classical sequences. LC 96 Unique Binary Search Trees is the Catalan number. LC 70 Climbing Stairs is Fibonacci. LC 22 Generate Parentheses is enumeration of Catalan structures. LC 1359 Count All Valid Pickup and Delivery Options is double factorial / Catalan. Recognising the pattern saves you 20 minutes of derivation.

Google and Meta especially reward candidates who say "this is the $n$-th Catalan number, so the answer is $\frac{1}{n+1}\binom{2n}{n}$" within a minute of seeing the problem. It signals breadth — and avoids the brittle DP you would otherwise write under pressure.

The Core Insight#

Fibonacci counts climbing-stairs paths, tilings of a $2 \times n$ board with dominoes, and binary strings of length $n$ with no two consecutive 1s. Closed form: $F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$ where $\phi = (1 + \sqrt 5)/2$. For $n$ up to $10^{18}$, use matrix exponentiation.

Triangular numbers count the number of unordered pairs from $n+1$ items, hence $T_n = \binom{n+1}{2}$. They satisfy $T_n = T_{n-1} + n$. Useful for problems like "how many handshakes among $n$ people".

Catalan numbers count an explosive number of structures: balanced parentheses, BSTs on $n$ nodes, monotone lattice paths under the diagonal, full binary trees with $n+1$ leaves, triangulations of a convex $(n+2)$-gon, non-crossing chord diagrams. The unifying identity:

Closed form: $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Lucas numbers are the "twin" of Fibonacci with a different start. Identity: $L_n = F_{n-1} + F_{n+1}$.

Pell numbers count perfect squares that are also triangular and appear in continued-fraction expansions of $\sqrt 2$.

Why Catalan equals $\binom{2n}{n}/(n+1)$. Reflection principle: among the $\binom{2n}{n}$ lattice paths from $(0,0)$ to $(n,n)$, exactly $\binom{2n}{n+1}$ cross the diagonal. The valid count is $\binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}$.

Visual Dry Run#

Catalan number for $n = 4$ via the recurrence.

C(0) = 1
C(1) = C(0)*C(0) = 1
C(2) = C(0)*C(1) + C(1)*C(0) = 1 + 1 = 2
C(3) = C(0)*C(2) + C(1)*C(1) + C(2)*C(0) = 2 + 1 + 2 = 5
C(4) = C(0)*C(3) + C(1)*C(2) + C(2)*C(1) + C(3)*C(0)
     = 5 + 2 + 2 + 5 = 14
 
Verify with closed form: C(4) = (1/5) * binomial(8, 4)
                                  = (1/5) * 70 = 14.

LC 96 with $n = 3$: count BSTs on 3 nodes.

Pick root r in {1, 2, 3}.
  r = 1: left subtree empty, right has {2, 3}     → 1 * C(2) = 2
  r = 2: left has {1}, right has {3}              → 1 * 1   = 1
  r = 3: left has {1, 2}, right empty             → C(2) * 1 = 2
 
Total = 5 = C(3). Matches.

Triangular number example.

T(5) = 5*6/2 = 15.
Visual: dot triangle with rows of 1, 2, 3, 4, 5 dots → total 15.

Solution (Optimal)#

Python — Direct Sequences#

# Fibonacci O(n) DP
def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
 
# Triangular closed form
def triangular(n: int) -> int:
    return n * (n + 1) // 2
 
# Catalan via DP O(n^2)
def catalan_dp(n: int) -> int:
    C = [0] * (n + 1)
    C[0] = 1
    for i in range(1, n + 1):
        C[i] = sum(C[j] * C[i - 1 - j] for j in range(i))
    return C[n]
 
# Catalan via closed form O(n)
from math import comb
def catalan(n: int) -> int:
    return comb(2 * n, n) // (n + 1)

Python — Catalan Modulo Prime#

MOD = 10**9 + 7
 
def catalan_mod(n: int) -> int:
    # Precompute factorials in O(n)
    fact = [1] * (2 * n + 2)
    for i in range(1, len(fact)):
        fact[i] = fact[i - 1] * i % MOD
    inv = pow(fact[2 * n], MOD - 2, MOD)
    binom = fact[2 * n] * pow(fact[n], MOD - 2, MOD) % MOD \
                       * pow(fact[n], MOD - 2, MOD) % MOD
    return binom * pow(n + 1, MOD - 2, MOD) % MOD

Complexity: $O(n)$ time per query (after precomputing factorials), $O(n)$ memory.

JavaScript#

function fib(n) {
    let [a, b] = [0n, 1n];
    for (let i = 0; i < n; i++) [a, b] = [b, a + b];
    return a;
}
 
function triangular(n) {
    return BigInt(n) * BigInt(n + 1) / 2n;
}
 
function catalan(n) {
    let C = 1n;
    for (let i = 0; i < n; i++)
        C = C * BigInt(2 * (2 * i + 1)) / BigInt(i + 2);
    return C;
}

Common Mistakes#

1. Computing Catalan with double factorials and floats. Use exact integer arithmetic. The intermediate $\binom{2n}{n}$ overflows 64 bits past $n = 33$.
2. Wrong base case for Fibonacci. Some sources use $F(1) = F(2) = 1$, others $F(0) = 0, F(1) = 1$. Confirm with the interviewer.
3. Triangular overflow. $n \cdot (n+1)$ overflows 32-bit ints for $n > 2^{15}$. Promote to 64-bit before the multiply.
4. Missing the modular inverse for Catalan. When the problem asks for the answer mod prime, compute $\binom{2n}{n}$ then multiply by the inverse of $n+1$.
5. Confusing zero-indexed and one-indexed Catalan. $C_0 = 1$ counts the empty structure. $C_1 = 1$ counts a single node.
6. Reaching for matrix exponentiation when DP suffices. For $n \le 10^5$ the simple DP is faster and clearer than the $O(\log n)$ matrix path.

Interview Tips#

• Recite the Catalan list quickly: 1, 1, 2, 5, 14, 42, 132, 429. If you see 14 or 42 in an example, scream "Catalan!"
• For "count valid parentheses" or "count BSTs", state the closed form before any code.
• For Fibonacci with $n$ huge, immediately mention matrix exponentiation; for $n$ medium, just do the iterative DP.
• Mention the bijection between Catalan structures (parens, BSTs, paths) — interviewers love structural arguments.

Follow-up Questions#

Q1: Compute $F(n)$ for $n = 10^{18}$. A: Matrix exponentiation in $O(\log n)$ using the $2 \times 2$ Fibonacci matrix.

Q2: Why does the same Catalan number count BSTs and balanced parens? A: Build a bijection: in-order traversal of a BST with $n$ nodes yields a sequence of "open" and "close" events that form a balanced parenthesis string of length $2n$.

Q3: What is the asymptotic growth of $C_n$? A: $C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}$ (Stirling's approximation).

Q4: Generalised Catalan: count paths from $(0,0)$ to $(m, n)$ that never go above the diagonal. A: Ballot problem; the count is $\binom{m+n}{n} - \binom{m+n}{n-1}$ for $m \ge n$.

Key Takeaways#

• Fibonacci counts staircase paths and tilings; closed form $F_n = (\phi^n - \psi^n)/\sqrt 5$, matrix form for $n = 10^{18}$.
• Triangular numbers are $\binom{n+1}{2} = n(n+1)/2$ — the answer to nearly every "handshake" or "pair" question.
• Catalan numbers count balanced parens, BSTs, full binary trees, lattice paths, and triangulations; closed form $C_n = \frac{1}{n+1}\binom{2n}{n}$.
• The Catalan recurrence $C_{n+1} = \sum_i C_i C_{n-i}$ comes from picking the root (or first matched paren) and recursing on left and right halves.
• For modular Catalan, precompute factorials and inverse factorials, then assemble the closed form.
• Recognising the sequence on sight saves 20 minutes of DP derivation — memorise the first ten Catalan terms.