IMO 1974 · Problem 3

Prove that the number \(\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\) is not divisible by \(5\) for any integer \(n\geq 0\).

Official text of the problem. Official problem paper (PDF)

Solution

Fix an integer \(n\geq 0\), and write \[ S=\sum_{k=0}^{n}\binom{2n+1}{2k+1}8^k, \qquad T=\sum_{k=0}^{n}\binom{2n+1}{2k}8^k. \] Both \(S\) and \(T\) are integers. By the binomial theorem, separating the even and odd powers of \(\sqrt8\), we obtain \[ (1+\sqrt8)^{2n+1}=T+\sqrt8\,S, \qquad (1-\sqrt8)^{2n+1}=T-\sqrt8\,S. \] Multiplying these identities gives \[ T^2-8S^2=(1-8)^{2n+1} =(-7)^{2n+1}=-7\cdot49^n. \]

Suppose that \(5\mid S\). Reducing the last identity modulo \(5\), we get \[ T^2\equiv -7\cdot49^n \equiv 3(-1)^n\pmod5. \] Thus \(T^2\) is congruent to \(3\) when \(n\) is even and to \(2\) when \(n\) is odd. But the only possible square residues modulo \(5\) are \(0,1,4\), as follows by squaring \(0,1,2,3,4\).

This contradiction proves that \(5\nmid S\) for every integer \(n\geq0\). \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).