| For All Solvers
OMC212

OMC212(C) - 二項定理に似た式から考える方法

ユーザー解説 by Tempurabc

　公式解説より易しいとは思いませんが，次のような立式をした場合はどうなるのか，に対する回答です． 2024C1+2023C2⋅2+2022C3⋅22+⋯+1013C1012⋅21011 {}_{2024}\mathrm{C}_{1}+{}_{2023}\mathrm{C}_{2}\cdot 2+{}_{2022}\mathrm{C}_{3}\cdot 2^2+\cdots +{}_{1013}\mathrm{C}_{1012}\cdot 2^{1011}

（立式に至るまでのプロセス）
　公式解説と同様に，一番左上のマスを黒色で塗った場合を考える．ある列を 22 行とも黒で塗った場合，その隣接する列を 22 行とも黒で塗ることはできない．よって，20242024 列のうち 22 行とも黒である列を，左から x1,x2,⋯ ,xnx_1, x_2, \cdots , x_n 列目とすると，その数列が満たすべき条件は， 1≤x1<x2<⋯<xn≤2024,xn+1−xn≥21 \leq x_1 \lt x_2 \lt \cdots \lt x_n \leq 2024, x_{n+1}-x_n \geq 2 であり，その値は 2025−nCn{}_{2025-n}\mathrm{C}_{n} となる（なお，nn は 11 以上 10121012 以下を動く変数である）．
　さらに，問題文の条件を満たすためには，11 列目から x1x_1 列目までは上の行をずっと黒で塗り，x1x_1 列目から x2x_2 列目までは上下いずれかの行をずっと黒で塗り，⋯\cdots，xnx_n 列目から 20242024 列目までは下の行をずっと黒で塗ればよい．このような塗り方は 2n−12^{n-1} 通りである．
　以上の議論から，最初に記した式を得る．

（最初の式を解く） 　Sn=nC0+n−1C1⋅2+n−2C2⋅22+⋯+n−⌊n2⌋C⌊n2⌋⋅2⌊n2⌋S_n={}_{n}\mathrm{C}_{0}+{}_{n-1}\mathrm{C}_{1}\cdot 2+{}_{n-2}\mathrm{C}_{2}\cdot 2^2+\cdots +{}_{n-\lfloor \frac{n}{2} \rfloor}\mathrm{C}_{\lfloor \frac{n}{2} \rfloor}\cdot 2^{\lfloor \frac{n}{2} \rfloor} とおく．いま求めたい値は，2×S2025−122×\dfrac{S_{2025}-1}{2} である．
　数列 {Sn}\lbrace S_n \rbrace について漸化式を作りたい．床関数が厄介なので，n<kn \lt k の範囲で nCk=0{}_{n}\mathrm{C}_{k}=0 であると定義する．このように定義すれば，Sn=∑k=0nn−kCk 2kS_n=\sum\limits_{k=0}^{n} {}_{n-k}\mathrm{C}_{k}\ 2^k であり，また重要なこととして nCk+nCk+1=n+1Ck+1{}_{n}\mathrm{C}_{k}+{}_{n}\mathrm{C}_{k+1}={}_{n+1}\mathrm{C}_{k+1} が満たされる． 　Sn+1=∑k=0n+1n+1−kCk 2k=1+∑k=1n+1n+1−kCk 2k=1+2∑k=0nn−kCk+1 2kS_{n+1}=\sum\limits_{k=0}^{n+1} {}_{n+1-k}\mathrm{C}_{k}\ 2^k=1+\sum\limits_{k=1}^{n+1} {}_{n+1-k}\mathrm{C}_{k}\ 2^k=1+2 \sum\limits_{k=0}^{n} {}_{n-k}\mathrm{C}_{k+1}\ 2^k と変形すると， Sn+1+2Sn=1+2∑k=0nn−kCk+1 2k+2∑k=0nn−kCk 2k=1+2∑k=0nn+1−kCk+1 2k=1+∑k=0nn+1−kCk+1 2k+1=1+∑k=1n+1n+2−kCk 2k=Sn+2\begin{aligned} S_{n+1}+2 S_n &=1+2 \sum\limits_{k=0}^{n} {}_{n-k}\mathrm{C}_{k+1}\ 2^k +2 \sum\limits_{k=0}^{n} {}_{n-k}\mathrm{C}_{k}\ 2^k \\ &= 1+ 2 \sum\limits_{k=0}^{n} {}_{n+1-k}\mathrm{C}_{k+1}\ 2^k\\ &= 1+ \sum\limits_{k=0}^{n} {}_{n+1-k}\mathrm{C}_{k+1}\ 2^{k+1}\\ &= 1+ \sum\limits_{k=1}^{n+1} {}_{n+2-k}\mathrm{C}_{k}\ 2^{k}\\ &= S_{n+2} \end{aligned} を得る．あとは，S1=1S_1=1，S2=3S_2=3 より漸化式を解いて Sn=2n+1+(−1)n3S_n=\dfrac{2^{n+1}+(-1)^n}{3} となる．

（余談）
　ほぼ同様の発想で， 　Sn=nC0+n−1C1+n−2C2+⋯+n−⌊n2⌋C⌊n2⌋S_n={}_{n}\mathrm{C}_{0}+{}_{n-1}\mathrm{C}_{1}+{}_{n-2}\mathrm{C}_{2}+\cdots +{}_{n-\lfloor \frac{n}{2} \rfloor}\mathrm{C}_{\lfloor \frac{n}{2} \rfloor} とおくとき，SnS_n はフィボナッチ数列になることが示されます．
　証明したことがない人は是非やってみてください．