Trasformazione di una ricorsione in una sommatoria

[_clockwise]

Buongiorno a tutti!
Volevo sottoporvi qualche mio dubbio. Sto studiando matematica discreta e il mio testo (il Graham-Knuth-Patashnik), riporto testualmente, recita:

Conversely, many recurrences can be reduced to sums [...]- The Tower of Hanoi recurrence is a case in point:

\( \begin{cases}
T_0=0 \\
T_n=2T_{n-1}+1,\;\;\;\text{for}\;n>0;
\end{cases} \)

It can be put into the special form (2.6)* if we divide both sides by \(2^n\):

\( \begin{cases}
\dfrac{T_0}{2^0}=0 \\
\dfrac{T_n}{2^n}=\dfrac{T_{n-1}}{2^{n-1}}+\dfrac{1}{2^n}
\end{cases} \)

Now we can set \(S_n=T_n/2^n\), and we have

\( \begin{cases}
S_0=0 \\
S_n=S_{n-1}+2^{-n},\;\;\;\text{for}\;n>0.
\end{cases} \)

It follows that

\( S_n=\displaystyle\sum^n_{k=1} 2^{-k}. \)

* La "special form" a cui si riferisce è una ricorrenza del tipo:

\( \begin{cases}
R_0=\alpha \\
R_n=R_{n-1}+\beta+\gamma n,\;\;\;\text{per}\;n>0.
\end{cases} \)

Il mio primo dubbio è questo: è chiaro che la sommatoria rispetta la seconda equazione del sistema, ma sicuramente non rispetta la prima (l'esponenziale è positivo). Ma anche immaginando di ignorare tutto ciò, c'è un'altra cosa che non capisco: come mai la sommatoria deve iniziare da \(k=1\), perdendosi così un termine (ossia 1)?

Ho pensato che forse è proprio perché deve rispettare la prima condizione. O magari, dato che il nostro obiettivo a monte è risolvere la ricorsione e abbiamo fatto in modo di trasformarla in sommatoria solo perché è più semplice da trattare, il libro intende questo:

\( S_n=\begin{cases}
0, &\text{se}\;n=0 \\
\displaystyle\sum^n_{k=1} 2^{-k}, &\text{se}\;n>0
\end{cases} \)

Sareste in grado di darmi delle delucidazioni? Grazie!

[Derio97]

La sommatoria invece rispetta anche la prima equazione:

per convenzione, dati $m , n in ZZ$, con $m > n$, allora $ sum_{k=m}^n f(k) = 0$, se $f$ è a valori reali.
Dunque $S_0 = sum_{k=1}^0 2^-k = 0$.

Il termine 1 non viene perso, infatti $1=T_1=2S_1=2(2^-1)$.

[_clockwise]

Sono leggermente (...) in ritardo, ma ti ringrazio molto! Non conoscevo quella convenzione.
Per cui se riscrivo il tutto come:

\( T_n=2^n \displaystyle\sum_{k=1}^{n} 2^{-k} \)

e pongo \( n=1 \) ottengo \( T_n=2\cdot\dfrac{1}{2}=1 \), e così via per valori crescenti di \( n\in\mathbb{N} \).
Grazie ancora.