<s>[INST] find the solution to recurrent relation Solving some math problem, I have faced this recurrent equation: $$S(n) = 3 S(n - 3) + 2 \sum\limits_{k = 2}^{n / 3} S(n - 3 k) \times k.$$
Here $n = 3 \alpha$, means, $n$ can be divided by $3$ ($\alpha$ is integer), and $S(0) = 1$.
Could anyone please help me to find $S(n)$ in a closed form if it's possible? Thanks!
UPD: Of course, $n >= 6$.
 [/INST] Call $S(3 n) = s_n$, write the recurrence with no subtractions in indices:
$\begin{align}
   s_{n + 2} 
      &= 3 s_{n + 1} + 2 \sum_{2 \le k \le n + 2} k s_{n + 2 - k} \\
      &= 3 s_{n + 1} + 2 \sum_{0 \le k \le n} (k + 2) s_{n - k} \\
      &= 3 s_{n + 1} + 2 \sum_{0 \le k \le n} (n - k + 2) s_k
\end{align}$
Define the generating function $S(z) = \sum_{n \ge 0} s_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$:
$\begin{align}
   \sum_{n \ge 0} s_{n + 2} z^n
     &= 3 \sum_{n \ge 0} s_{n + 1} z^n
          + 2 \sum_{n \ge 0} z^n \sum_{0 \le k \le n} (n + 2 - k) s_k \\
   \frac{S(z) - s_0 - s_1 z}{z^2}
     &= 3 \frac{S(z) - s_0}{z}
          + 2 \sum_{n \ge 0} z^n \sum_{0 \le k \le n} (n -k) s_k
          + 2 \sum_{n \ge 0} z^n \sum_{0 \le k \le n} s_k \\
     &= 3 \frac{S(z) - s_0}{z}
          + 2 \left( \sum_{n \ge 0} n z^n \right)
               \left( \sum_{n \ge 0} s_n z^n \right)
          + 2 \frac{S(z)}{1 - z} \\
     &= 3 \frac{S(z) - s_0}{z}
          + 2 \frac{z}{(1 - z)^2} S(z)
          + 2 \frac{S(z)}{1 - z}
\end{align}$
This results in:
$\begin{align}
   S(z)
     = \frac{(1 - z)^2 (s_0 + s_1 - 3 s_0 z)}
            {1 - 5 z + 5 z^2 - 3 z^3}
\end{align}$
This doesn't factor easily, so I'll leve it at this. Next step would be splitting into partial fractions, and get the coefficients off the resulting simpler terms (geometric series, binomial theorem).
</s>