1
$\begingroup$

I was trying to solve the following recurrence in closed form (in terms of the initial conditions/base cases):

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

with base cases:

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

I came up with the following solution but it seems to much a coincidence that all the numbers come out perfectly, it nearly feels like the cosmos aligned so that it worked but I'm shocked and confused. Here is my solution:

So to solve the simple recurrence:

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

guess the solution $C_n = x^n$ and get:

$$ x^n = p x^{n-1} - x^{n-2} $$

and then:

$$ x^2 - p x^{n-1} + x^{n-2} = 0$$

then using the quadratic formula:

$$ x_{1,2} = \frac{p \pm \sqrt{p^2 - 4}}{2}$$

Plug in $p = 2C_{1}$ to get:

$$x_{1,2} = C_1 \pm \sqrt{C^2_1 - 1}$$

so since linear combinations of solutions is the solution we get:

$$ C_n = Ax^n_1 + Bx^n_2 = A(C_1 + \sqrt{C^2_1 - 1}) + B(C_1 - \sqrt{C^2_1 - 1})$$

Now lets choose constants $A$ and $B$ to satisfy the initial conditions:

$$ C_1 = A(C_1 + \sqrt{C^2_1 - 1}) + B(C_1 - \sqrt{C^2_1 - 1})$$

$$ C_2 = 2C_1^2 - 1 = A(C_1 + \sqrt{C^2_1 - 1})^2 + B(C_1 - \sqrt{C^2_1 - 1})^2$$

if we try to make the first equation true one can notice that we satisfy the first equation with the following condition:

$$A+B = 1$$

$$A-B = 0$$

with this we get:

$$A = B = \frac{1}{2}$$

satisfies the first equation. But its not clear it should satisfy the second one without further inspection (here is when the cosmos align to my advantage). If we plug in those values $A = B = \frac{1}{2}$ and simplify, we can tell that indeed we get that the second equation is satisfied. Let me show you:

$$C_2 = 2C_1^2 - 1 = \frac{1}{2}(C_1 + \sqrt{C^2_1 - 1})^2 + \frac{1}{2}(C_1 - \sqrt{C^2_1 - 1})^2$$

$$ 2C_1^2 - 1 = \frac{1}{2}(C^2_1 + 2C_1\sqrt{C^2_1 - 1}) + C^2_1 - 1) + \frac{1}{2}(C^2_1 - 2C_1\sqrt{C^2_1 - 1}) + C^2_1 - 1)$$

I find it astonishing that it automatically satisfies the second one without even considering it before hand. I am not sure why this happens but I'd love to understand why this is the case and what would happen if something else was chosen instead. Is this method valid to solve any arbitrary recurrence of the form:

$$ C_n = pC_{n-1} - C_{n-1}$$

or is there something fishy going on?

If one writes the initial condition as linear algebra equations (matrix equations) one can appreciate that the matrix is always singular, no matter what the initial conditions are. Not sure if that is behind this strange behavior.

$\endgroup$
2
$\begingroup$

I would have set the relation as $$C_n = 2a C_{n-1} - C_{n-2}$$ with conditions $C_1=a$, $C_2=b$.

The characteristic equation being $r^2=2ar-1$, the roots of it are given by $$r_{1,2}=a\pm\sqrt{a^2-1}$$ and so $$C_n=c_1 r_1^n+c_2 r_2^n$$ Applying the conditions $C_1=a$, $C_2=b$ then gives $$c_1=\frac{a r_2-b}{r_1 (r_2-r_1)}$$ $$c_2=\frac{b-a r_1}{r_2 (r_2-r_1)}=2a^2-b-c_1$$

I do not see particular cases in this problem which would impose $c_1=c_2=\frac 12$ except if $b=2a^2-1$ which is precisely the case if $C_0=1$ ($b=C_2=2aC_1-C_0=2a^2-C_0$).

Using what I wrote above, in general $C_0=2a^2-b$.

$\endgroup$

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.