문제는 여기: https://arca.live/b/math/40494856
----------------------------------------------------------------------------------------------
가로로 N+2칸으로 구성된 표를 생각하자. 처음에는 가운데N칸은 모두 흰색이였고, 양끝의 한 칸 만 검정으로 색칠되어있었다.
흰색 칸중에서 균등랜덤하게 한 칸을 고른 후 인접한 두칸 중 한 곳을 균등랜덤하게 선택하여 검정색이 아닌경우 검정색으로 칠하는 시행을 생각하자.
이런 시행을 계속해서 반복하여 모든 흰색칸의 인접지역이 모두 검정으로 칠해질 때까지 반복한다고 하자.
w(N)은 이때 남아있는 흰색칸의 수에 대한 기댓값이다. 다음 식의 값을 구하여라.
<출처 : Putnam 2020>
----------------------------------------------------------------------------------------------
w(n)의 점화식은 divide-and-conquer 로 구할 수 있다.
처음에 선택한 칸이 첫 번째 칸이면
1/2 의 확률로 흰 칸 전체가 그대로 남고
1/2 의 확률로 1칸과 n-2 칸으로 나누어진다.
처음에 선택한 칸이 2번째 칸이면
1/2 의 확률로 n-1 칸이 남고
1/2 의 확률로 2칸과 n-3 칸으로 나누어진다.
처음에 선택한 칸이 k (3 ≦ k ≦ n-2) 번째 칸이면
1/2 의 확률로 k-2 칸과 n-k+1 칸으로 나누어지고
1/2 의 확률로 k 칸과 n-k-1 칸으로 나누어진다.
따라서
2n w(n) =
(w(n) + (w(1) + w(n-2)) +
(w(n-1) + (w(2) + w(n-3)) +
((w(1) + w(n-2)) + (w(3) + w(n-4)) +
((w(2) + w(n-3)) + (w(4) + w(n-5)) +
...
((w(n-4) + w(3)) + (w(n-2) + w(1)) +
((w(n-3) + w(2)) + w(n-1)) +
((w(n-2) + w(1)) + w(n))
= 2 w(n) + 2w(n-1) + 4( w(n-2) + w(n-3) + ... + w(2) + w(1))
즉
n w(n) = w(n) + w(n-1) + 2 w(n-2) + 2 w(n-3) + ... + 2 w(1)
(n-1) w(n-1) = w(n-1) + w(n-2) + 2 w(n-3) + ... + 2 w(1)
n w(n) - (n-1) w(n-1) = w(n) + w(n-2)
∴ w(n) = w(n-1) + w(n-2) / (n-1)
문제에서 요구하는 것은 w(n) 이 아닌 w(n)/n 의 극한값이므로
f(n) = w(n) / (n+1) 로 식을 변형해보면
(n+1) f(n) = n f(n-1) + f(n-2)
참고로 이를 통해서 f(n)은 f(n-1)과 f(n-2) 사이에 있음을 알 수 있다. 더 나아가 f(n+1), f(n+2), ... 도 모두 f(n-1) 과 f(n-2) 사이에 있다.
f 값을 계산해보면
f(1) = w(1)/2 = 1/2 = 0.5
f(2) = w(2)/3 = 1/3 = 0.333...
f(3) = (3 f(2) + f(1)) / 4 = (1 + 1/2) / 4 = 3/8 = 0.375
f(4) = (4 f(3) + f(2)) / 5 = (3/2 + 1/3) / 5 = 11/30 = 0.3666...
f(5) = (5 f(4) + f(3)) / 6 = (11/6 + 3/8) / 6 = 53/144 = 0.36805...
로 n→∞ 일 때 f(n) 값의 범위를 대략 구할 수 있다.
그러면 이제 f(n)의 일반항을 구해보도록 하자.
그런데 여기서 자백하자면, 구하는 법은 모른다. 하지만 때려맞춰서 구하기는 했다. 
일단 f(n) = a(n) / b(n) 으로 표기하도록 하자.
a(1) = 1, a(2) = 1, a(3) = 3, a(4) = 11, a(5) = 53
b(1) = 2, b(2) = 3, b(3) = 8, b(4) = 30, b(5) = 144
이제 b 값을 잘 관찰해보면 
b(n) = n! + (n-1)! 이 되는 것을 볼 수 있다.
그러면 일단 b(n) = n! + (n-1)! 로 놓고 a(n) 의 점화식을 구해보도록 하자.
f(n) = (n f(n-1) + f(n-2)) / (n+1) 에서
정리하면
이 점화식으로 a(n) 의 일반항을 구하면 좋겠지만, 다시 말하지만 구하는 법은 모른다. 
하지만 a(n) 의 일반항을 때려맞추고 나면, 그 a(n) 값이 맞다는 것은 증명할 수 있다.
참고로, b(n) 도 동일한 점화식을 만족한다.
그럼 b(n) 과 비슷한 형태가 나올 것을 예상하고, 이제 다시 a(n) 값들을 잘 관찰해보자.
a(3) = (3! + 2!) / (1/2!) - 1
a(4) = (4! + 3!) / (1/2! - 1/3!) + 1
a(5) = (5! + 4!) / (1/2! - 1/3! + 1/4!) - 1
고로 다음과 같은 식을 예상할 수 있다.
증명은 점화식 + 수학적 귀납법으로 자명하게 할 수 있다.
a(n) 과 b(n)을 구했으므로 이제 f(n) 을 구할 수 있다.
이제 e^x 의 테일러 급수에서
n→∞ 일 때 f(n) = e^(-1) 임을 알 수 있다.
n→∞ w(n)/n = n→∞ f(n) 이므로 n→∞ w(n)/n = e^(-1)
