This is a continuation for this question.
Let $$S_q=\sum_{k=0}^{q} \binom{2q+1}{2k} 3^k $$
$$T_q=\sum_{k=0}^{q} \binom{2q+1}{2k+1} 3^k $$.
(i) Is it true that $S_{(2q+1)n+q}$ is divisible by $S_q$, for any natural numbers $n,q$?
The answer for (i) is yes, because we have $$ S_{(2q+1)n+q}=S_q\sum_{j\ge0}3^j\binom{2n+1}{2j}S_q^{2(n-j)}T_q^{2j}.$$ Note that since $2nq+n+q$ is a symetric function of ($n,q$), $\ \ S_n$ also divides $S_{(2q+1)n+q}$.
(ii) Is it true that $s_q=\frac{S_q}{2^q}$ and $t_r=\frac{T_r}{2^r}$ are coprime, whatever $q,r$ any natural numbers ?
EDIT: Thanks to @Steven Stadnicki:
- the sequences $t$ and $s$ can be found at A001835 and A001834. They follow the general second order linear recurrence $a_n=4a_{n-1}-a_{n-2}$, with $s_0=t_0=1$ and $t_1=3$ and $s_1=5$.
- $s_{q+1}-2s_q=3t_q$
EDIT 24th Feb. 2018: the answer to question (ii) is yes, as it has been proven here
It seems that the prime divisors of the $s$, the prime divisors of the $t$ and the primes that do not divide any $s$ nor any $t$ make a partition of the set of all primes. Moreover, the three classes would have the same density, because it is known** that the prime divisors of the $s$ and those of the $t$ have both density $\frac{1}{3}$. **J.C. Lagarias, $\it Pacific \ Journal \ of \ Mathematics$, Vol. 118, No 2, 1985.
Also
(iii) is it true that $$\gcd[s_n,s_m]=s_{\frac{1}{2}(\gcd[2n+1,2m+1]-1)}$$ and similarly for $t$?