5
$\begingroup$

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?

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

According to $OEIS$ (have a look here) $$a_n=\sum_{k=0}^n \frac{1}{k+1}\binom{n}{k} \binom{n+k}{n}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Somos Sep 9 at 22:40
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.