Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}.$$

share|improve this question
    
This is identic to mathoverflow.net/questions/74102/rational-function-identity . –  darij grinberg Dec 11 '11 at 18:30
add comment

2 Answers

up vote 14 down vote accepted

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.

share|improve this answer
    
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? –  Aryabhata Sep 8 '10 at 13:37
1  
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. –  whuber Sep 8 '10 at 15:48
    
@whuber: I agree the idea is superb! –  Aryabhata Sep 8 '10 at 16:09
    
This is exactly what I was looking for! Thanks. –  Byron Schmuland Sep 8 '10 at 16:12
add comment

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}^{*})$$

where

$$ 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)$$

share|improve this answer
    
Thanks for your solution. This is similar to the way I solved it. –  Byron Schmuland Sep 8 '10 at 16:13
    
@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. –  Aryabhata Sep 8 '10 at 16:17
    
OK, sorry about that. –  Byron Schmuland Sep 8 '10 at 16:39
    
P.S. Your algebraic proof also works if the numbers are positive, negative, or whatever. Provided we never divide by zero. –  Byron Schmuland Sep 8 '10 at 17:25
1  
@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. –  Aryabhata Sep 8 '10 at 17:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.