Demonstre que o número de elementos em qualquer OLista de profundidade
é
. (Use indução em
.)
Passo 1
O enunciado pede que demonstremos, por indução no inteiro
, que toda OLista de profundidade
possui exatamente
elementos. Vamos usar a definição recursiva de OLista:
- Uma OLista de profundidade
tem um único elemento. - Para
, uma OLista de profundidade é formada pela concatenação de duas OListas de profundidade .
Passo 2
Base da indução (
):
Por hipótese de definição, uma OLista de profundidade tem exatamente
elemento. Como
Por hipótese de definição, uma OLista de profundidade
a propriedade vale para
.
Passo 3
Passo indutivo: suponha que a propriedade valha para
, isto é, toda OLista de profundidade
tem
elementos. Considere então uma OLista de profundidade
.
Pela definição recursiva, ela é composta por duas OListas independentes de profundidade . Pelo passo indutivo cada uma dessas sublistas tem
elementos, logo o total é
Pela definição recursiva, ela é composta por duas OListas independentes de profundidade
Portanto, a propriedade vale para
.
Passo 4
Concluímos, pelo princípio da indução matemática, que para todo inteiro
qualquer OLista de profundidade
possui exatamente
elementos.
Resposta
Para todo
, o número de elementos em qualquer OLista de profundidade
é
.