# recurrence relations for proportional division

I am looking for a solution to the following recurrence relation:

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

$$D(x,n) = \min_{k=1,\ldots,n-1}{D\left({{x(k-a)} \over n},k\right)} \ \ \ \ [n>1]$$

Where $a$ is a constant, $0 \leq a \leq 1$. Also, assume $x \geq 0$.

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, with some loss ($a$) in the division process.

For $a=0$ (no loss), it is easy to prove by induction that:

$$D(x,n) = {x \over n}$$

For $a=1$, it is also easy to see that:

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

But I have no idea how to solve for general $a$.

Additionally, it is interesting that small modifications to the formula lead to entirely different results. For example, starting the iteration from $k=2$ instead of $k=1$:

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

$$D(x,n) = \min_{k=2,\ldots,n-1}{D\left({{x(k-a)} \over n},k\right)} \ \ \ \ [n>2]$$

For $a=0$ we get the same solution, but for $a=1$ the solution is:

$$D(x,n) = {x \over n(n-1)}$$

Again I have no idea how to solve for general $a$.

I created a spreadsheet with some examples, but could not find the pattern.

Is there a systematic way (without guessing) to arrive at a solution?

-
Is it enough to suppose $x>0$? – Boris Novikov Jun 25 '13 at 16:06
Yes, I will add in the question. – Erel Segal-Halevi Jun 25 '13 at 20:35

For $x>0$ the answer is $$D(x,n)=\frac{x(1-a)(2-a)\ldots (n-1-a)}{n!}$$

Proof: induction on $n$. Indeed,

$$D(x,n)=\min_{k=1,\ldots,n-1}\frac{x(k-a)(1-a)\ldots (k-1-a)}{k!n}$$ $$=\frac{x}{n}\min_{k=1,\ldots,n-1}\frac{(1-a)\ldots (k-a)}{k!}$$ andf it remains to prove

$$\frac{(1-a)\ldots (k-a)}{k!}>\frac{(1-a)\ldots (k+1-a)}{(k+1)!}$$ But this is evident.

For $x>0$ similarly.

-
Interesting! Can you describe the solution in a more concise way (i.e. not as a product of n elements)? Maybe even an asymptotic bound as n goes to $\infty$? – Erel Segal-Halevi Jun 26 '13 at 18:40
@ Erel Segal Halevi: Sorry, I am an algebraist, not expert in similar problems. What I can say, is that $D(x,n)$ is connected with generalized binomial coefficients (en.wikipedia.org/wiki/…), namely: $$D(x,n)=x{n-\alpha \choose n}$$ – Boris Novikov Jun 26 '13 at 18:54
What happens when the minimum starts with $k=2$, as in the second part of the question? It seems that the answer will be the same, except the factor $(1-a)$ in the nominator. – Erel Segal-Halevi Jun 28 '13 at 11:54
@Erel Segal Halevi: Yes, you are right. – Boris Novikov Jun 28 '13 at 14:22