Hi,

In computer science often the "runtime" of an algorithm can be described with a recurrence relation, here is an example:


$\displaystyle

T(n) = \left\{
\begin{array}{lr}
c & n = 1 \\
T( \lfloor n/2 \rfloor ) + n & n > 1
\end{array}
\right.


$
where
$\displaystyle n \in \mathbb{N}$


If you let

$\displaystyle
A(t) = \sum _ {n = 0} ^ \infty T(n) t^n
$

then

$\displaystyle
\sum _{n=0} ^ \infty T(\lfloor n/2 \rfloor) t^n= (1 + t)A(t^2)
$

so

$\displaystyle
A(t) - (1+t)A(t^2) = \sum _ {n=0} ^\infty n t ^n = \frac{t}{(1-t)^2}
$

Idealy I could write $\displaystyle A(t^2)$ in terms of $\displaystyle A(t)$ somehow then use partial fractions and find the appropriate taylor series to solve this. The problem is I don't know how to proceed, how to write $\displaystyle A(t^2)$ in terms of $\displaystyle A(t)$. Has anyone ever come across this before?

This is purely for interest sake, no rush, any hints greatly appreciated.