  The length $a(n)$ of the longest common subsequence of the $n$'th Thue-Morse
word and its bitwise complement is studied. An open problem suggested by Jean
Berstel in 2006 is to find a formula for $a(n)$. In this paper we prove new
lower bounds on $a(n)$ by explicitly constructing a common subsequence between
the Thue-Morse words and their bitwise complement. We obtain the lower bound
$a(n) = 2^{n}(1-o(1))$, saying that when $n$ grows large, the fraction of
omitted symbols in the longest common subsequence of the $n$'th Thue-Morse word
and its bitwise complement goes to $0$. We further generalize to any prefix of
the Thue-Morse sequence, where we prove similar lower bounds.
