<s>[INST] Integrality of a sequence formed by sums Consider the following sequence defined as a sum
$$a_n=\sum_{k=0}^{n-1}\frac{3^{3n-3k-1}\,(7k+8)\,(3k+1)!}{2^{2n-2k}\,k!\,(2k+3)!}.$$

QUESTION. For $n\geq1$, is the sequence of rational numbers $a_n$ always integral?

 [/INST] Here is another proof, inspired by Tewodros Amdeberhan's. We represent the sum as a constant term in a power series.
To represent $(7k+8) \frac{(3k+1)!}{k!\,(2k+3)!}$ as a constant term, we need to express it as a linear combination of binomial coefficients. To do this we express $7k+8$ as a linear combination of $(2k+2)(2k+3)$, $k(2k+3)$, and $k(k-1)$ since each of these polynomials yields a binomial coefficient when multiplied by $\frac{(3k+1)!}{k!\,(2k+3)!}$. We find that
$$(7k+8) \frac{(3k+1)!}{k!\,(2k+3)!}=\frac13 \left[4\binom{3k+1}{k} -7\binom{3k+1}{k-2} -2\binom{3k+1}{k-2}\right].$$
Using $\binom{n}{j} =\text{CT}\, (1+x)^n/x^j$, where CT denotes the constant term in $x$, we have
$$
\begin{aligned}
(7k+8) \frac{(3k+1)!}{k!\,(2k+3)!} &= \text{CT}\, \frac13\left( 4\frac{(1+x)^{3k+1}}{x^k}
   -7\frac{(1+x)^{3k+1}}{x^{k-1}}-2\frac{(1+x)^{3k+1}}{x^{k-2}}\right)\\
   &=\text{CT}\,\frac{(1-2x)(x+4)(1+x)^{3k+1}}{3x^k}.
 \end{aligned}
$$
Multiplying by $3^{3n-3k-1}/2^{2n-2k}$, summing on $k$ from 0 to $n-1$, and simplifying gives
$$
a_n = 3\,\text{CT}\, \frac{(1+x)^{3n+1}}{x^{n-1}(1-2x)} -3\left(\frac{27}{4}\right)^n\!\text{CT}\,\frac{x(1+x)}{1-2x}.
$$
The second constant term is 0, so $a_n = 3\,[x^{n-1}]\, (1+x)^{3n+1}/(1-2x)$, which is clearly an integer.
In fact this gives the formula
$$a_n = 3 \sum_{k=0}^{n-1}2^{n-k-1}\binom{3n+1}{k}.$$
Tewodros's formula can also be derived in the same way; if we represent his sum as a constant term and simplify we also get
$3\,[x^{n-1}]\, (1+x)^{3n+1}/(1-2x)$.
</s>