Waste less time on Facebook — follow Brilliant.
×

I cannot solve this recurrence...

So I have been thinking about this series:

\(\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?

I just don't know how to start with this.Do I just guess the formula and prove it by induction, or do I somehow solve the recurrence relation?Please help me in the comments.

Note by Bogdan Simeonov
3 years, 4 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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

http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html Jon Haussmann · 3 years, 4 months ago

Log in to reply

@Jon Haussmann Hmm...I can't find a relation between these Chebyshev polynomials and \(a_n\)...Could you please explain what they have in common? Bogdan Simeonov · 3 years, 4 months ago

Log in to reply

@Bogdan Simeonov 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.\] Jon Haussmann · 3 years, 4 months ago

Log in to reply

@Jon Haussmann 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}\) Bogdan Simeonov · 3 years, 3 months ago

Log in to reply

@Bogdan Simeonov There you go! Well done. Jon Haussmann · 3 years, 3 months ago

Log in to reply

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? Daniel Remo · 3 years, 4 months ago

Log in to reply

@Daniel Remo 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 Bogdan Simeonov · 3 years, 4 months ago

Log in to reply

@Bogdan Simeonov The formula you got doesn't look too dissimilar to that for Chebyshev polynomials Daniel Remo · 3 years, 3 months ago

Log in to reply

i know it can be generalized but how many times to write 2,how you will decide\ Umer Rauf · 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...