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.