I am working on problem 8 in chapter 5 of The Probabilistic Method and I couldn't solve the second half of it.
Problem: For every $n\ge1$ and every sequence of lists of symbols $L_1,L_2,..., L_n$, each of size $4$, there is a non-repetitive sequence $s_1,s_2,...,s_n$, where $s_i\in L_i$. Moreover, there is a randomized algorithm that finds such a sequence in $O(n)$ iterations with high probability, given the lists.
I find the related paper Grytczuk et al., but it only gives proof of the first half as well (though it states the linear expected running time in final remarks.)
Following the argument and notation in the paper, my approach is to use the following recurrence function $$ f[i][j]=\begin{cases} 1 & j=1\\ \sum_{k=j-1}^{\min\{n,2j-1\}}f[i-1][k] & 1<j\le i\\ 0 & j>i, \end{cases} $$ where $f[i][j]$ is the upper bound of the number of possibilities that sequence $s$ is of length $j$ after the $i$-th iteration.
Then $\sum_{j=1}^nf[M][j]$ can replace the Catalan number estimation of $T_M$ in the paper. But I failed to show, for example, the summation is $=o(3.999^M)$.