二項係数の公式

eq1:

$ \sum_{k=0}^n \binom{n}{k} = 2^n

proof

$ (1 + 1) ^ n = \sum_{k=0}^n \binom{n}{k}

$ (1 + 1) ^ n = 2^n

eq2:

$ \sum_{k=0}^n (-1)^k \binom{n}{k} = 0

proof

$ (-1 + 1) ^ n = \sum_{k=0}^n (-1)^k 1^{n-k} \binom{n}{k} = \sum_{k=0}^n (-1)^k \binom{n}{k}

$ (-1 + 1) ^ n = 0^n = 0

eq3:

$ \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} = 2^{n-1}

proof

from eq1, eq2

$ (1 + 1) ^ n + (-1 + 1) ^ n = 2^n

kが奇数の時には打ち消し合うため

$ \sum_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k}

eq5:

$ \sum_{i=0}^k \sum_{j=0}^l \binom{i+j}{i} = \binom{k+l+2}{k+1}-1

パスカルの三角形的解釈

https://gyazo.com/161c01a67680a23524d71745a7cb5c38

$ \sum_{i=0}^k \binom{n}{i}\binom{m}{k - i} = \binom{n+m}{k}

special case(k=n, m=n)

$ \sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}

$ \sum_i \binom{i}{A}\binom{N-i-1}{B} = \binom{N}{A+B+1}

ボール的解釈

https://gyazo.com/9aabb603ccaadea2194910347eb52fa4

eq6-3

$ \sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} = \binom{A + B + K + 1}{K}

eq7:

$ \sum_{i=0}^k \binom{n+1}{i}\binom{m-i}{k - i} = \binom{n+m+1}{k}

$ \sum_i \binom{N-i}{i} = F_N

https://gyazo.com/68fc51e0aad6ed0f251979427ce9fbfe

eq8:

$ r\binom{n}{r} = n\binom{n-1}{r-1}

ref