0

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.

Charlie Parker
  • 6,546
  • 1
    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? – L F Jun 30 '15 at 01:00
  • @LuisFelipeVillavicencioLopez yes :P oops. – Charlie Parker Jun 30 '15 at 14:43

2 Answers2

6

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

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

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$

A.A.
  • 143