Сколько N-значных чисел можно составить, используя цифры 5 и 9, в которых три одинаковые цифры не стоят рядом? Pascal

Формировать полное число в N знаков совсем не нужно.
Т. к. для проверки достаточно условия, что не идут подряд 3 одинаковые цифры 555 или 999,
достаточно помнить только 3 последние цифры, а большие третьего порядка - отбрасывать. (Нам же не сказано вывести такие числа! )
Таким образом организуем рекурсию, где к полученному на предыдущем шаге числу прибавляем в конец 5 или 9 (т. е. число * 10 и прибавить 5 или 9).
Если число начинает превышать трёх знаков, то отбрасываем первые знаки (остаток от деления на 1000).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
var
N : Byte;
K : Integer;

procedure Next(Cifr, C : Byte; S : Word);
begin
S := S * 10 + C;

// от числа нам нужны только последние 3 цифры
if S > 1000 then
S := S mod 1000;

if S <> 555 then // нет трёх подрят 5
if S <> 999 then // нет трёх подряд 9
if Cifr + 1 = N then // достигли размеров числа = N
Inc(K) // Увеличим счётчик
else
begin // формируем новые числа прибавлением 5 или 9
Next(Cifr + 1, 5, S); // Прибавим 5
Next(Cifr + 1, 9, S); // Прибавим 9
end;
end;

begin
Write('Введите N='); ReadLn(N);
K := 0;
Next(0, 5, 0); // Начинаем с прибавления 5
Next(0, 9, 0); // Начинаем с прибавления 9
WriteLn('Возможных чисел =', K);
end.