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.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted
+50

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.

share|improve this answer
    
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
1  
@ 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

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.