1. Fibonacci thứ
   $n$ :

$$f_n=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}},\varphi =\frac{1+\sqrt{5}}{2},\psi =\frac{1-\sqrt{5}}{2}$$

3. Công thức tích Vandermonde :
   

   $$\sum _{i=0}^k(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{m}{k-i})=(\genfrac{}{}{0ex}{}{n+m}{k})$$

4. Nhị thức Newton :

   $$(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})\cdot a^i\cdot b^{n-i}$$

5. Catanlan độ dài

   $2n$:
   
   $$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$$

6. Phi hàm Euler:

$$\phi (n)=n\times \prod _{p_i}(1-\frac{1}{p_i})=\prod _{i=1}^k{p}_i^{a_i-1}(p_i-1)$$

7. GCD của hai số Fibonacci

   $$gcd(Fi{b}_n,Fi{b}_m)=Fi{b}_{gcd(n,m)}$$

8. Sinh các bộ

   $(a,b,c)$ Pythagoras
   $a^2+b^2=c^2$ :
   $a=m^2-n^2,b=mn,c=m^2+n^2$, trong đó
   $m>n>0,gcd(n,m)=1,nmod2=1$ hoặc
   $mmod2=1$

9. Tính

   $\sum _{i=1}^n{i}^k$ bằng Lagrange :

for(int i=1; i<=k+2; ++i){
    y[i]=add(y[i-1], binpow(i, k));
  }
  if(n<=k+2) return cout<<y[n], void();
 
  int convolution=1;
  fact[0]=inv[0]=1;
  for(int i=1; i<=k+2; ++i){
    fact[i]=mul(fact[i-1], i);
    inv[i]=inverse(fact[i]);
  }
  prefix[0]=suffix[k+3]=1;
  for(int i=1, j=k+2; j>0; ++i, --j){
    prefix[i]=mul(prefix[i-1], (n-i));
    suffix[j]=mul(suffix[j+1], (n-j));
  }
 
  int ans=0;
  for(int i=1; i<=k+2; ++i){
    int res=mul(prefix[i-1], suffix[i+1]);
    res=mul(res, mul(y[i], inverse(mul(fact[i-1], fact[k+2-i]))));
    if(k+2-i&1) ans=(ans-res+M)%M;
    else ans=(ans+res)%M;
  }
  cout<<ans;

10. Euler Phi Sieve:

for (int i = 1; i <= maxN; i++) EulerPhi[i] = i;
for (int i = 2; i <= maxN; i++) {
    if (EulerPhi[i] != i) continue; // i is composite
    for (int j = 1; i * j <= maxN; j++)
        EulerPhi[i * j] = (EulerPhi[i * j] / i) * (i - 1);
}

11. Principle of inclusion-exclusion

Size of

$n$ sets union:

$$|A_1\cup A_2\cup \cdots \cup A_n|=\sum |A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|\times (-1{)}^{k-1}$$

for every

$\{i_1,i_2,\cdots ,i_k\}$ is a subset of

$\{1,2,\cdots ,n\}$.

11. Định lý Lucas :
    

    $${\mathrm{\Pi }}_{i=0}^k(\genfrac{}{}{0ex}{}{n_i}{m_i})=(\genfrac{}{}{0ex}{}{n}{m})\text{(mod M)}$$
    $$n=n_0{M}^0+n_1{M}^1+n_2{M}^2+...+n_k{M}^k$$
    $$m=m_0{M}^0+m_1{M}^1+m_2{M}^2+...+m_k{M}^k$$

12. Extended Catalan with a fixed prefix with

    $k$ open brackets :

$$C_n^{(k)}=\frac{k+1}{n+k+1}(\genfrac{}{}{0ex}{}{2n+k}{n})$$

13. Expected Value theorem :
    
    $$E(X)=\sum _{i=1}^n{x}_i{p}_i$$
    
    $$p_1+p_2+p_3+...+p_n=1$$