Problema sul principio di induzione (e non solo)

Messaggioda Comemipare » 13/04/2019, 15:11

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.
Comemipare
New Member
New Member
 
Messaggio: 36 di 78
Iscritto il: 13/01/2018, 17:56

Re: Problema sul principio di induzione (e non solo)

Messaggioda dan95 » 14/04/2019, 07:36

Perché scomodare il principio di induzione quando esiste l'aritmetica modulare
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2486 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Problema sul principio di induzione (e non solo)

Messaggioda Comemipare » 14/04/2019, 09:23

dan95 ha scritto: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?
Comemipare
New Member
New Member
 
Messaggio: 37 di 78
Iscritto il: 13/01/2018, 17:56

Re: Problema sul principio di induzione (e non solo)

Messaggioda dan95 » 14/04/2019, 11:24

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.
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2487 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Problema sul principio di induzione (e non solo)

Messaggioda gugo82 » 14/04/2019, 11:40

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)$.
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 21146 di 44915
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Re: Problema sul principio di induzione (e non solo)

Messaggioda Comemipare » 14/04/2019, 11:48

dan95 ha scritto: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
Comemipare
New Member
New Member
 
Messaggio: 38 di 78
Iscritto il: 13/01/2018, 17:56

Re: Problema sul principio di induzione (e non solo)

Messaggioda dan95 » 14/04/2019, 20:02

È 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 81 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.

Note

  1. Si dimostra per induzione che non può essere 6 mod 8
"Chi è padrone del proprio respiro, è padrone della propria vita."~ Antico proverbio

"La capacità di scegliere è un dono che la natura fa all'uomo. Scegliere è un dono che l'uomo fa a se stesso." D.B.

"Il genio è semplicemente un uomo con la mente da donna." D. B.
dan95
Cannot live without
Cannot live without
 
Messaggio: 2488 di 5268
Iscritto il: 10/06/2013, 16:37
Località: Roma Caput Mundi

Re: Problema sul principio di induzione (e non solo)

Messaggioda Comemipare » 14/04/2019, 20:39

Perfetto ti ringrazio ancora per la disponibilità, da solo non ci sarei mai arrivato
Comemipare
New Member
New Member
 
Messaggio: 39 di 78
Iscritto il: 13/01/2018, 17:56


Torna a Scervelliamoci un po'

Chi c’è in linea

Visitano il forum: axpgn e 1 ospite