수학 퀴즈 해답 - 수학 채널 (arca.live) 애 있는 문제입니다.

2k-1은 n 이하의 홀수 중 가장 큰 수이다.  다음 식

이 가리키는 수 p는 항상 2^(n-1)으로 나누어떨어질 수 있음을 증명하여라.

수학적 귀납법으로 증명할 수 있습니다. 그런데 출제하신 분의 의도에는 상당히 어긋나는 것일 가능성이 높아보이기는 합니다.

(1 + sqrt(5))^n = Sigma(i even) nCi sqrt(5)^i + Sigma(i odd) nCi sqrt(5)^i

(1 - sqrt(5))^n = Sigma(i even) nCi sqrt(5)^i - Sigma(i odd) nCi sqrt(5)^i

에서

(1 + sqrt(5))^n - (1 - sqrt(5))^n  = 2 Sigma(i odd) nCi sqrt(5)^i = 2 sqrt(5) p 를 얻을 수 있습니다.

따라서

f(n) = ( (1 + sqrt(5))^n - (1 - sqrt(5))^n ) / sqrt(5) 

로 놓으면, f(n) 이 항상 2^n 으로 나누어떨어진다는 것을 보이면 됩니다.

sqrt(5) 를 일일이 쓰는 건 번거롭기도 하고 가독성이 떨어지므로 X 라고 표기하겠습니다. X^2 = 5

f(n) = ( (1 + X)^n - (1 - X)^n ) / X

f(n) ( (1 + X) + (1 - X) ) = ( (1 + X)^n - (1 - X)^n ) ((1 + X) + (1 - X) ) / X 

2 f(n) = ( (1 + X)^(n+1) - (1 - X)^(n+1) + (1 + X)(1 - X)( (1 + X)^(n+1) - (1 - X)^(n+1) ) ) / X

        = ( (1 + X)^(n+1) - (1 - X)^(n+1) + (1^2 - X^2)( (1 + X)^(n-1) - (1 - X)^(n-1) ) ) / X

        = ( (1 + X)^(n+1) - (1 - X)^(n+1) ) / X - 4 ( (1 + X)^(n-1) - (1 - X)^(n-1) ) / X

        = f(n+1) - 4 f(n-1)

f(n+1) = 2 f(n) + 4 f(n-1)

이 점화식을 이용하면 수학적 귀납법으로 증명할 수 있습니다. (자명하므로 생략합니다.)

f(n)의 점화식을 보면 아시겠지만, 결국 피보나치 수열과 똑같습니다. 단지 p 가 피보나치 수열에서 나왔다는 사전지식 없이도 증명이 가능하다는 것이지요. 다른 방식이 있는지는 더 생각해봐야 할 것 같습니다.