SNS 1976 - Numero divisibile per 8
"Mostrare che, per ogni intero positivo $n$, il numero $5^n+2*3^(n-1)+1$ è divisibile per 8$
Io ho provato con l'induzione:
-Per $n=1$, 5+2+1=8, divisibile per 8;
-Per $n+1$, $5^(n+1)+2*3^n+1$, che è $5*(5^n)+3(2*3^(n-1))+1$
Come faccio a dimostrare che quest'ultimo polinomio è anch'esso divisibile per 8? C'è una qualche proprietà che dice che se $a+b$ e $c+d$ sono divisibili per 8, lo sono anche $a*c+b*d$?
Oppure l'induzione è la strada sbagliata?
Io ho provato con l'induzione:
-Per $n=1$, 5+2+1=8, divisibile per 8;
-Per $n+1$, $5^(n+1)+2*3^n+1$, che è $5*(5^n)+3(2*3^(n-1))+1$
Come faccio a dimostrare che quest'ultimo polinomio è anch'esso divisibile per 8? C'è una qualche proprietà che dice che se $a+b$ e $c+d$ sono divisibili per 8, lo sono anche $a*c+b*d$?
Oppure l'induzione è la strada sbagliata?
Risposte
Faccio un tentativo seguendo la tua strada
$5\cdot 5^n+3( 2\cdot 3^{n-1})+1 =2\cdot 5^n -2 +3(5^n+2 \cdot3^{n-1}+1)=2(5^n-1)+3(5^n+2 \cdot3^{n-1}+1)$.
A questo punto ti basta dimostrare che $5^{n}-1$ e' divisibile per $4$ ...
Probabilmente pero' c'e' una strada piu' breve.
$5\cdot 5^n+3( 2\cdot 3^{n-1})+1 =2\cdot 5^n -2 +3(5^n+2 \cdot3^{n-1}+1)=2(5^n-1)+3(5^n+2 \cdot3^{n-1}+1)$.
A questo punto ti basta dimostrare che $5^{n}-1$ e' divisibile per $4$ ...
Probabilmente pero' c'e' una strada piu' breve.
Non ho fatto tutti i calcoli, ma ecco il metodo che userei: la formula può essere scritta come $(4+1)^n+2*(4-1)^(n-1)+1$. Applico per le due parentesi la formula per la potenza del binomio; i primi termini possono essere trascurati perchè divisibili per 16 e restano solo l'ultimo e il penultimo che, a parte il segno, valgono rispettivamente 1 e (4*esponente); completo poi il calcolo. Conviene distinguere a seconda della parità di n, in modo che i segni non diano problemi; non escludo che nel caso di n pari il risultato sia del tipo 4n, magari moltiplicato per qualcosa.
mi sembra un po' più semplice così:
$5^(n+1)+2*3^n+1=5*5^n+3*2*3^(n-1)+1=(1+4)*5^n+(1+2)*2*3^(n-1)+1=$
$=(5^n+2*3^(n-1)+1)+(4*5^n+2*2*3^(n-1))={5^n+2*3^(n-1)+1}+{4*(5^n+3^(n-1))}$
la prima "parentesi graffa" è divisibile per 8 per l'ipotesi induttiva, la seconda perché la "parentesi tonda" è un numero pari in quanto somma di due dispari.
$5^(n+1)+2*3^n+1=5*5^n+3*2*3^(n-1)+1=(1+4)*5^n+(1+2)*2*3^(n-1)+1=$
$=(5^n+2*3^(n-1)+1)+(4*5^n+2*2*3^(n-1))={5^n+2*3^(n-1)+1}+{4*(5^n+3^(n-1))}$
la prima "parentesi graffa" è divisibile per 8 per l'ipotesi induttiva, la seconda perché la "parentesi tonda" è un numero pari in quanto somma di due dispari.
"ViciousGoblin":
Faccio un tentativo seguendo la tua strada
$5\cdot 5^n+3( 2\cdot 3^{n-1})+1 =2\cdot 5^n -2 +3(5^n+2 \cdot3^{n-1}+1)=2(5^n-1)+3(5^n+2 \cdot3^{n-1}+1)$.
A questo punto ti basta dimostrare che $5^{n}-1$ e' divisibile per $4$ ...
Probabilmente pero' c'e' una strada piu' breve.
No, è quella giusta infatti...
$5^n + 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
Ho capito i vostri ragionamenti, grazie mille..
Non mi è chiaro solo questo passaggio:
Non mi è chiaro solo questo passaggio:
"vict85":
$5^n + 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
"elios":[/quote]
Ho capito i vostri ragionamenti, grazie mille..
Non mi è chiaro solo questo passaggio:
[quote="vict85"]
$5^n + 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
È difficile capirlo visto che il testo ha un errore di segno la forma esatta, come scritto nella riga precedente a quella quotata, è
$5^n - 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
"elios":[/quote]
Ho capito i vostri ragionamenti, grazie mille..
Non mi è chiaro solo questo passaggio:
[quote="vict85"]
$5^n + 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
Per capirlo ( a parte l'errore gia' segnalato) devi dare un'occhiata all' "aritmetica modulare" -
non e' difficile ed e' piuttosto utile in quei problemini di divisibilita' che stai guardando.
Ho provato a rifare il tuo problema usando l'aritmetica modulo $8$ - puo' esserti utile per capire l'idea (anche non ho trovato un modo sufficientemente
semplice - forse gli esperti potrebbero fare meglio)
$5^n+2\cdot 3^{n-1}+1=(-3)^n+(-6)\cdot 3^{n-1}+1=(-1)^n\cdot 3^{n}-2\cdot 3^n+1=((-1)^n-2)3^n+1$
Se $n$ e' pari viene $-3^n+1$ se $n$ e' dispari viene $-3^{n+1}+1$; (in ogni caso l'esponente e' pari).
Allora basta verificare che $3^{2k}=1("mod "8)$, se $k$ e' intero e in effetti
$3^{2k}=9^k=1^k=1$ (modulo $8$).
Spero di non aver fatto errori.
Continuo a ritenere più facile e veloce la mia soluzione e per convincervene la completo e miglioro; la riprendo dall'inizio per non obbligarvi a leggere in due diversi interventi.
Scrivo la formula come $(4+1)^n+2*(4-1)^(n-1)+1$ e applico alle due parentesi la formula per la potenza del binomio; posso trascurare i termini in cui 4 è elevato ad esponenti maggiori di 1 (sono divisibili per 16) nonché, nella seconda, anche quello con l'esponente 1 (moltiplicato per il 2 in evidenza è divisibile per 8). Mi resta quindi $4n+1+2*(-1)^(n-1)+1$ e distinguo due casi:
n è pari) $=4n+1-2+1=4n$ che è divisibile per 8 perché n è pari
n è dispari) $=4n+1+2+1=4(n+1)$ che è divisibile per 8 perché n+1 è pari
Scrivo la formula come $(4+1)^n+2*(4-1)^(n-1)+1$ e applico alle due parentesi la formula per la potenza del binomio; posso trascurare i termini in cui 4 è elevato ad esponenti maggiori di 1 (sono divisibili per 16) nonché, nella seconda, anche quello con l'esponente 1 (moltiplicato per il 2 in evidenza è divisibile per 8). Mi resta quindi $4n+1+2*(-1)^(n-1)+1$ e distinguo due casi:
n è pari) $=4n+1-2+1=4n$ che è divisibile per 8 perché n è pari
n è dispari) $=4n+1+2+1=4(n+1)$ che è divisibile per 8 perché n+1 è pari
"giammaria":
Continuo a ritenere più facile e veloce la mia soluzione e per convincervene la completo e miglioro; la riprendo dall'inizio per non obbligarvi a leggere in due diversi interventi.
Scrivo la formula come $(4+1)^n+2*(4-1)^(n-1)+1$ e applico alle due parentesi la formula per la potenza del binomio; posso trascurare i termini in cui 4 è elevato ad esponenti maggiori di 1 (sono divisibili per 16) nonché, nella seconda, anche quello con l'esponente 1 (moltiplicato per il 2 in evidenza è divisibile per 8). Mi resta quindi $4n+1+2*(-1)^(n-1)+1$ e distinguo due casi:
n è pari) $=4n+1-2+1=4n$ che è divisibile per 8 perché n è pari
n è dispari) $=4n+1+2+1=4(n+1)$ che è divisibile per 8 perché n+1 è pari
perché, scusa, la mia è più complicata?
"adaBTTLS":
mi sembra un po' più semplice così:
$5^(n+1)+2*3^n+1=5*5^n+3*2*3^(n-1)+1=(1+4)*5^n+(1+2)*2*3^(n-1)+1=$
$=(5^n+2*3^(n-1)+1)+(4*5^n+2*2*3^(n-1))={5^n+2*3^(n-1)+1}+{4*(5^n+3^(n-1))}$
la prima "parentesi graffa" è divisibile per 8 per l'ipotesi induttiva, la seconda perché la "parentesi tonda" è un numero pari in quanto somma di due dispari.
"giammaria":
Continuo a ritenere più facile e veloce la mia soluzione e per convincervene la completo e miglioro; la riprendo dall'inizio per non obbligarvi a leggere in due diversi interventi.
Scrivo la formula come $(4+1)^n+2*(4-1)^(n-1)+1$ e applico alle due parentesi la formula per la potenza del binomio; posso trascurare i termini in cui 4 è elevato ad esponenti maggiori di 1 (sono divisibili per 16) nonché, nella seconda, anche quello con l'esponente 1 (moltiplicato per il 2 in evidenza è divisibile per 8). Mi resta quindi $4n+1+2*(-1)^(n-1)+1$ e distinguo due casi:
n è pari) $=4n+1-2+1=4n$ che è divisibile per 8 perché n è pari
n è dispari) $=4n+1+2+1=4(n+1)$ che è divisibile per 8 perché n+1 è pari
Non è una gara... Lo scopo della scuola normale è quello di vedere se sai trovare una soluzione, non se sai trovare la soluzione che hanno pensato loro o una migliore... Ogni soluzione ritengo abbia degli aspetti positivi e degli aspetti negativi. Personalmente trovo quella di Ada la più semplice perché usa semplici calcoli algebrici, l'ipotesi induttiva e che la somma di numeri dispari è pari senza tirar fuori binomiali o l'aritmetica modulare (che tra l'altro tu usi implicitamente quando elimini i multipli di 16 e 8, cosa che in una dimostrazione formale non potresti fare).
Sottoscrivo quello che dice vict85 - non e' una gara!.
Personalmente volevo aiutare elios a capire come si usano certe tecniche per cui, per esempio, all'inizio ho seguito la sua idea di usare l'induzione.
Mi pare sia istruttivo vedere piu' procedimenti e confrontarli tra loro, decidendo alla fine quale sia il migliore e quale sia quello che
ha piu' prospettive di essere usato in altre situazioni.
A elios l'ardua sentenza.
Personalmente volevo aiutare elios a capire come si usano certe tecniche per cui, per esempio, all'inizio ho seguito la sua idea di usare l'induzione.
Mi pare sia istruttivo vedere piu' procedimenti e confrontarli tra loro, decidendo alla fine quale sia il migliore e quale sia quello che
ha piu' prospettive di essere usato in altre situazioni.
A elios l'ardua sentenza.
E' semplice anche la tua, ma in generale ritengo che un ragionamento induttivo sia meno intuitivo di un ragionamento diretto. Comunque, la soluzione era iniziata così, e non era male continuare nello stesso modo.
la traduzione "a parole" della mia è che la differenza tra due "valori consecutivi" è un multiplo di 8.
comunque è vero che i vari tentativi sono partiti da elios e quindi un po' condizionati "a catena", com'è vero che ogni proposta diversa offre comunque uno spunto di riflessione.
comunque è vero che i vari tentativi sono partiti da elios e quindi un po' condizionati "a catena", com'è vero che ogni proposta diversa offre comunque uno spunto di riflessione.
Dopo mesi di rielaborazione (in realtà avevo perso di vista questo problema, e me ne scuso), trascrivo per amor di chiarezza tutte le soluzioni che sono venute fuori, ringraziando ViciousGoblin, adaBTTLS, giammaria.
1°: $5\cdot 5^n+3( 2\cdot 3^{n-1})+1 =2\cdot 5^n -2 +3(5^n+2 \cdot3^{n-1}+1)=2(5^n-1)+3(5^n+2 \cdot3^{n-1}+1)$. Si dimostra che $5^{n}-1$ e' divisibile per $4$: $5^n - 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
2°: $5^(n+1)+2*3^n+1=5*5^n+3*2*3^(n-1)+1=(1+4)*5^n+(1+2)*2*3^(n-1)+1=(5^n+2*3^(n-1)+1) (4*5^n+2*2*3^(n-1))={5^n+2*3^(n-1)+1}+{4*(5^n+3^(n-1))}$, la prima "parentesi graffa" è divisibile per 8 per l'ipotesi induttiva, la seconda perché la "parentesi tonda" è un numero pari in quanto somma di due dispari.
3°: Usando l'aritmetica modulo $8$, $5^n+2\cdot 3^{n-1}+1=(-3)^n+(-6)\cdot 3^{n-1}+1=(-1)^n\cdot 3^{n}-2\cdot 3^n+1=((-1)^n-2)3^n+1$. Se $n$ e' pari viene $-3^n+1$ se $n$ e' dispari viene $-3^{n+1}+1$; (in ogni caso l'esponente e' pari). Basta verificare che $3^{2k}=1("mod "8)$, se $k$ e' intero e in effetti $3^{2k}=9^k=1^k=1$ (modulo $8$).
4°: Scrivo la formula come $(4+1)^n+2*(4-1)^(n-1)+1$ e applico alle due parentesi la formula per la potenza del binomio; posso trascurare i termini in cui 4 è elevato ad esponenti maggiori di 1 (sono divisibili per 16) nonché, nella seconda, anche quello con l'esponente 1 (moltiplicato per il 2 in evidenza è divisibile per 8). Mi resta quindi $4n+1+2*(-1)^(n-1)+1$ e distinguo due casi:
n è pari) $=4n+1-2+1=4n$ che è divisibile per 8 perché n è pari
n è dispari) $=4n+1+2+1=4(n+1)$ che è divisibile per 8 perché n+1 è pari
1°: $5\cdot 5^n+3( 2\cdot 3^{n-1})+1 =2\cdot 5^n -2 +3(5^n+2 \cdot3^{n-1}+1)=2(5^n-1)+3(5^n+2 \cdot3^{n-1}+1)$. Si dimostra che $5^{n}-1$ e' divisibile per $4$: $5^n - 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$
2°: $5^(n+1)+2*3^n+1=5*5^n+3*2*3^(n-1)+1=(1+4)*5^n+(1+2)*2*3^(n-1)+1=(5^n+2*3^(n-1)+1) (4*5^n+2*2*3^(n-1))={5^n+2*3^(n-1)+1}+{4*(5^n+3^(n-1))}$, la prima "parentesi graffa" è divisibile per 8 per l'ipotesi induttiva, la seconda perché la "parentesi tonda" è un numero pari in quanto somma di due dispari.
3°: Usando l'aritmetica modulo $8$, $5^n+2\cdot 3^{n-1}+1=(-3)^n+(-6)\cdot 3^{n-1}+1=(-1)^n\cdot 3^{n}-2\cdot 3^n+1=((-1)^n-2)3^n+1$. Se $n$ e' pari viene $-3^n+1$ se $n$ e' dispari viene $-3^{n+1}+1$; (in ogni caso l'esponente e' pari). Basta verificare che $3^{2k}=1("mod "8)$, se $k$ e' intero e in effetti $3^{2k}=9^k=1^k=1$ (modulo $8$).
4°: Scrivo la formula come $(4+1)^n+2*(4-1)^(n-1)+1$ e applico alle due parentesi la formula per la potenza del binomio; posso trascurare i termini in cui 4 è elevato ad esponenti maggiori di 1 (sono divisibili per 16) nonché, nella seconda, anche quello con l'esponente 1 (moltiplicato per il 2 in evidenza è divisibile per 8). Mi resta quindi $4n+1+2*(-1)^(n-1)+1$ e distinguo due casi:
n è pari) $=4n+1-2+1=4n$ che è divisibile per 8 perché n è pari
n è dispari) $=4n+1+2+1=4(n+1)$ che è divisibile per 8 perché n+1 è pari
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo