Equazioni di ricorrenza

[iDesmond]

Ho cercato sul forum e ho trovato tanti post sulle equazioni di ricorrenza, ma erano tutti problemi particolari, diversi dal mio (che probabilmente è assai banale).

Non ricordo come si svolgono le equazioni d ricorrenza del tipo:
$a_(n+4) - a_n = 2(a_(n+3)-a_(n+1))+3*2^n$
con condizioni iniziali:
$a_0=1, a_1=2, a_2=4, a_3=0$

Oppure problema analogo:
$t_n=2t_(n-2) - t_(n-4) + 8$ con $t_0=2, t_1=3, t_2=10, t_3=11$

Mi ricordo che dovevo sostituire un polinomio con variabile n (del tipo $b, an+b, an^2 +bn +c$)... ma mi sono scordato tutto il resto!

E poi dato che ci sono ne approfitto per quest'altro quesito:
con $T(1)=1$ e $T(n)= 4T(n/2)+n^2$
so calcolare l'ordine di grandezza (se non ricordo male è $n^2log(n)$), e poi il problema mi chiede di determinare la soluzione esatta quando n è una potenza di 2.
Se non ricordo male bisognava sostituire chiaramente $n=2^k$, si ottiene $T(2^k)= 4T(2^(k-1))+2^(2k)$, da qui come dovevo ri-sostituire? (questo problema si risolve con il metodo dei fattori sommanti giusto?)

Grazie mille!

PS per $T(n) = 2T(sqrt(n)) + logn$? come la riporto in una forma per usare il teorema principale?

[iDesmond]

"iDesmond":E poi dato che ci sono ne approfitto per quest'altro quesito:
con $T(1)=1$ e $T(n)= 4T(n/2)+n^2$
so calcolare l'ordine di grandezza (se non ricordo male è $n^2log(n)$), e poi il problema mi chiede di determinare la soluzione esatta quando n è una potenza di 2.
Se non ricordo male bisognava sostituire chiaramente $n=2^k$, si ottiene $T(2^k)= 4T(2^(k-1))+2^(2k)$, da qui come dovevo ri-sostituire? (questo problema si risolve con il metodo dei fattori sommanti giusto?)

Okay, devo sostituire probabilmente $T(2^k)=H(k)$ e così ottengo:
$H(k)=4H(k-1) + 2^(2k)$ (l'ultimo termine rimane invariato giusto? perché ho sostituito T non la variabile dentro T)
questa è come scrivere $H(k) = 4(H(k-1) + 4^(k-1))$
quindi la soluzione sarebbe? qualcosa del tipo $4^k$ che moltiplica la sommatoria da 0 a k-1 di $4^(k-1)$?
Come sfrutto l'informazione che $T(1)=1$?

"iDesmond":
per $T(n) = 2T(sqrt(n)) + logn$? come la riporto in una forma per usare il teorema principale?

Ok questa semplicemente si pone $m=log_2(n) -> T(2^m)=2T(2^(m/2)) + m$ e sostituendo $S(m)=T(2^m)$ si ricava:
$S(m)=2S(m/2) + m$... dunque la soluzione è $\teta(nlogn)$


Comunque quello che più mi preme è il primo quesito

[iDesmond]

"iDesmond":Non ricordo come si svolgono le equazioni d ricorrenza del tipo:
$a_(n+4) - a_n = 2(a_(n+3)-a_(n+1))+3*2^n$
con condizioni iniziali:
$a_0=1, a_1=2, a_2=4, a_3=0$

Oppure problema analogo:
$t_n=2t_(n-2) - t_(n-4) + 8$ con $t_0=2, t_1=3, t_2=10, t_3=11$

Okay trovata la risposta:
per prima cosa si risolve l'equazione omogenea associata, per esempio nel primo caso diviene:
$x^4 - 1 = 2(x^3 - x)$ cioè $x^4 -2x^3 +2x -1=0$
Si trova la classe delle soluzioni ${\lambda_1x_1, \lambda_2x_2, ..., \lambda_4x_4}$ con $x_i$ soluzioni (nel caso ci siano radici multiple si fa in modo leggermente diverso).

Poi si cerca di risolvere l'omogena, in genere sostituendo forme del tipo $b, an+b, an^2+bn+c, an+b + c^n...$
A quel punto si mettono insieme le soluzioni particolare e generale (con i \lambda_i) e, sostituendo le condizioni iniziali, si ricava la soluzione esatta.

Scritto molto veloce e poco chiaro, ma qualcosa meglio di niente è