1

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

Nikita Astrakhantsev
  • 113
  • 1
    A couple of suggestions: Maybe try rearranging things so it's $S(3\alpha) = \cdots$ and you don't have to think about $n$ being divisible by three as "background knowledge", it'll be built in to the formula. Have you computed several values $S(0) = 1, S(3) = \cdots$? You might try plugging those values into the Online Encyclopedia of Integer Sequences to see if anything comes up. – Aaron Golden Nov 11 '15 at 21:39

2 Answers2

1

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.

Aaron Golden
  • 1,031
  • 6
  • 12
0

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

vonbrand
  • 27,812