# How to find the maximum of this equation $x(1 - (1 - \frac{1}{x})^K)$

For x in reals and K some positive integer, can you find the maximum of this function analytically?

$f(x) = x(1 - (1 - \frac{1}{x})^K)$

-

Alphabet soup: Imagine a sequence $(a_1, a_2,\dots, a_K)$ over the alphabet $\{1,2,\dots,x\}$ chosen uniformly at random among the $x^K$ possibilities. What is the expected size of the set $\{a_1,a_2,\dots,a_K\}$?

Solution: Let $A_i$ be the event that the letter $i$ is present in the random sequence. The size of the set is just $X=\sum_{i=1}^x 1_{A_i}$ which has expected value $$\mathbb{E}(X)=\sum_{i=1}^x \mathbb{P}(A_i)=x\left[1-\left(1-{1\over x}\right)^K\right].$$

But the size of the set cannot exceed $K$, so $X\leq K$ with full probability and therefore also $\mathbb{E}(X)\leq K$. On the other hand, $K\mathbb{P}(X=K)\leq \mathbb{E}(X)$ but this probability is easily calculated, giving the bounds $$K\left({x\over x}{x-1\over x}\cdots{x-K+1\over x}\right) \leq x\left[1-\left(1-{1\over x}\right)^K\right]\leq K.$$ This shows that the expression converges to its upper bound $K$ as $x\to\infty$. Of course, all of this assumes that $x$ and $K$ are natural numbers.

-
I first saw this idea here: math.stackexchange.com/questions/5775/… but then I couldn't remember where I'd seen it. – Byron Schmuland Mar 4 '12 at 18:31

Seems unlikely. If you differentiate, set to zero, and simplify, you get a polynomial equation of degree $k-1$. If $k\ge6$ I wouldn't expect there to be a formula for $x$ in terms of radicals and the four arithmetical operations.

-

We'll show that for $K$ even there is no extreme value on $(0,\infty)$. Behaviour to the left of $0$ is similar. However, we won't show how to find the extreme values when they exist (i.e. for $K>1$ odd). However, I think this argument partially answers the question so I decided to post it.

First assume $x\ge 1$. Set $g(x) = \left(1+\frac{K-1}{x}\right)\left(1-\frac{1}{x}\right)^{K-1}$, so that $f^\prime(x) = 1 - g(x)$. Make the substitution $v = 1 - 1/x$ and note that $x\ge 1$ implies $0\le v<1$. Then $$g(v) = (v+K(1-v))v^{K-1}= v^{K-1}(v(1-K) + K)\le v^{K-1}(1-K+K) < 1.$$ The second to last inequality holds since $v<1$. Therefore the derivative is positive on $(1,\infty)$.

Now assume $0<x<1$. This case is trickier. If $K$ is even then the derivative is also positive on $(0,1)$ because $v<0$ and $K-1$ is odd. In this case $f(x)$ has no extreme values on $(0,\infty)$. But $K$ odd will lead to $$g(v) \le v^{K-1}(1-K+K) = v^{K-1}$$ and we can make the right side as large as we like ($v$ is unbounded below). Therefore $f^\prime(x) = 1 - g(x)$ will be negative somewhere on $(0,1)$ so there's a minimum somewhere in $(0,1)$. But I can't solve for it which was probably what the OP wanted to know, but on the other hand, we can see it doesn't always have a max. In fact, the only extreme values on $(0,\infty)$ are minumums (when $K >1$ is odd), and lie in $(0,1)$.

-

When $K = 1$, $f(x) = 1$. So assume $K > 1$ (not necessarily an integer).

The derivative of your function is $$1 - \left(1 - \frac{1}{x}\right)^K - \frac{K}{x}\left(1 - \frac{1}{x}\right)^{K-1} = 1 -\left(1 + \frac{K-1}{x}\right)\left(1 - \frac{1}{x}\right)^{K-1} .$$ The derivative approaches $1$. In particular, when $x$ is large enough, this derivative is at least $1/2$ (say). Therefore the function grows to infinity with $x$.

Edit: In fact, as André points out, the derivative approaches $0$, and what is even worse, it's not even clear whether it remains positive. In fact, approximately $(1-1/x)^{K-1} = 1-(K-1)/x+(K-1)(K-2)/2x^2$ and so the derivative is approximately $$1 - \left(1 + \frac{K-1}{x}\right)\left(1 - \frac{K-1}{x} + \frac{(K-1)(K-2)}{2x^2}\right) = \frac{K(K-1)}{2x^2} + \frac{(K-1)^2(K-2)}{2x^3}.$$ So it does appear that the function is ever-increasing. At the limit, we get the value $K$, as mentioned in the comments.

-
As $x$ gets large, the derivative appears to approach $1 - 1(1) = 0$. But it's hard to tell if the second term is greater than 1 or less than 1. – Patrick Mar 1 '12 at 23:07
@Yuval Filmus: I have trouble with this argument, since for huge $x$ the exponential is roughly $1-\frac{K}{x}$. – André Nicolas Mar 1 '12 at 23:16
Playing around with a graphing program, $f$ looks to be increasing on the positive axis with limit $K$ as $x$ increases without bound. Similar behavior to the left of $0$. – Patrick Mar 1 '12 at 23:30
@Patrick: The limit is indeed $K$, easy proof. – André Nicolas Mar 1 '12 at 23:54