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