# Book Index Range

Solution

Copyright © 1996-2018 Alexander Bogomolny

Let rn(p) be the sought expectation. We shall show that

 (1) rn(p) = p + (n - 1)p(1 - p)

by induction on n.

When n = 1, (1) becomes r1(p) = p, which is clearly true.

Suppose n > 1 and assume (1) holds for rn-1(p), which is the expected number of ranges for an (n-1)-page book. The addition of one more page may or may not change the total number of ranges. When page n is added, the number of ranges increases by one if the term occurs on page n and does not occur on page (n - 1); this happens with probability p(1 - p). Otherwise, the number of ranges does not change. Therefore,

 rn(p) = p(1 - p)·[rn-1(p) + 1] + [1 - p(1 - p)]·rn-1(p) = rn-1(p) + p(1 - p) = p + (n - 1)p(1 - p).

### References

1. G. G. Chappell, A Quicky, Math Magazine, Vol. 72, No. 4, October 1999, Q893 (p. 326), A893 (p. 331).

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]