Principio induzione
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.
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
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$
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...
$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...
"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 ...

Cordialmente, Alex
Ok, direi che ci siamo capiti..............
P.S.:
Allegramente.
Marco

P.S.:
Allegramente.
Marco
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
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
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
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$
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$