조합적 항등식 증명

궁극적으로 아래 문제를 해결해 보겠다.

임의의 자연수 $n, m$에 대해 $$\sum_{x=1}^{n}\prod_{y=0}^{m}(x+y)=\frac{1}{m+2}\prod_{x=0}^{m+1}(x+n)$$가 항상 성립함을 증명하여라.

두 가지 방법으로 증명해 보겠다.

---

수학적 귀납법

별로 좋아하는 방법은 아니지만 현실적으로 시험이나 타임어택이라면 가장 성공률이 높은 방법이다. 먼저 $n=1$인 경우 좌변은 $(m+1)!$이고, 우변이 $\displaystyle \frac{1}{m+2} \times (m+2)!=(m+1)!$여서 성립한다. $n=k$일때 성립한다 가정하고 $n=k+1$일 때 성립함을 증명하면 된다. $$\sum_{x=1}^{k+1}\prod_{y=0}^{m}(x+y)=\sum_{x=1}^{k}\prod_{y=0}^{m}(x+y)+\prod_{y=0}^{m}(k+y+1)=\frac{1}{m+2}\prod_{x=0}^{m+1}(x+k)+\prod_{x=0}^{m}(k+x+1)=$$ $$\frac{(k+m+1)!}{(m+2)\times(k-1)!}+\frac{(k+m+1)!}{k!}=\frac{(k+m+1)!\times k+(k+m+1)!\times (m+2)}{(m+2)\times k!}=$$ $$\frac{(k+m+2)!}{(m+2) \times k!} =\frac{1}{m+2} \prod_{x=0}^{m+1}(x+k+1)$$단순 식 정리라서 딱히 의미 있지는 않다.

---

이항계수 성질 이용(조합적)

이항계수를 사용하기 위해 일단 깔끔하게 팩토리얼로 정리해보자. 좌변은 $$\sum_{x=1}^{n}\prod_{y=0}^{m}(x+y)=\sum_{x=1}^{n}\frac{(m+x)!}{(x-1)!}$$로 정리되고, 우변은 $$\frac{1}{m+2}\prod_{x=0}^{m+1}(x+n)=\frac{(n+m+1)!}{(m+2) \times (n-1)!}$$로 정리된다. 양쪽을 $(m+1)!$로 나눠보자. 그러면 좌변은 $$\sum_{x=1}^{n}\frac{(m+x)!}{(x-1)!(m+1)!}=\sum_{x=1}^{n}\binom{x+m}{m+1}=\binom{n+m+1}{m+2}$$가 되고($\because \displaystyle \sum_{x=0}^{n}\binom{x+r}{r}=\binom{n+r+1}{r+1}$ 이항계수 부분합 공식) 우변은 $$\frac{(n+m+1)!}{(m+2)! \times (n-1)!}=\binom {n+m+1}{m+2}$$가 되어서 성립한다.

---

의미?

대충 보면 의민지 모르겠다. 사실 $n$보다 $m$이 중요한 변수이다. $m=0$이면 $$\sum_{x=1}^{n}x=\frac{n(n+1)}{2}$$ $m=1$이면 $$\sum_{x=1}^{n}x(x+1)=\frac{n(n+1)(n+2)}{3}$$ 즉, 따로 $$\sum_{x=1}^{n}x^{2}=\frac{n(n+1)(2n+1)}{6}$$ 같은 거 전혀 안 외워도 된다(사실 이거 외우는 게 더 편하다). 근데 $m=3$이상 이면 좌변 $x$의 최고차항이 4 이상여서 유용하다(근데 사실 전혀 쓸 일이 없다). 그냥 알아만 두는 게 나을 듯하다. 추가로 서울대인가 어디 기출이다.