In the course of analyzing a certain Markov chain, I once had to prove the following algebraic identity.

Is there a slick or known proof?

For $n$-tuples $(x_1,x_2,\dots, x_n)$ of positive real numbers define $$\mu(x_1,x_2,\dots, x_n)=\prod_{j=1}^n {x_j\over x_j+x_{j+1}+\cdots+x_n}.$$

Then if $x^\ast$ is another positive real, and $1\leq k\leq n+1$, then define $x^*_k$ to be the $(n+1)$-tuple $(x_1,x_2,\dots, x^*,\dots, x_n)$ where $x^*$ is in the $k$th place. The identity is

$$\sum_{k=1}^{n+1}\ \mu(x^\ast_k)=\mu(x_1,x_2,\dots, x_n).$$

For example, $$ {xyz\over(x+y+z)(y+z)z} + {yxz\over(y+x+z)(x+z)z} + {yzx\over(y+z+x)(z+x)x}={yz\over(y+z)z}.$$


Consider the following experiment: there is an interval of length $x_1 + \cdots + x_n$ divided into $n$ segments of sizes $x_1,\ldots,x_n$. We sample an infinite sequence of points from the interval, and write out the segments corresponding to the points. Then, we look at the order in which the segments are "discovered", i.e. which one was hit first, which was the next one, and so on. Then $\mu(x_1,\ldots,x_n)$ is the probability that the segments will be discovered in the order $x_1,\ldots,x_n$.

Now suppose we add an extra segment $x^* $, and repeat the same experiment. If we just forget about this extra segment, the new experiment is just like the old one. This is the same as running the new experiment and deleting $x^* $ from the order of discovery. Your identity follows.

  • $\begingroup$ Interesting! Could you please elaborate a bit more, especially the second paragraph? It does not look obvious to me that the two experiments (one with forgetting) must lead to the same chances of the order of x_1,..., x_n being the same. For instance, say we added two segments x* and y*, would it be same? $\endgroup$ – Aryabhata Sep 8 '10 at 13:37
  • 1
    $\begingroup$ This is a brilliant idea. @Moron: Both sides give the probability of discovering segments 1, 2, ..., n in order. The left side enumerates all the possible ways in which an n+1st segment could be accounted for. The expressions must be equal by the law of total probability. If you were to add any finite number of new segments, you would have to sum over all possible ways in which they could be inserted in the order. This would be algebraically the same as repeatedly applying the identity for inserting one new segment. $\endgroup$ – whuber Sep 8 '10 at 15:48
  • $\begingroup$ @whuber: I agree the idea is superb! $\endgroup$ – Aryabhata Sep 8 '10 at 16:09
  • $\begingroup$ This is exactly what I was looking for! Thanks. $\endgroup$ – user940 Sep 8 '10 at 16:12

Here is a proof by induction on the number of elements in the tuple.

(Hopefully, I got the algebra right. In any case, it would be easy to verify).

First a Lemma.

Lemma: For $n \ge 2$ we have that $\displaystyle \mu(x_1, ..., x_n) = \frac{x_{n-1}}{x_{n-1}+x_n} \mu(x_1, .., x_{n-2}, x_{n-1} + x_n)$

Proof: Easy Algebra.

Let $y = x^{*}$.

Base Case

For $n=1$ it is easy to see that $ \displaystyle \mu(y, x) + \mu(x, y) = \mu(x)$

Induction Step

Now suppose $n \ge 2$

We have that (I have changed your notation slightly, I start from 0 instead of 1)

$$\sum_{k=0}^{n-2} \mu(x_1, x_2, \dots , x_k, y, x_{k+1}, \dots,x_{n-1}, x_{n})$$ $$ = \sum_{k=0}^{n-2}\frac{x_{n-1}}{x_{n-1}+x_{n}} \mu(x_1, x_2, ..., x_k, y, \dots, x_{n-1} + x_{n})$$

Now it is easy to see that

$$\mu(x_1, \dots, x_{n-1}, y, x_n) + \mu(x_1, \dots, x_{n-1}, x_n, y)$$

$$ = \frac{x_{n-1}}{x_{n-1}+x_n} \mu(x_1, x_2, ..., x_{n-2}, x_{n-1} + x_n, y)$$

Thus we have that

$$ \sum_{k=0}^{n} \mu(x_{k}^{*}) $$ $$ = \sum_{k=0}^{n-1} \frac{x_{n-1}}{x_{n-1}+x_{n}} \mu (z_{k}^{*})$$


$$ z = (x_1, \dots, x_{n-2}, x_{n-1}+x_{n})$$

Thus by induction hyptothesis, this is the same as

$$ \frac{x_{n-1}}{x_{n-1}+x_{n}} \mu (x_1, \dots, x_{n-2}, x_{n-1}+x_{n}) $$

= $$ \mu(x_1, x_2, \dots, x_{n-1}, x_n)$$

  • $\begingroup$ Thanks for your solution. This is similar to the way I solved it. $\endgroup$ – user940 Sep 8 '10 at 16:13
  • $\begingroup$ @Byron: If you have a solution and are looking for a different proof, I suggest you mention your approach in the question itself. This will save everyone some time. $\endgroup$ – Aryabhata Sep 8 '10 at 16:17
  • $\begingroup$ OK, sorry about that. $\endgroup$ – user940 Sep 8 '10 at 16:39
  • $\begingroup$ P.S. Your algebraic proof also works if the numbers are positive, negative, or whatever. Provided we never divide by zero. $\endgroup$ – user940 Sep 8 '10 at 17:25
  • 1
    $\begingroup$ @Bryon: True, but proving it just for numbers in (0,1) is enough, as we can get a polynomial identity in any variable we want and that would generalize to complex numbers. $\endgroup$ – Aryabhata Sep 8 '10 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy