Principio induzione

Iago98
Salve ragazzi,
sono un nuovo membro di questo forum e volevo chiedervi un aiuto per un esercizio. Il quesito che mi attanaglia dice: "Dimostrare per induzione che per ogni intero $n>=14$ esistono interi non negativi $x$,$y in NN$ tali che $n=3x+8y$". L'esercizio già ti dice come risolvere il problema e la verifica di $P(n_0)$ è immediata, prendendo $(2,1)$. La mia difficoltà sta nel passo induttivo, cioè nel dimostrare che se vale per $n$ vale anche per $n+1$. Qualche indizio su come andare avanti?? Grazie.

Risposte
axpgn
Per me la devi dimostrare usando l'induzione forte ovvero devi dimostrare come passo base i tre casi $n=14, 15, 16$, dopodiché il passo induttivo diventa $n+1=3x_0+8y_0\ ->\ n-2=3x_0+8y_0+3\ ->\ n-2=3(x_0+1)+8y_0$

teorema55
Temo di non essere d'accordo. Il passaggio corretto è

$n+1=3x_0 +8y_0$

$n-2=3x_0 +8y_0 -3$

$n-2=3(x_0 -1)+8y_0$

Inoltre, se $n=14$, la formula non si applica ad $n-2$ !

Interessante, ci devo pensare...

axpgn
"teorema55":
Inoltre, se $n=14$, la formula non si applica ad $n-2$ !

Infatti, ho detto che devi dimostrarla per $14$, $15$ e $16$ come passo base, a quel punto puoi applicare il passo induttivo come detto sopra perché il "primo $n+1$" sarà $17$ e quindi $n-2=14$ già verificato ... ok?

Grazie per la correzione del refuso ... :D

Cordialmente, Alex

teorema55
Ok, direi che ci siamo capiti.............. :-D

P.S.:


Allegramente.

Marco

Iago98
Scusate l'ora tarda e grazie per le risposte, comunque credo non sia la risposta. Primo perchè il principio di induzione forte lo spiega nel capitolo successivo all'esercizio quindi credo non se ne richieda l'uso. Secondo, come avete fatto voi sarebbe l'analogo a dimostrare con l'induzione semplice che se vale per $n$ vale per $n+3$, e perciò la proprietà vale per tutti gli $n$ congruenti a $n_0$ modulo 3. Ugualmente per 8, vale per i numeri congruenti a $n_0$ modulo 8. Ma non esauriscono tutti i numeri, quindi non credo sia la strada giusta o che almeno la dimostrazione sia finita, ma comunque grazie per avermi risposto. Ciao

axpgn
Questo tipo di problemi (con due variabili) si presta bene per dimostrazioni con l'induzione forte mentre non mi viene in mente niente con l'induzione debole.
Non ho capito bene il tuo discorso sulle congruenze ma ti garantisco che la mia dimostrazione vale per tutti i numeri: dopo aver validato la proposizione per i tre valori base qualsiasi numero tu prenda (maggiore di $16$ e pensabile come $n+1$) lo puoi sempre ricondurre al caso $n-2$ che è vero per ipotesi induttiva.
Cordialmente, Alex

@melia
Non trovo contraddizione nel fatto che,
dimostrato per $n=14$ valga per tutti gli $n+3$,
poi dimostrato per $n=15$ valga per tutti gli $n+3$, e, infine
dimostrato per $n=16$ valga per tutti gli $n+3$, dà la dimostrazione per ogni $n>=14$

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.