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&gt;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&gt;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)$.
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)$.