Комплемент посл.-ти рекуррентно

[kthxbye]

Нашел одну интересную и вероятно тривиальную закономерность, но доказать ее, увы, не могу. Разберем на примерах.

Имеем последовательность простых чисел $\operatorname{prime}(n)$. Последовательность начинается

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79$$

Ее комплемент (без учета $0$ и $1$) - это последовательность составных чисел $\operatorname{composite}(n)$. Последовательность начинается

$$4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34$$

Пусть задана последовательность

$$a(n)=\operatorname{prime}(n)-n$$

а также последовательность

$$b(n)=\begin{cases} 1,&\text{если $n\in a(k)$;}\\ 0,&\text{в противном случае.} \end{cases}$$

Тогда справедливо рекуррентное соотношение

$$\operatorname{composite}(n)=1+\operatorname{composite}(n-1)+b(n), \operatorname{composite}(1)=4$$

Что примечательно, все члены $a(n)$ за исключением первых двух не повторяются. Возможна и обратная операция.

Пусть задана последовательность

$$a_1(n)=\operatorname{composite}(n)-n$$

а также последовательность

$$b_1(n)=\begin{cases} m,&\text{если $n\in a(k)$, где $m$ - это число повторений $n$ в $a(k)$;}\\ 0,&\text{в противном случае.} \end{cases}$$

Тогда справедливо рекуррентное соотношение

$$\operatorname{prime}(n)=1+\operatorname{prime}(n-1)+b_1(n), \operatorname{prime}(1)=2$$

Определение $b_1(n)$ более полно, чем определение $b(n)$. Все это работает для любых комплементарных последовательностей. Но почему?

[iifat]

Лень доводить до конца, но для возрастающей последовательности $\{a_n\}$ $a_n-n$ есть число членов комплементарной на отрезке $[1;a_n]$. Уточняя, что наша последовательность не содержит пар чисел $k, k+1$, $b_n=b_{n-1}+1$ либо $b_n=b_{n-1}+2$. Подозреваю, отсюда выводятся прочие формулы.