А потом кто-то придумал, что можно пройти рассуждением, аналогичным тому, что мы уже видели: доказать по индукции, что число разрешённых слов L_n растёт по крайней мере как L_{n+1}>=2 L_n.

Потому что — опять же, из разрешённых слов длины n можно получить 4*L_n слов, дописывая все возможные последние буквы. После этого — если на конце появился повтор XX, то есть w=RXX, то ему можно сопоставить слово w’=RX, и по w’ исходное w восстанавливается: мы видим, сколько букв вычеркнуто, и повторяем хвост такой длины. Так что
L_{n+1} >= 4*L_n - L_n - L_{n-1} - L_{n-2} - …,
и индукция по n завершает рассуждение (буквально так же, как мы уже видели) : вычтя 2L_n из обеих частей, получаем
L_{n+1}-2L_n >= L_n - L_{n-1} - L_{n-2} - …
>= L_{n-1} - L_{n-2} - L{n-3} - …
>= L_{n-2} - L_{n-3} - L{n-4} - …
>= 0.

А вопрос про k=3 — всё ещё открыт!