Principio d'induzione
Ho due esercizi che non riesco a risolvere:
1) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0, y, z) = z \times y[/tex]
[tex]f(x + 1, y, z) = z + f(x, y, z)[/tex]
è tale che, per ogni [tex]x, y, z \in N[/tex]
[tex]f(x, y, z) = (x+ y) \times z[/tex]
2) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0) = 1[/tex]
[tex]f(n + 1) = f(n) + f(n)[/tex]
è tale che, per ogni [tex]n \in N[/tex]
[tex]f(n) = 2^n[/tex]
Per entrambi considero come Base la prima eq. che c'è nel sistema e come Passo induttivo cosa metto come ipotesi e come tesi? Come si svolge?
Grazie mille
1) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0, y, z) = z \times y[/tex]
[tex]f(x + 1, y, z) = z + f(x, y, z)[/tex]
è tale che, per ogni [tex]x, y, z \in N[/tex]
[tex]f(x, y, z) = (x+ y) \times z[/tex]
2) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0) = 1[/tex]
[tex]f(n + 1) = f(n) + f(n)[/tex]
è tale che, per ogni [tex]n \in N[/tex]
[tex]f(n) = 2^n[/tex]
Per entrambi considero come Base la prima eq. che c'è nel sistema e come Passo induttivo cosa metto come ipotesi e come tesi? Come si svolge?
Grazie mille
Risposte
"vfldj":
Ho due esercizi che non riesco a risolvere:
1) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0, y, z) = z \times y[/tex]
[tex]f(x + 1, y, z) = z + f(x, y, z)[/tex]
è tale che, per ogni [tex]x, y, z \in N[/tex]
[tex]f(x, y, z) = (x+ y) \times z[/tex]
2) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0) = 1[/tex]
[tex]f(n + 1) = f(n) + f(n)[/tex]
è tale che, per ogni [tex]n \in N[/tex]
[tex]f(n) = 2^n[/tex]
Per entrambi considero come Base la prima eq. che c'è nel sistema e come Passo induttivo cosa metto come ipotesi e come tesi? Come si svolge?
Grazie mille
devi verificare che la base funzioni, comunque.
ad esempio, nel secondo:
base: \(f(0)=1=2^0\) ok
passo: \(f(n)=2^n\)
\(f(n+1)=f(n)+f(n)=2^n+2^n=2\cdot2^n=2^{n+1}\) ok
"albertobosia":
devi verificare che la base funzioni, comunque.
ad esempio, nel secondo:
base: \(f(0)=1=2^0\) ok
passo: \(f(n)=2^n\)
\(f(n+1)=f(n)+f(n)=2^n+2^n=2\cdot2^n=2^{n+1}\) ok
Grazie per la risposta.
Quindi [tex]f(n)=2^n[/tex] è l'ipotesi del passo induttivo e la tesi è [tex]f(n+1)=f(n)+f(n)[/tex]?
In ogni problema di questo genere quindi la tesi è la seconda eq. che c'è nel sistema?
Stavo guardando l'es 2 qui http://corsiadistanza.polito.it/corsi/pdf/9335N/eserc1.pdf
Come arriva a dire [tex]2 \cdot n![/tex]?
E nell'esercizio 8 qui http://www.mat.unimi.it/users/massa/eserind.pdf come fa a dimostrare la tesi? Non capisco i passaggi
Come si svolge quest'esercizio?
Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
[tex]f(0) = 0[/tex]
[tex]f(s(n)) = s(s(f(n)))[/tex]
dove [tex]s(n) = n + 1[/tex], si dimostri che [tex]\forall n \in N . f(n) = 2n[/tex]
Come base metto [tex]f(0) = 0 = 2 \cdot 0[/tex]. Nel passo induttivo invece considero come ipotesi [tex]f(n) = 2n[/tex] e come tesi [tex]f(s(n)) = s(s(f(n)))[/tex]. So che [tex]f(s(n)) = f(n + 1)[/tex] e poi come procedo? E' un pò incasinata
Grazie ancora
Nessuno mi può aiutare?
E' importante..
\(f(s(n))=s(s(f(n)))\)
riscrivilo come
\(f(n+1)=f(n)+2\)
il tuo passo induttivo è
\(f(n+1)=f(n)+2=2n+2=2(n+1)\)
riscrivilo come
\(f(n+1)=f(n)+2\)
il tuo passo induttivo è
\(f(n+1)=f(n)+2=2n+2=2(n+1)\)
Grazie 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo