How to mathematically derive Height & number of Leafs of this Recursion Tree

Question

I was studying following tree and get stuck on deriving it's Height & number of Leafs:

It says the height is [log_bn ]: How to derive it? (also i think height = [log_bn] + 1)

How They derive number of Leafs: a^log_bn = n^log_ba

Please help me to mathematically derive Height & number of Leafs of this Recursion Tree in a very simple way.Thanks

Answer 1

Height
The top of the tree begins with n and for every step down it is divided by b. So it goes n, n/b, n/b²,...,1. To find the height we need to find a k such that n / b^k = 1 or b^k = n, which gives k = log_bn.

Number of leaves
For every step down the tree, the leaves are multiplied by a times. The number of leaves is a^k, where k is the number of steps or height of the tree. The number of leaves = a^log_bn.