section_heading: Teorem 1
paragraph_text: Počinjemo pokazujući da podstablo s korijenom u bilo kojem čvoru x sadrži barem <math>2^{bh(x)}-1</math> unutrašnjih čvorova. Dokazujemo ovu tvrdnju matematičkom indukcijom za visinu x-a. Ako je vrijednost x-a 0, onda x mora biti list nil[T]) i podstablo s korijenom u x zaista sadrži barem <math>2^{bh(x)}-1</math>= <math>2^0</math> - 1 = 0. unutrašnjih čvorova. Za korak indukcije, smatrajmo da čvor x ima pozitivnu vrijednost te da je unutrašnji čvor s dva djeteta. Svako dijete ima crnu-visinu od bh(x) ili bh(x) - 1, ovisno o tome je li boja crna ili crvena. Budući da je visina djeteta od x manja od same vrijednosti x, možemo primijeniti induktivnu hipotezu da zaključimo da svako dijete ima barem <math>2^{bh(x)}-1</math> unutarnjih čvorova. Stoga podstablo s korijenom u x sadrži barem <math>(2^{bh(x)-1}-1)</math> + <math>(2^{bh(x)-1}-1)</math> + 1 = <math>2^{bh(x)}-1</math> unutrašnjih čvorova što dokazuje tvrdnju.