# Can the recurrence $C_n = 2 C_1 C_{n-1} - C_{n-2}$ be expressed in a closed expression?

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!

Edit:

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.

• 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.. – Bernard Jun 29 '15 at 23:12
• should it says and for $n<1, C_n$ is undefined. in the thrid fourth? – Luis Felipe Jun 30 '15 at 1:00
• @LuisFelipeVillavicencioLopez yes :P oops. – Pinocchio Jun 30 '15 at 14:43

## 2 Answers

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

• sorry if this is a simple question, but, how do you know $\alpha + \beta = 1$, $\alpha \beta = 1$ and why does it matter? – Pinocchio Jun 30 '15 at 17:36
• @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. – mathlove Jun 30 '15 at 17:44
• 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$). – Pinocchio Jun 30 '15 at 18:47
• @Pinocchio: See the addition in my answer. – mathlove Jun 30 '15 at 18:56
• @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. – 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$