MathLabs

Problem 3

Prove that ∑k=0n(2n+12k+1)23k\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k} is not divisible by 55 for any integer n≥0n\ge0.
Step 1 of 5: Rewrite the sum modulo 55
Previous stepNext step
2nS=∑j=0n(2n+12j)2j(mod5)2^nS=\sum_{j=0}^{n}\binom{2n+1}{2j}2^j\pmod5
Detailed analysis

Reverse the binomial index by setting j=n−kj=n-k. After multiplying by 2n2^n, the power becomes 2n23(n−j)=24n−3j≡2j(mod5)2^n2^{3(n-j)}=2^{4n-3j}\equiv2^j\pmod5, so 2nS=∑j=0n(2n+12j)2j2^nS=\sum_{j=0}^{n}\binom{2n+1}{2j}2^j modulo 55. Because 2n2^n is nonzero modulo 55, it is enough to prove this new sum is nonzero.