Dimostrare per induzione che 2=3
Se ho capito bene, la dimostrazione per induzione funziona così:
Data una proposizione P, per dimostrare che è vera per ogni numero, si dimostra P(0) e l implicazione P(n)=>P(n+1).
Ora però sorge un problema.
Per quanto riguarda la seconda parte della qeustione, ciò significa che dobbiamo assumere come vera P(n) (ovvero come ipotesi) e vedere se vale anche per un numero successivo.
Ma ciò non ha senso, perchè se assumiamo l ipotesi P(n) allora stiamo assumendo per vero il fatto che per ogni n vale P(n), dunque ciò varrà anche per P(n+1).
Un esempio sul quale mi sto contorcendo da qualche giorno:
Vogliamo dimostrare che il doppio di ogni numero n è uguale al suo triplo (cosa palesemente falsa).
Dunque:
P(n): 2n=3n
DIM:
p(0): 2*0 = 3*0
Vero.
Passiamo alla seconda parte:
P(n+1): 2(n+1)=3(n+1)
ma se assumiamo per vera Pn, per forza anche questa sarà vera.
Non capisco davvero cosa vuol dire quella seconda parte della dim per induzione...
[mod="Martino"]Sposto in algebra.[/mod]
Data una proposizione P, per dimostrare che è vera per ogni numero, si dimostra P(0) e l implicazione P(n)=>P(n+1).
Ora però sorge un problema.
Per quanto riguarda la seconda parte della qeustione, ciò significa che dobbiamo assumere come vera P(n) (ovvero come ipotesi) e vedere se vale anche per un numero successivo.
Ma ciò non ha senso, perchè se assumiamo l ipotesi P(n) allora stiamo assumendo per vero il fatto che per ogni n vale P(n), dunque ciò varrà anche per P(n+1).
Un esempio sul quale mi sto contorcendo da qualche giorno:
Vogliamo dimostrare che il doppio di ogni numero n è uguale al suo triplo (cosa palesemente falsa).
Dunque:
P(n): 2n=3n
DIM:
p(0): 2*0 = 3*0
Vero.
Passiamo alla seconda parte:
P(n+1): 2(n+1)=3(n+1)
ma se assumiamo per vera Pn, per forza anche questa sarà vera.
Non capisco davvero cosa vuol dire quella seconda parte della dim per induzione...
[mod="Martino"]Sposto in algebra.[/mod]
Risposte
C'è un errore concettuale nella dimostrazione del passo induttivo. Vediamo l'errore nel tuo caso:
Supporre che è vera P(n), significa che per questo numero generico $n$ vale la proprietà, cioè
$2n=3n$
Ma ciò non significa che vale per tutti i numeri, ma solo per questo generico $n$! Otterresti
$2(n+1)=2n+2=3n+2$ che è diverso da $3(n+1)=3n+3$ !!!
Quindi non si riesce a dimostrare il passo induttivo.
Di solito si dice che fare un ragionamento per induzione è come far cadere le tessere di un domino; per far cadere tutte le tessere devi essere in grado:
- di buttare giù la prima tessera P(0)
- se ne cade una, cade anche la successiva P(n) implica P(n+1)
Il tuo errore è nella dimostrazione del passo induttivo: esso non corrisponde a chiedere che se cadono tutte allora cadono tutte (questo è ovvio, non è alcuna richiesta aggiuntiva!)
Ciao, spero di averti aiutato!
Supporre che è vera P(n), significa che per questo numero generico $n$ vale la proprietà, cioè
$2n=3n$
Ma ciò non significa che vale per tutti i numeri, ma solo per questo generico $n$! Otterresti
$2(n+1)=2n+2=3n+2$ che è diverso da $3(n+1)=3n+3$ !!!
Quindi non si riesce a dimostrare il passo induttivo.
Di solito si dice che fare un ragionamento per induzione è come far cadere le tessere di un domino; per far cadere tutte le tessere devi essere in grado:
- di buttare giù la prima tessera P(0)
- se ne cade una, cade anche la successiva P(n) implica P(n+1)
Il tuo errore è nella dimostrazione del passo induttivo: esso non corrisponde a chiedere che se cadono tutte allora cadono tutte (questo è ovvio, non è alcuna richiesta aggiuntiva!)
Ciao, spero di averti aiutato!
"Hop Frog":
...Passiamo alla seconda parte:
P(n+1): 2(n+1)=3(n+1)
ma se assumiamo per vera Pn, per forza anche questa sarà vera.
Se P(n): $2n=3n$ è vera allora P(n+1): $ 2(n+1)=3(n+1) \Rightarrow 2n+2=3n+3 \Rightarrow 2=3$ è falsa.
Dunque l'implicazione $\forall n [P(n) \Rightarrow P(n+1)]$ è falsa.
@Hop Frog
Il problema sta nello scrivere correttamente il "passo induttivo". Tu dici: "e l implicazione P(n)=>P(n+1)."
Ma è importante specificare per bene!!
Mettiamoci d'accordo sul fatto che $NN = {0,1,2,...}$ (per evitare equivoci).
Per provare che una proprietà $P(n)$ vale per ogni $n \in NN$, si può usare il cosiddetto "metodo per induzione".
Ovvero, si ritiene equivalente riuscire a dimostrare la validità di queste 2 proposizioni:
- $P(0)$ è vera $\quad\quad$ [BASE]
- $AA n \in NN\ : \ [P(n) \implies P(n+1)]$ $\quad$ [PASSO INDUTTIVO]
Ora, tu, proprio per una non adeguata specificazione del passo induttivo, lo interpreti così:
- $[AA n \in NN \ P(n)] \implies [AA n \in NN \ P(n+1)]$
Ma questa è ben altra cosa! Ed anzi si riduce ad una banalità (se P vale in tutto $NN$, ovviamente varrà per ${1,2,3,...}$
Il problema sta nello scrivere correttamente il "passo induttivo". Tu dici: "e l implicazione P(n)=>P(n+1)."
Ma è importante specificare per bene!!
Mettiamoci d'accordo sul fatto che $NN = {0,1,2,...}$ (per evitare equivoci).
Per provare che una proprietà $P(n)$ vale per ogni $n \in NN$, si può usare il cosiddetto "metodo per induzione".
Ovvero, si ritiene equivalente riuscire a dimostrare la validità di queste 2 proposizioni:
- $P(0)$ è vera $\quad\quad$ [BASE]
- $AA n \in NN\ : \ [P(n) \implies P(n+1)]$ $\quad$ [PASSO INDUTTIVO]
Ora, tu, proprio per una non adeguata specificazione del passo induttivo, lo interpreti così:
- $[AA n \in NN \ P(n)] \implies [AA n \in NN \ P(n+1)]$
Ma questa è ben altra cosa! Ed anzi si riduce ad una banalità (se P vale in tutto $NN$, ovviamente varrà per ${1,2,3,...}$
Avrei altri dubbi sulla dimostrazione per induzione, quindi li metto qui.
Innanzitutto noi sappiamo che per i due punti P(0) e P(n)=>P(n+1) può venir dimostrato un qualsiasi (o quasi) teorema sui numeri naturali..
dunque:
domanda 1: se inoltre io dimostrassi che P(n)=>P(n-1) potrei estendere la dimostrazione ai numeri Z?
domanda 2: se si, esisterebbe un modo per estendere anche la cosa ai numeri Q e addirittura R?
domanda 3: se, stando nel campo dei numeri naturali, ho un affermazione che dipende da due variabili, posso comunque applicare il suddetto processo (per esempio dimostrare che per ogni n,m appartenenti a N, n+m>m)
Innanzitutto noi sappiamo che per i due punti P(0) e P(n)=>P(n+1) può venir dimostrato un qualsiasi (o quasi) teorema sui numeri naturali..
dunque:
domanda 1: se inoltre io dimostrassi che P(n)=>P(n-1) potrei estendere la dimostrazione ai numeri Z?
domanda 2: se si, esisterebbe un modo per estendere anche la cosa ai numeri Q e addirittura R?
domanda 3: se, stando nel campo dei numeri naturali, ho un affermazione che dipende da due variabili, posso comunque applicare il suddetto processo (per esempio dimostrare che per ogni n,m appartenenti a N, n+m>m)
1) io non l'ho mai visto fare, quindi non saprei;
2) no: in $QQ$ ed $RR$ se vuoi provare che una cosa vale $\forall x \in QQ$ oppure $\forall x \in RR$, supponi $x$ generico senza richiedere particolari proprietà;
3) prima appichi l'induzione su una variabile e poi sull'altra, nel caso tu voglia applicare una doppia induzione, ma nella maggior parte dei casi non occorre, difatti in alcuni casi puoi omettere la seconda induzione per la simmetria dei ruoi delle variabili, oppure perché puoi introdurre una unica variabile che le sostituisca entrambe e indurre con essa.
2) no: in $QQ$ ed $RR$ se vuoi provare che una cosa vale $\forall x \in QQ$ oppure $\forall x \in RR$, supponi $x$ generico senza richiedere particolari proprietà;
3) prima appichi l'induzione su una variabile e poi sull'altra, nel caso tu voglia applicare una doppia induzione, ma nella maggior parte dei casi non occorre, difatti in alcuni casi puoi omettere la seconda induzione per la simmetria dei ruoi delle variabili, oppure perché puoi introdurre una unica variabile che le sostituisca entrambe e indurre con essa.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo