number of leaves in a strict binary tree

Question

I looking for derivation how we came to following result.

sum of 2 to power of i, as i goes from 0 to n => answer is given as (2 power of (n+1) -1).

Can any one show me how we achieved above result or to proper link where we have solution.

Thanks!

Answer 1

Proof by induction.

Observe it's true for n=0 - sum0->0 = 1 = 2^1 - 1

Assume true for n = k-1, so sum[0->k-1] = 2^k - 1. Then sum[0->k] = sum[0->k-1] + 2^k = 2^k - 1 + 2^k = 2(2^k) - 1 = 2^(k+1) - 1.

Therefore true for all n.

Answer 2

It comes from the mathematical geometric progression.

If you want a clearer (more intuitive) explanation, you can read this nice explanation