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.

Is there a analytical method that we can get a closed-form expression for $C_n$ sequence. 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, we 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.


1 Answer 1


The standard way to get a closed form for a sequence with a rational generating function is to perform a partial fraction decomposition of the generating function, either completely or in this case in terms of $x^2$, and then recast the individual terms by substituting their geometric series. (The associated formulas are generalized Binet formulas). So the result will most likely be the same as the one you already indicated, but complex terms in that expression are probably unavoidable, because $1-t-t^2-t^3$, where $t=x^2$, does have two complex roots.

Of course you can also compute the first 10 or 20 terms and start from http://oeis.org/A213816 .

  • $\begingroup$ My attitude to the $C_n$ sequence is different from $A213816$ . Please notice that to selection of initial values. $\endgroup$
    – Amin235
    Sep 14, 2016 at 14:28
  • $\begingroup$ @Amin235: It’s the same sequence with a different offset. The are related by $a_n=C_{n+3}$. (The OEIS sequence is indexed starting at $a_1$.) $\endgroup$ Sep 14, 2016 at 20:48
  • $\begingroup$ @BrianM.Scott you right but I said just my attitude to the $C_n$ sequence is different from $A213816$. I think, it is not important that the sequence is $a_n$ or $C_n$. It is important that how to find a closed-form expression for $a_n$ or $C_n$ sequence, Thank you. $\endgroup$
    – Amin235
    Sep 14, 2016 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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