Maths Olympiad Prep

Library / /60 of 136

Algebra Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

Let f(n)=(n0)+(n3)+(n6)++(n3n3)2n3f(n) = \left| \binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \dots + \binom{n}{3\left\lfloor \frac{n}{3} \right\rfloor} \right| - \frac{2^n}{3}, where [x][x] is the greatest integer not exceeding xx. Find f(1)+f(2)++f(2021)f(1) + f(2) + \dots + f(2021).

Solution

The answer is 898.

Indeed, let ω=e2πi3\omega = e^{\frac{2\pi i}{3}} be a cube root of unity. By the binomial theorem, we have
(1+1)n=(n0)+(n1)++(nn), (1 + 1)^n = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n},
(1+ω)n=(n0)+(n1)ω++(nn)ωn, (1 + \omega)^n = \binom{n}{0} + \binom{n}{1}\omega + \dots + \binom{n}{n}\omega^n,
(1+ω2)n=(n0)+(n1)ω2++(nn)ω2n. (1 + \omega^2)^n = \binom{n}{0} + \binom{n}{1}\omega^2 + \dots + \binom{n}{n}\omega^{2n}.
It is known that 1+ωk+ω2k=01 + \omega^k + \omega^{2k} = 0 for any 3k3 \nmid k, and 1+ωk+ω2k=31 + \omega^k + \omega^{2k} = 3 for any 3k3 \mid k.

Thus, adding up the above 3 equations, we obtain
3((n0)+(n3)+(n6)++(n3n3))=(1+1)n+(1+ω)n+(1+ω2)n=2n+(ω2)n+(ω)n={2n+2if n0(mod6),2n+1if n1,5(mod6),2n1if n2,4(mod6),2n2if n3(mod6). \begin{aligned} & 3\left(\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \dots + \binom{n}{3\left\lfloor \frac{n}{3} \right\rfloor}\right) \\ &= (1+1)^n + (1+\omega)^n + (1+\omega^2)^n \\ &= 2^n + (-\omega^2)^n + (-\omega)^n \\ &= \begin{cases} 2^n + 2 & \text{if } n \equiv 0 \pmod{6}, \\ 2^n + 1 & \text{if } n \equiv 1,5 \pmod{6}, \\ 2^n - 1 & \text{if } n \equiv 2,4 \pmod{6}, \\ 2^n - 2 & \text{if } n \equiv 3 \pmod{6}. \end{cases} \end{aligned}
Therefore, we have f(n)=13f(n) = \frac{1}{3} if 3n3 \nmid n, and f(n)=23f(n) = \frac{2}{3} if 3n3 \mid n. As 20213=673\lfloor \frac{2021}{3} \rfloor = 673, we have
f(1)+f(2)++f(2021)=673(23)+(2021673)(13)=898. f(1) + f(2) + \dots + f(2021) = 673\left(\frac{2}{3}\right) + (2021 - 673)\left(\frac{1}{3}\right) = 898.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.