I was wondering if the expression:

$$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$

could be expressed as a closed expression in terms of (hopefully polynomials of) $C_1$ (or $C_2$). The bases cases for this recursion are:

$$ C_1 = C_1 $$ $$ C_2 = 2 C^2_1 - 1$$

and for $ n < 1 $, $C_n$ is undefined.

I've tried the natural/obvious method of plugging the recursion back into itself but wasn't sure how to terminate it properly:

$$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$

$$ C_n = 2C_1 (2 C_1 C_{n-2} - C_{n-3}) - C_{n-2} = 2^2 C_1^2 C_{n-2} - 2 C_1 C_{n-3}$$

$$ C_n = 2C_1 (2C_1 (2C_1 C_{n-3} - C_{n-4}) - C_{n-3}) - C_{n-2} = 2^3C_1^3 C_{n-3} - 2^2 C_1^2 C_{n-4} - 2 C_1 C_{n-3} - C_{n-2} $$

$$ C_n = 2C_1 (2C_1 (2C_1 (2 C_1 C_{n-4} - C_{n-5}) - C_{n-4}) - C_{n-3}) - C_{n-2} = 2^4 C_1^4 C_{n-4} - 2^3 C_1^3 C_{n-5} - 2^2 C_1^2 C_{n-4} - 2 C_1 C_{n-3} - C_{n-2} $$

Which I believe has the following pattern:

$$ C_n = 2^{n-1} C^{n-1} C_1- \sum^K_{i=0}C^i 2^i C_{n-2 - i}$$

Where $K$ can be chosen such that the summation stops at some base case ($C_1 = C_1 $ or $ C_2 = 2 C^2_1 - 1$). For example $K = n-4$ or $K = n-3$.

After that I wasn't 100% sure how to proceed but the idea is that I want that formula to be expressed only as a function of $C_1$ (or $C_2$). I was hoping that it was expressed like something of the following form:

$$ C_n = \sum^n_{j} a_j C_1^j $$

I suspect that it can be done because as someone pointed at its related to the formula $cos(n \theta) = $ and its part of something similar to pascal's triangle and I was hoping the coefficients had some nice expression.

Also, I have a proof (by induction) that $C_n$ is a function of $C_1$ (which I will include later) but I seem unable to get the actual closed for expression for this the coefficients. Feels so close!


At this point I've been told that the expression for $C_n$ is:

$$ C_n = \frac{1}{2} \left( \left( C_1 + \sqrt{C_1^2 -1} \right)^n + \left( C_1 - \sqrt{C_1^2 - 1} \right)^n \right) $$

But I will be completely honest, I am not 100% sure where that came from.

  • 1
    $\begingroup$ It can since it is a linear recurrence relation of order $2$. It is a sum of exponentials: it is the discrete version of linear differential equations of order $2$ with constant coefficients.. $\endgroup$ – Bernard Jun 29 '15 at 23:12
  • $\begingroup$ should it says and for $n<1, C_n$ is undefined. in the thrid fourth? $\endgroup$ – Luis Felipe Jun 30 '15 at 1:00
  • $\begingroup$ @LuisFelipeVillavicencioLopez yes :P oops. $\endgroup$ – Pinocchio Jun 30 '15 at 14:43

For $$C_n=pC_{n-1}-C_{n-2}$$ where $p$ is a constant, consider $x^2-px+1=0$. Let $\alpha,\beta$ be the solutions of $x^2-px+1=0$. Here, note that we have $\alpha+\beta=p,\alpha\beta=1$.

Case 1 : If $\alpha\not=\beta$, then we have $$C_{n+2}-\alpha C_{n+1}=\beta(C_{n+1}-\alpha C_{n})$$ and $$C_{n+2}-\beta C_{n+1}=\alpha (C_{n+1}-\beta C_{n}).$$ Hence, we have $$C_{n+1}-\alpha C_n=(C_2-\alpha C_1)\beta^{n-1}\tag 1$$ and $$C_{n+1}-\beta C_n=(C_2-\beta C_1)\alpha^{n-1}\tag 2$$ Now, $(1)-(2)$ gives us $$C_n=\frac{1}{\beta-\alpha}((C_2-\alpha C_1)\beta^{n-1}-(C_2-\beta C_1)\alpha^{n-1})\tag3$$

Added : $(3)$ can be simplified to $$C_n=\frac{1}{2}\left(\left(C_1+\sqrt{C_1^2-1}\right)^n+\left(C_1-\sqrt{C_1^2-1}\right)^n\right)$$ using $p=2C_1,\alpha=C_1-\sqrt{C_1^2-1},\beta=C_1+\sqrt{C_1^2-1}$.

(Note that this includes the following case.)

Case 2 : If $\alpha=\beta$, then we have $$C_{n+1}-\alpha C_n=(C_2-\alpha C_1)\alpha^{n-1}.$$ Dividing the both sides by $\alpha^{n+1}$ gives us $$\frac{C_{n+1}}{\alpha^{n+1}}-\frac{C_n}{\alpha^n}=\frac{C_2-\alpha C_1}{\alpha^2}.$$ So, $\left\{\frac{C_n}{\alpha^n}\right\}$ is an arithmetic progression.

Added : Hence, we have $$\frac{C_{n}}{\alpha^{n}}-\frac{C_{n-1}}{\alpha^{n-1}}=\frac{C_2-\alpha C_1}{\alpha^2}$$ $$\frac{C_{n-1}}{\alpha^{n-1}}-\frac{C_{n-2}}{\alpha^{n-2}}=\frac{C_2-\alpha C_1}{\alpha^2}$$ $$\vdots$$ $$\frac{C_{3}}{\alpha^{3}}-\frac{C_{2}}{\alpha^{2}}=\frac{C_2-\alpha C_1}{\alpha^2}$$ $$\frac{C_{2}}{\alpha^{2}}-\frac{C_{1}}{\alpha^{1}}=\frac{C_2-\alpha C_1}{\alpha^2}$$ Now adding these gives you $$\frac{C_{n}}{\alpha^{n}}-\frac{C_{1}}{\alpha^{1}}=(n-1)\cdot\frac{C_2-\alpha C_1}{\alpha^2},$$ i.e. $$C_n=(\alpha C_1+(n-1)(C_2-\alpha C_1))\alpha^{n-2}.$$

| cite | improve this answer | |
  • $\begingroup$ sorry if this is a simple question, but, how do you know $\alpha + \beta = 1$, $\alpha \beta = 1$ and why does it matter? $\endgroup$ – Pinocchio Jun 30 '15 at 17:36
  • 1
    $\begingroup$ @Pinocchio: Note that $\alpha+\beta=p$, not $1$. We can get these by Vieta's formulas. These matter because $C_{n+2}=pC_{n+1}-C_{n}\Rightarrow C_{n+2}=(\alpha+\beta)C_{n+1}-\alpha\beta C_n\Rightarrow C_{n+2}-\alpha C_{n+1}=\beta (C_{n+1}-\alpha C_n)$ and so on. $\endgroup$ – mathlove Jun 30 '15 at 17:44
  • $\begingroup$ Interesting. Sorry if this is a dum question, but even though its an Arithmetic Progression (AP), the formula I had: $ C_n = 2^{n-1} C^{n-1} C_1- \sum^K_{i=0}C^i 2^i C_{n-2 - i}$ Has the annoying term $C^i 2^i$, which looks like a arithmetic progression (AP) combined with a geometric progression (GP). Basically, even though $\left\{\frac{C_n}{\alpha^n}\right\}$ is an AP, its not clear how to use that fact because in this case we don't have the usual summation of terms of an AP (cuz of $C^i 2^i$). $\endgroup$ – Pinocchio Jun 30 '15 at 18:47
  • $\begingroup$ @Pinocchio: See the addition in my answer. $\endgroup$ – mathlove Jun 30 '15 at 18:56
  • 1
    $\begingroup$ @Pinocchio : Why don't you simplify (3) to get the expression using $p=2C_1,\alpha=C_1-\sqrt{C_1^2-1},\beta=C_1+\sqrt{C_1^2-1}$? See the addition in the middle of my answer. $\endgroup$ – mathlove Jul 1 '15 at 11:27

Multiplying the equation by $x^{n-1}$, and defined$f(x)=\sum_{n=0}^{\infty}C_nx^n$, we have that $\frac{f(x)-C_o-C_1x}{x^2} = C_1*\frac{f(x)-C_0}{x}+f(x)$, and so, $f(x)(x^2+C_1x-1) = -C_0+C_1x(C_0 -1)$ and we got that $f(x) = \frac{-C_0+C_1x(C_0 -1)}{x^2+C_1x-1}$. you just need find the Taylor expansion of f(x). a hint: expand f(x) in this form $\frac{A}{1-\frac{x}{r_1}}+\frac{B}{1-\frac{x}{r_2}}$, where $r_1,r_2$ are roots of $x^2+C_1x-1$, and see that: $\frac{A}{1-\frac{x}{r_1}} = A\sum_{n=0}^{\infty}r_1^n*x^n$

| cite | improve this answer | |

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.