【数セミ】エレガントな解答をもとむ2【2016．11】 [無断転載禁止]©2ch.net

**１３２人目の素数さん** · 2016/10/17(月) 20:05:12.65

過去スレ：
【数セミ】エレガントな解答をもとむ【2011．2】
http://rio2016.2ch.net/test/read.cgi/math/1295154182/

**１３２人目の素数さん** · 2017/07/12(水) 13:04:32.32

>>467

問１：
上からn段目、端からk列目にかかる荷重の 2^(n-1)倍を W_(n,k) とおきます。
両端はすぐに解けて
　W_(n,1) = W_(n,n) = 2^(n-1) -1,
中間の漸化式は
　W_(n,k) = W_(n-1,k) + W_(n-1,k-1) + 2^(n-1)
右辺の最後の項を残しておくと、いつまでも同所徘徊→遭難の恐れが…
そこで、横方向の階差数列（差分）を取ります。
Pascal型になります。
本問の場合、２階階差まで考えれば
　2W_(n,k) - W_(n,k-1) - W_(n,k+1) = C_(n+1,k)
となって出口が見えます。
両端の条件（上記）を考えつつ和分すると、
　W_(n,k) = (2k-1){2^(n-1) -1} -(k-1)n -納L=2,k-1] C(n+1,L)
nが奇素数pの場合は
　2≦L≦k-1　⇒　p｜C_(p+1,L)
最後に、フェルマーの小定理 2^(p-1) -1 ≡0（mod p）でトドメです。

**１３２人目の素数さん** · 2017/07/12(水) 13:10:27.14

>>468 の訂正

　W_(n,k）=（2k-1){2^(n-1) -1｝-（k-1)n - Σ_[L=2,k-1］（k-L）C(n+1,L)
でした。