I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows:


Pick $k$ distinct numbers out of numbers $[1,n]$ uniformly at random, order them increasingly by size and denote them with $\alpha\_1, \alpha\_2, \dots , \alpha\_k$.


I would like to calculate
$$\mu:=\mathrm{E}\left(\sum\_{i=1}^{k}\left(\frac{1}{2}\right)^{\alpha\_{i}-i}\right),$$
or at least find a good upperbound to it. Trivial bounds are obviously
$$k\cdot 2^{k-n} \leq \mu \leq k.$$


EDIT: I am sorry for not being clear enough. In my problem, all chosen numbers are integers (not reals). Hopefully there is not much difference when using just integers. 



Expected value of a function over random sets
I assume you mean picking a random $k$-subset from {1,...,n}, i.e. drawing without
replacement? In this case one finds for $X\_j=\alpha\_j-j$ that


$$\mathbb{E}(t^{X\_j})= {k!\,(n-k)! \over n!} [x^{n-k}]{1 \over (1-tx)^j(1-x)^{k+1-j}}$$


and $$\mu(t):=\mathbb{E} \sum\_{j=1}^k t^{X\_j}={n+1 \over n+1-k}{1-t^{n+1-k} \over 1-t}-
t\,{1-t^{n-k} \over 1-t} -1={k \over n-k+1}{1-t^{n-k+1} \over 1-t}$$


