Esercizi induzione
Non sono sicuro della correttezza di due esercizi e di come svolgerne uno.
Usando l'induzione devo dimostrare che:
1) $ P(n): n < 2^n AA n >= 1 $
Base $ P(1): 1 < 2 $ OK
Passo $ (P(n) rArr P(n+1)): (n < 2^n rArr n+1<2^(n+1)) $ da cui ricavo $ n < 2^n < 2^n*2 - 1 $
Posso affermare che questa relazione è vera? A me sembra palese essendo n >= 1 però dato che in matematica nulla si da per scontato devo specificare qualcosa?
2) $ P(n): 3^n < n! AA n >= 7 $
Base $ P(7): 3^7 < 7! hArr 36*18 < 42 * 120 $ OK
Passo $ (P(n) => P(n+1)): (3^n < n! => 3^(n+1) < (n+1)!) $ da cui ricavo $ 3^n < n! < n! * (n+1)/3 $
Essendo n >= 7, (n+1)/3 è sempre > 1 quindi n! per una quantità maggiore di 1 è sempre maggiore di n!. Di conseguenza la relazione è vera. E' sufficiente scrivere ciò per affermare che la dimostrazione è vera??
3) $ P(n): n^3 - n $ è divisibile per 3 per ogni n >= 1
In questo caso come rappresento la condizione di divisibilità?
Usando l'induzione devo dimostrare che:
1) $ P(n): n < 2^n AA n >= 1 $
Base $ P(1): 1 < 2 $ OK
Passo $ (P(n) rArr P(n+1)): (n < 2^n rArr n+1<2^(n+1)) $ da cui ricavo $ n < 2^n < 2^n*2 - 1 $
Posso affermare che questa relazione è vera? A me sembra palese essendo n >= 1 però dato che in matematica nulla si da per scontato devo specificare qualcosa?
2) $ P(n): 3^n < n! AA n >= 7 $
Base $ P(7): 3^7 < 7! hArr 36*18 < 42 * 120 $ OK
Passo $ (P(n) => P(n+1)): (3^n < n! => 3^(n+1) < (n+1)!) $ da cui ricavo $ 3^n < n! < n! * (n+1)/3 $
Essendo n >= 7, (n+1)/3 è sempre > 1 quindi n! per una quantità maggiore di 1 è sempre maggiore di n!. Di conseguenza la relazione è vera. E' sufficiente scrivere ciò per affermare che la dimostrazione è vera??
3) $ P(n): n^3 - n $ è divisibile per 3 per ogni n >= 1
In questo caso come rappresento la condizione di divisibilità?
Risposte
1) Il ragionamento è corretto...per essere pignoli, si potrebbe contestare il fatto che non hai esplicitato che $2^n-1>0$ se $n >0$ e quindi è lecito effettuare una maggiorazione, aggiungendo tu una quantità positiva a destra del $<$, ma sono piccolezze.
2) Perfetto (hai anche esplicitato il ragionamento).
3) La divisibilità non ha bisogno di una qualche espressione per essere verificata, basta far vedere che funziona:
$ P(n) : 3 | n^3-n \quad \quad \forall n \ge 1$
Mostriamo che è vera per $n=1$:
$1^3-1 = 0$ che è divisibile per $3$.
Mostriamo che $P(n) \Rightarrow P(n+1)$:
$ (n+1)^3-(n+1) = n^3 +3n^2+3n +1 -n -1 = (n^3-n) +3(n^2 +n) $
Il primo addendo è divisibile per $3$ per ipotesi di induzione e il secondo è evidentemente multiplo di $3$.
Ciao!
2) Perfetto (hai anche esplicitato il ragionamento).
3) La divisibilità non ha bisogno di una qualche espressione per essere verificata, basta far vedere che funziona:
$ P(n) : 3 | n^3-n \quad \quad \forall n \ge 1$
Mostriamo che è vera per $n=1$:
$1^3-1 = 0$ che è divisibile per $3$.
Mostriamo che $P(n) \Rightarrow P(n+1)$:
$ (n+1)^3-(n+1) = n^3 +3n^2+3n +1 -n -1 = (n^3-n) +3(n^2 +n) $
Il primo addendo è divisibile per $3$ per ipotesi di induzione e il secondo è evidentemente multiplo di $3$.
Ciao!
Grazie 
Per caso è possibile dimostrare la divisibilità per 3 scomponendo i polinomi in fattori? Ossia:
$ n^3 - n = n(n+1)(n-1) $ è divisibile per 3, quindi uno dei suoi fattori dev'essere un multiplo;
$ (n+1)^3-(n+1) = n(n+1)(n+2) $ da questa scomposizione posso dire che è anch'esso divisibile per 3 pur mancando il fattore $ (n - 1) $ ? In teoria avendo dimostrato prima che è divisibile dovrebbe essere possibile dimostrarlo anche in questo modo, sto sbagliando qualcosa?
Per caso è possibile dimostrare la divisibilità per 3 scomponendo i polinomi in fattori? Ossia:
$ n^3 - n = n(n+1)(n-1) $ è divisibile per 3, quindi uno dei suoi fattori dev'essere un multiplo;
$ (n+1)^3-(n+1) = n(n+1)(n+2) $ da questa scomposizione posso dire che è anch'esso divisibile per 3 pur mancando il fattore $ (n - 1) $ ? In teoria avendo dimostrato prima che è divisibile dovrebbe essere possibile dimostrarlo anche in questo modo, sto sbagliando qualcosa?
"raxell":
Grazie
Per caso è possibile dimostrare la divisibilità per 3 scomponendo i polinomi in fattori? Ossia:
$ n^3 - n = n(n+1)(n-1) $ è divisibile per 3, quindi uno dei suoi fattori dev'essere un multiplo;
$ (n+1)^3-(n+1) = n(n+1)(n+2) $ da questa scomposizione posso dire che è anch'esso divisibile per 3 pur mancando il fattore $ (n - 1) $ ? In teoria avendo dimostrato prima che è divisibile dovrebbe essere possibile dimostrarlo anche in questo modo, sto sbagliando qualcosa?
Per completare il ragionamento secondo me ti mancherebbe solo dimostrare che se ( n -1) è divisibile per 3 allora lo è anche ( n+2).
Effettivamente in quel modo sarebbe corretto, però per dimostrare quell'implicazione mi ricondurrei sempre a una somma: 3|(n-1)+3, quindi tanto varrebbe dimostrate direttamente come ha fatto Bremen000.
Però mi sa che non ci sono altri modi visto che $ (n+1)^3-(n+1) $ non è divisibile per $ n^3-n $, quindi un resto lo avrei sempre.
Però mi sa che non ci sono altri modi visto che $ (n+1)^3-(n+1) $ non è divisibile per $ n^3-n $, quindi un resto lo avrei sempre.
In realtà se scrivi $n^3-n$ come $(n-1)n(n+1)$ è già evidente di per sé che quel numero è divisibile per $3$, essendo $n$ intero. Tuttavia questa non è una dimostrazione per induzione ma è di tipo "diretto". Deriviamo direttamente dall'ipotesi la tesi.
Mischiare le due cose (dimostrazione per induzione e "diretta") è molto confusionario.
Spero sia chiaro!
Mischiare le due cose (dimostrazione per induzione e "diretta") è molto confusionario.
Spero sia chiaro!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo