Relazione di ricorrenza

[stefano_89]

Ciao a tutti, ho un esercizio da proporvi, in realtà sarebbe di Dati e Algoritmi, ma ciò che non capisco è proprio la parte algebrica..
Ho la relazione di ricorrenza: $T(n) = T(n - d) - d + n^2$ con $d$ costante e maggiore di 1.
Ora, la relazione chiama sè stessa fino a quando $T(n - d)$ non diventa $T(1)$.

Inizialmente si ha: $T(n) = T(n - d) - d + n^2$
Comincia la ricorsione:$T(n − 2d) + d + (n − d)^2 + d + n^2$
Altro passo ricorsivo: $T(n − 3d) + d + (n − 2d)^2 + d + (n − d)^2 + d + n^2$

E fin qui tutto ok..

Ciò che non capisco è come possa essere riscritto tutto come: $n + \sum_{i=1}^(n/d) (n - id)^2$
Qualcuno può aiutarmi ?
Grazie in anticipo..

[misanino]

"stefano_89":Ciao a tutti, ho un esercizio da proporvi, in realtà sarebbe di Dati e Algoritmi, ma ciò che non capisco è proprio la parte algebrica..
Ho la relazione di ricorrenza: $T(n) = T(n - d) - d + n^2$ con $d$ costante e maggiore di 1.
Ora, la relazione chiama sè stessa fino a quando $T(n - d)$ non diventa $T(1)$.

Inizialmente si ha: $T(n) = T(n - d) - d + n^2$
Comincia la ricorsione:$T(n − 2d) + d + (n − d)^2 + d + n^2$
Altro passo ricorsivo: $T(n − 3d) + d + (n − 2d)^2 + d + (n − d)^2 + d + n^2$

E fin qui tutto ok..

Ciò che non capisco è come possa essere riscritto tutto come: $n + \sum_{i=1}^(n/d) (n - id)^2$
Qualcuno può aiutarmi ?
Grazie in anticipo..

C'e' un po' di confusione in cio' che scrivi.
Allora:
T(1) e' data dal problema, giusto?
Per ricorsione definisci T(n) come $T(n) = T(n - d) - d + n^2$. Il che pero' ti dice che non hai definito $T(n)$ per ogni n, ma solo per quelli che si possono scrivere come $n=1+kd$ con $k\inNN$. E' cosi' o c'e' qualcosa di sbagliato in quello che hai scritto?
E poi cosa puo' essere riscritto come $n + \sum_{i=1}^(n/d) (n - id)^2$?

[stefano_89]

In realtà in questo caso, T(1) non viene data.
Per rispondere alla tua ultima domanda: T(n) viene richiamato ricorsivamente un certo numero di volte, dopo 2 o 3 chiamate ricorsive, uno dovrebbe riuscire a notare come scrivere il risultato ottenuto attraverso la serie. In questo caso, le serie è quella cheho scritto, ma io non riesco proprio a vederla e ricavarmela dagli sviluppi dei T(n)..

[misanino]

"stefano_89":In realtà in questo caso, T(1) non viene data.
Per rispondere alla tua ultima domanda: T(n) viene richiamato ricorsivamente un certo numero di volte, dopo 2 o 3 chiamate ricorsive, uno dovrebbe riuscire a notare come scrivere il risultato ottenuto attraverso la serie. In questo caso, le serie è quella cheho scritto, ma io non riesco proprio a vederla e ricavarmela dagli sviluppi dei T(n)..

Ma la serie che hai scritto è T(n) (o meglio quello che dovrebbe essere T(n)) o cosa?