find the solution to recurrent relation

Question

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$.

Answer 1

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).

Answer 2

I calculated several entries in the sequence using the formula from your latest edit:

\begin{align} S(0) &= 1\\ S(3) &= 3\\ S(6) &= 13\\ S(9) &= 57\\ S(12) &= 249\\ S(15) &= 1087\\ S(18) &= 4745\\ S(21) &= 20713\\ S(24) &= 90417\\ S(27) &= 394691\\ S(30) &= 1722917\\ S(33) &= 7520929\\ S(36) &= 32830585\\ S(39) &= 143313055\\ S(42) &= 625594449 \end{align}

This appears to be a known sequence. The fact that the OEIS does not give a nice closed form suggests to me that no such form is known.