Proprietà distributiva generalizzata
Ciao a tutti, sono nuovo e sono alla ricerca di un aiuto per capire un passaggio della dimostrazione riportata dal mio prof riguardo la proprietà distributiva generalizzata.
Nel mio caso la dimostrazione ha questa veste:
E mi incespico sull'ultimo passaggio, $sum_0^s sum_0^t a_(s+1) b_j=sum_0^(s+1) sum_0^t a_i b_j$ (**).
In particolare il dubbio è il seguente: riesco a farmi un esempio del fatto che funzioni questo passaggio, ma il fatto che questo valga per ogni s e s+1 non dovrebbe a sua volta essere dimostrato per induzione. Voglio dire che questo passaggio non mi sembra una dimostrazione in quanto io per dimostrare il primo passaggio nella pic. giungo tramite l'induzione a quest' ultimo passaggio che non mi convince che mi sembra di nuovo da dimostrarsi per induzione.
Insomma non mi sembra una dimostrazione perché comunque sia io non posso garantire che per ogni s valga (**), dovrei dimostrarlo....per induzione a sua volta
(è un cane che si morde la coda), non capisco cosa mi sfugga del ragionamento sotteso.
Nel mio caso la dimostrazione ha questa veste:
E mi incespico sull'ultimo passaggio, $sum_0^s sum_0^t a_(s+1) b_j=sum_0^(s+1) sum_0^t a_i b_j$ (**).
In particolare il dubbio è il seguente: riesco a farmi un esempio del fatto che funzioni questo passaggio, ma il fatto che questo valga per ogni s e s+1 non dovrebbe a sua volta essere dimostrato per induzione. Voglio dire che questo passaggio non mi sembra una dimostrazione in quanto io per dimostrare il primo passaggio nella pic. giungo tramite l'induzione a quest' ultimo passaggio che non mi convince che mi sembra di nuovo da dimostrarsi per induzione.
Insomma non mi sembra una dimostrazione perché comunque sia io non posso garantire che per ogni s valga (**), dovrei dimostrarlo....per induzione a sua volta
(è un cane che si morde la coda), non capisco cosa mi sfugga del ragionamento sotteso.
Risposte
Ti riferisci a questo passaggio?
\[ \Bigl(\sum_{i=0}^s \sum_{j=0}^t a_i b_j\Bigr) + \Bigl(\sum_{j=0}^t a_{s+1} b_j\Bigr) = \sum_{i=0}^{s+1} \sum_{j=0}^t a_i b_j \]
Ho aggiunto le parentesi in caso non fosse chiaro come erano raggruppati i termini. In ogni caso non serve alcune induzione, usa solo la definizione di \(\sum\). Infatti \[ \sum_{i=0}^s \sum_{j=0}^t a_i b_j = \Bigl(\sum_{j=0}^t a_0 b_j\Bigr) + \Bigl(\sum_{j=0}^t a_1 b_j\Bigr) + \dotsb + \Bigl(\sum_{j=0}^t a_s b_j\Bigr) \] ne ha solo aggiunto un termine.
\[ \Bigl(\sum_{i=0}^s \sum_{j=0}^t a_i b_j\Bigr) + \Bigl(\sum_{j=0}^t a_{s+1} b_j\Bigr) = \sum_{i=0}^{s+1} \sum_{j=0}^t a_i b_j \]
Ho aggiunto le parentesi in caso non fosse chiaro come erano raggruppati i termini. In ogni caso non serve alcune induzione, usa solo la definizione di \(\sum\). Infatti \[ \sum_{i=0}^s \sum_{j=0}^t a_i b_j = \Bigl(\sum_{j=0}^t a_0 b_j\Bigr) + \Bigl(\sum_{j=0}^t a_1 b_j\Bigr) + \dotsb + \Bigl(\sum_{j=0}^t a_s b_j\Bigr) \] ne ha solo aggiunto un termine.
Sì, esatto mi riferivo proprio a quello ma mi sono incasinato cercando di capire come scriverlo in formule, non avevo mai usato questo sistema. ma ho capito l'errore di scrittura.
Detto ciò,
non riesco a capire però perché non debba dimostrarlo, nel senso che la definizione vale per un s fissato ad esempio se fosse s=5 riporto i 5 addendi della forma da te mostrata cui aggiungo il s+1 esimo (nel caso specifico il 5 + 1 esimo). però questo vale per un certo s, chi mi dice valga per s+1. Cioè in un certo senso mi sembra da dimostrarsi per induzione che dato qualunque s vale quella proprietà. Invece dici che vale per definizione, e non riesco bene a capire perché.
grazie
Detto ciò,
non riesco a capire però perché non debba dimostrarlo, nel senso che la definizione vale per un s fissato ad esempio se fosse s=5 riporto i 5 addendi della forma da te mostrata cui aggiungo il s+1 esimo (nel caso specifico il 5 + 1 esimo). però questo vale per un certo s, chi mi dice valga per s+1. Cioè in un certo senso mi sembra da dimostrarsi per induzione che dato qualunque s vale quella proprietà. Invece dici che vale per definizione, e non riesco bene a capire perché.
grazie
Una sommatoria è una notazione e ha una sua definizione (ovviamente induttiva). Uso la scrittura \(S(n, m, a)\) per la sommatoria \(\sum_{i=n}^{m} a_i\) perché è più rapida e ugualmente espressiva per i miei scopi.
Senza voler entrare in questioni troppo formali, allora
\[
S(n, m, a) \triangleq \begin{cases} 0 & \text{ se } n > m \\ a_n + S(n+1, m, a) & \text{ altrimenti} \end{cases}
\]
Nota che per la proprietà associativa, puoi anche definirla come:
\[
S(n, m, a) \triangleq \begin{cases} 0 & \text{ se } n > m \\ S(n, m-1, a) + a_m & \text{ altrimenti} \end{cases}
\]
Concordi? Nota che usato \(\triangleq\) con il significato di uguale per definizione, ovvero quella è la definizione formale della sommatoria, non qualcosa da dimostrare.
Nel tuo caso hai semplicemente \(S(0, s, c)\) con \(c_i = S(0, t, d^i)\) e \(d^i_j = a_ib_j\) (gli esponenti sopra e sotto sono solo per comodità). Il punto è che \(\Bigl(\sum_{j=0}^t a_{s+1} b_j\Bigr) = c_{s+1}\) e, per la definizione induttiva di \(S\), hai che \(S(0,s+1, c) \triangleq S(0, s, c) + c_{s+1}\).
Cioè, è vero che c'è un passo induttivo, ma è insito nella definizione di sommatoria. Spero di aver chiarito il concetto.
Senza voler entrare in questioni troppo formali, allora
\[
S(n, m, a) \triangleq \begin{cases} 0 & \text{ se } n > m \\ a_n + S(n+1, m, a) & \text{ altrimenti} \end{cases}
\]
Nota che per la proprietà associativa, puoi anche definirla come:
\[
S(n, m, a) \triangleq \begin{cases} 0 & \text{ se } n > m \\ S(n, m-1, a) + a_m & \text{ altrimenti} \end{cases}
\]
Concordi? Nota che usato \(\triangleq\) con il significato di uguale per definizione, ovvero quella è la definizione formale della sommatoria, non qualcosa da dimostrare.
Nel tuo caso hai semplicemente \(S(0, s, c)\) con \(c_i = S(0, t, d^i)\) e \(d^i_j = a_ib_j\) (gli esponenti sopra e sotto sono solo per comodità). Il punto è che \(\Bigl(\sum_{j=0}^t a_{s+1} b_j\Bigr) = c_{s+1}\) e, per la definizione induttiva di \(S\), hai che \(S(0,s+1, c) \triangleq S(0, s, c) + c_{s+1}\).
Cioè, è vero che c'è un passo induttivo, ma è insito nella definizione di sommatoria. Spero di aver chiarito il concetto.
Per capire meglio il concetto, pensa alla moltiplicazione sugli interi con la assiomatizzazione di Peano.
Se segno con \(\sigma(a)\) il successivo di \(a\) allora ho che \(a\times 1 \triangleq a\) e \(a\times \sigma(b) \triangleq a\times b + a\). Insomma, usando questa assiomatizzazione, \(a\times b + a = a\times (b+1)\) non ha bisogno di essere dimostrato perché è vero per definizione della moltiplicazione. Al contrario, con questa definizione, \(a \times (b + c) = a\times b + a\times c\) richiederebbe una dimostrazione. Anche se, ovviamente, nessun che non stia facendo un corso sugli assiomi di Peano si metterebbe a farlo.
Se segno con \(\sigma(a)\) il successivo di \(a\) allora ho che \(a\times 1 \triangleq a\) e \(a\times \sigma(b) \triangleq a\times b + a\). Insomma, usando questa assiomatizzazione, \(a\times b + a = a\times (b+1)\) non ha bisogno di essere dimostrato perché è vero per definizione della moltiplicazione. Al contrario, con questa definizione, \(a \times (b + c) = a\times b + a\times c\) richiederebbe una dimostrazione. Anche se, ovviamente, nessun che non stia facendo un corso sugli assiomi di Peano si metterebbe a farlo.
Direi che ora mi è molto chiaro, in particolare per il messaggio precedente. Non mi era difatti mai stata mostrata come definizione ricorsiva/induttiva ma mi è subito stata usata come qualcosa di intrinsecamente conosciuto da noi studenti.
Devo dire che con la fomralizzazione 1 e poi 2 per associatività mi sembra molto chiaro, ho solo applicato quella definizione vera per induzione già di per sé.
Devo dire che con la fomralizzazione 1 e poi 2 per associatività mi sembra molto chiaro, ho solo applicato quella definizione vera per induzione già di per sé.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo