@Allen Knutson, Thank you for your useful idea. I have listed the polynomials in basis $\{ {x\choose k} \}$. I think it is also hard to prove that $Q(x)$ is $\mathbb Z$-valued as you mentioned.

Thank you for your good ideas and suggestions for this question. I have proved the third-order recurrence by Multi-Varible Zeilberger algorithm. In my proof, I obtain a very complicated fifth-order recurrence. What I have done is that: $M(s),N(s)$ denote the third recurrence and fifth-order recurrence respectively. Then I prove $c_0(s)N(s)+d_0(s)M(s)+d_1(s)M(s+1)+d_2(s)M(s+2)=0$ where $c_0(s),d_0(s),d_1(s),d_2(s)$ are polynomials with integer coefficients, from this fact, I prove the third-order recurrence by induction. If proof without software is found, it will be better.

I use the corrected version and verify it via maple, it is correct recurrence, you are right! The sequence is not in OEIS. I can't find the recurrence by zeilberger algorithm. How do you find the recurrence?Thank you very much!

I verify the recurrence via maple, and find $a_s$ don't satisfy the recurrence. Could you tell me how you find this third-order recurrence? If the right recurrence is found, it is helpful to solve this problem. Thanks!