How to understand the perfect binary tree formula?

Question

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says:

I'm not quite understand his meaning here, how did him convert that into

And if it is , if I got 4 knights, I'll need 3 match to get the winner, the binary tree looks like

           A
         /   \
        A     C
       / \   / \
      A   B C   D

The height is 3, won't 23 be 8? or 22 be 4? How could that be 3?

I'm really confused.

Answer 1

Use the following identity for the first part where you can prove it by induction or just simply apply the formula for the sum of the first $h$ consecutive terms of a geometric progressions with $a_0=2^0$ and the ratio equals $2$:

$$2^0+2^1+\cdots+2^{h-1}=2^h-1$$

For the second part, note that if only two people are playing, there's only one match deciding the winner, so the hight of the binary tree is $1.$ Generalize this observation and see the height of binary tree you drew is $2$ not $3.$