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 a1i+a2i2+a3i3+⋯+anin, 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
Sn2Sn−14Sn−22n−2S22n−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=1kW(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∑nr=1∑k(r−1k−1)2n−kkir=i2n−1k=1∑nk2−(k−1)r=1∑k(r−1k−1)ir−1=i2n−1k=1∑nkzk−1
where z=21(1+i). Continue as above.
The problems on this page are the property of the MAA's American Mathematics Competitions