내가 알고 싶은건 이 부등식이 성립한다는 걸 어떻게 보이냐는 거였음.
저 부등식에 들어가는 \sum_{d |(m,n) , \omega(d)=j} 1 이 term이 kCj보다는 작거나 같다는 건 금방 알겠는데
alternating sum이라서 바로 부등식을 보이진 못했음.
어떻게 해야될까
저 부등식에 들어가는 \sum_{d |(m,n) , \omega(d)=j} 1 이 term이 kCj보다는 작거나 같다는 건 금방 알겠는데
alternating sum이라서 바로 부등식을 보이진 못했음.
어떻게 해야될까
그냥 수학적 귀납법 잘 써서 바로 보이는게 빠를거 같음. (m,n)을 소인수분해했을때 p_1^{e_1} p_2^{e_2} ... p_t^{e_t}를 얻는다고 가정하면, 결국 본문의 부등식의 좌변은 다항식 h_t(x) = (1 - e_1 x)(1 - e_2 x)...(1 - e_t x)의 x^{2J+1}에 붙은 coefficient가 되고, 부등식의 우변은 x^{2J}에 붙은 coefficient가 됨.
임의의 0 이상 t 이하인 정수 i에 대해서, h_i(x) = (1 - e_1 x)(1 - e_2 x)...(1 - e_i x)라 하면, [x^j]h_i(x)를 x^j의 coefficient라 하면 짝수인 j에 대해서는 [x^j]h_i(x)가 0 이상, 홀수인 j에 대해서는 [x^j]h_i(x)가 0 이하임을 i에 대한 수학적 귀납법을 써서 증명하면 충분함. i=0인 경우는 자명하고, i>0인 경우는 i-1일때 참이라고 가정하면, h_i(x) = h_{i-1}(x) (1 - e_i x)니까, [x^j]h_i(x) = [x^j]h_{i-1}(x) - e_i [x^{j-1}]h_{i-1}(x)를 얻으니까, 귀납가정에 의해서 j가 짝수면 0 이상, j가 홀수면 0 이하가 되어서 증명 완료.