In Part 2 of this series, we have seen one way to determine the average-case running time of linear search. We have used the following lemma without proving it:
Now I will prove the correctness of this indentity.
We will start from the left hand side and simplify a little bit:
Where in the last step, we have used a formula for the summation of binomial coefficients over upper values. This formula can be proved using induction together with Pascal’s rule.
Now we need to evaluate a summation that is actually similar to the one we have started with. However, the latter one is easier to compute. There are two ways to compute it, the first only works in this kind of summations, the other works even in more complicated summations. Both ways are actually very tricky.
The trick is to turn the i multiplier into a trivial summation as follows:
Now by exchanging the summations and further algebraic manipulations we get:
Note that we already have a formula for the inner summations (which has been used once above). We apply the formula and simplify:
Substituting into (1):
The last step follows from Pascal’s rule. This concludes the proof.
The idea is to turn the term inside the summation into a product of binomial coefficients. Then we can apply a variation of Vandermonde’s identity which looks like this:
In fact, the term that we have can be very easily transformed into a product of binomial coefficients. All we have to do is to substitute the term i for C(i,1):
In the second to last step, we used the fact that C(0, 1) = 0 and so letting the index start from 0 will not affect the total value of the summation. In the last step, we have applied (2).
This completes the proof of the lemma.