# Balanced tree number of nodes

This should be a simple one but maybe I'm dumb or maybe I'm just tired, but how to prove that

$$n = 1 + 2^1 + 2^2 + \cdots + 2^h$$

is equal to

$$n = 2^{h+1} - 1$$

?

-

2
Find $2n - n$. Solve for $n$. – ladaghini Aug 10 '12 at 13:06

2
multiply the first expression by $(2 - 1)$ and expand. A bunch of stuff cancels and gives you the second expression. – countinghaus Aug 10 '12 at 13:19
– MJD Aug 10 '12 at 13:59
You can try induction. – ᴊ ᴀ s ᴏ ɴ Aug 10 '12 at 14:12

## 2 Answers

-

Thank you, I didn't think of the geometric series! – John Smith Aug 10 '12 at 13:15

It’s a straightforward geometric series, as noted by rbm, but there are other ways to see it.

(1) Write it in binary: $2^n$ in binary is a $1$ followed by $n$ zeroes. Thus, in binary you’re adding $$1+10+100+\ldots+1\underbrace{0\dots0}_h=\underbrace{1\dots1}_{h+1}\;.$$ But clearly $\underbrace{1\dots1}_{h+1}+1=1\underbrace{0\dots0}_{h+1}$, which is the binary representation of $2^{h+1}$. Thus, $$1+2^1+2^2+\ldots+2^h=2^{h+1}-1\;.$$

(2) Prove it by induction on $h$. It’s certainly true for $h=0$: $1=2^1-1$. Suppose that for some $h\ge 0$ we have $$1+2^1+2^2+\ldots+2^h=2^{h+1}-1\;.$$ Then

$$\begin{align*} 1+2^1+2^2+\ldots+2^h+2^{h+1}&=\left(1+2^1+2^2+\ldots+2^h\right)+2^{h+1}\\\\ &=\left(2^{h+1}-1\right)+2^{h+1}\\\\ &=2\cdot2^{h+1}-1\\\\ &=2^{(h+1)+1}-1\;, \end{align*}$$

as desired.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.950211226940155, "perplexity_flag": "middle"}