# The Question.

Suppose we have $$n$$ linear functions $$f_k$$ defined on $$[x_1,x_2]$$. Let $$f_k(x_1)=y_k$$ and $$f_k(x_2)=z_k$$ denote the function values at the endpoints of the interval. We would like to calculate

$$\mathfrak{P}(n)=\int_{x_1}^{x_2} \prod_{k=1}^n f_k(x) \, dx$$

in terms of $$x_1,x_2,$$ and $$y_k, z_k$$ for $$k\in\{1,\ldots,n\}$$.

The motivation for this comes from mathematical programming-- specifically, an algorithm I'm writing that requires integrating the product of a large number of piecewise linear functions. What I would like is to find a closed form for $$\mathfrak{P}(n)$$.

Let's work through a few examples and see if a formula jumps out at us.

## Example: $$n=2$$

The first thing to do is write the $$f_k$$ in terms of the endpoint values. Solving $$f_k(x_1)=mx_1+b=y_k$$ and $$f_k(x_2)=mx_2+b=z_k$$, we get

$$f_k(x)=\frac{z_k-y_k}{x_2-x_1}x+\frac{y_k x_2-z_kx_1}{x_2-x_1}$$

So, then, we are calculating

$$\mathfrak{P}(2)=\int_{x_1}^{x_2} \left(\frac{z_1-y_1}{x_2-x_1}x+\frac{y_1 x_2-z_1x_1}{x_2-x_1}\right)\left(\frac{z_2-y_2}{x_2-x_1}x+\frac{y_2 x_2-z_2x_1}{x_2-x_1}\right) \, dx$$

which, God help us, is

$$\left.\frac{x \left(3 x (y_1 z_2 (x_1+x_2)+y_2 z_1 (x_1+x_2)-2 x_1 z_1 z_2-2 x_2 y_1 y_2)+6 (x_1 z_1-x_2 y_1) (x_1 z_2-x_2 y_2)+2 x^2 (y_1-z_1) (y_2-z_2)\right)}{6 (x_1-x_2){}^2}\right|_{x_1}^{x_2}$$ Luckily, this simplifies quite a bit down to $$\frac{1}{6} (x_2-x_1)(y_1 (2 y_2+z_2)+z_1 (y_2+2 z_2)).$$

Alright! It didn't turn out that bad.

## Example: $$n=3,\ldots, 6$$

Let's take a look at some other values of $$\mathfrak{P}$$. I'll spare you the intermediate calculations.

$$\begin{eqnarray*}\mathfrak{P}(3)&=&\frac{1}{12} (x_2-x_1) (y_1 y_3 (3 y_2+z_2)+y_1 z_3 (y_2+z_2)+y_3 z_1 (y_2+z_2)+z_1 z_3 (y_2+3 z_2))\\ \mathfrak{P}(4)&=&\frac{1}{60} (x_2-x_1) (y_1 y_4 (3 y_2 (4 y_3+z_3)+z_2 (3 y_3+2 z_3))+y_1 z_4 (3 y_2 y_3+2 y_2 z_3+2 y_3 z_2+3 z_2 z_3)+y_4 z_1 (3 y_2 y_3+2 y_2 z_3+2 y_3 z_2+3 z_2 z_3)+z_1 z_4 (y_2 (2 y_3+3 z_3)+3 z_2 (y_3+4 z_3)))\\ \mathfrak{P}(5)&=&\frac{1}{60}(x_2-x_1) (y_1 y_5 (2 y_2 y_4 (5 y_3+z_3)+y_2 z_4 (2 y_3+z_3)+y_4 z_2 (2 y_3+z_3)+z_2 z_4 (y_3+z_3))+y_1 z_5 (y_2 y_4 (2 y_3+z_3)+y_2 z_4 (y_3+z_3)+y_4 z_2 (y_3+z_3)+z_2 z_4 (y_3+2 z_3))+y_5 z_1 (y_2 y_4 (2 y_3+z_3)+y_2 z_4 (y_3+z_3)+y_4 z_2 (y_3+z_3)+z_2 z_4 (y_3+2 z_3))+z_1 z_5 (y_2 y_4 (y_3+z_3)+y_2 z_4 (y_3+2 z_3)+y_4 z_2 (y_3+2 z_3)+2 z_2 z_4 (y_3+5 z_3)))\\ \mathfrak{P}(6)&=&\frac{1}{420} (x_2-x_1) (y_1 y_2 (2 y_3 y_6 (5 y_4 (6 y_5+z_5)+z_4 (5 y_5+2 z_5))+y_3 z_6 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+y_6 z_3 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+z_3 z_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5))+y_1 z_2 (y_3 y_6 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+y_3 z_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+y_6 z_3 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+z_3 z_6 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5))+y_2 z_1 (y_3 y_6 (10 y_4 y_5+4 y_4 z_5+4 y_5 z_4+3 z_4 z_5)+y_3 z_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+y_6 z_3 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+z_3 z_6 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5))+z_1 z_2 (y_3 y_6 (4 y_4 y_5+3 y_4 z_5+3 y_5 z_4+4 z_4 z_5)+y_3 z_6 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5)+y_6 z_3 (3 y_4 y_5+4 y_4 z_5+4 y_5 z_4+10 z_4 z_5)+2 z_3 z_6 (y_4 (2 y_5+5 z_5)+5 z_4 (y_5+6 z_5))))\end{eqnarray*}$$

There certainly seems to be some pattern here.

The coefficient has a denominator of $$\operatorname{lcm}\{1,\ldots,n+1\}$$ and we're always multiplying by $$x_2-x_1$$, so let's just get rid of that first term by looking at $$\frac{\operatorname{lcm}\{1,\ldots,n+1\}}{x_2-x_1}\mathfrak{P}_n$$. Maybe it will help us see the pattern if we expand everything out.

$$\begin{eqnarray*}\frac{\operatorname{lcm}\{1,\ldots,4\}}{x_2-x_1}\mathfrak{P}_3&=&3 y_1 y_2 y_3+y_1 y_2 z_3+y_1 y_3 z_2+y_1 z_2 z_3+y_2 y_3 z_1+y_2 z_1 z_3+y_3 z_1 z_2+3 z_1 z_2 z_3\\ \frac{\operatorname{lcm}\{1,\ldots,5\}}{x_2-x_1}\mathfrak{P}_4&=&12 y_1 y_2 y_3 y_4+3 y_1 y_2 y_3 z_4+3 y_1 y_2 y_4 z_3+2 y_1 y_2 z_3 z_4+3 y_1 y_3 y_4 z_2+2 y_1 y_3 z_2 z_4+2 y_1 y_4 z_2 z_3+\cdots\\ &\cdots&3 y_1 z_2 z_3 z_4+3 y_2 y_3 y_4 z_1+2 y_2 y_3 z_1 z_4+2 y_2 y_4 z_1 z_3+3 y_2 z_1 z_3 z_4+2 y_3 y_4 z_1 z_2+3 y_3 z_1 z_2 z_4+\cdots\\&\cdots&3 y_4 z_1 z_2 z_3+12 z_1 z_2 z_3 z_4\\ \frac{\operatorname{lcm}\{1,\ldots,6\}}{x_2-x_1}\mathfrak{P}_5&=&10 y_1 y_2 y_3 y_4 y_5+2 y_1 y_2 y_3 y_4 z_5+2 y_1 y_2 y_3 y_5 z_4+y_1 y_2 y_3 z_4 z_5+2 y_1 y_2 y_4 y_5 z_3+y_1 y_2 y_4 z_3 z_5+\cdots\\&\cdots&y_1 y_2 y_5 z_3 z_4+y_1 y_2 z_3 z_4 z_5+2 y_1 y_3 y_4 y_5 z_2+y_1 y_3 y_4 z_2 z_5+y_1 y_3 y_5 z_2 z_4+y_1 y_3 z_2 z_4 z_5+\cdots\\&\cdots&y_1 y_4 y_5 z_2 z_3+y_1 y_4 z_2 z_3 z_5+y_1 y_5 z_2 z_3 z_4+2 y_1 z_2 z_3 z_4 z_5+2 y_2 y_3 y_4 y_5 z_1+y_2 y_3 y_4 z_1 z_5+\cdots\\&\cdots&y_2 y_3 y_5 z_1 z_4+y_2 y_3 z_1 z_4 z_5+y_2 y_4 y_5 z_1 z_3+y_2 y_4 z_1 z_3 z_5+y_2 y_5 z_1 z_3 z_4+2 y_2 z_1 z_3 z_4 z_5+\cdots\\&\cdots&y_3 y_4 y_5 z_1 z_2+y_3 y_4 z_1 z_2 z_5+y_3 y_5 z_1 z_2 z_4+2 y_3 z_1 z_2 z_4 z_5+y_4 y_5 z_1 z_2 z_3+2 y_4 z_1 z_2 z_3 z_5+\cdots\\&\cdots&2 y_5 z_1 z_2 z_3 z_4+10 z_1 z_2 z_3 z_4 z_5\\ \frac{\operatorname{lcm}\{1,\ldots,7\}}{x_2-x_1}\mathfrak{P}_6&=& 60 y_1 y_2 y_3 y_4 y_5 y_6+10 y_1 y_2 y_3 y_4 y_5 z_6+10 y_1 y_2 y_3 y_4 y_6 z_5+4 y_1 y_2 y_3 y_4 z_5 z_6+10 y_1 y_2 y_3 y_5 y_6 z_4+\cdots\\&\cdots& 4 y_1 y_2 y_3 y_5 z_4 z_6+4 y_1 y_2 y_3 y_6 z_4 z_5+3 y_1 y_2 y_3 z_4 z_5 z_6+10 y_1 y_2 y_4 y_5 y_6 z_3+4 y_1 y_2 y_4 y_5 z_3 z_6+\cdots\\&\cdots& 4 y_1 y_2 y_4 y_6 z_3 z_5+3 y_1 y_2 y_4 z_3 z_5 z_6+4 y_1 y_2 y_5 y_6 z_3 z_4+3 y_1 y_2 y_5 z_3 z_4 z_6+3 y_1 y_2 y_6 z_3 z_4 z_5+\cdots\\&\cdots& 4 y_1 y_2 z_3 z_4 z_5 z_6+10 y_1 y_3 y_4 y_5 y_6 z_2+4 y_1 y_3 y_4 y_5 z_2 z_6+4 y_1 y_3 y_4 y_6 z_2 z_5+3 y_1 y_3 y_4 z_2 z_5 z_6+\cdots\\&\cdots& 4 y_1 y_3 y_5 y_6 z_2 z_4+3 y_1 y_3 y_5 z_2 z_4 z_6+3 y_1 y_3 y_6 z_2 z_4 z_5+4 y_1 y_3 z_2 z_4 z_5 z_6+4 y_1 y_4 y_5 y_6 z_2 z_3+\cdots\\&\cdots& 3 y_1 y_4 y_5 z_2 z_3 z_6+3 y_1 y_4 y_6 z_2 z_3 z_5+4 y_1 y_4 z_2 z_3 z_5 z_6+3 y_1 y_5 y_6 z_2 z_3 z_4+4 y_1 y_5 z_2 z_3 z_4 z_6+\cdots\\&\cdots& 4 y_1 y_6 z_2 z_3 z_4 z_5+10 y_1 z_2 z_3 z_4 z_5 z_6+10 y_2 y_3 y_4 y_5 y_6 z_1+4 y_2 y_3 y_4 y_5 z_1 z_6+4 y_2 y_3 y_4 y_6 z_1 z_5+\cdots\\&\cdots& 3 y_2 y_3 y_4 z_1 z_5 z_6+4 y_2 y_3 y_5 y_6 z_1 z_4+3 y_2 y_3 y_5 z_1 z_4 z_6+3 y_2 y_3 y_6 z_1 z_4 z_5+4 y_2 y_3 z_1 z_4 z_5 z_6+\cdots\\&\cdots& 4 y_2 y_4 y_5 y_6 z_1 z_3+3 y_2 y_4 y_5 z_1 z_3 z_6+3 y_2 y_4 y_6 z_1 z_3 z_5+4 y_2 y_4 z_1 z_3 z_5 z_6+3 y_2 y_5 y_6 z_1 z_3 z_4+\cdots\\&\cdots& 4 y_2 y_5 z_1 z_3 z_4 z_6+4 y_2 y_6 z_1 z_3 z_4 z_5+10 y_2 z_1 z_3 z_4 z_5 z_6+4 y_3 y_4 y_5 y_6 z_1 z_2+3 y_3 y_4 y_5 z_1 z_2 z_6+\cdots\\&\cdots& 3 y_3 y_4 y_6 z_1 z_2 z_5+4 y_3 y_4 z_1 z_2 z_5 z_6+3 y_3 y_5 y_6 z_1 z_2 z_4+4 y_3 y_5 z_1 z_2 z_4 z_6+4 y_3 y_6 z_1 z_2 z_4 z_5+\cdots\\&\cdots& 10 y_3 z_1 z_2 z_4 z_5 z_6+3 y_4 y_5 y_6 z_1 z_2 z_3+4 y_4 y_5 z_1 z_2 z_3 z_6+4 y_4 y_6 z_1 z_2 z_3 z_5+10 y_4 z_1 z_2 z_3 z_5 z_6+\cdots\\&\cdots& 4 y_5 y_6 z_1 z_2 z_3 z_4+10 y_5 z_1 z_2 z_3 z_4 z_6+10 y_6 z_1 z_2 z_3 z_4 z_5+60 z_1 z_2 z_3 z_4 z_5 z_6 \end{eqnarray*}$$

The pattern in the variables is easy to see-- there are $$2^n$$ terms, each of which has terms $$1$$ through $$n$$ of either the $$y$$ or the $$z$$. (What I mean is, the terms are in 1-to-1 correspondence with $$\{y_1,z_1\}\times \cdots \times \{y_n,z_n\}$$.)

But, what are the coefficients?

• Do you specifically want a formula for each coefficient, or will any efficient algorithm to compute $\mathfrak{P}(n)$ suffice? – Mike Earnest May 3 at 18:51
• @MikeEarnest I was looking for the former but I'd take the latter. (Always the possibility it could turn into the former, too.) – Alexander Gruber May 3 at 18:54
• This probably doesn't help, but if you can do substitution (since any efficient algorithm is enough), this might be equivalent to calculating $\int_0^1 \prod(m_ix+c_i) dx$ – Gareth Ma May 3 at 22:28

By translating and rescaling you can write \begin{align*} \mathfrak{P}(n) &= (x_2 - x_1) \int_0^1 \prod_{k=1}^n (y_k(1 - x) + z_kx)\,dx \\ &= (x_2 - x_1) \int_0^1 \sum_{S \subset [n]}\left((1 - x)^{|S|}x^{n-|S|} \prod_{k \in S} y_k \prod_{k \not \in S} z_k\right)\,dx \\ &= (x_2 - x_1) \sum_{S \subset [n]} B\big(n-|S|+1\,,\, |S|+1 \big) \prod_{k \in S} y_k \prod_{k \not \in S} z_k \\ &= (x_2 - x_1) \sum_{S \subset [n]} \frac{1}{(n+1) \binom{n}{|S|}} \prod_{k \in S} y_k \prod_{k \not \in S} z_k \end{align*} where $$[n] = \{1, \dots, n\}$$ and $$B(a, b) = \int_0^1 x^{a-1} (1-x)^{b-1} \,dx = \frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}$$ is the Beta function.
Addendum: If you need a quick way to calculate this, note that this is $$(x_2 - x_1) \sum_{j=0}^n \frac{a_j}{(n+1)\binom{n}{j}}$$ where $$a_j$$ is the coefficient of $$x^j$$ in the polynomial $$\prod_{k=1}^n (xy_k + z_k)$$.