Problem of the Month
Problem 3: Three-sign sums

This month’s problem is an extension of Question B3 from the 2024 Canadian Intermediate Mathematics Contest, which was run by the CEMC in November 2024. The question that appeared on the contest can be found at the end of this problem. As a warm up, try the problem yourself and pay attention to the differences between the contest problem and this Problem of the Month.

Given an increasing list of integers \(L = \{a_1,a_2,\ldots,a_k\}\), the 3-sign sum of the list \(L\), denoted \(\mu(L)\), is the sum of the integers in the list, in order, except that every third integer is subtracted instead of added. For example, if \(L = \{3,4,5,8,10,11,13\}\), then \(\mu(L) = 3 + 4 - 5 + 8 + 10 - 11 + 13 = 22\).

Let \(n\) be a positive integer, and consider the list \(\{1,2,3,\ldots,n\}\). We define the integer \(f_n\) to be the sum of all 3-sign sums of all increasing sublists of \(\{1,2,3,\ldots,n\}\). For example, \[f_3 = \mu(\{1\}) + \mu(\{2\}) + \mu(\{3\}) + \mu(\{1,2\}) + \mu(\{1,3\}) + \mu(\{2,3\}) + \mu(\{1,2,3\}).\] The problems below use binomial coefficients and the binomial theorem. If you are unfamiliar with, or need a refresher for, these concepts, please see this Problem of the Month lesson.

1. 1. Compute \(f_3\), \(f_4\), and \(f_5\).

   2. Verify that \(f_5 = 2f_4 + 5\left(\binom{4}{0} + \binom{4}{1} - \binom{4}{2} + \binom{4}{3} + \binom{4}{4}\right)\).

2. For all integers \(n \geq 2\), prove that \(f_{n+1} = 2f_n + (n+1)\left(b_0 \binom{n}{0} + b_1\binom{n}{1} + b_2\binom{n}{2} + \cdots + b_n\binom{n}{n}\right)\) where \[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}\]

For the remainder of the problems, our goal is to work out how to compute the expression \[b_0 \binom{n}{0} + b_1\binom{n}{1} + b_2\binom{n}{2} + \cdots + b_n\binom{n}{n}.\] With that in mind, let \(\alpha\) be a number that satisfies \(\alpha^2 + \alpha = -1\).

It turns out that there is no real number \(\alpha\) with this property (see if you can prove this!), but we can still work with \(\alpha\) as a number. We simply treat \(\alpha\) like a variable, with the added flexibility that we can replace \(\alpha^2 + \alpha\) with \(-1\).

It’s very likely that you already have experience doing something like this. For example, when we write \(\sqrt 2\), it’s not important that \(\sqrt 2 \approx 1.41\). The important thing is that the number satisfies \((\sqrt 2)^2 = 2\). So, when working with \(\sqrt 2\), we simply treat it like a variable with the added bonus that we can replace \((\sqrt 2)^2\) with \(2\). Similarly, when we write a fraction like \(\frac{5}{3}\), while it’s true that this number is equal to \(1.\overline{6}\), the important thing is that when you multiply \(\frac{5}{3}\) by \(3\), you get \(5\).

3. Evaluate the following expressions (they should all be integers!).

   1. \(\alpha^3\)

   2. \(\alpha^8 + \alpha^4 + \alpha^9\)

   3. \((1+\alpha) - (1+\alpha)^2\)

4. Let \(n \geq 1\) be an integer. Let \(g_n(x) = (1 + x)^n\).

   1. Find numbers \(A\), \(B\), and \(C\) in terms of \(\alpha\) such that \[b_0 \binom{n}{0} + b_1\binom{n}{1} + b_2\binom{n}{2} + \cdots + b_n\binom{n}{n} = Ag_n(1) + Bg_n(\alpha) + Cg_n(\alpha^2).\] [Note: The binomial theorem will be essential here.]

   2. Using the values you found in part (a), Let \(d_n = Ag_n(1) + Bg_n(\alpha) + Cg_n(\alpha^2)\). Evaluate \(d_n\) (it is always an integer!). Keep in mind that the value of \(d_n\) may depend on \(n\).

5. Evaluate \(f_6, f_7, f_8, f_9,f_{10},f_{11},\) and \(f_{12}\).

Here is Question B3 from the 2024 Canadian Intermediate Mathematics Contest.