Problema sul principio di induzione (e non solo)
Si provi che se \( n,m \in N \) allora il numero
\( 3^n + 3^m+1 \)
non è mai un quadrato perfetto.
La prima cosa che salta alla mente (o almeno nel mio caso) è tentare una dimostrazione sul principio di induzione…
1) \( P(0)=3 \)
2) dimostro che \( P(n+1,m+1) \) è vero presupponendo che \( P(n,m) \) sia vera...
\( 3^n\cdot 3+3^m\cdot 3+1 \)
qui non vedo una via d'uscita e per quanto possa "manipolare" l'espressione non vedo come proseguire.
Immagino che oltre questa strada ne esistano altre ben diverse e meno meccaniche.
\( 3^n + 3^m+1 \)
non è mai un quadrato perfetto.
La prima cosa che salta alla mente (o almeno nel mio caso) è tentare una dimostrazione sul principio di induzione…
1) \( P(0)=3 \)
2) dimostro che \( P(n+1,m+1) \) è vero presupponendo che \( P(n,m) \) sia vera...
\( 3^n\cdot 3+3^m\cdot 3+1 \)
qui non vedo una via d'uscita e per quanto possa "manipolare" l'espressione non vedo come proseguire.
Immagino che oltre questa strada ne esistano altre ben diverse e meno meccaniche.
Risposte
Perché scomodare il principio di induzione quando esiste l'aritmetica modulare
"dan95":
Perché scomodare il principio di induzione quando esiste l'aritmetica modulare
Grazie per l’attenzione.
Tuttavia non riesco ancora a trovare una strada percorribile. Potresti illuminarmi?
Se $k=3^n+3^m+1$ fosse un quadrato perfetto in modulo 8 sarebbe congruo 0 o 1 o 4... supponiamo per assurdi che sia un quadrato perfetto allora necessariamente $k\equiv 1 mod 8$ perché $k$ è dispari, quindi $3^n+3^m \equiv 0 mod 8$. Sia $m \geq n$ allora segue che $3^(m-n)+1 \equiv 0 mod 8$, dunque non resta che dimostare la tesi che 8 non divide $3^k+1$ per nessun $k$ per concludere.
Il problema è che ci sono due numeri naturali che possono essere scelti in maniera indipendente l’uno dall’altro.
Quindi il PIM si deve applicare con cautela e no, non basta dimostrare che $P(0,0)$ è vera e che vale l’implicazione $P(n,m) => P(n+1,m+1)$.
Quindi il PIM si deve applicare con cautela e no, non basta dimostrare che $P(0,0)$ è vera e che vale l’implicazione $P(n,m) => P(n+1,m+1)$.
"dan95":
Se $k=3^n+3^m+1$ fosse un quadrato perfetto in modulo 8 sarebbe congruo 0 o 1 o 4... supponiamo per assurdi che sia un quadrato perfetto allora necessariamente $k\equiv 1 mod 8$ perché $k$ è dispari, quindi $3^n+3^m \equiv 0 mod 8$. Sia $m \geq n$ allora segue che $3^(m-n)+1 \equiv 0 mod 8$, dunque non resta che dimostare la tesi che 8 non divide $3^k+1$ per nessun $k$ per concludere.
Grazie dan!
Solo un dubbio... perchè scegli proprio 8?
Scusami tanto per il disturbo ma non mi capita spesso di cimentarmi in problemi simili
È una strategia che si usa spesso. Se vuoi dimostrare che un espressione non è un quadrato perfetto lo riduci modulo 4 o 8 (di solito), siccome riducendo modulo 4 non andavo lontano ho provato mod 8 e alla fine viene l'assurdo. Infatti, usiamo il principio di induzione per dimostrare che $3^k+1$ non è 0 mod 8. Supponiamo verificato il caso base $k=0$, allora sia verificato per $k=n$ mostriamo che vale per $k=n+1$. Essendo $3^n+1$ pari è o 2 o 4 mod 8 [nota]Si dimostra per induzione che non può essere 6 mod 8[/nota] nei due rispettivi casi abbiamo
$3^(n+1)+1 \equiv 4 mod 8$
$3^(n+1)+1 \equiv 2 mod 8$
Quindi $3^k+1$ non può essere divisibile per 8 per nessun k, in particolare $3^n(3^k+1)+1$ non è 1 mod 8 per nessun n e k come volevamo dimostrare.
$3^(n+1)+1 \equiv 4 mod 8$
$3^(n+1)+1 \equiv 2 mod 8$
Quindi $3^k+1$ non può essere divisibile per 8 per nessun k, in particolare $3^n(3^k+1)+1$ non è 1 mod 8 per nessun n e k come volevamo dimostrare.
Perfetto ti ringrazio ancora per la disponibilità, da solo non ci sarei mai arrivato
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo