Return to Revisions

For $n\geq 1$, let $p_n$ be the $(n+1)$-th term of A000262, and let $q_n$ be $n$-th term of A002720. Then, according to the description of these two sequences (more precisely by the contributions of Dennis P. Walsh and Paul Berry) $$p_n=\sum_{k=0}^{n-1}\binom{n}{k}\binom{n-1}{k}k!\qquad\text{and}\qquad q_n=\sum_{k=0}^{n-1}\binom{n-1}{k}^2k!\ .$$ We derive some identities. First, \begin{align}p_{n+1}-q_{n+1}&=\sum_{k=0}^{n}\binom{n+1}{k}\binom{n}{k}k!-\sum_{k=0}^{n}\binom{n}{k}^2k!\\[6pt] &=\sum_{k=0}^n\left(\binom{n+1}{k}-\binom{n}{k}\right)\binom{n}{k}k!\\[6pt] &=\sum_{k=1}^n\binom{n}{k-1}\binom{n}{k}k!\\[6pt] &=n\sum_{k=1}^n\binom{n}{k-1}\binom{n-1}{k-1}(k-1)!\\[6pt] &=n\sum_{k=0}^{n-1}\binom{n}{k}\binom{n-1}{k}k!\\[6pt] &=np_n. \end{align} That is, $$p_{n+1}=np_n+q_{n+1}.\tag{1}$$ Second, \begin{align}q_{n+1}-p_n&=\sum_{k=0}^{n}\binom{n}{k}^2k!-\sum_{k=0}^{n-1}\binom{n}{k}\binom{n-1}{k}k!\\[6pt] &=n!+\sum_{k=0}^{n-1}\binom{n}{k}\left(\binom{n}{k}-\binom{n-1}{k}\right)k!\\[6pt] &=n!+\sum_{k=1}^{n-1}\binom{n}{k}\binom{n-1}{k-1}k!\\[6pt] &=n!+n\sum_{k=1}^{n-1}\binom{n-1}{k-1}^2(k-1)!\\[6pt] &=n!+n\sum_{k=0}^{n-2}\binom{n-1}{k}^2k!\\[6pt] &=n\sum_{k=0}^{n-1}\binom{n-1}{k}^2k!\\[6pt] &=nq_n.\end{align} That is, $$q_{n+1}=p_n+nq_n.\tag{2}$$ From $(1)$ and $(2)$, it follows by induction that $$a_n=\frac{p_n}{q_n}.\tag{3}$$ Indeed, $(3)$ holds for $n=1$. Assuming $(3)$ holds for a given $n$, it also holds for $n+1$ in place of $n$, since $$a_{n+1}=1+\frac{na_n}{n+a_n}=1+\frac{np_n}{p_n+nq_n}=1+\frac{p_{n+1}-q_{n+1}}{q_{n+1}}=\frac{p_{n+1}}{q_{n+1}}.$$ This answers the second part of the OP's question. More precisely, it would also be desirable to prove that $\gcd(p_n,q_n)=1$. This seems straightforward along similar lines, but I have not verified it (for lack of time).