이항 계수의 상계와 하계

이항 계수의 상계 

$${n \choose k}\le 2^n$$

pf) ${n \choose k}=\frac{n!}{k!(n-k)!}$에서 일반성을 잃지 않고 $k \le  \frac{n}{2}$라 하자. ($k>\frac{n}{2}$인 경우에는 $n-k \le \frac{n}{2}$이므로 일반성을 잃지 않을 수 있다.) 이때,  $$\dfrac{n-k+1}{1} \le \dfrac{n-k+2}{2} \le \cdots \dfrac{n-1}{k-1} \le \dfrac{n}{k} \le 2$$이므로 $${n \choose k} = \dfrac{n-k+1}{1}\dfrac{n-k+2}{2}\cdots\dfrac{n-1}{k-1}\dfrac{n}{k} \le 2^n$$이게 된다.   $\blacksquare$

또한, $${n \choose k}=\dfrac{n(n-1)\cdots(n-k+1)}{k!}\le\dfrac{n^k}{k!}\le\dfrac{n^k}{2^{k-1}}$$와 같이도 상계를 구할 수 있다.

 

이항 계수의 하계 

$${n \choose \lfloor n/2 \rfloor} \ge \dfrac{2^n}{n}$$

pf) $n$개의 수들 ${n \choose 0}+{n \choose n}$, ${n \choose 1}$, ${n \choose 2}$, $\cdots$, ${n \choose n-1}$을 생각하자. 이들의 합은 이항 계수 항등식에 의하여 $2^n$이므로 평균은 $\frac{2^n}{n}$인데, 그 중 ${n \choose \lfloor n/2 \rfloor}$가 가장 큰 값이므로 위의 부등식이 성립한다.   $\blacksquare$

특히, $${2n \choose n} \ge \dfrac{4^n}{2n}$$이 성립한다.

 

Exponential 17 김지하