Evaluate the sum \[ \sum_{k=0}^{[n/2]} (-4)^{n-k} \binom{n-k}{k} ,\] where [x] denotes the greatest integer less than or equal to x.
The best solution was submitted by Kang, Dongyub (강동엽), 전산학과 2009학번. Congratulations!
Here is his Solution of Problem 2011-24.
Alternative solutions were submitted by 장경석 (2011학번, +3), 서기원 (수리과학과 2009학번, +3), 김범수 (수리과학과 2010학번, +3), 박준하 (하나고등학교 2학년, +3).
GD Star Rating
loading...
loading...
풀이 중 Bijective proof 도 있었나요?
아니요
bijective solution을 하나 찾았었기에 여기에 소개하고자 합니다.
1×1과 1×2로 1xn 직사각형을 채우는 상황을 생각합니다. 이 때, 1×1에는 a,a’,b,b’ 중 하나를 써넣고 1×2에는 ab,ab’,a’b,a’b’ 중 하나를 써넣습니다. 그러면 1×2의 개수가 k개일 때에 이러한 조건을 만족시키는 경우의 수는 4^{n-k} binom{n-k}{k}가 됩니다.
한 편, 다음과 같은 map을 생각합니다. 왼쪽에서부터 오른쪽으로 scan하다가, 최초로 (i) 1×2가 나오거나 (ii) 1×1 두 개가 연속으로 나오되 앞의 것엔 a or a’가, 뒤의 것엔 b or b’가 써있는 경우를 찾으면, (i)의 경우 1×2를 1×1 두 개로 분할하고 그에 쓰인 word가 xy였다면 앞의 것에 x, 뒤의 것에 y를 써넣고, (ii)의 경우 두 1×1를 합쳐서 1×2로 만들고 두 1×1에 써있던 alphabet을 순서대로 붙인 word를 써넣습니다. 만약 (i)나 (ii)의 경우가 발생하지 않으면 그대로 둡니다.
이 map의 fixed point를 제외하면 이것은 convolution이 됨을 확인할 수 있습니다. 또한 그럴 때에 k(1×2의 개수)의 기우성이 항상 변화함을 확인할 수 있습니다. 이제 이 map의 fixed point가 어떤 것인지를 확인하면, 1×2가 없어야 하며 1×1에 a or a’가 쓰인 것 직후에 b or b’가 쓰인 것이 나타나선 안 됩니다. 즉 1×1이 n개 있으며, 맨 앞엔 b or b’만 있고 그 이후엔 a or a’만 나오는 경우가 되며 그 경우의 수는 (n+1)2^n이 됩니다. 또한 이 fixed points는 전부 k=0입니다.
따라서 k가 짝수인 것들과 홀수인 것들 사이엔, fixed points를 제외하면 bijection이 성립하며 이를 통해 sum_{2k leq n} (-1)^k 4^{n-k} binom{n-k}{k}=(n+1)2^n임을 얻습니다. 양변에 (-1)^n을 곱하면 원하는 결과를 얻습니다. 🙂
군복무 중에도 관심에 감사드려요.