# The closed-form expression for $C_n$ sequence

Suppose the following linear recurrence sequence $$C_n:=C_{n-2}+C_{n-4}+C_{n-6}\, .$$ With the initial values $$C_0=0 \, , \, C_1=1 \, , \, C_2=0 \, , \, C_3=0 \, , \, C_4=1 \, , \, C_5=1 \, , \, C_6=1 \, .$$ It can be proved that another form of the $C_n$ sequence is as follows $$C_n:=\left\{ \begin{array}{ccc} C_{n-3}+C_{n-1} &\mbox{if}& n=1~\mbox{mod}~2,\\ \\ C_{n-3}+C_{n-2} & \mbox{if}&n=0~\mbox{mod}~2. \end{array} \right.$$

With boundary conditions $$C_0=0 \, , \, C_1=1 \, , \, C_2=0 \, .$$

We can proof that the generating function of $C_n$ sequence is in the following form

$$C(x)=\frac{x-x^3+x^4}{1-x^2-x^4-x^6}\, .$$

In addition, I found the combinatorial forms of even and odd terms of $C_n$ sequence. For even terms, we have

$$C_{2n}=\sum_{(k_1,k_2,k_3)} \left( \begin{array}{c} k_1+k_2+k_3 \\ k_1,k_2 , k_3 \end{array} \right)$$ where the summation is over non-negative integers satisfying $$k_1+2\, k_2+3\, k_3=n-1 \, .$$ and for odd terms, the following relation is obtained $$C_{2n+1}=\sum_{(k_1,k_2,\cdots,k_p)} \frac{k_2+k_3}{k_1+k_2+k_3}\times \left( \begin{array}{c} k_1+k_2+k_3 \\ k_1,k_2 , k_3 \end{array} \right)$$ where the summation is over non-negative integers satisfying $$k_1+2\, k_2+3\, k_3+=n \, .$$ My question is that how to find a closed-form expression for $C_n$ sequence, based on the parameter $n$. I used the auxiliary equation method to find closed-form expression for $C_n$ sequence but the auxiliary equation of $C_n$ sequence have complex roots and it's closed-form expression is complicated.

I would greatly appreciate for any suggestions.

EDIT: I claimed that the closed-form expression of the $C_n$ sequence ,by using auxiliary equation method, is complicated. I want to show it's complexity. In fact, I want to say why I want to find a closed-form expression with less complexity. The auxiliary equation of the $C_n$ sequence is as follows $$x^6-x^4-x^2-1=0~.$$ The roots of the above equation are $$\left\{ \begin{array}{ccc} x_1&=1.356203066~,&\\ x_2&=-1.356203066~,&\\ x_3&=0.3985657592&+ \hspace{3mm} 0.7605905878\,i~,\\ x_4&=0.3985657592&- \hspace{3mm} 0.7605905878\,i~,\\ x_5&=-0.3985657592&+ \hspace{3mm} 0.7605905878\,i~,\\ x_6&=-0.3985657592&- \hspace{3mm} 0.7605905878\,i~.\\ \end{array} \right.$$ Using the Demorgan's law about complex number $$Z=x+\,i y \Leftrightarrow Z=r(\cos(\theta)+\,i \sin(\theta))$$ and based on initial values of the $C_n$ sequence that is defined at the first, the following closed-form expression for the $C_n$ sequence is obtained \begin{eqnarray}\nonumber C_n&=&0.1954392117(1.356203066)^n-0.01263567906(-1.356203066)^n \\ \nonumber &&+{0.8586924398}^n(0.2878832995\cos(1.088116773n) \\ \nonumber &&\hspace{32mm}- 0.06742448463\sin(1.088116773n) \\ \nonumber &&\hspace{32mm}-0.4706868334\cos(2.053475881n) \\ \nonumber &&\hspace{32mm}+0.6136685762\sin(2.053475881n))~. \end{eqnarray} In my research, the above closed-form is not applicable, just because of this, I asked this question.

• So, you have found a closed-form solution, but you are not happy because it is complicated. Well, maybe it is complicated, and you just have to live with it. – Gerry Myerson Sep 15 '16 at 8:20
• @GerryMyerson you right. I edited my question to clarify what I mean. – Amin235 Sep 15 '16 at 10:23
• There are well known expressions of power sums through elementary symmetric functions, you can use these. Equivalently (wrt your case) there are explicit formulæ for coefficients of reciprocal series. – მამუკა ჯიბლაძე Sep 15 '16 at 11:07
• But, Amin, what makes you think there is a simpler form for this function? – Gerry Myerson Sep 15 '16 at 13:16
• @GerryMyerson maybe a reasonable answer to your question is the structure of $C_n$ sequence. In fact, $C_n$ sequence is partitioned by the two dimensional Tribonacci sequence oeis.org/A213816 – Amin235 Sep 15 '16 at 13:37

The roots of your denominator $x^6 - x^4 - x^2 - 1$ are $\pm \sqrt{r_i}$ where $r_1, \ldots, r_3$ are the roots of $z^3 - z^2 - z - 1$, namely \eqalign{r_1 &= \dfrac{1}{3} + \dfrac{1}{3} (19 + 3 \sqrt{33})^{1/3} + \dfrac{4}{3} (19+3 \sqrt{33})^{-1/3}\cr r_2, r_3 &= \dfrac{1}{3} - \dfrac{1}{6} (19 + 3 \sqrt{33})^{1/3} - \dfrac{2}{3} (19 + 3 \sqrt{33})^{-1/3}) \cr &\pm \frac{i \sqrt{3}}{6} \left((19 + 3 \sqrt{33})^{1/3} - 4 (19 + 3 \sqrt{33})^{-1/3}\right) }