# I cannot solve this recurrence...

$$\displaystyle a_n=x^n+ \frac{1}{x^n}$$.

I've found the following relation :

$$a_n=a_{n-1}.a_1 -a_{n-2}$$

Imagine we know the first term $$a_1$$, so $$\displaystyle a_1=x+\frac{1}{x}=c$$ (c is a constant).

Now can we find a general formula for $$a_n$$ involving c?I know that we can solve for x in $$a_1$$ , but then in $$x^{-n}$$ the denominator would be an ugly mess...

So my idea was to solve the recurrence relation

$$a_{n}=c.a_{n-1}-a_{n-2}$$.

We get $$a_2=c^2-2$$, $$a_3=c^3-3c$$, $$a_4=c^4-4c^2+2$$ etc.

Now look at $$a_4$$. It turns out it is equal to $$a_2^2 -2$$. Remind you of something?

That is kind of weird, isn't it?

Note by Bogdan Simeonov
4 years, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

The expressions for $$a_n$$ are related to the Chebyshev Polynomial of the First Kind. You can find more information at the usual websites:

http://en.wikipedia.org/wiki/Chebyshev_polynomials

- 4 years, 3 months ago

Hmm...I can't find a relation between these Chebyshev polynomials and $$a_n$$...Could you please explain what they have in common?

- 4 years, 3 months ago

Let $$T_n(x)$$ denote the $$n$$th Chebyshev Polynomial of the First Kind. Then $a_n = 2 T_n \left( \frac{c}{2} \right).$

For example, $$T_3(x) = 4x^3 - 3x$$, so $a_3 = 2 T_3 \left( \frac{c}{2} \right) = 2 \left[ 4 \left( \frac{c}{2} \right)^3 - 3 \cdot \frac{c}{2} \right] = c^3 - 3c.$

- 4 years, 3 months ago

Aha!Now I get it...you let x=c/2 and then expressed $$a_n$$ as $$2T_n(\frac{c}{2})$$ .So the formula I got is actually the same as the one on the Wikipedia page , which says

$$\displaystyle T_n(x)=\frac{(x-\sqrt{x^2-1})^n +(x+\sqrt{x^2-1})^n }{2}$$

- 4 years, 3 months ago

There you go! Well done.

- 4 years, 3 months ago

You could solve it by considering the characteristic equation of the recurrence, which will be $$x^{2}-cx+1=0$$ Letting both solutions be $$a,b$$ you couldn't then 'hope' the general formula is of the form $$a_{n}=ua^{n}+vb^{n}$$ some constants $$u,v$$ then as you can calculate the first couple of terms of the sequence manually, you could solve the simultaneous equations for $$u,v$$ and maybe that might be your formula?

- 4 years, 3 months ago

That worked!Thanks! But that's practically solving for x in $$1+ \frac{1}{x}=c$$,which is equivalent to the characteristic equation.That is why u=v=1 works, because by Vieta we get ab=1, or $$a=\frac{1}{b}$$.So $$a^n+b^n=x^n+x^{-n}=a_n$$.That means that the only thing we needed is to solve for x in $$a_1$$... The final formula is

$$\displaystyle a_n=(\frac{(c+\sqrt{c^2-4})}{2})^n+(\frac{(c-\sqrt{c^2-4})}{2})^n$$

I don't know why, but I still am kind of confused :D

- 4 years, 3 months ago

The formula you got doesn't look too dissimilar to that for Chebyshev polynomials

- 4 years, 3 months ago

i know it can be generalized but how many times to write 2,how you will decide\

- 4 years, 3 months ago