SNS 1976 - Numero divisibile per 8

[elios]

"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?

[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.

[giammaria]

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.

[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.

[vict85]

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)$

[elios]

Ho capito i vostri ragionamenti, grazie mille..
Non mi è chiaro solo questo passaggio:

$5^n + 1 -= 1^n -1 (mod 4) -= 1-1 (mod 4) = 0 (mod 4)$

[@melia]

Ho capito i vostri ragionamenti, grazie mille..
Non mi è chiaro solo questo passaggio:

$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)$

[ViciousGoblin]

Ho capito i vostri ragionamenti, grazie mille..
Non mi è chiaro solo questo passaggio:

$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.

[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

[adaBTTLS]

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?

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.