Posts Tagged ‘ 차분법 ’

Finite Difference Method

미분 가능한 함수에서 미분이란 함수값의 변화량을 수치화한 것이다. 그렇다면 연속도 아닌 이산적인 함수에서 (즉, 정의역이 구간이 아니라 띄엄띄엄 떨어진 수들의 집합인 경우) 미분에 해당하는 것은 무엇일까? 논의는 여기에서 시작한다.

f\mathbb{Z}에서 정의되는 경우를 보자. 이 때 답은 단순하다. f(x+1)-f(x)f의 변화량을 나타낸다. 이제 Df(x)f(x+1)-f(x)로 정의하자. 즉 Df(x)라는 함수를 f(x+1)-f(x)로 바꾸는 함수의 변환이라 볼 수 있겠다. (마치 미분이 f(x)f'(x)로 바꾸듯)

그러면 D^nf(x)=\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f(x+i)가 성립한다. 증명이야 뭐.. 수학적 귀납법말곤 딱히.. 아무튼 이를 finite difference라 하고, 한국어로 어떻게 번역해야할지 고민한 끝에 차분법으로 명하기로 했다. (미분과 대조되는 개념으로, 차로 나눈다는 뜻의 差分) 그래서 차분법이란 이름으로 내가 쓴 책 “올림피아드 조합론”에도 실어버렸는데, 놀랍게도 일본어에서 똑같은 한자의 단어로 번역하고 있었다!

이제 특수한 경우, 즉 f가 다항수인 경우를 보자. 만약 f의 차수가 d이고 최고차항이 c_dx^d라 하자. 그러면 Df=c_d((x+1)^d-x^d)+\cdots인데 여기서 x^d는 전부 없어지고 x^{d-1}은 맨 첫 항에서만 나타나며 그 항은 dc_d x^{d-1}으로 계수가 0이 아니다. 따라서 차수는 정확히 1 줄어든다. 곧 D^nf(x)의 차수는 d-n이 된다. 곧 n=d이면 상수함수가 되고, n>d이면 0이 된다. 이를 다시 정리하면 다음과 같다.

n>d이면 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} f(k)=0이 성립한다.

실제론 f(k)가 아니라 f(x+k)인데, x만큼 옮기면 어차피 같은 함수니까 x=0인 경우만 state해줘도 상관이 없다.

사실 위의 정리는 다른 풀이가 많다. 다음은 그들을 간략히 설명한 것들.

First Solution. 앞의 풀이대로, D를 적용하면 차수가 하나씩 줄어들어서 성립.

Second Solution. 라그랑주 보간법. n=d+1일 때만 하면 그 이후는 자명한데, 그 때는 d+1개의 함수값이 주어지면 f를 결정할 수 있으므로 x=0,1,\cdots,d일 때를 대입한 결과들로 f를 구한 후 그에 x=d+1를 대입하면 얻을 수 있다. 방법만 알면 그 이후는 그저 계산일 뿐..

Third Solution. \binom{x}{i}i차 다항식으로, \binom{x}{0},\cdots,\binom{x}{n}n차 이하의 다항식들의 vector space over \mathbb{C}의 한 basis가 된다. 위 식에서 D^n(af+bg)=aD^nf+bD^ng이므로 \binom{x}{i}들에 대해서만 보이면 된다. 이는 \binom{n}{k}\binom{k}{i}=\binom{n}{i}\binom{n-i}{k-i}란 유명한 등식을 이용하면 증명이 된다.

Fourth Solution. 서인석 형님의 증명이다. 위와 같은 이유로 x^i에 대해서만 성립함을 보이면 되는데, \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}k^ii개의 원소를 가진 집합에서 n개의 원소를 가진 집합으로 대응되는 전사함수의 개수와 같음을 포함과 배제의 원리로 보일 수 있다. 그러나 i \leq d <n이므로 그런 함수는 없으므로 이 값은 0이 된다.

저 정리를 이용하면 많은 문제들을 쉽게 증명하는 것이 가능하다. 먼저 조합등식들 중에 일부 문제들은 위의 내용을 응용하면 한 방에 증명이 된다. 그 예로 다음 문제를 본다.

p_1+p_2+\cdots+p_r<n을 만족하는 자연수 p_1,p_2,\cdots,p_r,n에 대하여 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{p_1+k}{k}\cdots \binom{p_r+k}{k}=0임을 보여라.

2003년 KMO 여름학교의 연습문제 중의 하나로 나온 문제. (출처가 더 있을 법한데 잘 모르겠다.) 책에는 모의고사라고 썼는데 오타..라기보다 헷갈렸다. 여튼, f(x)=\binom{p_1+x}{p_1} \cdots \binom{p_r+x}{p_r}로 잡으면 이 다항식의 차수가 p_1+\cdots+p_r<n이 되어 바로 대입하면 증명이 끝난다. 와우

이 문제의 별해도 있어 생성함수를 이용하여 증명할 수도 있고, 조합적인 해석을 할 수도 있다. 그러나 지금 너무 졸려져서 왠지 귀찮고.. 궁금하신 분들은 책을 참조하시길… (후에 귀차니즘에서 회복하면 다시 쓸 수도)

남은 문제들의 일부를 옮겨 적으면 다음과 같다.

1. (4th Mathlinks Contest) m \geq n일 때 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}\binom{m-k}{n}의 값을 구하여라.

2. (2008 Putnam) n \geq 3인 정수가 있다. 실계수 다항식 f,g가 있어 좌표평면에서 (f(1),g(1)),(f(2),g(2)),\cdots,(f(n),g(n))이 정n각형의 점들을 반시계방향으로 나열한 것이 되게 한다. 이 때 f,g중 적어도 하나는 차수가 n-1 이상임을 보여라.

3. (1983 IMO Short-list) F_1=F_2=1인 피보나치 수열 F_n이 있다. k=992,993,\cdots,1982일 때 P(k)=F_k를 만족하는 차수 990인 다항식 P에 대해 P(1983)=F_{1983}-1임을 보여라.