Principio di Induzione
Non mi è chiara una cosa del principio di induzione: se io volessi dimostare che 4 è divisibile per tutti gli n+1.... questa proprietà vale per 0 , vale per 1 ma poi non più, eppure vale per due numeri consecutivi. Dov'è l'errore?
Risposte
cosa vuol dire che 4 è divisibile per tutti gli n+1?
Che quattro è divisibile per n+1, quindi per tutti i numeri(cosa ovviamente non vera).... non capisco come l'induzione possa essere valida considerando solo due numeri consecutivi....
infatti è sbagliata l'induzione in questo caso
provo a riformulare cosí:
TEO: 4 è divisibile per n, qualunque sia n
DIM: induzione
passo base: 4=1*4 ok
passo induttivo: suppongo che 4 sia divisibile per (n-1) e dimostro che è divisibile per n
sia $4=(n-1)*k$ etc...
...qua dovresti andare avanti e trovare un j t.c. $4=n*j$, ma chiaramente non riuscirai mai, perchè 4 NON è divisibile per ogni n
provo a riformulare cosí:
TEO: 4 è divisibile per n, qualunque sia n
DIM: induzione
passo base: 4=1*4 ok
passo induttivo: suppongo che 4 sia divisibile per (n-1) e dimostro che è divisibile per n
sia $4=(n-1)*k$ etc...
...qua dovresti andare avanti e trovare un j t.c. $4=n*j$, ma chiaramente non riuscirai mai, perchè 4 NON è divisibile per ogni n
ma tu hai mai visto una dimostrazione per induzione? ne conosci una per capire bene come funzionano?
@kobe
La prossima volta inverti le risposte ...
La prossima volta inverti le risposte ...
Ahahah 
Mmmm non mi é ancora molto chiaro... se j fosse 2 e n fosse 2 funzionerebbe...
Ma DEVE funzionare per tutti gli $n$ (questo vuole la tesi ...) non solo per alcuni ...
Però il consiglio è quello di rileggerti per bene cosa dice il principio di induzione ...
Però il consiglio è quello di rileggerti per bene cosa dice il principio di induzione ...
Ma come faccio ad assicurarmi che valga per n??
Per ipotesi ...
Il passo induttivo funziona così (grossolanamente ...): ipotizzi che la tesi sia verificata per un generico $n$ (quindi non uno specifico $n$ come hai fatto tu nel primo post); se utilizzando questa ipotesi riesci a dimostrare che la tesi è verificata anche per $n+1$ allora hai verificato il passo induttivo.
Se hai verificato anche il passo base allora concludi che la tesi è vera ...
Spesso quando viene presentato il principio di induzione viene fatto l'esempio del domino ... ecco, cerca in rete questo, forse ti chiarirà il concetto ...
Il passo induttivo funziona così (grossolanamente ...): ipotizzi che la tesi sia verificata per un generico $n$ (quindi non uno specifico $n$ come hai fatto tu nel primo post); se utilizzando questa ipotesi riesci a dimostrare che la tesi è verificata anche per $n+1$ allora hai verificato il passo induttivo.
Se hai verificato anche il passo base allora concludi che la tesi è vera ...
Spesso quando viene presentato il principio di induzione viene fatto l'esempio del domino ... ecco, cerca in rete questo, forse ti chiarirà il concetto ...
ti faccio un esempio, anche se dovresti averne già visti in giro
TEO: $\sum_{i=1}^n i=1+2+...+n=frac{n*(n+1)}{2}$ (nb: $\sum_{i=1}^{n-1} i= frac{(n-1)*(n-1+1)}{2}=frac{n*(n-1)}{2}$)
Verifico per n=1: $1=frac{1*(1+1)}{2}$ ok
ora suppongo vera per n-1, cioè suppongo vero che $\sum_{i=1}^{n-1} i= frac{n*(n-1)}{2}$ e dimostro che vale anche per n:
$\sum_{i=1}^n i= \sum_{i=1}^{n-1} i+ n= frac{n*(n-1)}{2}+n=frac{n^2-n+2n}{2}=frac{n^2+n}{2}=frac{n*(n+1)}{2}$
fine
di piú non so che dirti, devi studiartela tu l'induzione
TEO: $\sum_{i=1}^n i=1+2+...+n=frac{n*(n+1)}{2}$ (nb: $\sum_{i=1}^{n-1} i= frac{(n-1)*(n-1+1)}{2}=frac{n*(n-1)}{2}$)
Verifico per n=1: $1=frac{1*(1+1)}{2}$ ok
ora suppongo vera per n-1, cioè suppongo vero che $\sum_{i=1}^{n-1} i= frac{n*(n-1)}{2}$ e dimostro che vale anche per n:
$\sum_{i=1}^n i= \sum_{i=1}^{n-1} i+ n= frac{n*(n-1)}{2}+n=frac{n^2-n+2n}{2}=frac{n^2+n}{2}=frac{n*(n+1)}{2}$
fine
di piú non so che dirti, devi studiartela tu l'induzione
diciamo che il principio di induzione si può formalizzare così:
sia $P(n)$ una certa proprietà che dipende da $n$. Questa proprietà potrà valere su un determinato insieme di numeri $A={ninNN: P(n)$ \(\displaystyle vera \)$}$
il passo base ci dice di provare la veridicità della proposizione per $0$ e se $P(0)$ è vera allora $0inA$ da questo 'supponiamo' che la proposizione valga per un generico $n$ e vogliamo provare che dall'essere vera $P(n)$ riesco a dedurre che sia vera $P(n+1)$ ovvero che se $ninA$ allora $(n+1)inA$ questo principio di induzione è uno degli assiomi di Peano.
Dunque se riesci a provare che l'implicazione $P(n)=>P(n+1)$ è vera, allora l'insieme degli $n$ che rendono vera $P(n)$ è tutto l'insieme dei numeri naturali. Naturalmente si può generalizzare il concetto partendo da una 'base' che non sia $0$ ma un generico $n_0geq0$
un esempio è quello di Kobe, ora te ne mostro un altro:
dimostrare che $0^2+1^2+2^2+...+n^2=(n(n+1)(2n+1))/6$
$P(n)$ in questo caso è una proprietà della somma dei primi $n$ quadrati perfetti dei numeri naturali. Proviamo il passo base per $0$
$P(0): 0=(0(0+1)(0+2))/6$ è vera per $n=0$ e dunque $0$ rende vera la proprietà $P(n)$
ora voglio dimostrare che dall'essere vera per un generico valore $n$ posso dedurre che sia vera per il successivo di $n$, ovvero $n+1$. Questo mi direbbe che se è vera per $0$, sarà vera anche per $1$ e se è vera per $1$ sarà vera anche per $2$ e così via.
$P(n+1): 1^2+2^2+3^2+...+(n+1)^2=((n+1)(n+2)(2n+3))/6$
quì @G.D. mi fece riflettere una volta sull'errore che si commette cercando di dimostrare che sia vera direttamente su $P(n+1)$ che invece è quanto vogliamo dimostrare. Noi come 'ipotesi' abbiamo soltanto che sia vera questa:
$P(n): 1^2+2^2+...+n^2=(n(n+1)(2n+1))/2$ e dobbiamo dimostrare che possiamo ricavare $P(n+1)$.
aggiungiamo $(n+1)^2$ a entrambi i membri
$1^2+2^2+...+n^2+(n+1)^2=(n(n+1)(2n+1))/6+(n+1)^2=(n(n+1)(2n+1)+6(n+1)^2)/6$
$((n+1)(n(2n+1)+6(n+1)))/6=((n+1)(2n^2+n+6n+6))/6=((n+1)(2n^2+7n+6))/6$
smontando il polinomio.. $2(n+2)(n+3/2)=(n+2)(2n+3)$
dunque $1^2+2^2+...+(n+1)^2=((n+1)(n+2)(2n+3))/6$
questa è proprio la $P(n+1)$ che tentavamo di dimostrare. Dunque cosa abbiamo dimostrato? che dall'essere vera $P(n)$ riesco a dedurre che sia vera anche $P(n+1)$ ovvero abbiamo che:
1. $0inA$
2. $ninA => (n+1)inA$ e per l'assioma di Peano possiamo dire che $A=NN$
Probabilmente dimostrare che l'implicazione sia vera, partendo direttamente da $P(n+1)$ sarebbe un po' come dimostrare che una funzione derivabile in un punto sia ivi continua, partendo direttamente da:
$lim_(x->x_0)f(x)=f(x_0)$ ovvero dalla tesi.
Spero, che qualora lo legga G.D. non trovi nulla di sbagliato, sennò mi bastona
sia $P(n)$ una certa proprietà che dipende da $n$. Questa proprietà potrà valere su un determinato insieme di numeri $A={ninNN: P(n)$ \(\displaystyle vera \)$}$
il passo base ci dice di provare la veridicità della proposizione per $0$ e se $P(0)$ è vera allora $0inA$ da questo 'supponiamo' che la proposizione valga per un generico $n$ e vogliamo provare che dall'essere vera $P(n)$ riesco a dedurre che sia vera $P(n+1)$ ovvero che se $ninA$ allora $(n+1)inA$ questo principio di induzione è uno degli assiomi di Peano.
Dunque se riesci a provare che l'implicazione $P(n)=>P(n+1)$ è vera, allora l'insieme degli $n$ che rendono vera $P(n)$ è tutto l'insieme dei numeri naturali. Naturalmente si può generalizzare il concetto partendo da una 'base' che non sia $0$ ma un generico $n_0geq0$
un esempio è quello di Kobe, ora te ne mostro un altro:
dimostrare che $0^2+1^2+2^2+...+n^2=(n(n+1)(2n+1))/6$
$P(n)$ in questo caso è una proprietà della somma dei primi $n$ quadrati perfetti dei numeri naturali. Proviamo il passo base per $0$
$P(0): 0=(0(0+1)(0+2))/6$ è vera per $n=0$ e dunque $0$ rende vera la proprietà $P(n)$
ora voglio dimostrare che dall'essere vera per un generico valore $n$ posso dedurre che sia vera per il successivo di $n$, ovvero $n+1$. Questo mi direbbe che se è vera per $0$, sarà vera anche per $1$ e se è vera per $1$ sarà vera anche per $2$ e così via.
$P(n+1): 1^2+2^2+3^2+...+(n+1)^2=((n+1)(n+2)(2n+3))/6$
quì @G.D. mi fece riflettere una volta sull'errore che si commette cercando di dimostrare che sia vera direttamente su $P(n+1)$ che invece è quanto vogliamo dimostrare. Noi come 'ipotesi' abbiamo soltanto che sia vera questa:
$P(n): 1^2+2^2+...+n^2=(n(n+1)(2n+1))/2$ e dobbiamo dimostrare che possiamo ricavare $P(n+1)$.
aggiungiamo $(n+1)^2$ a entrambi i membri
$1^2+2^2+...+n^2+(n+1)^2=(n(n+1)(2n+1))/6+(n+1)^2=(n(n+1)(2n+1)+6(n+1)^2)/6$
$((n+1)(n(2n+1)+6(n+1)))/6=((n+1)(2n^2+n+6n+6))/6=((n+1)(2n^2+7n+6))/6$
smontando il polinomio.. $2(n+2)(n+3/2)=(n+2)(2n+3)$
dunque $1^2+2^2+...+(n+1)^2=((n+1)(n+2)(2n+3))/6$
questa è proprio la $P(n+1)$ che tentavamo di dimostrare. Dunque cosa abbiamo dimostrato? che dall'essere vera $P(n)$ riesco a dedurre che sia vera anche $P(n+1)$ ovvero abbiamo che:
1. $0inA$
2. $ninA => (n+1)inA$ e per l'assioma di Peano possiamo dire che $A=NN$
Probabilmente dimostrare che l'implicazione sia vera, partendo direttamente da $P(n+1)$ sarebbe un po' come dimostrare che una funzione derivabile in un punto sia ivi continua, partendo direttamente da:
$lim_(x->x_0)f(x)=f(x_0)$ ovvero dalla tesi.
Spero, che qualora lo legga G.D. non trovi nulla di sbagliato, sennò mi bastona
Capisco che sia un classico senza tempo, però è lo stesso esempio di Kobe ...
Ho visto la sommatoria e mi sembrava la dimostrazione dei primi quadrati(in realtà mi sono ho guardato di sfuggita )... la cambio e metto quella dei primi quadrati 
edit: fatto.
)... la cambio e metto quella dei primi quadrati edit: fatto.
non solo le uguaglianze, si possono mostrare pure le disuguaglianze
esempio stupidissimo
per $n>2$ ho $n^2>2n$, cioè il quadrato è maggiore del doppio
verifico per n=3: 3*3>2*3 ok
ora suppongo vera per n-1 e dimostro per n
$(n-1)^2>2*(n-1)$ cioè $n^2-2n+1>2n-2$ quindi $n^2>4n-1>2n$
devo solo far vedere che vale effettivamente $4n-1>2n$ (per n>2)
ho $n>2 => 2n>4 => 4n>2n+4 => 4n-1>2n+3>2n$
esempio stupidissimo
per $n>2$ ho $n^2>2n$, cioè il quadrato è maggiore del doppio
verifico per n=3: 3*3>2*3 ok
ora suppongo vera per n-1 e dimostro per n
$(n-1)^2>2*(n-1)$ cioè $n^2-2n+1>2n-2$ quindi $n^2>4n-1>2n$
devo solo far vedere che vale effettivamente $4n-1>2n$ (per n>2)
ho $n>2 => 2n>4 => 4n>2n+4 => 4n-1>2n+3>2n$
@Kobe
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo