<s>[INST] Prove that for $n$ and $m$ integers: $ 3^mn \mid \sum\limits_{k=0}^{m} {\binom{3m}{3k}}(3n-1)^k$ If $m$ and $n$ are positive integers, with $m$ odd, then prove that: 
$$3^mn \mid \sum\limits_{k=0}^m \binom{3m}{3k} (3n-1)^k$$
Proving divisibility by $3n$, we look at $\sum\limits_{k=0}^m (-1)^k\binom{3m}{3k}$. My idea is to substitute cube roots of unity in binomial expansion of $(1+x)^{3m}$. But, how do I get the additional divisibility by $3^{m-1}$?
Perhaps we can use some variation of $\displaystyle \binom{3m}{3k} \equiv \binom{m}{k} \pmod {3^{2+2\operatorname{ord}_3 m}}$, or induction on $m$ henceforth. ($\operatorname{ord_{3}}n$ is the heighest power of $3$ in $n$).
Edit: I add my approach (induction on $m$)
We have the identity $$(1+x)^{3m}+(1+\omega x)^{3m}+(1+\omega^2 x)^{3m} = 3\sum\limits_{k=1}^{m}\binom{3m}{3k}x^{3k}$$
Let, $\omega_1 = 1+x$, $\omega_2 = 1+\omega x$ and $\omega_3 = 1+\omega^2 x$, then $\omega_i$ are the roots of $P(t) = t^3 - 3t^2 + 3t -(1+x^3)$.
Denoting, $S_k = \sum\limits_{j=1}^{3}\omega_j^k$, then it satisfies the recurssion: $S_{k+3} - 3S_{k+2} + 3S_{k+1}-(1+x^3)S_k = 0, \forall \, x \in \mathbb{N}$
Setting $x = \sqrt[3]{3n-1} \implies x^3+1 = 3n$.
The recurssion becomes $S_{k+3} = 3S_{k+2} - 3S_{k+1} + 3nS_k$.
A small calculation shows $S_{k+7}= 63nS_{k+2} + 9(n^2-3n+3)S_{k+1} + 27n(2n+1)S_k$.
Where, $S_{2+1} = 9n$, so it follows from induaction that $3^{2k+2}n \mid S_{6k+3}$, i.e. $3^{m+1}n \mid S_{3m}$, where $m=2k+1$.
I am also very interested in a solution that uses a combinatorial approach to the problem(if possible), any ideas with computing the residues $\binom{3m}{3k} \pmod{3^m}$ to solve the problem, or any other approach. Thank you.
 [/INST] Let us denote
$$A_m = \sum_{k=0}^m \binom{3m}{3k}(3n-1)^k.$$
Writing $z = \sqrt[3]{3n-1}$ and $\rho = e^{2\pi i/3}$, we find
$$3A_m = (1+z)^{3m} + (1+\rho z)^{3m} + (1+ \rho^2 z)^{3m}.$$
The sequence given by
$$3u_k = (1+z)^k + (1+\rho z)^k + (1+\rho^2 z)^k$$
satisfies the linear recurrence
$$u_{k+3} = 3 u_{k+2} - 3 u_{k+1} + 3n u_k\tag{1}$$
since
$$\bigl(X - (1+z)\bigr)\bigl(X-(1+\rho z)\bigr)\bigl(X-(1+\rho^2 z)\bigr) = (X-1)^3 - z^3 = X^3 - 3X^2 + 3X - 3n.$$
We have $u_0 = u_1 = u_2 = 1$ and want to prove
$$3^{2r+1}n \mid u_{6r+3}.$$
It is probably easiest to replace $n$ with an indeterminate $Y$ and consider
$$u_k(Y) = \frac{1}{3}\left((1+\sqrt[3]{3Y-1})^k + (1+\rho\sqrt[3]{3Y-1})^k + (1+\rho^2\sqrt[3]{3Y-1})^k\right)$$
with the recurrence
$$u_{k+3}(Y) = 3 u_{k+2}(Y) - 3 u_{k+1}(Y) + 3Y u_k(Y).$$
An easy induction then shows that $u_k(Y) \equiv 0 \pmod{Y}$ if and only if $k\equiv 3\pmod{6}$, and that all coefficients of $u_k(Y)$ are divisible by $3^{\lfloor k/3\rfloor}$.
</s>