Ricorrenza a doppio indice che è semplice ma boh

[Gottinger95]

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}\)

[karlosson_sul_tetto]

Scusa, ma come posso definire $ T_{k,2} $ se nella formulozza viene $ T_{k,0} $?

[Gottinger95]

Scusa, manca anche \( T_{k,0} = 0 \) a parte \(T_{0,0} = 1\)

[Drago96]

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?

[Gottinger95]

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.

[Gottinger95]

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.

[xXStephXx]

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

[EvaristeG]

Uhm ... ma scrivere la funzione generatrice e risolvere?

Testo nascosto:

Poni $f(x,y)=\sum T_{k,n}x^ky^n$ ed allora
$$f(x,y)=2xy(f(x,y)-T_{0,0}) -y^2 f(x,y) + T_{0,0} + \sum_k T_{k,0}x^k +T_{0,1}y + T_{1,1}xy$$
da cui
$$f(x,y)(1-2xy+y^2)=1-xy$$
ovvero
$$f(x,y)=\dfrac{1-xy}{1-2xy+y^2}=\sum_{h}y^h(2x-y)^h(1-xy)=\sum_hy^h\sum_{j=0}^h(-1)^{h-j}2^jx^jy^{h-j}\binom{h}{j} - \sum_h xy^h\sum_{j=0}^h(-1)^{h-j}2^jx^jy^{h-j}\binom{h}{j}$$
e riordinando si ottiene che $T_{k,n}$ è nullo se $k>n$ o se $k$ e $n$ hanno parità diversa, altrimenti si ha
$$T_{k,n}=(-1)^{\frac{n-k}{2}}2^{k-1}\left(2\binom{\frac{n+k}{2}}{k}-\binom{\frac{n+k}{2}-1}{k-1}\right)$$

[Gottinger95]

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} \).