SNS 1976 - Numero divisibile per 8

[elios]

"Mostrare che, per ogni intero positivo \( \displaystyle {n} \), il numero \( \displaystyle {{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1} \) è divisibile per 8\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{I}{o}{h}{o}{p}{r}{o}{v}{a}\to{c}{o}{n}{l}'\in{d}{u}{z}{i}{o}\ne:\lt{b}\frac{{r}}{\succ}{P}{e}{r} \)n=1\( \displaystyle ,{5}+{2}+{1}={8},\div{i}{s}{i}{b}{i}\le{p}{e}{r}{8};\lt{b}\frac{{r}}{\succ}{P}{e}{r} \)n+1\( \displaystyle , \)5^(n+1)+2*3^n+1\( \displaystyle ,{c}{h}{e}è \)5*(5^n)+3(2*3^(n-1))+1\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{C}{o}{m}{e}{f{{a}}}{\mathcal{{i}}}{o}{a}\dim{o}{s}{t}{r}{a}{r}{e}{c}{h}{e}{q}{u}{e}{s}{t}'{\underline{{t}}}{i}{m}{o}{p}{o}{l}\in{o}{m}{i}{o}è{a}{n}{c}{h}'{e}{s}{s}{o}\div{i}{s}{i}{b}{i}\le{p}{e}{r}{8}?{C}'è{u}{n}{a}{q}{u}{a}{l}{c}{h}{e}\propto{r}{i}{e}{t}à{c}{h}{e}{d}{i}{c}{e}{c}{h}{e}{s}{e} \)a+b\( \displaystyle {e} \)c+d\( \displaystyle {s}{o}{n}{o}\div{i}{s}{i}{b}{i}{l}{i}{p}{e}{r}{8},{l}{o}{s}{o}{n}{o}{a}{n}{c}{h}{e} \)a*c+b*d$?
Oppure l'induzione è la strada sbagliata?

[ViciousGoblin]

Faccio un tentativo seguendo la tua strada
\( \displaystyle {5}\cdot{{5}}^{{n}}+{3}{\left({2}\cdot{{3}}^{{{n}-{1}}}\right)}+{1}={2}\cdot{{5}}^{{n}}-{2}+{3}{\left({{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right)}={2}{\left({{5}}^{{n}}-{1}\right)}+{3}{\left({{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right)} \).

A questo punto ti basta dimostrare che \( \displaystyle {{5}}^{{{n}}}-{1} \) e' divisibile per \( \displaystyle {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 \( \displaystyle {{\left({4}+{1}\right)}}^{{n}}+{2}\cdot{{\left({4}-{1}\right)}}^{{{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ì:
\( \displaystyle {{5}}^{{{n}+{1}}}+{2}\cdot{{3}}^{{n}}+{1}={5}\cdot{{5}}^{{n}}+{3}\cdot{2}\cdot{{3}}^{{{n}-{1}}}+{1}={\left({1}+{4}\right)}\cdot{{5}}^{{n}}+{\left({1}+{2}\right)}\cdot{2}\cdot{{3}}^{{{n}-{1}}}+{1}= \)
\( \displaystyle ={\left({{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right)}+{\left({4}\cdot{{5}}^{{n}}+{2}\cdot{2}\cdot{{3}}^{{{n}-{1}}}\right)}={\left\lbrace{{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right\rbrace}+{\left\lbrace{4}\cdot{\left({{5}}^{{n}}+{{3}}^{{{n}-{1}}}\right)}\right\rbrace} \)
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
\( \displaystyle {5}\cdot{{5}}^{{n}}+{3}{\left({2}\cdot{{3}}^{{{n}-{1}}}\right)}+{1}={2}\cdot{{5}}^{{n}}-{2}+{3}{\left({{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right)}={2}{\left({{5}}^{{n}}-{1}\right)}+{3}{\left({{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right)} \).

A questo punto ti basta dimostrare che \( \displaystyle {{5}}^{{{n}}}-{1} \) e' divisibile per \( \displaystyle {4} \) ...

Probabilmente pero' c'e' una strada piu' breve.

No, è quella giusta infatti...

\( \displaystyle {{5}}^{{n}}+{1}\equiv{{1}}^{{n}}-{1}{\left(\text{mod}{4}\right)}\equiv{1}-{1}{\left(\text{mod}{4}\right)}={0}{\left(\text{mod}{4}\right)} \)

[elios]

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

\( \displaystyle {{5}}^{{n}}+{1}\equiv{{1}}^{{n}}-{1}{\left(\text{mod}{4}\right)}\equiv{1}-{1}{\left(\text{mod}{4}\right)}={0}{\left(\text{mod}{4}\right)} \)

[@melia]

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

\( \displaystyle {{5}}^{{n}}+{1}\equiv{{1}}^{{n}}-{1}{\left(\text{mod}{4}\right)}\equiv{1}-{1}{\left(\text{mod}{4}\right)}={0}{\left(\text{mod}{4}\right)} \)

È difficile capirlo visto che il testo ha un errore di segno la forma esatta, come scritto nella riga precedente a quella quotata, è
\( \displaystyle {{5}}^{{n}}-{1}\equiv{{1}}^{{n}}-{1}{\left(\text{mod}{4}\right)}\equiv{1}-{1}{\left(\text{mod}{4}\right)}={0}{\left(\text{mod}{4}\right)} \)

[ViciousGoblin]

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

\( \displaystyle {{5}}^{{n}}+{1}\equiv{{1}}^{{n}}-{1}{\left(\text{mod}{4}\right)}\equiv{1}-{1}{\left(\text{mod}{4}\right)}={0}{\left(\text{mod}{4}\right)} \)

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 \( \displaystyle {8} \) - puo' esserti utile per capire l'idea (anche non ho trovato un modo sufficientemente
semplice - forse gli esperti potrebbero fare meglio)

\( \displaystyle {{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}={{\left(-{3}\right)}}^{{n}}+{\left(-{6}\right)}\cdot{{3}}^{{{n}-{1}}}+{1}={{\left(-{1}\right)}}^{{n}}\cdot{{3}}^{{{n}}}-{2}\cdot{{3}}^{{n}}+{1}={\left({{\left(-{1}\right)}}^{{n}}-{2}\right)}{{3}}^{{n}}+{1} \)

Se \( \displaystyle {n} \) e' pari viene \( \displaystyle -{{3}}^{{n}}+{1} \) se \( \displaystyle {n} \) e' dispari viene \( \displaystyle -{{3}}^{{{n}+{1}}}+{1} \); (in ogni caso l'esponente e' pari).
Allora basta verificare che \( \displaystyle {{3}}^{{{2}{k}}}={1}{\left(\text{mod }\ {8}\right)} \), se \( \displaystyle {k} \) e' intero e in effetti

\( \displaystyle {{3}}^{{{2}{k}}}={{9}}^{{k}}={{1}}^{{k}}={1} \) (modulo \( \displaystyle {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 \( \displaystyle {{\left({4}+{1}\right)}}^{{n}}+{2}\cdot{{\left({4}-{1}\right)}}^{{{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 \( \displaystyle {4}{n}+{1}+{2}\cdot{{\left(-{1}\right)}}^{{{n}-{1}}}+{1} \) e distinguo due casi:
n è pari) \( \displaystyle ={4}{n}+{1}-{2}+{1}={4}{n} \) che è divisibile per 8 perché n è pari
n è dispari) \( \displaystyle ={4}{n}+{1}+{2}+{1}={4}{\left({n}+{1}\right)} \) 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 \( \displaystyle {{\left({4}+{1}\right)}}^{{n}}+{2}\cdot{{\left({4}-{1}\right)}}^{{{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 \( \displaystyle {4}{n}+{1}+{2}\cdot{{\left(-{1}\right)}}^{{{n}-{1}}}+{1} \) e distinguo due casi:
n è pari) \( \displaystyle ={4}{n}+{1}-{2}+{1}={4}{n} \) che è divisibile per 8 perché n è pari
n è dispari) \( \displaystyle ={4}{n}+{1}+{2}+{1}={4}{\left({n}+{1}\right)} \) che è divisibile per 8 perché n+1 è pari

perché, scusa, la mia è più complicata?

mi sembra un po' più semplice così:
\( \displaystyle {{5}}^{{{n}+{1}}}+{2}\cdot{{3}}^{{n}}+{1}={5}\cdot{{5}}^{{n}}+{3}\cdot{2}\cdot{{3}}^{{{n}-{1}}}+{1}={\left({1}+{4}\right)}\cdot{{5}}^{{n}}+{\left({1}+{2}\right)}\cdot{2}\cdot{{3}}^{{{n}-{1}}}+{1}= \)
\( \displaystyle ={\left({{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right)}+{\left({4}\cdot{{5}}^{{n}}+{2}\cdot{2}\cdot{{3}}^{{{n}-{1}}}\right)}={\left\lbrace{{5}}^{{n}}+{2}\cdot{{3}}^{{{n}-{1}}}+{1}\right\rbrace}+{\left\lbrace{4}\cdot{\left({{5}}^{{n}}+{{3}}^{{{n}-{1}}}\right)}\right\rbrace} \)
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.