MathGoldMedalist
Sign InRegister

Olympiad Toolkit

A growing collection of essential formulas, identities, and techniques for mathematical olympiad problem solving.

Showing 50 of 156 toolkits
  1. 1.
    Sum of the first n integers
    1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}{2}
  2. 2.
    Sum of squares
    12+22+⋯+n2=n(n+1)(2n+1)61^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}
  3. 3.
    Sum of cubes
    13+23+⋯+n3=(n(n+1)2)21^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2
  4. 4.
    Geometric Sequences and Series
    an=a1rn−1a_n=a_1r^{n-1}
    an2=an−1an+1a_n^2=a_{n-1}a_{n+1}
    Sn=a1+a1r+a1r2+⋯+a1rn−1=a1(rn−1)r−1S_n=a_1+a_1r+a_1r^2+\cdots+a_1r^{n-1}=\frac{a_1(r^n-1)}{r-1}
    ∣r∣<1:S∞=a1+a1r+a1r2+⋯=a11−r|r|<1:\quad S_\infty=a_1+a_1r+a_1r^2+\cdots=\frac{a_1}{1-r}
  5. 5.
    Telescoping
    11⋅2+12⋅3+⋯+1n(n+1)=(1−12)+⋯+(1n−1n+1)=1−1n+1\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{n(n+1)}=\left(1-\frac{1}{2}\right)+\cdots+\left(\frac{1}{n}-\frac{1}{n+1}\right)=1-\frac{1}{n+1}
  6. 6.
    Square of a sum
    (a+b)2=a2+2ab+b2(a+b)^2=a^2+2ab+b^2
  7. 7.
    Square of a difference
    (a−b)2=a2−2ab+b2(a-b)^2=a^2-2ab+b^2
  8. 8.
    Cube of a sum
    (a+b)3=a3+3a2b+3ab2+b3(a+b)^3=a^3+3a^2b+3ab^2+b^3
  9. 9.
    Cube of a difference
    (a−b)3=a3−3a2b+3ab2−b3(a-b)^3=a^3-3a^2b+3ab^2-b^3
  10. 10.
    Difference of squares
    a2−b2=(a−b)(a+b)a^2-b^2=(a-b)(a+b)
  11. 11.
    Difference of cubes
    a3−b3=(a−b)(a2+ab+b2)a^3-b^3=(a-b)(a^2+ab+b^2)
  12. 12.
    Sum of cubes (factored)
    a3+b3=(a+b)(a2−ab+b2)a^3+b^3=(a+b)(a^2-ab+b^2)
  13. 13.
    General difference of powers
    an−bn=(a−b)(an−1+an−2b+⋯+bn−1)a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)
  14. 14.
    Sum of odd power
    n odd:an+bn=(a+b)(an−1−an−2b+⋯+bn−1)n\text{ odd}:\quad a^n+b^n=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots+b^{n-1}\right)
  15. 15.
    Difference of even power
    n even:an−bn=(a+b)(an−1−an−2b+⋯−bn−1)n\text{ even}:\quad a^n-b^n=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots-b^{n-1}\right)
  16. 16.
    Hockey Stick Identity
    (kk)+(k+1k)+(k+2k)+⋯+(nk)=(n+1k+1)\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots+\binom{n}{k}=\binom{n+1}{k+1}
  17. 17.
    Vandermonde's Identity
    (m0)(nk)+(m1)(nk−1)+(m2)(nk−2)+⋯+(mk)(n0)=(m+nk)\binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\binom{m}{2}\binom{n}{k-2}+\cdots+\binom{m}{k}\binom{n}{0}=\binom{m+n}{k}
  18. 18.
    Symmetric cubic sum
    a3+b3+c3=(a+b+c)(a2+b2+c2−ab−ac−bc)+3abca^3+b^3+c^3=(a+b+c)(a^2+b^2+c^2-ab-ac-bc)+3abc
  19. 19.
    Factoring quadratic by grouping
    x2+(a+b)x+ab=(x+a)(x+b)x^2+(a+b)x+ab=(x+a)(x+b)
  20. 20.
    Binomial Theorem
    (a+b)n=(n0)an+(n1)an−1b+(n2)an−2b2+⋯+(nn)bn(a+b)^n=\binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\binom{n}{2}a^{n-2}b^2+\cdots+\binom{n}{n}b^n
  21. 21.
    Quadratic Functions
    ax2+bx+c=0  ⇒  x=−b±b2−4ac2aax^2+bx+c=0\;\Rightarrow\;x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}
  22. 22.
    Approaches to Similar Equations
    Addition and Subtraction.\text{Addition and Subtraction.}
  23. 23.
    SFFT (Simon's Favorite Factoring Trick)
    xy+ax+by=c  ⇒  (x+b)(y+a)=c+abxy+ax+by=c\;\Rightarrow\;(x+b)(y+a)=c+ab
    GSFFT (General Form)\text{GSFFT (General Form)}
    axy+bx+cy=daxy+bx+cy=d
    a2xy+abx+acy=ada^2xy+abx+acy=ad
    (ax+c)(ay+b)=ad+bc(ax+c)(ay+b)=ad+bc
  24. 24.
    Square of a sum (n terms)
    (x1+x2+⋯+xn)2=x12+⋯+xn2+2x1x2+⋯+2xn−1xn(x_1+x_2+\cdots+x_n)^2=x_1^2+\cdots+x_n^2+2x_1x_2+\cdots+2x_{n-1}x_n
  25. 25.
    Arithmetic Sequences and Series
    an=a1+(n−1)da_n=a_1+(n-1)d
    Sn=a1+a2+⋯+an=n2(a1+an)S_n=a_1+a_2+\cdots+a_n=\frac{n}{2}(a_1+a_n)
    an=an−1+an+12a_n=\frac{a_{n-1}+a_{n+1}}{2}
    Number of elements=last−firstd+1\text{Number of elements}=\frac{\text{last}-\text{first}}{d}+1
  26. 26.
    Expansion (or factorization) of three binomials
    abc−ab−ac−bc+a+b+c−1=(a−1)(b−1)(c−1)abc-ab-ac-bc+a+b+c-1=(a-1)(b-1)(c-1)
  27. 27.
    Expansion (or factorization) of two binomials
    a2+ab+ac+bc=(a+b)(a+c)a^2+ab+ac+bc=(a+b)(a+c)
  28. 28.
    Mean Inequalities
    x1,…,xn∈R+x_1,\dots,x_n\in\mathbb{R}^+
    max⁡{xi}≥x12+x22+⋯+xn2n≥x1+x2+⋯+xnn≥x1x2⋯xnn≥n1x1+1x2+⋯+1xn≥min⁡{xi}\max\{x_i\}\ge\sqrt{\frac{x_1^2+x_2^2+\cdots+x_n^2}{n}}\ge\frac{x_1+x_2+\cdots+x_n}{n}\ge\sqrt[n]{x_1x_2\cdots x_n}\ge\frac{n}{\frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_n}}\ge\min\{x_i\}
    Equality holds if and only if all xi are equal.\text{Equality holds if and only if all }x_i\text{ are equal.}
  29. 29.
    Bounding the Fractional Part
    [x]: Integer part{x}: Fractional part[x]:\text{ Integer part}\qquad\{x\}:\text{ Fractional part}
    We can write x as:\text{We can write }x\text{ as:}
    x=k+r,k∈Z,  r∈R,  0≤r<1x=k+r,\qquad k\in\mathbb{Z},\;r\in\mathbb{R},\;0\le r<1
  30. 30.
    Vieta's Formula
    ax2+bx+c=0ax^2+bx+c=0
    r1+r2=−ba,r1r2=car_1+r_2=-\frac{b}{a},\qquad r_1r_2=\frac{c}{a}
    ax3+bx2+cx+d=0ax^3+bx^2+cx+d=0
    r1+r2+r3=−bar_1+r_2+r_3=-\frac{b}{a}
    r1r2+r1r3+r2r3=car_1r_2+r_1r_3+r_2r_3=\frac{c}{a}
    r1r2r3=−dar_1r_2r_3=-\frac{d}{a}
    anxn+an−1xn−1+⋯+a1x+a0=0a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0=0
    r1+r2+⋯+rn=−an−1anr_1+r_2+\cdots+r_n=-\frac{a_{n-1}}{a_n}
    r1r2+r1r3+⋯+rn−1rn=an−2anr_1r_2+r_1r_3+\cdots+r_{n-1}r_n=\frac{a_{n-2}}{a_n}
    ⋯\cdots
    r1r2⋯rn−1+⋯+r2r3⋯rn=(−1)n−1a1anr_1r_2\cdots r_{n-1}+\cdots+r_2r_3\cdots r_n=(-1)^{n-1}\frac{a_1}{a_n}
    r1r2⋯rn=(−1)na0anr_1r_2\cdots r_n=(-1)^n\frac{a_0}{a_n}
  31. 31.
    Quadratic Inequalities
    f(x)=ax2+bx+c,Δ=b2−4acf(x)=ax^2+bx+c,\qquad \Delta=b^2-4ac
    ConditionNumber of Real RootsSign of f(x)f(x)
    Δ>0\Delta>02
    sign(a)0−sign(a)0sign(a)r₁r₂
    Δ=0\Delta=01
    sign(a)0sign(a)r
    Δ<0\Delta<00
    sign(a)
  32. 32.
    Polynomial Remainders
    A(x)÷B(x):  A(x)=B(x)Q(x)+R(x),deg⁡(R(x))<deg⁡(B(x))A(x)\div B(x):\;A(x)=B(x)Q(x)+R(x),\quad \deg(R(x))<\deg(B(x))
    ⇒ If B(x)=0, then A(x)=R(x)\Rightarrow\text{ If }B(x)=0,\text{ then }A(x)=R(x)
  33. 33.
    Number of Positive Divisors
    n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
    Number of positive divisors of n:  (α1+1)(α2+1)⋯(αk+1)\text{Number of positive divisors of }n:\;(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)
  34. 34.
    Sum of Positive Divisors
    n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
    (1+p1+p12+⋯+p1α1)(1+p2+p22+⋯+p2α2)⋯(1+pk+pk2+⋯+pkαk)(1+p_1+p_1^2+\cdots+p_1^{\alpha_1})(1+p_2+p_2^2+\cdots+p_2^{\alpha_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{\alpha_k})
    =p1α1+1−1p1−1×p2α2+1−1p2−1×⋯×pkαk+1−1pk−1=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\times\frac{p_2^{\alpha_2+1}-1}{p_2-1}\times\cdots\times\frac{p_k^{\alpha_k+1}-1}{p_k-1}
  35. 35.
    Product of Positive Divisors
    n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
    t=(α1+1)(α2+1)⋯(αk+1)t=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)
    Product of positive divisors of n:  nt/2\text{Product of positive divisors of }n:\;n^{t/2}
  36. 36.
    General Solutions of Trigonometric Equations
    sin⁡α=sin⁡β  ⇒  α=β+360k,  180−β+360k,  k∈Z\sin\alpha=\sin\beta\;\Rightarrow\;\alpha=\beta+360k,\;180-\beta+360k,\;k\in\mathbb{Z}
    cos⁡α=cos⁡β  ⇒  α=±β+360k,  k∈Z\cos\alpha=\cos\beta\;\Rightarrow\;\alpha=\pm\beta+360k,\;k\in\mathbb{Z}
    tan⁡α=tan⁡β  ⇒  α=β+180k,  k∈Z\tan\alpha=\tan\beta\;\Rightarrow\;\alpha=\beta+180k,\;k\in\mathbb{Z}
    cot⁡α=cot⁡β  ⇒  α=β+180k,  k∈Z\cot\alpha=\cot\beta\;\Rightarrow\;\alpha=\beta+180k,\;k\in\mathbb{Z}
  37. 37.
    Trigonometric Transformations
    sin⁡(90∘−α)=cos⁡α\sin(90^\circ-\alpha)=\cos\alpha
    cos⁡(90∘−α)=sin⁡α\cos(90^\circ-\alpha)=\sin\alpha
    sin⁡(180∘−α)=sin⁡α\sin(180^\circ-\alpha)=\sin\alpha
    cos⁡(180∘−α)=−cos⁡α\cos(180^\circ-\alpha)=-\cos\alpha
    sin⁡(−α)=−sin⁡α\sin(-\alpha)=-\sin\alpha
    cos⁡(−α)=cos⁡α\cos(-\alpha)=\cos\alpha
    ⋯\cdots
  38. 38.
    Trigonometric Identities
    sin⁡2α+cos⁡2α=1\sin^2\alpha+\cos^2\alpha=1
    sin⁡(α+β)=sin⁡αcos⁡β+cos⁡αsin⁡β\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta
    cos⁡(α+β)=cos⁡αcos⁡β−sin⁡αsin⁡β\cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta
    sin⁡2α=2sin⁡αcos⁡α\sin2\alpha=2\sin\alpha\cos\alpha
    cos⁡2α=2cos⁡2α−1=1−2sin⁡2α\cos2\alpha=2\cos^2\alpha-1=1-2\sin^2\alpha
    ⋯\cdots
  39. 39.
    Trigonometric Sum-to-Product Identities
    sin⁡α+sin⁡β=2sin⁡(α+β2)cos⁡(α−β2)\sin\alpha+\sin\beta=2\sin\left(\frac{\alpha+\beta}{2}\right)\cos\left(\frac{\alpha-\beta}{2}\right)
    sin⁡α−sin⁡β=2cos⁡(α+β2)sin⁡(α−β2)\sin\alpha-\sin\beta=2\cos\left(\frac{\alpha+\beta}{2}\right)\sin\left(\frac{\alpha-\beta}{2}\right)
    cos⁡α+cos⁡β=2cos⁡(α+β2)cos⁡(α−β2)\cos\alpha+\cos\beta=2\cos\left(\frac{\alpha+\beta}{2}\right)\cos\left(\frac{\alpha-\beta}{2}\right)
    cos⁡α−cos⁡β=−2sin⁡(α+β2)sin⁡(α−β2)\cos\alpha-\cos\beta=-2\sin\left(\frac{\alpha+\beta}{2}\right)\sin\left(\frac{\alpha-\beta}{2}\right)
  40. 40.
    Trigonometric Product-to-Sum Identities
    sin⁡pcos⁡q=12(sin⁡(p+q)+sin⁡(p−q))\sin p\cos q=\frac{1}{2}(\sin(p+q)+\sin(p-q))
    cos⁡pcos⁡q=12(cos⁡(p+q)+cos⁡(p−q))\cos p\cos q=\frac{1}{2}(\cos(p+q)+\cos(p-q))
    sin⁡psin⁡q=12(cos⁡(p−q)−cos⁡(p+q))\sin p\sin q=\frac{1}{2}(\cos(p-q)-\cos(p+q))
  41. 41.
    Dual Pythagorean Theorem
    Dual Pythagorean Theorem figure
    CB2−CA2=EB2−EA2=FB2−FA2=DB2−DA2CB^2-CA^2=EB^2-EA^2=FB^2-FA^2=DB^2-DA^2
  42. 42.
    Angle Bisector Theorem
    Angle Bisector Theorem figure
    BDDC=cb\frac{BD}{DC}=\frac{c}{b}
  43. 43.
    Partial Fraction Decomposition
    5x+1(x−1)(x+2)=Ax−1+Bx+2\frac{5x+1}{(x-1)(x+2)}=\frac{A}{x-1}+\frac{B}{x+2}
    Method 1: Comparing coefficients\text{Method 1: Comparing coefficients}
    Method 2: Heaviside Cover-Up Method\text{Method 2: Heaviside Cover-Up Method}
  44. 44.
    Creating n Equations in n Variables for Probability Problems
  45. 45.
    Adjacency in Permutations
    Treat adjacent objects as one block\text{Treat adjacent objects as one block}
    Example: logarithm\text{Example: }\boxed{\mathrm{log}}\mathrm{arithm}
    7!×3!7!\times3!
  46. 46.
    Divisibility

    Definition

    a∣b  ⟺  there exists an integer k s.t. b=aka\mid b\iff \text{there exists an integer }k\text{ s.t. }b=ak

    Properties

    1.1.
    a∣b,  b∣c⟹a∣ca\mid b,\; b\mid c \Longrightarrow a\mid c
    2.2.
    a∣b,  a∣c⟹a∣mb+nca\mid b,\; a\mid c \Longrightarrow a\mid mb+nc
    3.3.
    gcd⁡(a,b)=1,  a∣bc⟹a∣c\gcd(a,b)=1,\; a\mid bc \Longrightarrow a\mid c
    4.4.
    p∣ab⟹p∣a or p∣b,p prime.p\mid ab \Longrightarrow p\mid a \text{ or } p\mid b,\qquad p\text{ prime.}
  47. 47.
    Modular Arithmetic

    Definition

    a≡b(modm)  ⟺  m∣(a−b)a\equiv b\pmod m\iff m\mid(a-b)

    Properties

    1.1.
    a≡b(modm),  b≡c(modm)⟹a≡c(modm)a\equiv b\pmod m,\; b\equiv c\pmod m\Longrightarrow a\equiv c\pmod m
    2.2.
    a≡b(modm)⟹an≡bn(modm),n∈Z+a\equiv b\pmod m\Longrightarrow a^n\equiv b^n\pmod m,\quad n\in\mathbb Z^+
    3.3.
    ac≡bc(modm)  ⟺  a≡b(modmgcd⁡(m,c))ac\equiv bc\pmod m\iff a\equiv b\pmod{\frac{m}{\gcd(m,c)}}
    4.4.
    a≡b(modm),  d∣m⟹a≡b(modd)a\equiv b\pmod m,\; d\mid m\Longrightarrow a\equiv b\pmod d
  48. 48.
    Principle of Inclusion–Exclusion (PIE): Fundamentals and Extensions

    Two Sets

    ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|

    Three Sets

    ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

    General Formula

    ∣A1∪⋯∪An∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+∑i<j<k∣Ai∩Aj∩Ak∣−⋯|A_1\cup\cdots\cup A_n|=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots

    Exactly One Set

    PA1,A2=∣A1∣+∣A2∣−2∣A1∩A2∣P_{A_1,A_2}=|A_1|+|A_2|-2|A_1\cap A_2|
    PA1,A2,A3=∣A1∣+∣A2∣+∣A3∣−2∣A1∩A2∣−2∣A1∩A3∣−2∣A2∩A3∣+3∣A1∩A2∩A3∣P_{A_1,A_2,A_3}=|A_1|+|A_2|+|A_3|-2|A_1\cap A_2|-2|A_1\cap A_3|-2|A_2\cap A_3|+3|A_1\cap A_2\cap A_3|
  49. 49.
    Euler's Totient Function φ(n)
    φ(n)=∣{1≤i≤n∣gcd⁡(i,n)=1}∣\varphi(n)=|\{1\le i\le n\mid\gcd(i,n)=1\}|

    φ(n)\varphi(n) is the number of integers from 11 to nn that are relatively prime to nn.

    If n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},

    φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)
  50. 50.
    Euler's Theorem

    Let nn be a positive integer. If gcd⁡(n,a)=1\gcd(n,a)=1,

    aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n