Ricorrenza, soluzione esatta

[vl4dster]

Niente bigO

$T(n) = \sum_{k=1}^{n-1}[T(k)+T(n-k)+1]$ con $T(1) = 1$

ho cercato una soluzione esatta ma mi sono ritrovato
cose non proprio carine...

forse ho sonno...

EDIT: le parentesi (uffa)

[elgiovo]

"vl4d":

$T(n) = \sum_{k=1}^{n-1}T(k)+T(n-k)+1$ con $T(1) = 1$

forse ho sonno...

E' ambiguo, usa meglio le parentesi. E' $T(n) = \sum_{k=1}^{n-1}[T(k)+T(n-k)+1]$ oppure $T(n) = \sum_{k=1}^{n-1}[T(k)+T(n-k)]+1$?

[elgiovo]

In primis, un'osservazione sulla sommatoria a secondo membro: $sum_(k=1)^(n-1) (T_k+T_(n-k)+1)=2sum_(k=1)^(n-1)T_k + n-1$ (occhio, $n-1$ è fuori dalla sommatoria).
Moltiplico per $x^n$ ambo i membri e sommo su tutti i valori di $n$ ammissibili (credo che la tua ricorrenza valga per $n=1,2,3,ldots$, visto che fornisci il valore $T_1$). A proposito: d'ora in poi invece di $T(k)$ scriverò $T_k$.
$sum_(n=1)^(+oo)T_nx^n=2sum_(n=1)^(+oo)sum_(k=1)^(n-1)T_k x^n + sum_(n=1)^(+oo)n x^n - sum_(n=1)^(+oo)x^n$. Si deve cercare di ricondurre tutto ad un'equazione nell'incognita $T(x)$, dove $T(x)=T_1x+T_2x^2+ldots$, per cui bisogna "aggiustare" in qualche modo quella doppia sommatoria al secondo membro. Scriviamola in forma estesa:
$sum_(n=1)^(+oo)sum_(k=1)^(n-1)T_k x^n = (T_1)x^2+(T_1+T_2)x^3+(T_1+T_2+T_3)x^4+ldots=T_1(x^2+x^3+x^4+ldots)+T_2(x^3+x^4+x^5+ldots)+T_3(x^4+x^5+x^6+ldots)=T_1x^2 1/(1-x)+T_2x^3 1/(1-x)+ldots+T_ix^(i+1) 1/(1-x)+ldots$
$=1/(1-x) (T_1x^2+T_2x^3+ldots+T_ix^(i+1)+ldots)=1/(1-x) sum_(n=1)^(+oo)T_n x^(n+1)$. A questo punto, allora, l'equazione in $T(x)$ diventa: $T(x)= (2x)/(1-x) T(x) + x d/(dx) 1/(1-x)-x/(1-x)$,
che ammette come soluzione la nostra bella funzione generatrice $T(x)=(x^2)/((x-1)(3x-1))$.
$T_n$ è il coefficiente di $x^n$ dello sviluppo in serie di $T(x)$.

[vl4dster]

mannaggia a me e alle mie funzioni generatrici