Matematyka.pl

Niech \(\displaystyle{ T_{n}}\) bedzie zbiorem uporządkowanym w typ drzewa binarnego (do kazdego wierzchołka dochodzi jedna krawedz, a wychodzą - poza końcowymi wierzchołka - dwie krawedzie), ktorego wszystkie drogi od korzenia do wierzcholka koncowego maja te samą długość \(\displaystyle{ n}\). Ile wierzchołków ma takie drzewo?

Co to jest suma drogi?

Przepraszam chodziło o długość drogi

Proponuje dowod indukcyjny

Dobrze, tylko nie wiem właśnie ile to wierzchołków, z dowodem raczej sobie poradzę

To na początek rozrysuj sobie przypadki dla \(\displaystyle{ n =1, n=2, n =3}\) - znajdź liczbę wierzchołków i popatrz jak wyglądają takie drzewa

Czy \(\displaystyle{ w=2^{(n+1)}-1}\)?

Tak - teraz czas na odwód indukcyjny