SA
메인 내용으로 이동

Binomial Theorem

(p+q)n=k=0n(nk)pkqnk(p + q)^n = \sum\limits_{k=0}^n {n \choose k} p^k q^{n-k}

j=1aj=a1a,a<1\sum\limits_{j=1}^{\infty} a^j = {a \over {1-a}}, |a| < 1

SN=j=1NajS_N = \sum\limits_{j=1}^N a^j

SN=a+a2++aNS_N = a + a^2 + \cdots + a^N — ①

aSN=a2+aN+1aS_N = a^2 + \cdots a^{N+1} — ②

If we subtract ② from ①, we get

SN=aan+11aS_N = {{a - a^{n+1}} \over {1-a}}

k=1kak=a(1a)2\sum\limits_{k=1}^{\infty} k a^k = {a \over (1-a)^2}

limn(1+xn)n=ex\lim\limits_{n \to \infty} ({1 + x \over n})^n = e^x

Number of OutcomesWith ReplacementWithout Replacements
2Binomial (different when until*\text{until}^\text{*}...)Hypergeometric
\geq 3MultinomialMultivariate Hypergeometric

until*\text{until}^\text{*}

  • 1st1^{\text{st}} success → geometric
  • rthr^{\text{th}} success → negative binomial

In Probability,

(p+q)n=k=0n(nk)pkqnk(p+q)^n = \sum\limits_{k=0}^n {n \choose k} p^k q^{n-k}

Proof

Base case

Let n=1n=1. Then

k=01(1k)pkqnk=(10)p0q1+(11)p1q0\sum\limits_{k=0}^1 {1 \choose k }p^k q^{n-k} = {1 \choose 0} p^0 q^1 + {1 \choose 1} p^1 q^0

Induction Hypothesis

Assume that (p+q)m=k=0m(1m)pkqmk(p+q)^m = \sum\limits_{k=0}^m {1 \choose m }p^k q^{m-k}. Let n=m+1n = m+1. Then

(p+q)m+1=(p+q)(p+q)m=(p+q)k=0m(1m)pkqmk(p+q)^{m+1} = (p+q) (p+q)^m = (p+q) \sum\limits_{k=0}^m {1 \choose m }p^k q^{m-k} pk=0m(mk)pkqmk+qk=0m(mk)pkqmkp \sum\limits_{k=0}^m {m \choose k}p^k q^{m-k} + q \sum\limits_{k=0}^m {m \choose k}p^k q^{m-k} k=0m(mk)pk+1qmk+k=0m(mk)pkqmk+1\sum\limits_{k=0}^m {m \choose k}p^{k+1} q^{m-k} + \sum\limits_{k=0}^m {m \choose k}p^k q^{m-k+1}

Let j=k+1j=k+1 and k=j1k=j-1 for the first and j=kj=k for the second sum. Then,

j=1j=m+1(mj1)pjqm+1j+j=0j=m(mj)pjqmj+1\sum\limits_{j=1}^{j=m+1} {m \choose {j-1}}p^{j} q^{m + 1 - j} + \sum\limits_{j=0}^{j=m} {m \choose j}p^j q^{m-j+1}