Posts Tagged ‘ 수학적 귀납법 ’

한 조합등식과 그 별해들

jackal_anu님의 블로그에서 퍼온 문제와 그 원형이 되는 문제 (sos440님의 블로그에서 퍼옴).

먼저 sos440님 블로그에 올라온 문제는 다음과 같다.

n이 음 아닌 정수이면 \displaystyle \sum_{k=0}^n \binom{n+k}{n}\frac{1}{2^{n+k}}=1이 성립한다.

이 문제도 여러 가지의 풀이를 발견하였다. 사실 예전에 봤던 문제인데 어디에서 봤는지는 기억이 잘 안 난다.

First Solution. 문제를 조금 바꾸어 \displaystyle \sum_{k=0}^n \frac{1}{2^k}\binom{n+k}{n}=2^n임을 증명하자. 이것의 생성함수는 \displaystyle \sum_{n=0}^{\infty}\sum_{k=0}^n\binom{n+k}{n}2^{-k}x^n=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\binom{n+k}{n}2^{-k}x^n, 즉 \displaystyle \sum_{k=0}^{\infty}2^{-k} \left(\binom{2k}{k}x^k+\binom{2k+1}{k}x^{k+1}+\cdots \right)가 된다.

여기서 잠시 다른 길로 빠진다. 다음 Lemma를 보자.
Lemma. \displaystyle P_c(x)=\sum_{n=0}^{\infty}\binom{2n+c}{n}x^n이라 하자. 그러면 \displaystyle P_c(x)=\frac{1}{\sqrt{1-4x}} \left( \frac{1-\sqrt{1-4x}}{2x} \right)^n가 성립한다.
Proof of Lemma. P_c(x)=xP_{c+1}(x)+P_{c-1}(x)임을 쉽게 얻을 수 있다. (주세걸의 항등식 혹은 반데르몬드의 항등식) P_0(x)=\frac{1}{\sqrt{1-4x}}임과 P_1(x)=\sum \binom{2n+1}{n}x^n = \sum \frac{1}{2} \binom{2n+2}{n+1}x^n = \frac{P_0-1}{2x}임에서 점화식을 풀면 원하는 결과를 얻는다. QED

따라서 다시 원래 식으로 돌아가면 그 식은 \displaystyle \sum_{k=0}^{\infty} \left( \binom{2k}{k}( \frac{x}{2})^k + \binom{2k+1}{k} (\frac{x}{2})^k x + \cdots \right)
\displaystyle =\frac{1}{\sqrt{1-2x}} \left( 1+(1-\sqrt{1-2x})+(1-\sqrt{1-2x})^2+\cdots \right)
\displaystyle =\frac{1}{\sqrt{1-2x}} \frac{1}{1-(1-\sqrt{1-2x})}
\displaystyle =\frac{1}{\sqrt{1-2x}} \frac{1}{\sqrt{1-2x}} = \frac{1}{1-2x}가 된다. 따라서 그 x^n의 계수는 2^n이 되므로 증명이 끝난다.

다음은 조합적인 풀이. 아쉽게도 내가 발견한 것은 아니고, 이 문제가 올라왔을 때 같이 있었던 풀이이다. 누구 것인지마저 가물..

Second Solution. 문제를 바꾸어 \displaystyle \sum_{k=0}^n \binom{n+k}{n}2^{n+1-k}=2^{2n+1}임을 증명한다. O와 X를 적당히 택해 길이 2n+1인 것들을 본다. 전체 개수는 2^{2n+1}이다. 이제 O와 X가 홀수개이므로 어느 하나는 반드시 다른 하나보다 개수가 커야 한다. 이제 O가 X보다 많은 경우를 보자. 이 경우 O의 개수는 n+1개 이상이어야 한다. 이 때 n+1번째 O의 위치를 선택한 후 개수를 세어보자. 그 O는 n+1,n+2,\cdots,2n+1번째 위치에 올 수 있다. 이것이 오는 위치를 n+1+k번째 위치라 하자. 그러면 그 앞에는 O가 n개, X가 k개 있어야 하므로 그 개수는 \binom{n+k}{n}이다. 그리고 n+1번째 O의 오른쪽에는 O,X가 아무렇게나 배열될 수 있으므로 그 개수는 2^{n-k}이다. 따라서 이러한 가지수는 \displaystyle \sum_{k=0}^n \binom{n+k}{n}2^{n-k}이다. X가 O보다 많은 경우도 마찬가지로 같은 값이므로, 이 식에 2를 곱한 값인 좌변은 2^{2n+1}이 되어 증명이 끝난다.

다음은 아마 수학 올림피아드를 공부하는 학생들 중 대다수가 발견할 법한 수학적 귀납법 풀이.

Third Solution n=0인 경우는… 자명하다. n인 경우 성립을 가정하고 n+1인 경우를 본다. 그러면 \displaystyle \binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{2^{2n+2}} = \binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+1}{n}\frac{1}{2^{2n+1}}=\binom{2n+1}{n+1}\frac{1}{2^{2n}}이므로 n+1일 때의 식에서 n일 때의 식을 빼주면
\displaystyle \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{2^{2n+2}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n}{n}\frac{1}{2^{2n}}
\displaystyle =\binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n+1}{n+1}\frac{1}{2^{2n}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n}{n}\frac{1}{2^{2n}}
\displaystyle =\binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n}{n+1}\frac{1}{2^{2n}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n-1}{n}\frac{1}{2^{2n-1}}
\displaystyle = \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n-1}{n+1}\frac{1}{2^{2n-1}}+\binom{2n}{n+1}\frac{1}{2^{2n-1}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n-1}{n}\frac{1}{2^{2n-1}}
이 된다. 여기서 잘 보면, 두 번째 식의 2n2n-1로 바꾼 식이 네 번째 식이다. 즉 위의 과정은 항을 두 개씩 줄이는 과정이 되고 이를 계속 하면 그 결과는 \displaystyle \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\binom{n+2}{n+1}\frac{1}{2^{n+1}}-\binom{n}{n}\frac{1}{2^n}-\binom{n+1}{n}\frac{1}{2^{n+1}}이 되고 이것이 0임은… 또 자명하다. 끝.

위의 증명에서 중간에 얻은 사실을 (수학적 귀납법의 step) 정리하면 다음과 같이 쓸 수 있다.
Lemma. \displaystyle \sum_{k=n+1}^m \binom{k}{n+1}\frac{1}{2^k}+\binom{m+1}{n+1}\frac{1}{2^m} = \sum_{k=n}^{m} \binom{k}{n}\frac{1}{2^k}

이제 다음 풀이를 보자. 이번엔 생성함수를 다른 방법으로 응용하였다. 후에 보게 되겠지만, 이 방법은 일반화에서도 유효하다.

Fourth Solution. \displaystyle \sum_{k=0}^n 2^{n-k}\binom{n+k}{n}=2^{2n}임을 보이자. 좌변은 \displaystyle \frac{1}{1-2x} \frac{1}{(1-x)^{n+1}}x^n의 계수가 됨을 알 수 있다. 그런데 \displaystyle \frac{1}{1-2x} \frac{1}{(1-x)^{n+1}}을 partial fractions로 나타내면 그 결과는 \displaystyle \frac{2^{n+1}}{1-2x}-\frac{2^n}{1-x}-\frac{2^{n-1}}{(1-x)^2}-\cdots-\frac{2^0}{(1-x)^{n+1}}이다. 따라서 이 식의 x^n의 계수는 \displaystyle 2^{n+1}2^n - 2^n \binom{n}{n}-2^{n-1}\binom{n+1}{n}-\cdots-2^0\binom{2n}{n}이 되는데, 잘 보면, \displaystyle 2^n \binom{n}{n}+2^{n-1}\binom{n+1}{n}+\cdots+2^0\binom{2n}{n}이 바로 우리가 구하는 값이다. (!) 따라서 이 값을 S라 하면 S=2^{2n+1}-S가 되어 S=2^{2n}이 되어 증명이 끝난다.

이제 이것의 일반화인 jackal_anu 님의 조합등식을 보자.

p,q가 음 아닌 정수이면 \displaystyle \sum_{k=0}^q \frac{1}{2^{p+k}}\binom{p+k}{k}+\sum_{k=0}^p \frac{1}{2^{q+k}}\binom{q+k}{k}=2가 성립한다.

p=q를 대입하면 처음에 소개한 조합등식을 얻을 수 있다.

First Solution. 위 문제의 Third Solution에서 쓴 방법을 그대로 이용한다. p는 그대로 놔두고 q에 대한 수학적 귀납법을 쓴다. q=0이면 \displaystyle \frac{1}{2^p}\binom{p}{0}+\binom{0}{0}+\frac{1}{2}\binom{1}{1}+\cdots+\frac{1}{2^p}\binom{p}{p}=2를 얻는다. 이제 q일 때 성립함을 가정하고 q+1일 때의 식에서 q일 때의 식을 빼면 그 값은
\displaystyle \frac{1}{2^{p+q+1}}\binom{p+q+1}{q+1} + \sum_{k=q+1}^{p+q+1}\frac{1}{2^k}\binom{k}{k-q-1} - \sum_{k=q}^{p+q} \frac{1}{2^k} \binom{k}{k-q}인데 이 식 정리하면 위의 Lemma에서 n=q,m=p+q를 대입한 것이 되어 0이다. 끝. (원래 문제의 Third Solution의 analogue)

Second Solution. 문제를 바꿔 \displaystyle 2^{p+q+1}=\sum_{k=0}^q 2^{q-k}\binom{p+k}{p} + \sum_{k=0}^p 2^{p-k}\binom{q+k}{q}임을 보이자. 앞 문제의 Fourth Solution과 비슷하게 생각하면, 앞의 summation은 \displaystyle [x^q]\frac{1}{1-2x}\frac{1}{(1-x)^{p+1}}이고 뒤의 summation은 \displaystyle [x^p]\frac{1}{1-2x}\frac{1}{(1-x)^{q+1}}이다. 앞에서 구한 결과를 이용하면 앞의 summation은 \displaystyle [x^q]( \frac{2^{p+1}}{1-2x}-\frac{2^p}{1-x}-\cdots-\frac{2^0}{(1-x)^{p+1}}이므로 \displaystyle 2^{p+q+1}-2^p\binom{q}{q}-2^{p-1}\binom{q+1}{q}-\cdots-2^0\binom{q+p}{q}가 된다. 마찬가지로 두 번째 summation의 값은 \displaystyle 2^{q+p+1}-2^q\binom{p}{p}-2^{q-1}\binom{p+1}{p}-\cdots-2^0\binom{p+q}{p}이다. 그런데 이번에도, 두 summation의 결과의 첫항을 제외한 것들은 원래 값과 같다! 그래서 그 합을 S라 하면 S=2^{p+q+2}-S가 되어 원하는 결과를 얻는다. (원래 문제의 Fourth Solution의 analogue)

Third Solution. 역시 \displaystyle 2^{p+q+1}=\sum_{k=0}^q 2^{q-k}\binom{p+k}{p} + \sum_{k=0}^p 2^{p-k}\binom{q+k}{q}를 보이자. 이번엔 앞의 문제의 Second Solution을 응용하자. O과 X를 p+q+1개를 늘어놓는다. 그러면 O가 p+1개 이상 나오거나 X가 q+1개 나오거나 둘 중 하나이며, 두 event가 동시에 일어날 수 없다. 앞의 경우 p+1번째 O가 나오는 곳이 p+k+1이라 하면 그 가지수는 \binom{p+k}{p}2^{q-k}가 된다. 이들을 모든 k에 대해 더하면 첫 번째 summation. 마찬가지로, 두 번째 event의 경우의 수가 두 번째 summation이 되어 증명이 끝난다.

여기서 부가적으로 \displaystyle \sum_{k=0}^q 2^{q-k}\binom{p+k}{p} = \sum_{k=0}^q \binom{p+q+1}{k}가 됨을 확인할 수 있다. 이는 앞의 문제의 refinement가 되겠다.

A Weak Generalization. \displaystyle \sum_{k=0}^q 2^{q-k}\binom{p+k}{p} = \sum_{k=0}^q \binom{p+q+1}{k}

jackal_anu 님의 마지막 일반화를 보자. 다음 등식 역시 sos440님의 등식이다.

p,q가 음 아닌 정수이면 \displaystyle (1-x)^{p+1}\sum_{k=0}^q\binom{p+k}{p}x^k+x^{q+1}\sum_{k=0}^p\binom{q+k}{q}(1-x)^k=1이 성립한다.

x=\frac{1}{2}를 대입하면 위의 문제가 됨을 확인할 수 있다.

First Solution. jackal_anu 님의 풀이. 이 풀이는 앞의 문제의 Third Solution과 관련이 깊다. 간략히 설명하자면, O,X를 p+q+1개 쓰되 O가 나올 확률을 1-x, X가 나올 확률을 x로 두고 O가 p+1개 이상 나오는 확률과 X가 q+1개 이상 나오는 확률의 합이 1임을 이용한다.

Second Solution. sos440님의 풀이. 또 간략히 설명하자면
\displaystyle \sum_{k=1}^{q} \binom{p+1+k}{k} x^k=\sum_{k=1}^{q} \sum_{j=0}^{k} \binom{p+j}{j} x^k
\displaystyle =\sum_{j=0}^{q} \sum_{k=j}^{q} \binom{p+j}{j} x^k=\sum_{j=0}^{q} \binom{p+j}{j} \frac{x^j - x^{q+1}}{1-x}
\displaystyle =\sum_{k=0}^{q} \binom{p+k}{k} \frac{x^k-x^{q+1}}{1-x}=\frac{1}{1-x} \left( \sum_{k=0}^{q} \binom{p+k}{k} x^k - \binom{p+q+1}{q} x^{q+1} \right)
임을 이용한다.

It’s my turn!

Third Solution. 설마 수학적 귀납법이 또 통할줄이야… 원래 문제의 Third Solution, 두 번째 문제의 First Solution의 뜻을 계승한다. 대략적인 설명만 하자면 q에 대한 수학적 귀납법으로 q=0인 경우는 또 자명하고 q+1일 때의 식에서 q일 때의 식을 빼면 그 결과가 정리하면 \displaystyle \sum_{k=0}^{p-1}\binom{q+1+k}{q+1}x(1-x)^{k}+\binom{q+p+1}{q+1}(1-x)^p - \sum_{k=0}^{p}\binom{q+k}{q}(1-x)^k가 되는데, 이번에도 맨 끝에서 장난을 쳐서 두 항을 없애는 식으로 계속 해나가면 0이 되어 원하는 결과를 얻는다.

Fourth Solution. 설마 생성함수 방법도 또 통할줄이야…… 원래 문제의 Fourth Solution, 두 번째 문제의 Second Solution과 뜻을 같이한다. 식을 변형하여 \displaystyle (1-x)\sum_{k=0}^q\binom{p+k}{p}\frac{1}{x^{q-k}}+x\sum_{k=0}^p\binom{q+k}{q}\frac{1}{(1-x)^{p-k}}=\frac{1}{x^q(1-x)^p}임을 보인다. 첫 번째 summation을 보자. 이것은 앞에서와 마찬가지로 생각하면 \displaystyle [z^q](1-x)\frac{1}{1-\frac{z}{x}}\frac{1}{(1-z)^{p+1}}인데, \displaystyle (1-x)\frac{1}{1-\frac{z}{x}}\frac{1}{(1-z)^{p+1}}을 partial fractions로 표현하면 그 결과 \displaystyle \frac{1}{(1-x)^p}\frac{1}{1-\frac{z}{x}}-\frac{x}{(1-x)^p}\frac{1}{1-z}-\cdots-\frac{x}{(1-x)^0}\frac{1}{(1-z)^{p+1}}이 된다. 이것의 z^q의 계수는 \frac{1}{(1-x)^p}\frac{1}{x^q}-\frac{x}{(1-x)^p}\binom{q}{q}-\cdots-\frac{x}{(1-x)^0}\binom{q+p}{q}가 되는데, 여기서 첫 항을 제외한 뒤의 항들의 합은 원래 식에서의 두 번째 summation이 되어 바로 증명이 끝난다. (합해서 2 \frac{1}{(1-x)^p}\frac{1}{x^q}-S=S이므로 어쩌구 이런 식의 논의로 해도 상관은 없다.)

Fifth Solution. 먼저 위 문제의 Third Solution에서 refine하듯 여기서도 First Solution에 의거하여 refine할 수 있다. 그 식이란 \displaystyle (1-x)^{p+1}\sum_{k=0}^q \binom{p+k}{k}x^k= \sum_{k=0}^q \binom{p+q+1}{k}x^k(1-x)^{q-k}이다. 여기서 1-x=y라 하고 x+y=1임을 이용하여 homogenization하면 다음과 같은 이쁜 식을 얻는다.
A Bit Stronger Generalization. \displaystyle \sum_{k=0}^q\binom{p+k}{k}x^k(x+y)^{q-k}=\sum_{k=0}^q\binom{p+q+1}{k}x^ky^{q-k}
이 일반화는 앞에서의 A Weak Generalization의 일반화도 된다. x=y=1을 대입하면..
이제 이 일반화를 증명하자. 0 \leq n \leq q에 대해 x^ny^{q-n}의 계수를 비교하면, \displaystyle \binom{p}{0}\binom{q}{n}+\binom{p+1}{1}\binom{q-1}{n-1}+\cdots+\binom{p+n}{n}\binom{q-n}{0}=\binom{p+q+1}{n}임을 보이면 된다. (거의 다른 문제로 바뀌었다!) 이 식의 좌변은 \displaystyle \left( \binom{p}{0}+\binom{p+1}{1}x+\cdots \right) \left( \binom{q-n}{0}+\binom{q-n+1}{1}x+\cdots \right), 즉 \displaystyle \frac{1}{(1-x)^{p+q-n+2}}x^n의 계수이다. 따라서 그 값은 \displaystyle \binom{(p+q-n+1)+n}{p+q-n+1}=\binom{p+q+1}{n}이 되어 증명이 끝난다.

Sixth Solution. 이 풀이로 별해 개수를 늘리는게 큰 의미가 있을까도 싶다만.. 앞의 A Bit Stronger Generalization을 다른 방법으로 증명한다. 먼저 위 식에 q 대신 q+n을 대입해 대칭꼴인 \displaystyle \sum_{k=0}^n \binom{p+k}{p}\binom{q+n-k}{q}=\binom{p+q+n+1}{n}으로 바꾼다. 이제 1,2,\cdots,p+q+n+1에서 p+q+1개의 수를 택하는 경우를 보자. 그 경우의 수는 물론 \binom{p+q+n+1}{p+q+1}, 즉 우변이다. 한 편 크기순으로 p+1번째 수가 무엇인지를 주목하자. 그것은 p+1,p+2,\cdots,p+n+1가 후보인데 p+1+k라 하면 그보다 작은 수들에선 p개를 뽑아야 해 경우의 수가 \binom{p+k}{p}가 되고 그보다 큰 수들에선 q개를 뽑아야 해 경우의 수가 \binom{q+k}{q}가 된다. 따라서 이들을 곱해 전부 합하면 그 값은 좌변이 되어 문제가 증명된다.

Any other solutions?

Advertisements