Demonstre que o número de elementos em qualquer OLista de profundidade p é 2^p. (Use indução em p.)

Passo 1

O enunciado pede que demonstremos, por indução no inteiro p, que toda OLista de profundidade p possui exatamente 2^p elementos. Vamos usar a definição recursiva de OLista:
  1. Uma OLista de profundidade 0 tem um único elemento.
  2. Para p>0, uma OLista de profundidade p é formada pela concatenação de duas OListas de profundidade p-1.

Passo 2

Base da indução ( p=0):
Por hipótese de definição, uma OLista de profundidade 0 tem exatamente 1 elemento. Como
2^0 = 1,
a propriedade vale para p=0.

Passo 3

Passo indutivo: suponha que a propriedade valha para p=k, isto é, toda OLista de profundidade k tem 2^k elementos. Considere então uma OLista de profundidade k+1.
Pela definição recursiva, ela é composta por duas OListas independentes de profundidade k. Pelo passo indutivo cada uma dessas sublistas tem 2^k elementos, logo o total é
2^k + 2^k ;=; 2cdot 2^k ;=; 2^k+1
Portanto, a propriedade vale para p=k+1.

Passo 4

Concluímos, pelo princípio da indução matemática, que para todo inteiro p>=0 qualquer OLista de profundidade p possui exatamente 2^p elementos.

Resposta

Para todo p, o número de elementos em qualquer OLista de profundidade p é 2^p.

Exercícios de Livros Relacionados