Principio di induzione. chiarimenti su esercizio.

[bla99hf]

Salve,

ho il seguente esercizio:
Dimostriamo per induzione su $n$ che $13$ divide $4^(2n+1)+3^(n+2) AA n \in NN$.

ecco la risoluzione nella quale alcuni passi non mi sono chiari:
In questo caso l'asserzione $P$ sui numeri interi è "$13$ divide $4^(2n+1)+3^(n+2)$", e si vuol dimostrare che $P$ è vera $AA$ numero intero $n >= 0$.
Mostriamo intanto che $P$ è vera per $n = 0$.
Quando $n = 0$ l'asserzione $P$ diventa "$13$ divide $4+3^2$", ossia "$13$ divide $13$", che è vera.
Sia ora $n > 0$ un numero intero e supponiamo che $P$ sia vera per il numero $n-1$, cioè supponiamo che $13$ divida $4^(2(n-1)+1)+3^((n-1)+2)$, ossia che $13$ divida $4^(2n-1)+3^(n+1)$.
Dato che $4^(2n+1)+3^(n+2) = 16 * 4^(2n-1)+3*3^(n+1) = 13*4^(2n-1)+3(4^(2n-1)+3^(n+1))$, se ne deduce che $4^(2n+1)+3^(n+2)$ è somma dei due numeri $13*4^(2n-1)$ e $3(4^(2n-1)+3^(n+1))$, entrambi divisibili per $13$, e quindi anche $4^(2n+1)+3^(n+2)$ è divisibile per $13$.
Pertanto l'asserzione $P$ è vera $AA$ numero intero $n >= 0$.


ecco i punti poco chiari:

... che $13$ divide $4^(2n+1)+3^(n+2) AA n \in $NN$$.

In questo caso l'asserzione $P$ sui numeri interi...

prima si parla di numeri naturali e poi si parla di numeri interi. è un errore o dal momento che $NN \sube ZZ$ è corretto dire così?

si è considerato il passo base per $n_0 = 0$
e poi il passo induttivo per $n = n-1$
ed è chiaro.

poi da qui non mi è più chiaro:

Dato che $4^(2n+1)+3^(n+2) = 16 * 4^(2n-1)+3*3^(n+1) = 13*4^(2n-1)+3(4^(2n-1)+3^(n+1))$, se ne deduce che $4^(2n+1)+3^(n+2)$ è somma dei due numeri $13*4^(2n-1)$ e $3(4^(2n-1)+3^(n+1))$, entrambi divisibili per $13$, e quindi anche $4^(2n+1)+3^(n+2)$ è divisibile per $13$.

correggetemi se sbaglio ma il fatto che $4^(2n+1)+3^(n+2) = 16 * 4^(2n-1)+3*3^(n+1)$ è perchè si può scrivere in tali modi e cioè $4^(2n+1) = 4 * 4^(2n) = 4 * 4 * 4^(2n-1)$ e quindi $16*4^(2n-1)$ e lo stesso per il numero $3$ con il suo esponente.
se non erro dovrebbe essere per questa ragione.
Da qui in poi non riesco ad andare avanti...

se per cortesia potete darmi una mano per capire meglio.
grazie mille.

[kekko89]

prima si parla di numeri naturali e poi si parla di numeri interi. è un errore o dal momento che è corretto dire così?

Specifica infatti,ogni intero maggiore di zero,ovvero ogni numero naturale,

Tu,supponi vera la dimostrazione per $n-1$ e cerchi di dimostrarla per $n$. Se ottieni una forma dove hai un numero divisibile per 13, più la base della tua induzione,allora hai finito.(questo ovviamente,dopo aver dimostrato che è valida per $n=1$ o a un qualsiasi numero di partenza). Lui lo suppone vero per $n-1$,poi lo calcola per $n$ cercando di ottenere la forma di $n-1$(per questo divide $4^(2n+1)=(4^((2n-1)+2)))=16*4^(2n-1)$ vedi anche tu che si è ridotto in questa maniera alla base dell'induzione e così ha fatto per tutti gli altri termini.Poi scrive $16=13+3$ quindi $(13+3)(4^(2n-1))=13*4^(2n-1)+3*4^(2n-1)$ (questo lo fa essenzialmente,per cercare di dimostrare che è divisibile per 13..ovvero esplicita il 13 e poi successivamente,raccoglie il 3 con il secondo termine). Infine,per induzione,tu sai che $4^(2n-1)$ è divisibile per 13,e quindi,a maggior ragione,lo è $13*4^(2n-1)$. Ed anche $3^(n+1)$ è divisibile per 13(sempre perchè ci siamo ricondotti al caso ($n-1$). Ovviamente,somma di numeri divisibili per un certo n, è anch'essa divisibile per lo stesso n, e quindi anche il caso $n$ è vero. Avendo supposto che valeva per $n-1$ e avendo così dimostrato che vale per $n$,abbiamo concluso.

[bla99hf]

scusami non mi è chiaro:

Infine,per induzione,tu sai che $4^(2n-1)$ è divisibile per $13$,e quindi,a maggior ragione,lo è $13*4^(2n-1)$. Ed anche $3^(n+1)$ è divisibile per $13$ (sempre perchè ci siamo ricondotti al caso $(n-1)$.

per induzione, o se non sbaglio usando altri termini "per il passo induttivo" o "per ipotesi induttiva" cioè per $n-1$ ho che:
$13 | 4^(2n-1)+3^(n+1)$
ma dopo mi sfugge qualcosa nel procedimento...

[gugo82]

Fissiamo $n\in NN\setminus \{ 0\}$.
Supposto che $13$ divide $4^(2n-1)+3^(n+1)$ (ipotesi induttiva; si suppone che la proprietà $P_(n-1)$ sia vera), si deve mostrare valida $P_n$.
Per fare ciò, cerchiamo di manipolare il numero $4^(2n+1)+3^(n+2)$: ricordando le proprietà delle potenze possiamo scrivere: $4^(2n+1)+3^(n+2)=4^(2n-1+2)+3^(n+1+1)=4^2*4^(2n-1)+3*3^(n+1)=16*4^(2n-1)+3*3^(n+1)$; visto che $16=13+3$, ricordando la proprietà distributiva, possiamo ulteriormente modificare l'ultimo membro della precedente catena d'uguaglianze, in modo da avere: $4^(2n+1)+3^(n+2)=(13+3)*4^(2n-1)+3*3^(n+1)=13*4^(2n-1)+3*4^(2n-1)+3*3^(n+1)=13*4^(2n-1)+3*(4^(2n-1)+3^(n+1))$.
Operando in tal modo siamo riusciti a scrivere $4^(2n+1)+3^(n+2)$ come somma di due numeri, cioè $13*4^(2n-1)$ e $3*(4^(2n-1)+3^(n+1))$: il primo di tali numeri è evidentemente divisibile per $13$ per le usuali regole dell'aritmetica (infatti $(13*4^(2n-1))/(13)=4^(2n-1)\in NN$ ed il resto è zero); il secondo è divisibile per $13$ in virtù dell'ipotesi induttiva. Ora, visto che la somma di due numeri divisibili per $13$ è pure essa divisibile per $13$, quanto appena detto implica che $4^(2n+1)+3^(n+2)$ è divisibile per $13$, ossia che vale $P_n$.

Abbiamo così verificato che vale l'implicazione $P_(n-1)\quad =>\quad P_n$ per un fissato $n$; d'altra parte, visto che la scelta di $n$ in $NN\setminus \{0\}$ è del tutto arbitraria, la precedente vale come verifica del fatto che $AAn \in NN\setminus \{ 0\}, P_(n-1)\quad =>\quad P_n$, ossia del fatto che il passo induttivo è valido.

Infine, constatato che $P_0$ è vera (ossia che la base dell'induzione è valida), il principio d'induzione ci consente di affermare che la proprietà $P_n$ (ossia $13|4^(2n+1)+3^(n+2)$) è valida per ogni $n \in NN$.

[bla99hf]

certo ho capito, ma ancora una cosa.

$3*(4^(2n-1)+3^(n+1))$ è divisibile per $13$ in virtù dell'ipotesi induttiva.

quindi esso è divisibile sicuramente ed è chiaro per ipotesi induttiva per $13$. Ma anche se esso è moltiplicato per $3$?
cioè abbiamo che $13|4^(2n-1)+3^(n+1)$ per ipotesi induttiva... ma $13|3*(4^(2n-1)+3^(n+1))$ è valido anche se abbiamo quella moltiplicazione per $3$?
cioè riconducendo il tutto in questa forma (se è giusto scriverlo in questo modo o se è giusto considerarlo in questo modo...): $(3*(4^(2n-1)+3^(n+1)))/13$ si ottiene che effettivamente è divisibile per $13$? come si è effettivamente visto nell'altro numero di prima?

(infatti $(13*4^(2n-1))/13 = 4^(2n-1) \in NN$ ed il resto è zero)

è solo questo dettaglio che ora non mi è chiaro.
il resto mi è stato chiarito grazie al vostro aiuto!!
grazie per la vostra pazienza.

[gugo82]

In realtà stai applicando una proprietà aritmetica che conosci fin dalle scuole elementari, anche se non è subito così evidente come nell'altro caso (lì si poteva farlo ad occhio semplificando la frazione).

Siano $p,q \in NN\setminus \{0\}$.
Se $p$ è divisibile per $q$ allora, $AAm\in NN\setminus \{0\}$, $m*p$ è divisibile per $q$; in altre parole, $q|p \quad =>\quad AAm\in \NN\setminus \{0\} , q|m*p$.

Dim.: Per l'ipotesi $q|p$ esiste $h\in NN\setminus \{0\}$ tale che $p=h*q$; moltiplicando ambo i membri per $m$ ed applicando la proprietà associativa troviamo $m*p=(m*h)*q$, cosicché $m*p$ è multiplo di $q$, ossia $q|m*p$.

[bla99hf]

Finito. Perfetto. è tutto chiaro!!
Tutto spiegato chiarissimo e dettagliato.

Vi ringrazio davvero tanto per il vostro aiuto!