Demostrar por inducción que para cada $n \geq 1$ todo árbol ternario no vacío de altura n tiene como máximo $(3^n − 1)/2$ nodos.

Question

Un árbol ternario es un árbol en el que cada nodo tiene como máximo tres hijos. Demuestre que para cada $n \geq 1$ todo árbol ternario no vacío de altura $n$ tiene como máximo $\dfrac{(3^n 1)}{2}$ nodos.

Estoy confuso sobre qué hacer aquí, ¿puede alguien explicarme la pregunta y cómo resolverla por inducción?

Answer 1

El caso en que $n=1$ está claro. Supongamos que la hipótesis se cumple para algún $n \geq 1$ . Entonces, para el caso de un árbol ternario de altura $n+1$ tenemos el subárbol $n$ con un máximo de $\frac {(3^{n}-1)}{2}$ nodos. Para la ampliación del árbol en el paso $n+1$ vemos que cada uno de los nodos anteriores en el paso $n$ puede tener como máximo $3$ nodos hijos por la definición de un árbol ternario. Así, para el $n+1$ tenemos $\frac{3^{n}-1}{2} + 3($ # Número de nodos en el paso $n$ del árbol $) \leq \frac{3^{n}-1}{2} + 3(3^{n-1})=\frac{3^{n}-1}{2} + 3^{n} = \frac{3^{n}-1}{2} +\frac{2(3^{n})}{2} = \frac{3(3^{n}) -1}{2}=\frac {3^{n+1}-1}{2}$ .

Por lo tanto, el número máximo de nodos para un árbol de altura $n+1 \leq \frac{3^{n+1}-1}{2}$ . La primera desigualdad con $3^{n-1}$ proviene del hecho de que este problema puede transformarse en uno relativo a una serie geométrica finita, más concretamente a la serie siguiente: $1+3+3^2+...+3^{n-1}+3^n$ para un árbol de altura $n+1$ .