Seja L uma lista, como na Definição 3.3. Defina uma função numérica f como se segue.
B. Se L=x, um único elemento, então f(L)=1.
R. Se L=L^prime, x para alguma lista L^prime, então f(L)=f(L^prime) 11.
(a) Mostre as etapas de um cálculo “descendente”, como no Exemplo 3.28, para encontrar o valor de f( veni, vidi, vici ).
(b) O que o valor de f(L) the diz a respeito da lista L, em geral?
(c) Demonstre a sua afirmação da parte (b), usando indução.

Passo 1

O enunciado define recursivamente uma função numérica f sobre listas L:
– Base (B): se L=lang<= xrang<= tem um único elemento, então
f(L)=1
– Recursão ®: se L=L'mathbinVertlang<= xrang<= (isto é, L é obtida de L' acrescentando-se o elemento x), então
f(L)=f(L'),11
Precisamos de (a) calcular f(lang<=veni,vidi,vicirang<=) por descida, (b) interpretar o que f(L) revela sobre L em geral e (c) provar essa interpretação por indução.

Passo 2

Para L=lang<=veni,vidi,vicirang<= fazemos descida:
f(L) = f(lang<=veni,vidirang<=),11 = l(f(lang<=venirang<=),11r),11 = (1,11),11 = 11111

Passo 3

Note que a cada elemento extraído após o primeiro somos obrigados a concatenar os dígitos 11. Se lvert Lrvert=n, o número de dígitos de f(L) é
1 + 2(n-1) ;=; 2n-1
Logo a partir de f(L) (que é um inteiro formado só por uns) podemos recuperar lvert Lrvert via
lvert Lrvert ;=;l(número de dígitos de f(L)r)+12 úí

Passo 4

Prova por indução em n=lvert Lrvert.
Base ( n=1)
Se L=lang<= xrang<= então f(L)=1 tem 2cdot1-1=1 dígito, conforme desejado.

Passo 5

Passo indutivo
Suponha que para toda lista L' com lvert L'rvert=k vale “ f(L') tem 2k-1 dígitos”. Seja agora L=L'mathbinVertlang<= xrang<= com lvert Lrvert=k+1. Então
f(L)=f(L'),11
e o número de dígitos de f(L) é
(2k-1) + 2 = 2(k+1)-1
Assim a propriedade vale para k+1 e, por indução, para todo n.

Resposta

(a) 11111\n
(b) f(L) é um inteiro formado exclusivamente por dígitos 1, de comprimento 2lvert Lrvert-1, de modo que lvert Lrvert=(dígitos de f(L)+1)/2í.\n
(c) Demonstrado por indução nos passos 4 e 5.