📚 Study Notes – Formulas & Functions
Target Audience: IIT‑JEE / Competitive Programming (NCO – Cyber Olympiad)
These notes cover the mathematical and programming fundamentals you’ll need to tackle “Formulas and Functions” problems.
They are written to be exam‑oriented: every derivation is included, key formulae are highlighted, and pitfalls are flagged.
1. Core Concepts
| Concept | Definition | Common Use‑Cases |
|---|---|---|
| Function (in math & programming) | A mapping f : A → B that assigns each element of A exactly one element of B. |
Recurrence, DP, modular arithmetic, combinatorics |
| Recurrence Relation | a_n = F(a_{n-1}, a_{n-2}, …) |
Fibonacci, Catalan, binomial coefficients |
| Modular Function | f(x) ≡ y (mod m) |
Fast exponentiation, combinatorics under modulo |
| Generating Function | Power series G(x) = Σ a_n x^n |
Counting, DP optimization |
| First‑Order Linear Recurrence | a_n = p·a_{n-1} + q |
Geometric series, linear DP |
| Higher‑Order Recurrence | a_n = Σ c_k a_{n-k} |
Linear DP, matrix exponentiation |
2. Fundamental Formulas
2.1. Arithmetic & Geometric Series
| Series | Sum (Finite) | Sum (Infinite) | Used in |
|---|---|---|---|
| Arithmetic | S_n = n/2 * (a_1 + a_n) |
– | Summation of consecutive integers |
| Geometric | S_n = a_1 * (1 - r^n) / (1 - r) |
S = a_1/(1-r) ( |
r |
2.2. Binomial Coefficients
| Formula | Modulo (Prime p) |
Complexity |
|---|---|---|
C(n, k) = n! / (k! (n-k)!) |
Pre‑compute factorials & inverse factorials | O(1) per query |
C(n, k) mod p = fact[n] * invFact[k] * invFact[n-k] mod p |
Fermat: x^(p-2) mod p |
O(log p) for inverse |
Derivation (Prime Modulus)
Using Fermat’s Little Theorem:
a^(p-1) ≡ 1 (mod p) → a^(p-2) ≡ a^(-1) (mod p).
2.3. Catalan Numbers
C_n = (1/(n+1)) * binom(2n, n)
Alternative recurrence: C_{n+1} = Σ C_i * C_{n-i}.
Used for counting balanced parentheses, binary trees, etc.
2.4. Fibonacci Numbers
| Recurrence | Closed‑form (Binet) | Matrix Form | Modulo |
|---|---|---|---|
F_n = F_{n-1} + F_{n-2} |
((φ^n - ψ^n)/√5) |
[[1,1],[1,0]]^n |
Fast doubling (O(log n)) |
Fast Doubling (key trick for competitive programming).
Let F(2k) = F(k) * (2*F(k+1) – F(k))
and F(2k+1) = F(k+1)^2 + F(k)^2.
2.5. Modular Exponentiation
powMod(a, b, m) implemented via binary exponentiation:
res = 1
while b > 0:
if b & 1: res = (res * a) % m
a = (a * a) % m
b >>= 1
Complexity: O(log b).
2.6. Inclusion–Exclusion Principle
For finite sets A1,…,Ak:
|⋃ Ai| = Σ |Ai| - Σ |Ai∩Aj| + Σ |Ai∩Aj∩Ak| - …
Used in counting problems with overlapping conditions.
3. Advanced Topics & Derivations
3.1. Lucas Theorem (Combinations Modulo Prime)
For n = n0 + n1*p + n2*p^2 + …
C(n, k) mod p = Π C(ni, ki) mod p
where ki are digits of k in base p.
Tricky Point: Works only for prime modulus; pre‑compute factorial up to p-1.
3.2. Chinese Remainder Theorem (CRT)
Given x ≡ a_i (mod m_i) with pairwise coprime m_i,
x ≡ Σ (a_i * M_i * inv(M_i, m_i)) (mod M) where
M = Π m_i, M_i = M/m_i.
Used to compute C(n, k) modulo composite numbers.
3.3. Euler’s Totient & Inverse Modulo
If gcd(a, m) = 1,
a^(φ(m)-1) ≡ a^(-1) (mod m) where φ is Euler’s totient.
Compute φ(m) via prime factorization for m ≤ 10^9.
4. Programming Patterns
| Pattern | When to Use | Code Snippet (C++17) |
|---|---|---|
| Iterative DP | Linear recurrence, state DP | `vector<long long> dp(n+1); dp[0] = 1; for(i=1..n) dp[i] = (dp[i-1] + dp[i |