Salve...
non mi è ben chiaro il perchè si possa passare da una definizione ricorsiva tipo:
$ a_{n+k}=t_{k-1}a_{n+k-1}+t_{k-1}a_{n+k-2}+\cdots+t_0a_n $
alla sua funzione generatrice (o polinomio caratteristico, è la stessa cosa?)
$ x^{n+k}=t_{k-1}x^{n+k-1}+t_{k-1}x^{n+k-2}+\cdots+t_0x^n $
Grazie
Relazioni di ricorrenza e funzioni generatrici
Forse dovrei fare una domanda più precisa:
ho capito che la funzione generatrice si comporta come la successione (parlo della ricorrenza), ma non mi è ben chiaro il perchè questa ci permetta poi di trovare una formula chiusa per i termini della successione. Se per esempio si parla dei numeri di Fibonacci, mi è abbastanza chiaro che la successione definita da $ q^{n+2}=q^{n+1}+q^{n} $ si comporti allo stesso modo, ma anche $ n+2=n+1+n $ lo fa (forse il motivo è che la precedente lo fa, con certi q, per tutti gli n?)
ho capito che la funzione generatrice si comporta come la successione (parlo della ricorrenza), ma non mi è ben chiaro il perchè questa ci permetta poi di trovare una formula chiusa per i termini della successione. Se per esempio si parla dei numeri di Fibonacci, mi è abbastanza chiaro che la successione definita da $ q^{n+2}=q^{n+1}+q^{n} $ si comporti allo stesso modo, ma anche $ n+2=n+1+n $ lo fa (forse il motivo è che la precedente lo fa, con certi q, per tutti gli n?)
prima di tutto: "polinomio caratteristico" e "funzione generatrice" non sono la stessa cosa. questo è un polinomio caratteristico, mentre la funzione generatrice sarebbe qualcosa tipo $ G(z) = \sum_{k\ge 0} a_k z^k $ (e qui si cade nel profondamente non-elementare, quindi non divago oltre - c'è un libro* che spiega come usarle, ma non ricordo se faccia le cose a modo o se tratti tutto come se stesse insegnando a dei fisici).
prima di tutto, cosa vuol dire "il polinomio caratteristico si comporta come la successione"?
nella mia testa il polinomio caratteristico non "si comporta", ma "è" e basta: tutt'al più puoi dire che "assomiglia" alla successione in qualche modo, ma non che "si comporti" come lei.
detto ciò, ci sono almeno tre risposte possibili al "perché" il polinomio caratteristico dovrebbe funzionare:
- la prima, molto insoddisfacente (per me), è semplicemente perché funziona, ovvero perché si dimostra per induzione che funziona.
- la seconda è una risposta strettamente da MNE, e passa per algebra lineare (e teorema di jordan, quando saprai cos'è), e spiega il nome "polinomio caratteristico": non ho intenzione di spenderci tante parole (anche perché sono off topic), ma si associano alla successione una matrice (la ricorrenza) ed un vettore (i valori iniziali) e da questi si ricostruisce la successione. il polinomio caratteristico di cui parli tu è il polinomio caratteristico della matrice.
- la terza passa appunto per le funzioni generatrici, e quindi non è strettamente matematica olimpica: manipolando (formalmente) la funzione generatrice, dovresti scoprire che c'è una relazione "buona" tra il polinomio caratteristico e la funzione generatrice (non ho carta e penna sottomano, quindi non la provo neppure a ricavare), quindi riesci a scrivere esplicitamente la funzione generatrice, e di conseguenza la successione.
spero che quello che ho scritto abbia un senso
* il libro si chiama "generatingfunctionology", e dovresti trovarlo online abbastanza facilmente.
prima di tutto, cosa vuol dire "il polinomio caratteristico si comporta come la successione"?
nella mia testa il polinomio caratteristico non "si comporta", ma "è" e basta: tutt'al più puoi dire che "assomiglia" alla successione in qualche modo, ma non che "si comporti" come lei.
detto ciò, ci sono almeno tre risposte possibili al "perché" il polinomio caratteristico dovrebbe funzionare:
- la prima, molto insoddisfacente (per me), è semplicemente perché funziona, ovvero perché si dimostra per induzione che funziona.
- la seconda è una risposta strettamente da MNE, e passa per algebra lineare (e teorema di jordan, quando saprai cos'è), e spiega il nome "polinomio caratteristico": non ho intenzione di spenderci tante parole (anche perché sono off topic), ma si associano alla successione una matrice (la ricorrenza) ed un vettore (i valori iniziali) e da questi si ricostruisce la successione. il polinomio caratteristico di cui parli tu è il polinomio caratteristico della matrice.
- la terza passa appunto per le funzioni generatrici, e quindi non è strettamente matematica olimpica: manipolando (formalmente) la funzione generatrice, dovresti scoprire che c'è una relazione "buona" tra il polinomio caratteristico e la funzione generatrice (non ho carta e penna sottomano, quindi non la provo neppure a ricavare), quindi riesci a scrivere esplicitamente la funzione generatrice, e di conseguenza la successione.
spero che quello che ho scritto abbia un senso
* il libro si chiama "generatingfunctionology", e dovresti trovarlo online abbastanza facilmente.
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12