Problem 18 Combinatorics

Problem 18: Combinatorics

AoPS

      3n 3n 3n Problem: For positive integers n find an explicit formula for + + ··· + . 0 3 3n Solution: Consider f (x) = (1 + x)3n . This is obviously  3n  X 3n k f (x) = x . k k=0

If we plug in x = 1, ω, ω 2 , the cube roots of unity, we get

f (1) =

 3n  X 3n k=0

k

 3n  X 3n k f (ω) = ω k k=0

f (ω 2 ) =

 3n  X 3n 2k ω . k k=0

Sum these up. Notice that 1 + ω + ω 2 = 0 and ω 3 = 1 so 1k + ω k + ω 2k = 0 when k ≡ 1, 2 (mod 3). When k ≡ 0 (mod 3), we get 1k +ω k +ω 2k = 3. So take one-third of this expression to get the desired sum. 1 3 (f (1)

+ f (ω) + f (ω 2 )) = 13 (23n + (ω + 1)3n + (ω 2 + 1)3n ).

This can be further simplfied by noting that ω 2 + 1 = −ω and ω + 1 = −ω 2 , hence: S=

1 3


23n + (−1)3n (ω 6n + ω 3n ) =

1 3


1 23n + 2(−1)3n = (8n + 2(−1)n ) 3

Note: The technique used here is sometimes called roots of unity filtering. This same technique was used in Problem 17, so look at it if you are having trouble understanding the solution.

Solution was written by Jeffrey Wang and compiled from Art of Problem Solving Forums.