Principio d'induzione

[vfldj]

Ho due esercizi che non riesco a risolvere:

1) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
\( \displaystyle f(0, y, z) = z \times y \)
\( \displaystyle f(x + 1, y, z) = z + f(x, y, z) \)

è tale che, per ogni \( \displaystyle x, y, z \in N \)

\( \displaystyle f(x, y, z) = (x+ y) \times z \)



2) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
\( \displaystyle f(0) = 1 \)
\( \displaystyle f(n + 1) = f(n) + f(n) \)

è tale che, per ogni \( \displaystyle n \in N \)

\( \displaystyle f(n) = 2^n \)


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

[albertobosia]

Ho due esercizi che non riesco a risolvere:

1) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
\( \displaystyle f(0, y, z) = z \times y \)
\( \displaystyle f(x + 1, y, z) = z + f(x, y, z) \)

è tale che, per ogni \( \displaystyle x, y, z \in N \)

\( \displaystyle f(x, y, z) = (x+ y) \times z \)



2) Dimostrare per induzione che la funzione definita dalle clausole (in sistema)
\( \displaystyle f(0) = 1 \)
\( \displaystyle f(n + 1) = f(n) + f(n) \)

è tale che, per ogni \( \displaystyle n \in N \)

\( \displaystyle f(n) = 2^n \)


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

[vfldj]

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 \( \displaystyle f(n)=2^n \) è l'ipotesi del passo induttivo e la tesi è \( \displaystyle f(n+1)=f(n)+f(n) \) ?
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 \( \displaystyle 2 \cdot n! \) ?

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)
\( \displaystyle f(0) = 0 \)
\( \displaystyle f(s(n)) = s(s(f(n))) \)
dove \( \displaystyle s(n) = n + 1 \) , si dimostri che \( \displaystyle \forall n \in N . f(n) = 2n \)

Come base metto \( \displaystyle f(0) = 0 = 2 \cdot 0 \) . Nel passo induttivo invece considero come ipotesi \( \displaystyle f(n) = 2n \) e come tesi \( \displaystyle f(s(n)) = s(s(f(n))) \) . So che \( \displaystyle f(s(n)) = f(n + 1) \) e poi come procedo? E' un pò incasinata

Grazie ancora

[vfldj]

Nessuno mi può aiutare?

[vfldj]

E' importante..

[albertobosia]

\(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)\)

[vfldj]

Grazie