# Proving every element of a sequence defined by a recurrence relation is an integer

Define the sequence $$(a_n)_n$$ as follows: $$\begin{cases} a_0 &= 1 \\ a_1 &= 2 \\ (n+3)a_{n+2}&=(6n+9)a_{n+1}-na_n \end{cases}$$ for $$n \ge 0$$

I am trying to prove that all terms of the sequence are integers. I have proved this using generating functions but it is long and messy. I want to know if there is a simpler proof that just uses elementary number theory. Perhaps an induction argument is possible?

• Just for your curiosity, these are the large Schroeder numbers – Claude Leibovici Sep 9 at 12:21
• Did you find the generating function ? – Claude Leibovici Sep 9 at 13:06
• @ClaudeLeibovici thanks for that - I didn't know they had a name. Yes, I found the generating function. – user1488 Sep 9 at 13:16
• In fact, they are also related to Gegenbauer polynomials. Congratulations for th g.f. – Claude Leibovici Sep 9 at 13:24
• In the page of $OEIS$, sequence $A006318$, in the commenst section, they write that $a_n$ is the number of lattice paths... – Claude Leibovici Sep 9 at 13:53

According to $$OEIS$$ (have a look here) $$a_n=\sum_{k=0}^n \frac{1}{k+1}\binom{n}{k} \binom{n+k}{n}$$
• Your summation formula is the row sums of OEIS sequence A088617 and this fact is mentioned in both $A088617$ and $A006318$. I am Still wondering how to connect this with the recurrence definition. – Somos Sep 9 at 22:40
Robert A. Sulanke, Bijective Recurrences concerning Schröder Paths, shows that if $$r_n$$ is the number of lattice paths from $$\langle 0,0\rangle$$ to $$\langle 2n,0\rangle$$ using only up-steps $$\langle 1,1\rangle$$, down-steps $$\langle 1,-1\rangle$$, and double flat-steps $$\langle 2,0\rangle$$ and remaining strictly above the $$x$$-axis except at their endpoints, then these numbers satisfy the recurrence
$$(n+1)r_{n+1}=3(2n-1)r_n-(n-2)r_{n-1}$$
for $$n\ge 2$$, with $$r-1=1$$ and $$r_2=2$$. This is your recurrence with the indexing offset by $$1$$, so this is a combinatorial proof that your $$a_n$$ are integers. The bijection used to prove the result is more than a bit complicated, but it is described fairly clearly.