What do you mean by average cost? The usual idea is to count the number of key comparisons in a search. I'm taking my answer directly from D. E. Knuth, Vol.3, Searching and Sorting, p. 410. I have 100% confidence in this source. So if you let SN be the average number of comparisons in a successful search of a binary search tree with N nodes (assuming each of the N keys is equally likely as a search argument), then
-- this is 1 more than your formula??
Next assume that an unsuccessful search is for a key that is equally likely to be in any of the N+1 intervals determined by the N keys of the tree. Then
If you read a few more pages in Knuth, you get the nice formula (assuming the tree was built initially by inserting the N keys in random order):
where is the Nth partial harmonic sum.