Induzione su più variabili
Ri-salve. 
Spero di aver azzeccato la sezione giusta, visto che questa sezione mi sembrava più adatta di sezioni come "Analisi Matematica" o "Statistica e Probabilità".
Veniamo al dunque: dovrebbe essere ormai chiaro a tanti la tecnica dimostrativa basata sul principio di induzione, si dimostra una proposizione per un certo $n_0$, la si suppone vera per $n-1$ e si dimostra che la proposizione per $n-1$ implica la proposizione per $n$.
Ma come si procede nel caso di più variabili? Faccio prima induzione su una variabile "tenendo fisse" le altre, procedendo così per tutte le variabili oppure si fa in un altro modo?
Un grazie anticipato a chi mi aiuta.
Spero di aver azzeccato la sezione giusta, visto che questa sezione mi sembrava più adatta di sezioni come "Analisi Matematica" o "Statistica e Probabilità".
Veniamo al dunque: dovrebbe essere ormai chiaro a tanti la tecnica dimostrativa basata sul principio di induzione, si dimostra una proposizione per un certo $n_0$, la si suppone vera per $n-1$ e si dimostra che la proposizione per $n-1$ implica la proposizione per $n$.
Ma come si procede nel caso di più variabili? Faccio prima induzione su una variabile "tenendo fisse" le altre, procedendo così per tutte le variabili oppure si fa in un altro modo?
Un grazie anticipato a chi mi aiuta.
Risposte
non credo ci sia un metodo standard, dipende dal problema.
se hai un esempio specifico scrivilo, se no non ti si può dire molto.
se hai un esempio specifico scrivilo, se no non ti si può dire molto.
Supponiamo che il problema sia: ci sono $n$ persone che dicono una certa cosa ad altre $k$ persone, in totale quante persone verranno a sapere tale cosa sapendo che ciascuna di queste $n$ persone dicono la cosa a persone tutte diverse fra loro?
Dimostriamo, per induzione, che il numero di persone è pari a $x = n(k+1)$, io procedo così:
Fissando $k$ e agendo per induzione su $n$:
$n = 1$
$x = k + 1$, cio è ragionevole poiché una persona dice la cosa ad altre $k$ persone e dunque $k+1$ persone sanno il fattarello (Le $k$ persone più la persona che ha detto il fattarello ovviamente)
Supponendo vera la tesi per $n-1$ mi accingo a dimostrare che ciò implica la veridicità della tesi per $n$, dunque $x = (n-1)(k+1)$.
Ora arriva un altra persona e dice il fatto ad altre $k$ persone dunque $x = (n-1)(k+1) + (k+1) = n(k+1)$ e ciò implica la tesi.
La dimostrazione per $k$ avviene (dovrebbe) nello stesso identico modo, si tiene "ferma" la $n$ e si applica il principio d'induzione per $k$.
Io mi chiedevo:
1. Questa dimostrazione è valida?
2. Tutte le dimostrazioni con più variabili intere possono essere dimostrate in questo modo?
Dimostriamo, per induzione, che il numero di persone è pari a $x = n(k+1)$, io procedo così:
Fissando $k$ e agendo per induzione su $n$:
$n = 1$
$x = k + 1$, cio è ragionevole poiché una persona dice la cosa ad altre $k$ persone e dunque $k+1$ persone sanno il fattarello (Le $k$ persone più la persona che ha detto il fattarello ovviamente
)Supponendo vera la tesi per $n-1$ mi accingo a dimostrare che ciò implica la veridicità della tesi per $n$, dunque $x = (n-1)(k+1)$.
Ora arriva un altra persona e dice il fatto ad altre $k$ persone dunque $x = (n-1)(k+1) + (k+1) = n(k+1)$ e ciò implica la tesi.
La dimostrazione per $k$ avviene (dovrebbe
) nello stesso identico modo, si tiene "ferma" la $n$ e si applica il principio d'induzione per $k$.Io mi chiedevo:
1. Questa dimostrazione è valida?
2. Tutte le dimostrazioni con più variabili intere possono essere dimostrate in questo modo?
non ci sono più variabili in questo problema, infatti quando dimostri per induzione su $n$ tieni fisso $k$, e quando dimostri per induzione su $k$ tieni fisso $n$.
non ti fare di questi problemi sulla generalizzazione dell'induzione in più variabili, affronta ogni problema come meglio credi, e basta, non ti serve altro credimi.
non ti fare di questi problemi sulla generalizzazione dell'induzione in più variabili, affronta ogni problema come meglio credi, e basta, non ti serve altro credimi.
"blackbishop13":
non ci sono più variabili in questo problema, infatti quando dimostri per induzione su $n$ tieni fisso $k$, e quando dimostri per induzione su $k$ tieni fisso $n$.
non ti fare di questi problemi sulla generalizzazione dell'induzione in più variabili, affronta ogni problema come meglio credi, e basta, non ti serve altro credimi.
Ma infatti io non voglio farmi problemi che non posso risolvere, anzi volevo sapere se in generale questa strategia di risoluzione è valida (Così da avere un metodo di approccio unico per tutti i problemi di questo tipo
), e da come mi hai risposto la risposta è senz'altro sì. Dunque grazie.
Se non ricordo male, l'induzione su due variabili si usa quando si vuole dimostrare che l'operazione di somma sui naturali è commutativa.
Vero, WiZ? (Dovrebbe essere su quelle famose vecchie dispense del Nappi...)
Vero, WiZ? (Dovrebbe essere su quelle famose vecchie dispense del Nappi...)
@gugo82
Sì.
Sì.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo