Renewal equation
= Renewal equation
{title2=$u_n=\sum_{k=1}^n f_k u_{n-k},\ u_0=1$}
A <renewal equation> decomposes a process at its first renewal. For returns of a <Markov chain> to a fixed state, $f_k$ is the first-return <probability> and $u_n$ the <probability> of being at that state at time $n$. Their <probability generating functions> satisfy $U=1+FU$.