# recurrence relation for proportional division

Consider the following recurrence relation, for a function $D(x,n)$, where x is a positive real number and n is a positive integer:

$$D(x,1) = x$$

$$D(x,n) = \min_{k=1..n-1}{D(xk/n,k)} \ \ \ \ [n>1]$$

This formula can be interpreted as describing a process of dividing a value of x to n people: if there is a single person ($n=1$), then he gets all of the value x, and if there are more people, they divide x in a proportional way.

By induction on n, it is possible to prove that:

$$D(x,n) = x/n$$

PROOF: For $n=1$, this is given. Assume it is true for $1, 2, ... n-1$. Then:

$$D(x,n) = \min_{k=1..n-1}{D(xk/n,k)} = \min_{k=1..n-1}{x/n} = x/n$$

Now consider a slight modification of the formula:

$$E(x,1) = x$$

$$E(x,2) = x/2$$

$$E(x,n) = \min_{k=2..n-1}{E(x(k-1)/n,k)} \ \ \ \ [n>2]$$

The modified version models division with loss - in each division process, we lose some value: we give to $k$ people, only $(k-1)/n$ of the original value. What is the solution to this formula?

-

By induction on n, it is possible to prove that, for $n \geq 2$:

$$E(x,n) = x/n(n-1)$$

PROOF: For $n=2$, this is given. Assume it is true for $2, ... n-1$. Then:

$$E(x,n) = \min_{k=2..n-1}{E(x(k-1)/n,k)} = \min_{k=2..n-1}{x/nk} = x/n(n-1)$$

This is interesting - even a small loss in the division process, leads to a large reduction of the value each person gets, from $O(1/n)$ to $O(1/n^2)$.

-
Why do you ask the question to answer it? Is there something else that you are getting at? – Calvin Lin Jun 10 '13 at 5:22
In the hope of finding other people working on similar problems (mathematics of fair division). – Erel Segal-Halevi Jun 10 '13 at 6:05
Here is the actual question that I couldn't solve: math.stackexchange.com/questions/416734/… – Erel Segal-Halevi Jun 12 '13 at 9:26