December 2024
We have \[\begin{aligned} f_3 &= \mu(\{1\}) + \mu(\{2\}) + \mu(\{3\}) + \mu(\{1,2\}) + \mu(\{1,3\}) + \mu(\{2,3\}) + \mu(\{1,2,3\}) \\ &= 1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 - 3) \\ &= 18. \end{aligned}\] For \(f_4\), we will organise ourselves a little differently to make computing \(f_5\) a little easier. Notice that if a sublist of \(\{1,2,3,4\}\) does not contain \(4\), then it is a sublist of \(\{1,2,3\}\). Therefore we have \[\begin{aligned} f_4&= f_3 + \mu(\{4\}) + \mu(\{1,4\}) + \mu(\{2,4\}) + \mu(\{3,4\}) \\ & \quad \quad \quad + \mu(\{1,2,4\}) + \mu(\{1,3,4\}) + \mu(\{2,3,4\}) + \mu(\{1,2,3,4\}) \\ &= 18 + 4 + (1 + 4) + (2 + 4) + (3 + 4) \\ &\quad \quad \quad + (1 + 2 - 4) + (1 + 3 - 4) + (2 + 3 - 4) + (1 + 2 -3 + 4) \\ &= 44.\end{aligned}\] When computing \(f_4\), notice that if we ignore all the \(4\)s that showed up in the sum, what is left over is again a copy of \(f_3\). With this in mind, for \(f_5\) we have \[\begin{aligned} f_5 &= f_4 + 5 + (1 + 5) + (2 + 5) + (3 + 5) + (4 + 5) \\ & \quad \quad \quad + (1 + 2 - 5) + (1 + 3 - 5) + (1 + 4 - 5) \\ & \quad \quad \quad + ( 2 + 3 - 5) + ( 2 + 4 - 5) + (3 + 4 - 5) \\ & \quad \quad \quad + (1 + 2 - 3 + 5) + (1 + 2 - 4 + 5) + (1 + 3 - 4 + 5) + (2 + 3 - 4 + 5) \\ & \quad \quad \quad + (1 + 2 - 3 + 4 + 5) \\ &= f_4 + f_4 + (5) + (5 + 5 + 5 + 5) - (5 + 5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5) + (5) \\ &= 44 + 44 + 5(1 + 4 - 6 + 4 + 1)\\ &= 108.\end{aligned}\] The \(5\)s in the third-last line are grouped by whether they come from computing \(\mu(L)\) for a list \(L\) of length \(1\), \(2\), \(3\), \(4\), or \(5\).
We have \(\binom{4}{0} = \binom{4}{4} = 1\), \(\binom{4}{1} =\binom{4}{3} = 4\), and \(\binom{4}{2} = 6\). Then \[2f_4 + 5\left(\binom{4}{0} + \binom{4}{1} - \binom{4}{2} + \binom{4}{3} + \binom{4}{4}\right) = 2(44) + 5(1 + 4 - 6 + 4 + 1) = 108\] which is the value we obtained for \(f_5\).
Our computation of \(f_5\) in Problem 1(a) above gives us some hints as to how to prove this result. Let’s pay close attention to this situation first before embarking on the general proof.
In the solution to 1(a) we arrived at the expression \[f_5 = 2f_4 + (5) + (5 + 5 + 5 + 5) - (5 + 5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5) + (5).\] The number of \(5\)s in the first set of parentheses is the number of sublists of \(\{1,2,3,4,5\}\) of length \(1\) that contain \(5\). There is only one such list, namely \(\{5\}\).
The number of \(5\)s in the second set of parentheses is the number of sublists of \(\{1,2,3,4,5\}\) of length \(2\) that contain \(5\). Every such list is of the form \(\{k,5\}\), where \(1 \leq a \leq 4\). There are \(4 = \binom{4}{1}\) ways to choose an element \(a\) from \(\{1,2,3,4\}\), so there are four sublists of length \(2\) that contain \(5\).
There are six \(5\)s in the third set of parentheses. This is the number of sublists of \(\{1,2,3,4,5\}\) of length \(3\) that contain \(5\). Every such sublist is of the form \(\{a,b,5\}\) where \(a < b\) and \(a\) and \(b\) belong to the set \(\{1,2,3,4\}\). The number of ways we can choose two distinct elements \(a\) and \(b\) from \(\{1,2,3,4\}\) is precisely the binomial coefficient \(\binom{4}{2} = 6\).
Similarly, there are four \(5\)s in the fourth set of parentheses because there are \(\binom{4}{3} = 4\) ways to select three elements \(a,b,c\) from \(\{1,2,3,4\}\) to create a sublist \(\{a,b,c,5\}\) of length \(4\).
Finally there is \(\binom{4}{4} = 1\) way to choose four elements from \(\{1,2,3,4\}\) to create a list of length \(5\) containing \(5\), which is the list \(\{1,2,3,4,5\}\).
Notice that the third set of parentheses is negated, and all the others are left as they are. Let’s look at this a little more closely. Here is what the 3-sign sum of lists containing a \(5\) look like, for lists of length \(1\), \(2\), \(3\), \(4\), and \(5\) respectively: \[\begin{aligned} \mu(\{5\}) &= 5\\ \mu(\{a,5\}) &= a + 5\\ \mu(\{a,b,5\}) &= a + b - 5 \\ \mu(\{a,b,c,5\}) &= a + b - c + 5 \\ \mu(\{a,b,c,d,5\}) &= a + b - c + d + 5.\end{aligned}\] The only time the \(5\) appears negated is when computing the 3-sign sum of a list of length \(3\).
Great! Let’s look at the general case now. We wish to relate \(f_{n+1}\) to \(f_n\). We can split up the computation of \(f_{n+1}\) into summing up the \(3\)-sign sums of sublists of \(\{1,\ldots,n+1\}\) that contain \(n+1\), and those that do not contain \(n+1\).
The sum of all the \(\mu(L)\) where \(n+1\) is not in \(L\) is simply summing up \(\mu(L)\) for \(L\) a sublist of \(\{1,\ldots,n\}\), which is precisely \(f_n\). Therefore we can write \[f_{n+1} = f_n + S\] where \(S\) is the sum of all \(3\)-sign sums of sublists that contain \(n+1\). Let’s look at an arbitrary term from the sum \(S\). For what follows, we must allow the empty list \(\emptyset\) to be a sublist of \(\{1,\ldots,n\}\) to be a sublist, and we define \(\mu(\emptyset) = 0\).
A sublist of length \(k\) that contains \(n+1\) is of the form \(\{a_1,a_2,\ldots,a_{k-1},n+1\}\) where \(\{a_1,a_2,\ldots,a_{k-1}\}\) is a sublist of \(\{1,\ldots,n\}\). So \[\mu(\{a_1,a_2,\ldots,a_{k-1},n+1\}) = \begin{cases} \mu(\{a_1,a_2,\ldots,a_{k-1}\}) - (n+1) &\text{if $k$ is a multiple of $3$,}\\ \mu(\{a_1,a_2,\ldots,a_{k-1}\}) + (n+1) &\text{if $k$ is not a multiple of $3$.} \end{cases}\] Observe that \(\mu(\{a_1,a_2,\ldots,a_{k-1}\})\) is the 3-sign sum of a sublist of \(\{1,\ldots,n\}\).
Every sublist of \(\{1,\ldots,n+1\}\) that contains \(n+1\) gives rise to a sublist of \(\{1,\ldots,n\}\) by removing \(n+1\) from the list. Furthermore, every sublist of \(\{1,\ldots,n\}\) gives rise to a sublist of \(\{1,\ldots,n+1\}\) containing \(n+1\) by simply appending \(n+1\) on to the end of the list. Therefore, when computing the sum of all \(3\)-sign sums of sublists of \(\{1,\ldots,n+1\}\) containing \(n+1\), we are left with the sum of all 3-sign sums of sublists of \(\{1,\ldots,n\}\) plus some number of \((n+1)\)s. More formally we have \[S = f_n + M(n+1)\] for some integer \(M\). To figure out the value of \(M\), we must pay attention to the length of each sublist. Sublists of \(\{1,\ldots,n+1\}\) containing \(n+1\) with length a multiple of three contribute \(-1\) to the value of \(M\), and sublists of \(\{1,\ldots,n+1\}\) containing \(n+1\) whose length is not a multiple of three contribute \(+1\). So, in order to figure out what \(M\) is, we must count the number of sublists containing \(n+1\) of each length.
The number of sublists of \(\{1,\ldots,n+1\}\) of length \(k\) containing \(n+1\) is equal to the number of sublists of \(\{1,\ldots,n\}\) of length \(k-1\). The number of sublists of \(\{1,\ldots,n\}\) of length \(k-1\) is the binomial coefficient \(\binom{n}{k-1}\). To write down an expression for \(M\), we must first introduce the integer \(b_t\). Let \(t\) be an integer and define \[b_t = \begin{cases} 1 &\text{if $t+1$ is not a multiple of $3$} \\ -1 &\text{if $t+1$ is a multiple of $3$}. \end{cases}\] Let \(C_k\) be the number of sublists of \(\{1,\ldots,n+1\}\) of length \(k\) that contain \(n+1\). Then \[M = b_0C_1+b_1C_2 + \cdots + b_nC_{n+1}.\] But from our discussion above we have \(C_k = \binom{n}{k-1}\). Therefore, \[M = b_0\binom{n}{0} + b_1\binom{n}{1} + \cdots + b_n\binom{n}{n}.\] Putting all of this together we have \[\begin{aligned} f_{n+1} &= f_n + f_n + M(n+1) \\ &= 2f_n + (n+1)\left(b_0\binom{n}{0} + b_1\binom{n}{1} + \cdots + b_n\binom{n}{n}\right)\end{aligned}\] completing the proof.
We have \[\begin{aligned} \alpha^3 &= (\alpha^2)\alpha \\ &= (-1-\alpha)\alpha \\ &= -\alpha - \alpha^2 \\ &= 1.\end{aligned}\]
Using the fact that \(\alpha^3 = 1\) we have \[\begin{aligned} \alpha^8 + \alpha^4 + \alpha^9 &= (\alpha^3)(\alpha^3)(\alpha^2) + (\alpha^3)(\alpha) + (\alpha^3)^3 \\ &= \alpha^2 + \alpha + 1 \\ &= -1 + 1\\ &= 0. \end{aligned}\]
We have \[\begin{aligned} (1 + \alpha) - (1 + \alpha)^2 &= (1 + \alpha) - (-\alpha^2)^2 \\ &= (1+\alpha ) - (\alpha^4) \\ &= 1+\alpha - \alpha & \text{since $\alpha^3 = 1$} \\ &= 1.\end{aligned}\]
Using the binomial theorem we have \[\begin{aligned} g_n(1) &= \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} \\ g_n(\alpha) &= \binom{n}{0} + \binom{n}{1}\alpha + \binom{n}{2}\alpha^2 + \cdots + \binom{n}{n}\alpha^n \\ g_n(\alpha^2) &= \binom{n}{0} + \binom{n}{1}\alpha^2 + \binom{n}{2}\alpha^4 + \cdots + \binom{n}{n}\alpha^{2n}.\end{aligned}\] Since \(\alpha^3 = 1\) we can rewrite the second and third expressions as \[\begin{aligned} g_n(\alpha) &= \binom{n}{0} + \binom{n}{1}\alpha + \binom{n}{2}\alpha^2 + \binom{n}{3} + \binom{n}{4}\alpha + \binom{n}{5}\alpha^2 + \binom{n}{6} + \cdots \\ g_n(\alpha^2) &= \binom{n}{0} + \binom{n}{1}\alpha^2 + \binom{n}{2}\alpha + \binom{n}{3} + \binom{n}{4}\alpha^2 + \binom{n}{5}\alpha + \binom{n}{6} + \cdots .\end{aligned}\] It is tempting to just take the sum of these two expressions. This would give every third term a coefficient of \(2\), and every other term a coefficient of \(\alpha^2 + \alpha = -1\). A promising development! After all, we want a sum of binomial coefficients where every third term is different from the other two. However, if we simply sum \(g_n(\alpha)\) and \(g_n(\alpha^2)\), the (approximately) one-third of terms that are different from the rest are in the wrong spot! To remedy this, let’s shift where the \(\alpha\) and \(\alpha^2\) appear by multiplying each equation by an appropriate power of \(\alpha\). We have \[\begin{aligned} \alpha g_n(\alpha) &= \binom{n}{0}\alpha + \binom{n}{1}\alpha^2 + \binom{n}{2} + \binom{n}{3}\alpha + \binom{n}{4}\alpha^2 + \binom{n}{5}+ \binom{n}{6}\alpha + \cdots \\ \alpha^2g_n(\alpha^2) &= \binom{n}{0}\alpha^2 + \binom{n}{1}\alpha + \binom{n}{2} + \binom{n}{3}\alpha^2 + \binom{n}{4}\alpha + \binom{n}{5} + \binom{n}{6}\alpha^2 + \cdots .\end{aligned}\] Much better! Taking the sum we get \[\begin{aligned} \alpha g_n(\alpha) + \alpha^2 g_n(\alpha^2) &= \binom{n}{0}(\alpha + \alpha^2) +\binom{n}{1} (\alpha^2 + \alpha) + 2\binom{n}{2} \\ & \quad \quad \quad + \binom{n}{3}(\alpha + \alpha^2) + \binom{n}{4}(\alpha^2 + \alpha) + 2\binom{n}{5} + \cdots \\ &= -\binom{n}{0} - \binom{n}{1} +2 \binom{n}{2} - \binom{n}{3} - \binom{n}{4} + 2\binom{n}{5} + \cdots.\end{aligned}\] Adding \(g_n(1)\) to this gives \[g_n(1) + \alpha g_n(\alpha) + \alpha^2g_n(\alpha^2) = 3\binom{n}{2} + 3\binom{n}{5} + 3\binom{n}{8} + \cdots.\] We can now start with \(g_n(1)\) and subtract an appropriate multiple of \(g_n(1) + \alpha g_n(\alpha) + \alpha^2g_n(\alpha^2)\) to get what we want. \[\begin{aligned} &g_n(1) - \frac{2}{3}\left(g_n(1) + \alpha g_n(\alpha) + \alpha^2g_n(\alpha^2)\right) \\ &\quad = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} \\ & \quad \quad \quad \quad - 2\left(\binom{n}{2} + \binom{n}{5} + \binom{n}{8} + \cdots \right) \\ & \quad = \binom{n}{0} + \binom{n}{1} - \binom{n}{2} + \binom{n}{3} + \binom{n}{4} - \binom{n}{5} + \binom{n}{6} + \cdots \\ & \quad = b_0\binom{n}{0} + b_1\binom{n}{1} + \cdots + b_n\binom{n}{n}.\end{aligned}\] We can now finally conclude that \[\begin{aligned} A &= \frac{1}{3} \\ B &= -\frac{2}{3} \alpha \\ C &= -\frac{2}{3} \alpha^2.\end{aligned}\]
We have \[\begin{aligned} d_n &= \frac{1}{3}g_n(1) - \frac{2}{3}\alpha g_n(\alpha) - \frac{2}{3}\alpha^2 g_n(\alpha^2) \\ &= \frac{1}{3}(2^n) - \frac{2}{3}\alpha(1 + \alpha)^n - \frac{2}{3} \alpha^2(1 + \alpha^2)^n & \text{since $g_n(x) = (1+x)^n$}\\ &= \frac{1}{3}(2^n) - \frac{2}{3} \alpha (-\alpha^2)^n - \frac{2}{3}\alpha^2(-\alpha)^n \\ &= \frac{1}{3}\left(2^n + 2\alpha^{2n+1}(-1)^{n+1} + 2\alpha^{2 + n}(-1)^{n+1}\right) \\ &= \frac{2}{3}\left(2^{n-1} + (-1)^{n+1}(\alpha^{2n+1} + \alpha^{2+n})\right).\end{aligned}\] Let \(r_n = (-1)^{n+1}(\alpha^{2n+1} + \alpha^{2+n})\). The behaviour of \((-1)^{n+1}\) depends on the remainder of \(n\) when divided by \(2\). The behaviour of powers of \(\alpha\) depends on the remainder of the power when divided by \(3\). With this in mind, let’s analyse the behaviour of \(r_n\) for different remainders of \(n\) when divided by \(2 \times 3 = 6\).
When \(n = 6k\) for some integer \(k\) we have \[\begin{aligned} r_{6k} &= (-1)^{6k+1}(\alpha^{12k + 1} + \alpha^{6k + 2}) \\ &= -(\alpha + \alpha^2) \\ &= 1.\end{aligned}\] When \(n = 6k+1\) we have \[\begin{aligned} r_{6k+1} &= (-1)^{6k+2}(\alpha^{12k + 3} + \alpha^{6k + 3}) \\ &= 2.\end{aligned}\] For \(n = 6k+2\), \[\begin{aligned} r_{6k+2} &= (-1)^{6k+3}(\alpha^{12k+5} + \alpha^{6k+4}) \\ &= - (\alpha^2 + \alpha) \\ &= 1.\end{aligned}\] The remaining cases are given by \[\begin{aligned} r_{6k+3} &= (-1)^{6k+4}(\alpha^{12k+7} + \alpha^{6k+5}) = \alpha + \alpha^2 = -1 \\ r_{6k+4} &= (-1)^{6k+5}(\alpha^{12k+9} + \alpha^{6k+6}) = -(1 + 1) = -2 \\ r_{6k+5} &= (-1)^{6k+6}(\alpha^{12k+11} + \alpha^{6k+7}) = \alpha^2 + \alpha = -1.\end{aligned}\] So, \(d_n = \frac{2}{3}(2^{n-1} + r_n)\), where \(r_n\) is given by the following table:
| \(n\) | \(r_n\) |
|---|---|
| \(6k\) | \(1\) |
| \(6k+1\) | \(2\) |
| \(6k+2\) | \(1\) |
| \(6k+3\) | \(-1\) |
| \(6k+4\) | \(-2\) |
| \(6k+5\) | \(-1\) |
Putting all the parts together we have the recursive formula \[f_{n+1} = 2f_n + \frac{2(n+1)}{3}(2^{n-1} + r_n)\] where \(r_n\) is given by the table above. From \(1\)(a) we know \(f_5 = 108\). Applying the recursive formula repeatedly gives \[\begin{aligned} f_6 = 2f_5 + \frac{2(6)}{3}(2^4 + r_5) = 2(108) + \frac{2(6)}{3}(2^4 + (-1)) &= 276. \\ f_7 = 2f_6 + \frac{2(7)}{3}(2^5 + r_6) = 2(276) + \frac{2(7)}{3}(2^5 + 1) &= 706. \\ f_8 = 2f_7 + \frac{2(8)}{3}(2^6 + r_7) = 2(706) + \frac{2(8)}{3}(2^6 + 2) &= 1\, 764. \\ f_9 = 2f_8 + \frac{2(9)}{3}(2^7 + r_8) = 2(1\, 764) + \frac{2(9)}{3}(2^7 + 1) &= 4\, 302. \\ f_{10} = 2f_9 + \frac{2(10)}{3}(2^8 + r_9) = 2(4\, 302) + \frac{2(10)}{3}(2^8 + (-1)) &= 10\, 304. \\ f_{11} = 2f_{10} + \frac{2(11)}{3}(2^9 + r_{10}) = 2(10\, 304) + \frac{2(11)}{3}(2^9 + (-2)) &= 24\, 348. \\ f_{12} = 2f_{11} + \frac{2(12)}{3}(2^{10} + r_{11}) = 2(24\, 348) + \frac{2(12)}{3}(2^{10} + (-1)) &= 56\, 880. \end{aligned}\] If you were to compute \(f_{12}\) directly from the definition, you would have had to compute the \(3\)-sign sum of \(4\,096\) lists. What we have done in this Problem of the Month is much less work, especially if you wanted to compute something larger like \(f_{30}\). If you were to compute \(f_{30}\) directly from the definition, you would need to compute over \(1\) billion 3-sign sums! That’s a lot of sums.