Find expected value of F(N)

Question

If we are given that a variable X is defined as

X=rand() % N  

Here rand() returns an integer between 0 and $10^{100}$ (inclusive) uniformly at random.

Now we need to find expected value f(N) where its defined as follow :

f(N) = $\sqrt{x+\sqrt{x+\sqrt{x+..............}}}$

Like If N = $5$ then here answer is $1.6964$

Now for given N we need to find expected value of f(N).Please help.

Answer 1

Hints:

• You might start by by finding a simple expression for $g(x)= \sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}$, ensuring you have a sensible answer for non-negative integer $x$, especially when $x=0$

• Take the average of $g(x)$ across integer $x$ for $0 \le x \lt N$.

• I doubt there is a closed form for the expected value. For example $f(5)=\frac{7+\sqrt{5}+\sqrt{13}+\sqrt{17}}{10}$

• There is an approximation for large $N$ of the form $cN^k$ for some $c$ and $k$ you can find and justify using integration rather than discrete sums, which is probably what is wanted here.

Answer 2

I found this out, and will edit with a more complete response as I figure it out:

Let $f(x) = \sqrt{x + \sqrt{x + ...}}$.

Then $f(x) = \sqrt{x + f(x)} \Rightarrow f(x)^2 - f(x) - x = 0 \Rightarrow f(x) = \frac{1}{2}\left(1 \pm \sqrt{1 + 4x}\right)$. We can, however, eliminate the minus from the $\pm$ since we want $f(x)$ to be positive. Thus:

$f(x) =\frac{1}{2}\left(1 + \sqrt{1 + 4x}\right)$

More to come, hopefully.