December 2024
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!
Split up your computation of \(f_{n+1}\) into adding up the 3-sign sums of those sublists of \(\{1,\ldots,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)\).
We have \(\alpha^2 + \alpha = -1\). Rearranging we get \[-\alpha = 1 + \alpha^2, \quad -\alpha^2 = 1 + \alpha, \quad \text{ and } \quad\alpha^2 + \alpha +1 = 0.\] Also, remember that \(\alpha^4 = \alpha(\alpha^3)\).
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?
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.
Combine your answers from 1(a), 2, and 4(b).