 Solution

For an array of size $2n+1$, the first probe finds the uniformly selected target with probability $1/(2n+1)$. Otherwise it leaves a half of size $n$; conditional on entering that half, its target is uniform there. Counting the first iteration in every case givesFor $n=2^k-1$, the successful-search decision tree has $2^d$ targets at depth $d$, requiring $d+1$ iterations. ThusThe numerator is $(k-1)2^k+1$, as follows by induction or by shifting and subtracting a finite geometric sum. Substituting $2^k=n+1$ givesThe base $k=1,n=1$ gives one iteration, as required.