Induzione
Sto dando un'occhiata al principio di induzione, che non abbiamo fatto (e non credo lo faremo mai al liceo) e a cui il libro dedica non più di 4 pagine.
Ci sono giusto due esempi, ho provato a fare alcuni esercizi ma anche se alcuni vengono, molti non so come farli... mi sembra di girare a vuoto.
Ne posto 3, spero siate genitili da farmi vedere come fate.
Dopo che pongo $n=n_0+1$ non so che fare...
1) Dimostrare che per qualunque n naturale, il numero $5^n+2*3^(n-1)+1$ è divisibile per 8.
2) Dimostrare che per qualunque n naturale, il numero $10^n-1$ è divisibile per 9.
E in ultimo, dimostrare che
$1+5+9...+(4n-3)=n(2n-1)$
Grazie infinite, inoltre sono graditi alcuni consigli generali nell'atteggiamento da assumere quando si procede per induzione
Ci sono giusto due esempi, ho provato a fare alcuni esercizi ma anche se alcuni vengono, molti non so come farli... mi sembra di girare a vuoto.
Ne posto 3, spero siate genitili da farmi vedere come fate.
Dopo che pongo $n=n_0+1$ non so che fare...
1) Dimostrare che per qualunque n naturale, il numero $5^n+2*3^(n-1)+1$ è divisibile per 8.
2) Dimostrare che per qualunque n naturale, il numero $10^n-1$ è divisibile per 9.
E in ultimo, dimostrare che
$1+5+9...+(4n-3)=n(2n-1)$
Grazie infinite, inoltre sono graditi alcuni consigli generali nell'atteggiamento da assumere quando si procede per induzione
Risposte
2)
$10^(n+1)-1=10*10^n-1$
ma abbiamo ipotizzato che $10^n-1-=0(mod9)$, ovvero $10^n-=1(mod9)$, dunque
$10*10^n-1-=10-1-=0(mod9)$
Il primo si fa analogamente
$10^(n+1)-1=10*10^n-1$
ma abbiamo ipotizzato che $10^n-1-=0(mod9)$, ovvero $10^n-=1(mod9)$, dunque
$10*10^n-1-=10-1-=0(mod9)$
Il primo si fa analogamente
$sum_(k=0)^n (4k-3)=n(2n-1)$
per n+1 si ha
$sum_(k=0)^(n+1) (4k-3)=sum_(k=0)^n (4k-3)+4(n+1)-3=n(2n-1)+4(n+1)-3=2n^2+3n+1=(n+1)(2n+1)$
per n+1 si ha
$sum_(k=0)^(n+1) (4k-3)=sum_(k=0)^n (4k-3)+4(n+1)-3=n(2n-1)+4(n+1)-3=2n^2+3n+1=(n+1)(2n+1)$
1)Poniamo $f(n)=5^n+2*3^(n-1)+1$
Si ha $f(1)=5+2+1=8$ e quindi per n=1 la divisibilita' per 8 e' assicurata.
Supposta vera la divisibilita' per un n generico (>1 ) risulta:
$f(n+1)=5^(n+1)+2*3^n+1=5*5^n+2*3*3^(n-1)+1=5*5^n+6*3^(n-1)+1$
Pertanto:
$f(n+1)-f(n)=4[5^n+3^(n-1)]$ ovvero:
$f(n+1)=f(n)+4[5^n+3^(n-1)]$
Poiche' per ipotesi f(n) e' divisibile per 8 e lo e' anche
l'espressione con la parentesi quadra ,resta dimostrata la divisibilta'
per 8 anche di f(n+1).I passi fondamentali dell'induzione sono soddisfatti.
2)Possiamo usare lo stesso metodo.
Poniamo $f(n)=10^n-1$
Si ha $f(1)=10-1=9$ e la divisibilita' per 9 c'e'.
Supposta vera la divisibilta' per un n generico (>1) ,risulta:
$f(n+1)=10^(n+1)-1 =10*10^n-1$ da cui:
$f(n+1)-f(n)=9*10^n$ e quindi $f(n+1)=f(n)+9*10^n$
Poiche' per ipotesi e' f(n) divisibile per 9 ,lo e' pure f(n+1) e l'induzione si completa.
karl
Si ha $f(1)=5+2+1=8$ e quindi per n=1 la divisibilita' per 8 e' assicurata.
Supposta vera la divisibilita' per un n generico (>1 ) risulta:
$f(n+1)=5^(n+1)+2*3^n+1=5*5^n+2*3*3^(n-1)+1=5*5^n+6*3^(n-1)+1$
Pertanto:
$f(n+1)-f(n)=4[5^n+3^(n-1)]$ ovvero:
$f(n+1)=f(n)+4[5^n+3^(n-1)]$
Poiche' per ipotesi f(n) e' divisibile per 8 e lo e' anche
l'espressione con la parentesi quadra ,resta dimostrata la divisibilta'
per 8 anche di f(n+1).I passi fondamentali dell'induzione sono soddisfatti.
2)Possiamo usare lo stesso metodo.
Poniamo $f(n)=10^n-1$
Si ha $f(1)=10-1=9$ e la divisibilita' per 9 c'e'.
Supposta vera la divisibilta' per un n generico (>1) ,risulta:
$f(n+1)=10^(n+1)-1 =10*10^n-1$ da cui:
$f(n+1)-f(n)=9*10^n$ e quindi $f(n+1)=f(n)+9*10^n$
Poiche' per ipotesi e' f(n) divisibile per 9 ,lo e' pure f(n+1) e l'induzione si completa.
karl
come consiglio generale:
supponi di dover dimostrare per induzione una proprieta' $P(n)$ per $n>0$.
Potra' succedere che anche se la base dell'induzione sara' solo $P(1)$, per portare a termine
il passo induttivo ti servira', ad esempio, aver sviluppato $P(2)$. Ad esempio,
quando ti sentirai a tuo agio con l'induzione, prova a dim. la disuguaglianza
di Cauchy-Schwarz:
$\sum_{i=1}^n a_ib_i <= \sqrt((\sum_{i=1}^n a_i^2) (\sum_{i=1}^n b_i^2))$ per $a_i,b_i \in RR$
(anche se per questa l'induzione non e' la dimostrazione piu' "naturale")
supponi di dover dimostrare per induzione una proprieta' $P(n)$ per $n>0$.
Potra' succedere che anche se la base dell'induzione sara' solo $P(1)$, per portare a termine
il passo induttivo ti servira', ad esempio, aver sviluppato $P(2)$. Ad esempio,
quando ti sentirai a tuo agio con l'induzione, prova a dim. la disuguaglianza
di Cauchy-Schwarz:
$\sum_{i=1}^n a_ib_i <= \sqrt((\sum_{i=1}^n a_i^2) (\sum_{i=1}^n b_i^2))$ per $a_i,b_i \in RR$
(anche se per questa l'induzione non e' la dimostrazione piu' "naturale")
Grazie a tutti e tre, le vostre spiegazioni sono state più che chiare. Ora una domanda che mi assilla.
Nell'induzione quasi sempre, una volta che si calcola la $f(n+1)$ poi si fa ricorso di nuovo alla f(n), come in questo caso:
In realtà, questo è proprio quello che dobbiamo dimostrare... infatti il testo dice
Dimostra che $f(n)=5^n+2*3^(n-1)+1$
Ecco, mi sembra che nell'induzione si ricorre molto spesso al testo iniziale per poi sostituire a piacimento.
Quindi chiedo: perchè ciò è lecito, se quella è la tesi e non l'ipotesi?
Grazie mille di nuovo, buona serata.
Nell'induzione quasi sempre, una volta che si calcola la $f(n+1)$ poi si fa ricorso di nuovo alla f(n), come in questo caso:
Poiche' per ipotesi f(n) e' divisibile per 8
In realtà, questo è proprio quello che dobbiamo dimostrare... infatti il testo dice
Dimostra che $f(n)=5^n+2*3^(n-1)+1$
Ecco, mi sembra che nell'induzione si ricorre molto spesso al testo iniziale per poi sostituire a piacimento.
Quindi chiedo: perchè ciò è lecito, se quella è la tesi e non l'ipotesi?
Grazie mille di nuovo, buona serata.
Supponi di dimostrare che se una proprietà vale per un certo n allora vale anche per n+1; in tal caso, essendo la proprietà vera per n=1, lo sarà anche per n=2, e quindi anche per n=3, e così via per tutti i valori di n. Dunque la proprietà rimane vera per ogni n.
Ok Luca, ora è chiaro. Grazie molte
Vl4d, perchè dovrebbe tornarmi utile verificare la relazione devo sviluppare P(2)?
E ci sono casi precisi in cui si procede così o è questione di esperienza e comodità?
Grazie e scusa, ma sull'argomento sono quasi totalmente ignorante.
Ciao
Vl4d, perchè dovrebbe tornarmi utile verificare la relazione devo sviluppare P(2)?
E ci sono casi precisi in cui si procede così o è questione di esperienza e comodità?
Grazie e scusa, ma sull'argomento sono quasi totalmente ignorante.
Ciao
Nel caso particolare della disuguaglianza di Cauchy-Swartz ti torna utile dimostrare il caso $n=2$ perchè poi nel passo induttivo ti puoi ridurre a quest'ultimo e concludere subito.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo