Summer Problem Solving Marathon Solution #10

We start by considering the non-empty subsets of {1,2,...,9}. We can divide these into two groups:

(i) Those containing 9.
(ii) Those not containing 9.

Note that, if we set aside the set {9}, there is a perfect correlation between the two groups -- for each subset containing 9, there is a unique subset not containing 9, obtained by removing 9 from it.

Furthermore, compare the power sum of two correlated sets, such as {1,3,7} and {1,3,7,9}. The two power sums are:

(i) 7i³ + 3i² + i¹
(ii) 9i⁴ + 7i³ + 3i² + i¹

That is, the two power sums are the same, except that the power sum of the 9-containing set has one further term which is 9 times some power of i. This is because in the power sum the elements of the set are listed in decreasing order, and 9 is always the largest element in any set containing it.

As a result, S₉ splits into three parts:

(i) The power sums of the sets not containing 9.
(ii) Those same power sums again, appearing as parts of the power sums of the 9-containing sets (the 9-free parts).
(iii) The terms generated by the 9s, which all have the form of 9 times a power of i, where the power of i is equal to the size of the 9-containing set. (In this part we will include the power sum of the set {9}.)

Now, part (i) is just S₈. Part (ii) is S₈ again. We are given S₈, so these two parts can be quickly calculated to be twice -176 - 64i, or -352 - 128i. So all that remains is to calculate part (iii).

Any 9-containing set of size n will generate a term of the form 9iⁿ. How many 9-containing sets of size n are there? Well, to form such a set, we select n-1 elements from {1,2,...,8}. There are C(8,n-1) ways to do this (8 choose n-1). So we have:

(i) One term of the form 9i, for a total of 9i.
(ii) 8 terms of the form 9i², for a total of -72.
(iii) 28 terms of the form 9i³, for a total of -252i.
(iv) 56 terms of the form 9i⁴, for a total of 504.
(v) 70 terms of the form 9i⁵, for a total of 630i.
(vi) 56 terms of the form 9i⁶, for a total of -504.
(vii) 28 terms of the form 9i⁷, for a total of -252i.
(viii) 8 terms of the form 9i⁸, for a total of 72.
(ix) One term of the form 9i⁹, for a total of 9i.

Summing this up, we have 144i.

So S₉ = -352 - 128i + 144i = -352 + 16i.