Ricorrenza a doppio indice che è semplice ma boh
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Ricorrenza a doppio indice che è semplice ma boh
Sia \(T_{k,n}\) una serie definita per ricorrenza così:
\(T_{k,n} = 2T_{k-1, n-1} - T_{k,n-2}\)
\(T_{k,1} = 0\) a parte \(T_{1,1}=1\)
Sono una scarsone in algebra lineare, ma penso si faccia proprio semplicemente! Se ci riuscite poi vi svelo cos'è \(T_{k,n}\)
\(T_{k,n} = 2T_{k-1, n-1} - T_{k,n-2}\)
\(T_{k,1} = 0\) a parte \(T_{1,1}=1\)
Sono una scarsone in algebra lineare, ma penso si faccia proprio semplicemente! Se ci riuscite poi vi svelo cos'è \(T_{k,n}\)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
- karlosson_sul_tetto
- Messaggi: 1454
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Ricorrenza a doppio indice che è semplice ma boh
Scusa, ma come posso definire $ T_{k,2} $ se nella formulozza viene $ T_{k,0} $?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Ricorrenza a doppio indice che è semplice ma boh
Scusa, manca anche \( T_{k,0} = 0 \) a parte \(T_{0,0} = 1\)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: Ricorrenza a doppio indice che è semplice ma boh
Direi che manca anche $T_{0,k}$, che è circa quello fondamentale!
Per ora la mia ricorrenza ha tutti zeri a parte $T_{k,k}=2^{k-1}$ xD
Comunque come lo puoi vedere in algebra lineare? Cioè, sarebbe circa una matrice infinita, ma come fai a riscrivere la relazione?
Per ora la mia ricorrenza ha tutti zeri a parte $T_{k,k}=2^{k-1}$ xD
Comunque come lo puoi vedere in algebra lineare? Cioè, sarebbe circa una matrice infinita, ma come fai a riscrivere la relazione?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Ricorrenza a doppio indice che è semplice ma boh
Per k<0 vale 0. Scusate ma l'ho mutuato da un altro problema, perció i casi base non erano cos chiari! Comunque a me è venuta con un metodo mio, ma mi avevano detto che era algebra lineare.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Ricorrenza a doppio indice che è semplice ma boh
Dai, per risollevare un po' le sorti di questo post svelo cos'è \(T_{k,n}\): il coefficiente di \(x^k\) nell' \(n\)-esimo polinomio di Chebyshev, e si riesce effettivamente a trovare una formula chiusa.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: Ricorrenza a doppio indice che è semplice ma boh
Mi viene che $\displaystyle T_{k,n} = 0$ se $n < k$ o se $n-k$ è dispari.
Altrimenti mi viene $\displaystyle T_{k,n} = (-1)^{\frac{n-k}{2}} \cdot 2^{k-1} \binom{\frac{n+k}{2} -1} {k-1}\frac{n}{k}$ che ovviamente dopo che è piovuta dal cielo si dimostra che è vera per induzione
Altrimenti mi viene $\displaystyle T_{k,n} = (-1)^{\frac{n-k}{2}} \cdot 2^{k-1} \binom{\frac{n+k}{2} -1} {k-1}\frac{n}{k}$ che ovviamente dopo che è piovuta dal cielo si dimostra che è vera per induzione
Re: Ricorrenza a doppio indice che è semplice ma boh
Uhm ... ma scrivere la funzione generatrice e risolvere?
Testo nascosto:
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Ricorrenza a doppio indice che è semplice ma boh
Io ho fatto così (usando quel fatto di cui ti avevo parlato una volta su fb, EvaristeG).
Non mi dilungo sul metodo generale, anche se sarebbe più pulito e meno frammentario. Se qualcuno è interessato lo scrivo.
Se associamo a \(T_{k,n}\) il punto \((n,k)\) sul piano, possiamo visualizzare la ricorrenza come un reticolo:
il punto \((k,n)\) è collegato a \((k-1,n-1)\) e a \((k,n-2)\), a cui "chiede" il loro valore moltiplicandoli rispettivamente per \(2\) e \(-1\). Così continua a catena, finchè non incontra un punto non nullo, ossia \((1,1)\) o \((0,0)\). In realtà \((0,0)\) darà un contributo solo ai punti \((n,0)\) sopra di lui, perchè tutti gli altri si fermeranno a \((1,1)\); allo stesso modo \((1,1)\) non darà alcun contributo ai punti \(T_{n,0}\).
Perciò:
1) \(T_{n,0}\):
\(T_{2n+1,0}\) non arriva mai a \((0,0)\), perciò è 0;
\(T_{2n}\) arriva a \((0,0)\) in un solo modo moltiplicato per \((-1)\) \(n\) volte, perciò \(T_{2n,0} = (-1)^n\).
2) \(T_{n,k}\), \(k>0\):
se \(n-k \equiv 1 \pmod{2}\), non arriva mai alla diagonale di \((1,1)\), perciò è 0.
se \(n-k \equiv 0 \pmod{2}\), faccio \(\frac{n-k}{2}\) passi verso il basso e \(k-1\) passi in diagonale; perciò ho \(\displaystyle T_{n,k} = \binom{ \frac{n+k}{2} -1 }{k-1} 2^{k-1} (-1)^{(n-k)/2} \).
Non mi dilungo sul metodo generale, anche se sarebbe più pulito e meno frammentario. Se qualcuno è interessato lo scrivo.
Se associamo a \(T_{k,n}\) il punto \((n,k)\) sul piano, possiamo visualizzare la ricorrenza come un reticolo:
il punto \((k,n)\) è collegato a \((k-1,n-1)\) e a \((k,n-2)\), a cui "chiede" il loro valore moltiplicandoli rispettivamente per \(2\) e \(-1\). Così continua a catena, finchè non incontra un punto non nullo, ossia \((1,1)\) o \((0,0)\). In realtà \((0,0)\) darà un contributo solo ai punti \((n,0)\) sopra di lui, perchè tutti gli altri si fermeranno a \((1,1)\); allo stesso modo \((1,1)\) non darà alcun contributo ai punti \(T_{n,0}\).
Perciò:
1) \(T_{n,0}\):
\(T_{2n+1,0}\) non arriva mai a \((0,0)\), perciò è 0;
\(T_{2n}\) arriva a \((0,0)\) in un solo modo moltiplicato per \((-1)\) \(n\) volte, perciò \(T_{2n,0} = (-1)^n\).
2) \(T_{n,k}\), \(k>0\):
se \(n-k \equiv 1 \pmod{2}\), non arriva mai alla diagonale di \((1,1)\), perciò è 0.
se \(n-k \equiv 0 \pmod{2}\), faccio \(\frac{n-k}{2}\) passi verso il basso e \(k-1\) passi in diagonale; perciò ho \(\displaystyle T_{n,k} = \binom{ \frac{n+k}{2} -1 }{k-1} 2^{k-1} (-1)^{(n-k)/2} \).
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe