I am unable to understand the following recurrence relation from the paper: https://people.inf.ethz.ch/emo/PublFiles/SubexLinProg_ALG16_96.pdf. Why is the probability for $t_k(n-1)$ not being accounted for and how is bound on probability for the second term used in the recurrence can someone help?
$t_k(n) \leq t_k(n-1) + 1 + \frac{1}{n-d} \sum_{i=1}^{\min\{n-d,k \} }{t_{k-i}(n)}$