Average-case analysis of linear search given that the desired element appears $k$ times The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":


  Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \ldots, A[n]$, until either it finds $A[i] = x$ or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.
  
  Suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the average-time running time of this algorithm?


Let $X$ be a random variable denoting the number of comparisons. 

$$
\begin{align*}
  E(X) &amp;= \sum_{i=1}^{i=n-k+1} i \cdot \Pr(X = i) \\
       &amp;= \sum_{i=1}^{i=n-k+1} i \cdot \left(\frac{n-k}{n} \cdot \frac{n-k-1}{n-1} \cdot \frac{n-k-2}{n-2} \cdot \cdots \cdot \frac{n-k-i+2}{n-i+2} \cdot \frac{k}{n-i+1}\right)
\end{align*}
$$

How to evaluate this summation? Or is there a simple solution to this problem?

Note that when $k=1$, $E(X)$ is $\frac{n+1}{2}$. When $k=n$, $E(X)$ is $1$.
Note
$$
\begin{align*}
E(X)&amp;=\sum_{i=1}^{n-k+1} i \cdot \Pr(X = i)\\
&amp;=\sum_{i=1}^{n-k+1} \sum_{j=1}^i\Pr(X = i)\\
&amp;=\sum_{j=1}^{n-k+1} \sum_{i=j}^{n-k+1}\Pr(X = i)\\
&amp;=\sum_{j=1}^{n-k+1} \Pr(X \ge j),
\end{align*}
$$
and $X\ge j$ means all $x$ are distributed among $A[j],\ldots,A[n]$, so 
$$
\Pr(X \ge j)=\frac{\binom{n-j+1}{k}}{\binom{n}{k}}.
$$
Therefore
$$
E(X)=\sum_{j=1}^{n-k+1} \frac{\binom{n-j+1}{k}}{\binom{n}{k}}=\frac{1}{\binom{n}{k}}\sum_{r=k}^{n}\binom{r}{k}=\frac{1}{\binom{n}{k}}\binom{n+1}{k+1}=\frac{n+1}{k+1}.
$$