Expected value uniform decreasing function We are given a function $f(n,k)$ as
for(i=0;i < k;i++)
  n = rand(n);
return n;

rand is defined as a random number generator that uniformly generates values in the range $[0,n)$. It returns a value strictly less than $n$; also $\operatorname{rand}(0)=0$.
What is the expected value of our function $f(n,k)$ given $n$ and $k$?

If the random numbers are not restricted to integers but are uniformly generated on the entire interval $[0,n)$, the expected value is halved in each iteration, and thus by linearity of expectation the expected value of $f(n,k)$ is $2^{-k}n$.
If $n$ and the random numbers are restricted to integers, the expected value decreases from $a_i$ to $(a_i-1)/2$ in each iteration, so we need to shift by $1$ to obtain the recurrence $a_{i+1}+1=(a_i+1)/2$, so in this case the expected value of $f(n,k)$ is $2^{-k}(n+1)-1$.
