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 \begin{equation} 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. \end{equation}

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.

  • 6
    $\begingroup$ 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. $\endgroup$ Sep 15, 2016 at 8:20
  • $\begingroup$ @GerryMyerson you right. I edited my question to clarify what I mean. $\endgroup$
    – Amin235
    Sep 15, 2016 at 10:23
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 15, 2016 at 11:07
  • $\begingroup$ But, Amin, what makes you think there is a simpler form for this function? $\endgroup$ Sep 15, 2016 at 13:16
  • $\begingroup$ @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 $\endgroup$
    – Amin235
    Sep 15, 2016 at 13:37

1 Answer 1


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) } $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.