数学的帰納法

連続する $n$ 個の整数の積は $n!$ の倍数である。

$(fg)^{(n)}={\displaystyle \sum_{k=0}^{n} {}_n\mathrm{C}_kf^{(k)}g^{(n-k)}}$

$$\begin{aligned} &|A_1\cup A_2\cup\cdots\cup A_n|\\ &=\sum_{i}|A_i|\\ &\quad -\sum_{i < j}|A_i\cap A_j|\\ &\quad +\sum_{i < j < k}|A_i\cap A_j\cap A_k|\\ &\quad -\cdots\\ &\quad +(-1)^{n-1}|A_1\cap\cdots\cap A_n| \end{aligned}$$

フィボナッチ数列(fibonacci sequence)とは，

• 最初の2つは $1$ で，
• 3つめ以降は「前の2つを足したもの」

になる数列のこと。つまり，

$1,1,2,3,5,8,13,21,34,\dots$

$f(x)$ が凸関数のとき，

• 任意の $x_1,\dots,x_n$ と
• $\lambda_i\geqq 0,\displaystyle\sum_{i=1}^n\lambda_i=1$ を満たす任意の $\lambda_1,\dots,\lambda_n$

に対して， $$\sum_{i=1}^{n} \lambda_{i} f(x_{i}) \geqq f \left( \sum_{i=1}^{n} \lambda_i x_i \right)$$ が成立する。

連結なグラフにおいて，

• 一筆書きして戻ってこれる $\iff$ 全ての頂点の次数が偶数
• （スタートとゴールが異なるような）一筆書きができる $\iff$ 次数が奇数であるものがちょうど2つ

任意の非負整数 $p,q,n$ に対して，

$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$

という恒等式が成立する。これをヴァンデルモンドの畳み込みと言う。 ただし，$p < k$ のとき ${}_p\mathrm{C}_k=0$ と定義する。