Problem:
If {a1​,a2​,a3​,…,an​} is a set of real numbers, indexed so that a1​<a2​<a3​<…<an​, its complex power sum is defined to be a1​i+a2​i2+a3​i3+⋯+an​in, where i2=−1. Let Sn​ be the sum of the complex power sums of all nonempty subsets of {1,2,…,n}. Given that S8​=−176−64i and S9​=p+qi, where p and q are integers, find ∣p∣+∣q∣.
Solution:
It suffices to express Sn+1​ in terms of Sn​ and n. The subsets of {1,2,3,…,n+1} that do not contain n+1 are just the subsets of {1,2,3,…,n}, and thus the sum of their complex power sums is just Sn​. The subsets of {1,2,3,…,n+1} that do contain n+1 are the subsets of {1,2,3,…,n} with n+1 adjoined as the greatest element. Notice that n+1 will be the only member in one of these subsets, the second member in n of these subsets, and in general will be the kth member in (k−1n​) of these subsets. The sum of the complex power sums of all subsets of {1,2,3,…,n+1} that contain n+1 is therefore
Sn​​+(0n​)(n+1)i+(1n​)(n+1)i2+(2n​)(n+1)i3+⋯+(nn​)(n+1)in+1=Sn​+i(n+1)k=0∑n​(kn​)ik​
which by the Binomial Theorem is equal to Sn​+i(n+1)(1+i)n. The desired recursion is therefore Sn+1​=2Sn​+i(n+1)(1+i)n. Thus
S9​=2S8​+9i(1+i)8=−352−128i+9i⋅16=−352+16i
so ∣p∣+∣q∣=368​.
Note: To solve the recursion, sum the equations
Sn​2Sn−1​4Sn−2​2n−2S2​2n−1S1​​=2Sn−1​+in(1+i)n−1=4Sn−2​+2i(n−1)(1+i)n−2=8Sn−3​+4i(n−2)(1+i)n−3⋮=2n−1S1​+2n−2i2(i+1), and =2n−1i​
to obtain
Sn​​=i(2n−1+2n−22(i+1)+⋯+n(1+i)n−1)=i2n−1(1+2z+3z2+⋯+nzn−1)​
where z=21​(1+i). Multiply both sides by 1−z to obtain
(1−z)Sn​=i2n−1(1+z+z2+⋯+zn−1−nzn)=i2n−1[1−z1−zn​−nzn]​
Then multiply both sides by (1−z)−1=1+i to obtain
Sn​=i2n−1[2i(1−(21+i​)n)−n(1+i)(21+i​)n]
which simplifies to Sn​=(n+1+i)(1+i)n−1−2n.
Here is a combinatorial approach to evaluating Sn​: Observe that, for 1≤k≤n and 1≤r≤k, the term kir occurs in the sum of complex power sums for each choice of 1≤a1​<a2​⋯≤n in which ar​=k. Thus Sn​=∑k=1n​∑r=1k​W(k,r)kir, where W(k,r) is the number of subsets {a1​,a2​,…} of {1,2,…,n} in which the rth smallest element is k. Notice that W(k,r)=(r−1k−1​)2n−k, because there are (r−1k−1​) ways to choose 1≤a1​<a2​<⋯<ar−1​≤k−1 and then 2n−k ways to choose {ar+1​,ar+2​,…}⊆{k+1,…,n}. Hence, by the Binomial Theorem,
Sn​​=k=1∑n​r=1∑k​(r−1k−1​)2n−kkir=i2n−1k=1∑n​k2−(k−1)r=1∑k​(r−1k−1​)ir−1=i2n−1k=1∑n​kzk−1​
where z=21​(1+i). Continue as above.
The problems on this page are the property of the MAA's American Mathematics Competitions