Hi,

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


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


If you let

<br />
A(t) = \sum _  {n = 0} ^ \infty T(n) t^n<br />

then

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

so

<br />
A(t) - (1+t)A(t^2) = \sum _ {n=0} ^\infty n t ^n = \frac{t}{(1-t)^2}<br />

Idealy I could write A(t^2) in terms of 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 A(t^2) in terms of A(t). Has anyone ever come across this before?

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