Progressione aritmetica su T(N)

[emotions1]

Buonasera a tutti, qualcuno gentilmente mi darebbe una mano a capire da dove esce il 2n-2 nella seguente progressione aritmetica?? Ho letto diverse guide su internet ma continuo a non capire come ottenerlo.

https://i.imgur.com/bv8qiaE.png

Inoltre da dove escono questi 2 + 4 iniziali??
2 + 4 +.....+ n/4 + n/2 + n = 2n - 2

[Studente Anonimo]

$n$ è una potenza di $2$, quindi $n=2^k$ e la somma è una progressione geometrica. Cioè quello che ti sta dicendo è che [tex]\sum_{i=1}^k 2^i = 2^{k+1}-2[/tex] che è un fatto classico riguardante le somme delle progressioni geometriche, prova a fare una ricerca.

[emotions1]

"Martino":$n$ è una potenza di $2$, quindi $n=2^k$ e la somma è una progressione geometrica. Cioè quello che ti sta dicendo è che [tex]\sum_{i=1}^k 2^i = 2^{k+1}-2[/tex] che è un fatto classico riguardante le somme delle progressioni geometriche, prova a fare una ricerca.

Questa è la differenza tra i due tipi di progressione:

- aritmetica: - Una progressione aritmetica è una successione di numeri reali tali che la differenza tra ciascuno di essi ed il precedente è costante; questa costante viene chiamata ragione della progressione e viene indicata con la lettera d.

- geometria: Una progressione geometrica è una successione di numeri reali tali che il rapporto tra ciascuno di essi ed il precedente è costante; questa costante viene chiamata ragione della progressione e viene indicata con la lettera q.

Da cosa capisco quale delle due tipologie di progressioni devo usare?

Ritornando all'esempio che ho postato il $T(n/8)$ non è da considerare nella progressione, infatti esso è lo sviluppo della complessita temporale della Relazione di Ricorrenza, e da come risultato il termine $a$ che si vede nella soluzione: $a + b(2n-2)$

Provo a postare un esempio piu semplice per capirci. sia PA(progressione aritmetica) e PG(progressione geometrica), il mio obbiettivo se non ho capito male dovrebbe essere quello di calcolare la somma della PA o PG e non la ragione $d$ della PA o PG. Detto questo, sia il seguente T(n) della relazione di ricorrenza datta dall'esercizio:

$T(n) = 2T[(n/2)] + b$ che sviluppata mi da $T(n) = 8T[(n/8)] + 4b + 2b + b$. Ora dovrei ricavare la somma della progressione seguente: $4b + 2b + b$ che per la proprieta commutativa dell'addizione posso scrivere anche come: $b + 2b + 4b$. Questa progressione dovrebbe essere uguale alla sommatoria seguente:

$\sum_{i = 0}^{n} 2^{i}b = b + 2b + 4b + .... + 2^{n-1}b + 2^{n}b$

Non so se ho scritto gli ultimi termini della sommatoria in modo corretto. Ora da quello che ho capito io per trovare la somma della progressione(per ora parlo per la PA, non so se vale anche per la PG) devo fare:
$\frac{(a_{1} + a_{n})}{2} \cdot n = \frac{(b + 2^{n}b)}{2} \cdot n$

La somma della PA scritto prima ricavata pero dal prof viene: $(n-1)b$. infatti la formula della progressione aritmetica per un termine generale dovrebbe essere questa: $ a_n=a_1 + (n-1)d$ dove $d$(ragione della progressione, e $n$ dovrebbe essere l'n-esimo termine della progressione). Quello che non capisco è dove è finito l' $a_{1}$? forse il prof ha usato la PG e non la PA?

[emotions1]

Per il momento sono arrivato a capire che si tratta di una PG in quanto con la PA la differenza dei termini non rimane costante. Di conseguenza non ha senso risolverla con la formula della PA, per quello nel post precedente le cose non tornavano.

[emotions1]

Dovrei aver risolto, applicando la formula della PG viene:

$S_{n} = a_{1} \frac{1 - q^n}{1-q} = b \cdot \frac{1 - 2^n}{1 - 2}$ , basta ricordare poi di mettere $n = log_{2}n$ (per motivi che vanno al di fuori del dubbio di questa domanda) e si ottiene $(n-1)b$