Относительно элегантная рекурсия

[kthxbye]

Пусть $a(n)$ это A301897. Что у нас с формулами? Во-первых, если $A(x)$ производящая функция, то будем иметь:

$$x^2A(x)^3 + (4x^2-3x+1)A(x)^2 + (5x^2-3x)A(x) + 2x^2=0$$

Далее

$$a(n)=\frac{1}{n+1}\binom{2n}{n}+\sum\limits_{k=1}^{n-2}\sum\limits_{j=1}^{n-k-1}\binom{n}{k-1}\binom{n-1}{k+j}\binom{n-k+j-1}{j-1}\frac{1}{j}$$

Еще есть рекурсия, но она какая-то страшненькая. Впрочем, можете сами на нее посмотреть.

Что я заметил? Экспериментируя с одной функцией, а именно

$$R_1(n,q)=\sum\limits_{j=0}^{q+1}R_1(n-1,j), R_1(0,q)=1$$

где

$$R_1(n-1,0)=\frac{1}{n+1}\binom{2n}{n}$$

Я кое-что подправил и получилось, что для

$$R_2(n,q)=\sum\limits_{j=0}^{q+q\bmod 3+1}R_2(n-1,j), R_2(0,q)=1$$

предположительно будем иметь

$$R_2(n-1,0)=a(n)$$

Достаточно элегантно, не правда ли?

Вот простенькая прога на PARI/GP для проверки:

R2_upto(n)=my(v1, v2, v3); v1=vector(3*n+1, i, 1); v2=v1; v3=vector(n+1, i, 0); v3[1]=1; for(i=1, n, for(q=0, 3*(n-i), v2[q+1]=sum(j=0, q+q%3+1, v1[j+1])); v1=v2; v3[i+1]=v1[1];); v3
a(n)=binomial(2*n,n)/(n+1)+sum(k=1,n-2,sum(j=1,n-k-1,binomial(n,k-1)*binomial(n-1,k+j)*binomial(n-k+j-1,j-1)*(1/j)))
test(n)=R2_upto(n)==vector(n+1,i,a(i))

Существует ли способ как-то это доказать?

[kthxbye]

К вопросу подключился сам Теренс Тао и опубликовал доказательство связанное с производящей функцией.

[mathematician123]

Оказывается, Теренс Тао использовал GPT4 для ответа на вопрос:
https://mathstodon.xyz/@tao/110601051375142142.