Russian 2000

Find [1/3] + [2/3] + [2²/3] + [2³/3] + ... + [2¹⁰⁰⁰/3].

Answer

(2/3)(2¹⁰⁰⁰-1)-500

Solution

Let f(n) = [2ⁿ/3]. Note that f(0) = f(1) = 0. We have 2ⁿ = (3-1)ⁿ = (-1)ⁿ mod 3, so if n is even, then 2ⁿ/3 = f(n) + 1/3 and hence 2ⁿ⁺¹/3 = 2f(n) + 2/3. So f(n+1) = 2f(n). Similarly, if n is odd, f(n+1) = 2f(n) + 1. Thus f(2n) = 2f(2n-1)+1 = 4f(2n-2)+1. Put u_n = f(2n) + 1/3, then u_n = 4u_n-1. But u₁ = 4/3, so u_n = 4ⁿ/3.

Hence u₁ + u₂ + ... + u_n = (4/3)(1 + ... + 4^n-1) = (4/9)(4ⁿ-1). So f(2) + f(4) + ... + f(2n) = (4/9)(4ⁿ-1) - n/3. We have f(2n+1) = f(2n), so f(3) + f(5) + ... + f(2n-1) = (8/9)(4^n-1-1) - (2/3)(n-1). Hence f(2) + f(3) + ... + f(2n) = (2/3)(4ⁿ-1) - n.

Thanks to Suat Namli

Russian 2000

© John Scholes
jscholes@kalva.demon.co.uk
7 February 2004
Last corrected/updated 7 Feb 04