Problem of the Month
Hint for Problem 3: Three-sign sums

1. Ignoring the empty sublist, there are fifteen sublists of $\{1,2,3,4\}$. However, seven of those are sublists of $\{1,2,3\}$. So, when computing $f_4$, you have already done almost half the work when you computed $f_3$! For the remaining half of the work, notice that $\mu (\{a,b,c\})=\mu (\{a,b\})-c$ and $\mu (\{a,b,c,d\})=\mu (\{a,b,c\})+d$.

   See if you can then use your work for $f_4$ to reduce the work required for you to compute $f_5$. Alternatively, ignoring the empty sublist, there are thirty-one sublists of $\{1,2,3,4,5\}$, you can just roll up your sleeves and compute the 3-sign sums of all of them!

2. Split up your computation of $f_{n+1}$ into adding up the 3-sign sums of those sublists of $\{1,\dots ,n+1\}$ that contain $n+1$, and those that do not contain $n+1$. When adding up the 3-sign sums of those sublists that contain $n+1$, notice that $\mu (\{a,b,n+1\})=\mu (\{a,b\})-(n+1)$ and $\mu (\{a,b,c,n+1\})=\mu (\{a,b,c\})+(n+1)$.

3. We have ${\alpha }^2+\alpha =-1$. Rearranging we get $$-\alpha =1+{\alpha }^2,-{\alpha }^2=1+\alpha ,\text{ and }{\alpha }^2+\alpha +1=0.$$ Also, remember that ${\alpha }^4=\alpha ({\alpha }^3)$.

4. 1. Use the binomial theorem to expand $g_n(1)$, $g_n(\alpha )$ and $g_n({\alpha }^2)$, keeping in mind your answer from 3(a). What happens if you multiply $g_n(\alpha )$ and $g_n({\alpha }^2)$ by powers of $\alpha$?

      Compute $g_n(1)+g_n(\alpha )+g_n({\alpha }^2)$. This isn’t quite what you want, but can you adjust the terms somehow to get what you want?

   2. You should find that $d_n$ involves powers of $(-1)$ in terms of $n$, and powers of $\alpha$ in terms of $n$. Powers of $(-1)$ depend on what the remainder of the power is when divided by $2$. How do powers of $\alpha$ behave? You may have to split your computation of $d_n$ up into $6$ cases.

5. Combine your answers from 1(a), 2, and 4(b).