Understanding math behind proof relating to binary search trees (issue with logarithms) I am posting the entire problem starting with the initial theorem since it is pertinent to the final solution. There are two things I don't understand here. 1. In the inductive case, why does it transform from greater than to (eventually) greater than or equal to? 2. Why do A and B become log(base 2)? !enter image description here

Question 1. The two inequalities in question are equivalent. Since all the function values are non-negative integers, saying $n>f-1$ is equivalent to $n\geq f$. To see this, try it with $f=10$. Then $n>f-1$ is $n>9$. The first integer greater than $9$ is $10=f$. So $n\geq f$.

Question 2. Since all logarithms can be transformed to a different base using the change of base theorem, they changed the base from using $\varphi$, which is hard to work with, to base $2$, which works very nicely with binary trees.