# (Solved) Closed-form formula for a simple sum of products

I'm trying to find a closed-form formula of the following expression involving a particular value. Consider a list of $$n$$ ones and $$t$$ twos $$(a_1,\cdots,a_{n+t})=(1_1,\cdots,1_n,2_1,\cdots,2_t)$$. For example $$n=2$$ and $$t=4$$: $$(1_1,1_2,2_1,2_2,2_3,2_4)$$. Define the sum over all $${n+1 \choose 2}$$ unique pairs of (indexed) $$1$$'s and $$2$$'s $$P=\{(a_i,a_j) \;|\; 1\le i < j \le n+t\}$$ as follows: $$S = \sum_{(a_i,a_j)\in P} a_ia_j$$ The sum can be decomposed in pairs of the form $$(1,1)$$, $$(1,2)$$ and $$(2,2)$$, which leads (I hope I didn't make any mistakes) to $$S = \sum_{i=1}^n \sum_{j=i+1}^n 1 + \sum_{i=1}^n \sum_{k=1}^t 2 + \sum_{j=1}^t \sum_{k=j+1}^t 4 = \frac{n(n - 1) + 4t(n + t - 1)}{2}.$$

Is there some closed-form formula involving only the total sum of the values $$\varphi=n+2t$$? For example, after rearranging: $$S = \frac{n(n - 1) + 4t(\varphi - t - 1)}{2}$$ but there are still $$n$$ and $$t$$ in the expression. Can someone provide a formula in the form I'm looking for?

## 2 Answers

If the desired expression were to exist, we would find that, for two $$(n,t)$$ pairs giving the same value of $$\varphi$$, we would get the same value of $$S$$. This doesn't happen. When $$(n,t) = (2,0)$$, we have $$(\varphi, S) = (2, 1)$$. When $$(n,t) = (0,1)$$, we have $$(\varphi, S) = (2,0)$$. So, for the same values of $$\varphi$$, we have different values of $$S$$. Therefore, $$S$$ does not depend only on $$\varphi = n+2t$$. That is, no such formula exists.

How close can we get?

Since the degree of $$n+2t$$ is one (for either variable), we can use polynomial division (with remainder) to see whether $$S = 1 \cdot \frac{n(n-1)}{2} + 2 \cdot n t + 4 \cdot \frac{t(t-1)}{2} = \frac{n(n-1)+4t(n+t-1)}{2}$$ is in the ideal generated by $$n+2t$$. \begin{align*} && S &= \frac{n+2t-1}{2}(n+2t) - t \\ &\text{or}& \\ && S &= \frac{n+2t-2}{2}(n+2t) + \frac{n}{2} \text{,} \end{align*} where in the first line we take $$n$$ as the variable and in the second line, $$t$$. In either case, there is a remainder (that is automatically not written in terms of $$n+2t$$). We had to be a little careful to ensure that $$n+2t$$ was the combination appearing in the quotient.

Another way to get at this is to write $$\varphi = n+2t$$, then there are two ways to go:

• apply the replacement $$n \mapsto u - 2t$$ and see if all $$t$$ dependence falls out, or
• apply the replacement $$t \mapsto \frac{u-n}{2}$$ and see if all $$n$$ dependence falls out.

When we make these substitutions, we obtain \begin{align*} && S &= \frac{\varphi(\varphi - 1)}{2} - t &\text{or}& \\ && S &= \frac{\varphi(\varphi - 2)}{2} + \frac{n}{2} \text{.} \end{align*} (In both cases, we should be able to compare with the matching expressions using polynomial division, above.) These have the advantage that writing the quotient in terms of $$\varphi$$ is automatic. Here also, we discover there is no such formula, but if we allow one "corrective" term at the end, we can get a formula with only one reference to either $$n$$ or to $$t$$.

• Oh, well. Without a formula my work is going to be slightly harder... But, my, I never thought of applying this technique and the formulae you gave are really going to be useful. Thanks a lot! Sep 5, 2020 at 5:35

This is not possible. Suppose towards a contradiction a closed formula exists in the form you are asking for. Then regardless of the values of $$n$$ and $$t$$ so long as $$n+2t= \varphi$$ the output of this closed formula will be the same. Let $$\varphi = 2$$. The two possible configurations are:

1. $$n = 2$$, $$t = 0$$
2. $$n = 0$$, $$t = 1$$

In the first case, there is one unique pair that sums to 1. In the second there are no unique pairs and so the sum is 0. We have a contradiction, no close formula only in terms of $$\varphi$$ exists.

• Oh, wow. I'm not going to work at night again. Thank you for the sweet and short answer. Sep 5, 2020 at 5:23