Let expected number of comparisons be E. Value of E is the sum of following expression for all the possible cases.
case: 1
If A[i] is found in the first attempt
number of comparisons = 1
probability of the case = 1/n
case: 2
If A[i] is found in the second attempt
number of comparisons = 2
probability of the case = (n-1)/n*1/n
case: 3
If A[i] is found in the third attempt
number of comparisons = 2
probability of the case = (n-1)/n*(n-1)/n*1/n
There are actually infinite such cases. So, we have following infinite series for E.
E = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + …. (1)
After multiplying equation (1) with (n-1)/n, we get
E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 +
[(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)
Subtracting (2) from (1), we get
E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………
The expression on right side is a GP with infinite elements. Let us apply the sum formula (a/(1-r))
E/n = [1/n]/[1-(n-1)/n] = 1
E = n