Solving "runtime" of recurrence realtion with generating functions

Hi,

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

where

If you let

then

so

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

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