Understanding proof of Theorem 3.3 in Karp's "Probabilistic Recurrence Relations"
In some cases the recurrence for $T$ does not determine it uniquely. We take the following interpretation of $T$, which gives the minimum $T$ consistent with the recurrence. 

Repeatedly substitute $T(x) = a(x) + T(h(x))$ to expand $T(x)$ as the (random) sum
$$
T(x) = a(x) + a(h(x)) + a(h(h(x))) + \cdots = \sum_{j=1}^\infty a_j
$$
where $a_i = a(h^{(i-1)}(x))$,
in which $h^{(0)}(x) = x$ and and $h^{(i+1)}(x) = h(h^{(i)}(x))$.

lemma. With this definition of $T$, 
we have $K_r(x) \le \sup_i K^i_r(x)$.

Proof.
Inspecting the definitions of $K^i_r$ and $K_r$, we have
$$
K_r(x) = \Pr[\textstyle\sum_{j=0}^\infty a_j &gt; r]
~~\mbox{and}~~
K^i_r(x) = \Pr[\textstyle\sum_{j=0}^{i-1} a_j \ge r].
$$
To prove the lemma, we will show something slightly stronger, namely
$$
\Pr[\textstyle\sum_{j=0}^\infty a_j &gt; r] ~~=~ \sup_i \Pr[\textstyle\sum_{j=0}^{i-1} a_j &gt; r].
$$
Define random variable $T = \min\{i : \sum_{j=0}^{i-1} a_j &gt; r\}$ to be the first step at which the sum of terms exceeds $r$ (with $T=\infty$ if that never happens).
Rewriting the desired equation in this notation, we want to show
$$
\textstyle \Pr[T &lt; \infty] ~=~ \sup_i \Pr[T \le i].
$$
But that equation follows from basic definitions as follows:
$$
\Pr[T &lt; \infty] 
= \sum_{j=0}^\infty \Pr[T = j] 
= \lim_{i\rightarrow\infty} \sum_{j=0}^i \Pr[T=j]
= \lim_{i\rightarrow\infty} \Pr[T \le i]
= \sup_i \Pr[T \le i ].$$
QED