Principio di induzione 02
Ciao,
Ex: Dimostrare per induzione la formula della progressione geometrica:
$\sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(x + 1))/(1 - x)$
dove n è un numero intero naturale e x è un numero(reale o complesso),
diverso da 1, detto la ragione della progressione.
Risoluzione:
Il principio di induzione e' che $AAn p(n)=> p(n+1)$ e' vera.
Con $p(n) = \sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$
si controlla subito che con $p(0)$ e' vera, adesso ponendo la formula $p(n+1)$ abbiamo:
$\sum_{k=0}^(n + 1) x^k =\sum_{k=0}^n x^k + x^(k+1)$ = (ipotesi di induzione)
$(1 - x^(n+ 1))/(1 - x) + x^(n + 1) = (1 - x^(n + 1) + (x^(n + 1))*(1 - x))/(1 - x)=$
$ (1 - x^(n + 1) + x^(n + 1) - x^(n + 2))/(x - 1)= (1 - x^(n + 2))/(1 - x)$
quindi anche con $p(n + 1)? non e' vero???
help dove sbaglio??
Ex: Dimostrare per induzione la formula della progressione geometrica:
$\sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(x + 1))/(1 - x)$
dove n è un numero intero naturale e x è un numero(reale o complesso),
diverso da 1, detto la ragione della progressione.
Risoluzione:
Il principio di induzione e' che $AAn p(n)=> p(n+1)$ e' vera.
Con $p(n) = \sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$
si controlla subito che con $p(0)$ e' vera, adesso ponendo la formula $p(n+1)$ abbiamo:
$\sum_{k=0}^(n + 1) x^k =\sum_{k=0}^n x^k + x^(k+1)$ = (ipotesi di induzione)
$(1 - x^(n+ 1))/(1 - x) + x^(n + 1) = (1 - x^(n + 1) + (x^(n + 1))*(1 - x))/(1 - x)=$
$ (1 - x^(n + 1) + x^(n + 1) - x^(n + 2))/(x - 1)= (1 - x^(n + 2))/(1 - x)$
quindi anche con $p(n + 1)? non e' vero???
help dove sbaglio??
Risposte
Sbagli nel dire
Il principio di induzione dice che dato $S \subseteq NN$, se $0 in S$ e $n in S => n+1 in S$, allora $S=NN$.
"giordi22":
Il principio di induzione e' che $EEn p(n)=>p(n+1)$
Il principio di induzione dice che dato $S \subseteq NN$, se $0 in S$ e $n in S => n+1 in S$, allora $S=NN$.
"giordi22":
Ciao,
Ex: Dimostrare per induzione la formula della progressione geometrica:
$\sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(x + 1))/(1 - x)$
dove n è un numero intero naturale e x è un numero(reale o complesso),
diverso da 1, detto la ragione della progressione.
Risoluzione:
Il principio di induzione e' che $EEn p(n)=> p(n+1)$ e' vera.
Con $p(n) = \sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$
si controlla subito che con $p(0)$ e' vera, adesso ponendo la formula $p(n+1)$ abbiamo:
$\sum_{k=0}^(n + 1) x^k =\sum_{k=0}^n x^k + x^(k+1)$ = (ipotesi di induzione)
$(1 - x^(n+ 1))/(1 - x) + x^(n + 1) = (1 - x^(n + 1) + (x^(n + 1))*(1 - x))/(1 - x)=$
$ (1 - x^(n + 1) + x^(n + 1) - x^(n + 2))/(x - 1)= (1 - x^(n + 2))/(1 - x)$
quindi anche con $p(n + 1)? non e' vero???
help dove sbaglio??
non hai mica sbagliato
tu hai trovato che
$\sum_{k=0}^(n + 1) x^k ==(1-x^(n+2))/(1-x)==(1 - x^((n + 1)+1))/(1 - x)$
quel $n+2$ all'esponente di x è giusto, perché è esattamente $(n+1)+1$ così come nel caso $n$ avevi $n+1$ all'esponente di x
siccome ho visto che anche nell'altro topic c'era un po' di confusione a riguardo, provo a spiegarlo così:
l'induzione è un principio che sfrutta la sequenzialità dei numeri $NN$. Tecnicamente funziona così:
Caso base: provi la proposizione per un n in particolare.
Caso base: provi che se è vero per un numero, è vero anche per il SUCCESSIVO (nota bene).
Quindi così come procedi?
Tu sai che è la proposizione è vera per $P(0)$, per esempio. Sai che $P(n)\rArr P(n+1)$, e se banalmente poni $n=0$ allora sai che $P(0)$ è vera, e dal passo induttivo sai che così anche $P(0+1)$ lo è. E così via, poi poni n=1, n=2 e si può andare avanti così all'infinito.
adesso ti propongo una dimostrazione per induzione sbagliata:
circola sul web una nota dimostrazione per induzione che dice che li uomini sono tutti senza orecchie
la dimostrazione procede così:
Caso base: n=0. 0 uomini sono senza orecchie, banale.
Induzione: poniamo che n siano senza orecchie per ipotesi. vediamo cosa succede a n+1. però se prendi n-1 uomini togliendo l'n-esimo che sono senza orecchie per ipotesi, e gli affianchi l'n+1-esimo uomo di cui non sappiamo ancora niente, abbiamo n uomini che però sono senza orecchie per ipotesi. Dunque anche l'n+1-esimo sono senza orecchie.
Dove sta lo sbaglio? lo sbaglio sta non nel caso base, ma nel passo induttivo. perché l'ipotesi non dice che è vera per n oggetti (o equivalentemente per n numeri naturali qualsiasi) ma per i PRIMI n oggetti sequenziali (ossia per i primi n numeri naturali). Quindi l'azione di buttare via l'n-esimo uomo e di prendere l'n+1-esimo ti manda in malora l'ipotesi.
perché ti ho detto questa scemenza?
perché quando devi dimostrare che è vera per n+1 per il passo induttivo (come dovevi provare tu per la serie geometrica) devi sempre pensare di porre un ipotetico $m=n+1$ alla fine e quindi hai che $m$ è il successivo di $n$, e se hai la stessa identica conclusione allora sei a posto
infatti, prima, se $m=n+1$ allora
$(1-x^(n+2))/(1-x)=(1-x^(m+1))/(1-x)$
cioè per il successivo di n hai la stessa cosa che ti capitava con n
l'induzione è un principio che sfrutta la sequenzialità dei numeri $NN$. Tecnicamente funziona così:
Caso base: provi la proposizione per un n in particolare.
Caso base: provi che se è vero per un numero, è vero anche per il SUCCESSIVO (nota bene).
Quindi così come procedi?
Tu sai che è la proposizione è vera per $P(0)$, per esempio. Sai che $P(n)\rArr P(n+1)$, e se banalmente poni $n=0$ allora sai che $P(0)$ è vera, e dal passo induttivo sai che così anche $P(0+1)$ lo è. E così via, poi poni n=1, n=2 e si può andare avanti così all'infinito.
adesso ti propongo una dimostrazione per induzione sbagliata:
circola sul web una nota dimostrazione per induzione che dice che li uomini sono tutti senza orecchie
la dimostrazione procede così:Caso base: n=0. 0 uomini sono senza orecchie, banale.
Induzione: poniamo che n siano senza orecchie per ipotesi. vediamo cosa succede a n+1. però se prendi n-1 uomini togliendo l'n-esimo che sono senza orecchie per ipotesi, e gli affianchi l'n+1-esimo uomo di cui non sappiamo ancora niente, abbiamo n uomini che però sono senza orecchie per ipotesi. Dunque anche l'n+1-esimo sono senza orecchie.
Dove sta lo sbaglio? lo sbaglio sta non nel caso base, ma nel passo induttivo. perché l'ipotesi non dice che è vera per n oggetti (o equivalentemente per n numeri naturali qualsiasi) ma per i PRIMI n oggetti sequenziali (ossia per i primi n numeri naturali). Quindi l'azione di buttare via l'n-esimo uomo e di prendere l'n+1-esimo ti manda in malora l'ipotesi.
perché ti ho detto questa scemenza?
perché quando devi dimostrare che è vera per n+1 per il passo induttivo (come dovevi provare tu per la serie geometrica) devi sempre pensare di porre un ipotetico $m=n+1$ alla fine e quindi hai che $m$ è il successivo di $n$, e se hai la stessa identica conclusione allora sei a postoinfatti, prima, se $m=n+1$ allora
$(1-x^(n+2))/(1-x)=(1-x^(m+1))/(1-x)$
cioè per il successivo di n hai la stessa cosa che ti capitava con n
Ciao,
ecco dove mi bloccavo!!
con $m = n + 1$ il risultato non cambia!
grazie, alla prossima induzione....
ecco dove mi bloccavo!!
con $m = n + 1$ il risultato non cambia!
grazie, alla prossima induzione....
"WiZaRd":
Sbagli nel dire
[quote="giordi22"]
Il principio di induzione e' che $EEn p(n)=>p(n+1)$
Il principio di induzione dice che dato $S \subseteq NN$, se $0 in S$ e $n in S => n+1 in S$, allora $S=NN$.[/quote]
giusto $AAn p(n)=>p(n+1)$ errore di battitura...
Si ma questa condizione da sola non è sufficiente.
"WiZaRd":
Si ma questa condizione da sola non è sufficiente.
quindi devo sistemare ancora l'esercizio...
No. Ci tengo che tu abbia bene a mente che la proprietà va verificata prima per $0$ (o per $1$) e poi, sopponendola vera per $n$, la si verifica per $n+1$.
"WiZaRd":
No. Ci tengo che tu abbia bene a mente che la proprietà va verificata prima per $0$ (o per $1$) e poi, sopponendola vera per $n$, la si verifica per $n+1$.
be', in realtà il caso base dipende dall'enunciato del teorema che si intende dimostrare
Giusto.
"Rinhos":
[quote="WiZaRd"]No. Ci tengo che tu abbia bene a mente che la proprietà va verificata prima per $0$ (o per $1$) e poi, sopponendola vera per $n$, la si verifica per $n+1$.
be', in realtà il caso base dipende dall'enunciato del teorema che si intende dimostrare
[/quote]E vabbe' riscriviamo il tutto...
Ex: Dimostrare per induzione la formula della progressione geometrica:
$\sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$
dove n è un numero intero naturale e x è un numero(reale o complesso),
diverso da 1, detto la ragione della progressione.
Risoluzione:
Il principio di induzione e' che $AAn p(n)=> p(n+1)$ e' vera.
Si ha con $n >= 0$ e $p(n) = \sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$.
Si controlla subito che con $p(0)$ e' vera; per mostrare che l'implicazione $AAn p(n)=> p(n+1)$
e' vera occore verificare che da
$\sum_{k=0}^(n + 1) x^k =\sum_{k=0}^n x^k + x^(k+1)$ = (ipotesi di induzione)
$(1 - x^(n+ 1))/(1 - x) + x^(n + 1) = (1 - x^(n + 1) + (x^(n + 1))*(1 - x))/(1 - x)=$
$ (1 - x^(n + 1) + x^(n + 1) - x^((n + 1) + 1))/(x - 1)= (1 - x^((n + 1) + 1))/(1 - x)$
Ragazzi, devo concludere di essere stato esaustivo...
Possiamo giuducare il topic soddisfatto???
"giordi22":
Il principio di induzione e' che $AAn p(n)=> p(n+1)$ e' vera.
E' qui che sbagli. Il principio di induzione non si esaurisce con $\forall n, p(n) => p(n+1)$: solo questo enunciato non include il fatto che si debba verificare essere vera $p(0)$. Il principio di induzione è $p(0) ^^^ [p(n)=>p(n+1)]$, se bisogna iniziare la prova con $0$.
"WiZaRd":
[quote="giordi22"]
Il principio di induzione e' che $AAn p(n)=> p(n+1)$ e' vera.
E' qui che sbagli. Il principio di induzione non si esaurisce con $\forall n, p(n) => p(n+1)$: solo questo enunciato non include il fatto che si debba verificare essere vera $p(0)$. Il principio di induzione è $p(0) ^^^ [p(n)=>p(n+1)]$, se bisogna iniziare la prova con $0$.[/quote]
Ex: Dimostrare per induzione la formula della progressione geometrica:
$\sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$
dove n è un numero intero naturale e x è un numero(reale o complesso),
diverso da 1, detto la ragione della progressione.
Risoluzione:
Il principio di induzione e' che $p(0) ^^^ [p(n)=> p(n+1)]$ e' vera.
Si ha con $n >= 0$ e $p(n) = \sum_{k=0}^n x^k =1 + x + x^2 + ... + x^n = (1 - x^(n + 1))/(1 - x)$.
Si controlla subito che con $p(0)$ e' vera; per mostrare che l'implicazione $p(n)=> p(n+1)$
e' vera occore verificare che da
$\sum_{k=0}^(n + 1) x^k =\sum_{k=0}^n x^k + x^(k+1)$ = (ipotesi di induzione)
$(1 - x^(n+ 1))/(1 - x) + x^(n + 1) = (1 - x^(n + 1) + (x^(n + 1))*(1 - x))/(1 - x)=$
$ (1 - x^(n + 1) + x^(n + 1) - x^((n + 1) + 1))/(x - 1)= (1 - x^((n + 1) + 1))/(1 - x)$
WiZaRd, grazie per la pazieza sulla mia attusaggine...
Vedi ora come va.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo