MathLabs

第3题

证明对任意整数 n≥0n\ge0,∑k=0n(2n+12k+1)23k\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k} 都不被 55 整除。
第 1/5 步：模 55 重写该和
上一步下一步
2nS=∑j=0n(2n+12j)2j(mod5)2^nS=\sum_{j=0}^{n}\binom{2n+1}{2j}2^j\pmod5
详细分析

令 j=n−kj=n-k 反转二项式下标。乘以 2n2^n 后幂次变为 2n23(n−j)=24n−3j≡2j(mod5)2^n2^{3(n-j)}=2^{4n-3j}\equiv2^j\pmod5，所以模 55 下 2nS=∑j=0n(2n+12j)2j2^nS=\sum_{j=0}^{n}\binom{2n+1}{2j}2^j。因为 2n2^n 模 55 非零，只需证明这个新和非零。