Aiuto esercizi induzione

[boss.nass]

Salve a tutti! non riesco a risolvere questi 2 esercizi di preparazione all'esame di logica. Qualcuno potrebbe aiutarmi per favore?

Esercizio 1:
Dato un linguaggio del prim'ordine \(\displaystyle L\) con simbolo funzionale binario \(\displaystyle f \) ed un simbolo di costante \(\displaystyle a \), dimostrare per induzione che per ogni \(\displaystyle n > 0 \) esiste un termine \(\displaystyle L \) che contine \(\displaystyle 2n \) occorrenze del simbolo \(\displaystyle a \)

Esercizio 2:
Una parola su un insieme \(\displaystyle A \) (l'alfabeto) è una sequenza, eventualmente vuota, di elementi di \(\displaystyle A \). Dimostrare, per induzione su \(\displaystyle n \), che esistono \(\displaystyle 2^n \) parole di lunghezza \(\displaystyle n \) sull'alfabeto \(\displaystyle \{ 0,1 \}\)

grazie a tutti in anticipo!

[spugna]

1) Per $n=1$ puoi prendere $f(a,a)$, altrimenti se $t$ è un termine con $2(n-1)$ occorrenze di $a$ va bene ad esempio $f(t,f(a,a))$.

2) Se $n=0$ c'è solo la parola vuota, altrimenti una parola di lunghezza $n$ si ottiene in modo unico dalla concatenazione di un simbolo (due possibilità) e di una parola di lunghezza $n-1$ ($2^(n-1)$ possibilità per ipotesi induttiva), e facendo il prodotto si ha la tesi.

[boss.nass]

Tutto chiarissimo! Grazie mille davvero! =D