Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    18
    ReputationRep:
    (Original post by Smaug123)
    I am sad that there doesn't seem to be a nice proof of this
    Oh there definitely is. In fact it is one of the cleverest proofs I know, and it is about 3 lines long.
    • PS Helper
    • Study Helper
    Offline

    13
    ReputationRep:
    PS Helper
    Study Helper
    (Original post by Lord of the Flies)
    Oh there definitely is. In fact it is one of the cleverest proofs I know, and it is about 3 lines long.
    There's an infinite-descent proof of the form "suppose this fails; then we prove that there is an infinite number of points", but I don't think that proof is very nice do you have a different one in mind?
    Offline

    15
    ReputationRep:
    Problem 562*

    Factorise x^{2n+1}-1 as a product of real linear and quadratic polynomials.
    Write x^{2n}+x^{2n-1}+...+x+1 as a product of real quadratic polynomials.
    Offline

    10
    ReputationRep:
    Solution 562
    Spoiler:
    Show

    The roots of x^{2n+1} - 1 = 0 are  1,w, w^2, .... w^{2n} where  w= \cos \frac{2\pi}{2n+1} + i \sin \frac{2\pi}{2n+1}.

    Hence we can write

    x^{2n+1} - 1 

= (x -1)(x -w )(x-w^2)....(x - w^{2n})



 = (x - 1)[(x - w)(x - w^{2n})][(x - w^2)(x-w^{2n-1})]....[(x - w^n)(x - w^{n+1}]



= (x - 1)[x^2 - (w + w^{2n})x + 1][x^2 - (w^2 + w^{2n-1})x + 1]...[x^2 - (w^n + w^{n+1})x + 1]



= (x -  1)(x^2 - (2\cos \frac{2\pi}{2n+1}) x + 1)(x^2 - (2\cos \frac {4\pi}{2n+1}) x + 1)....(x^2 - (2\cos \frac{2n\pi}{2n+1}) x + 1)

    For the final part note that (x - 1)(x^{2n} + x^{2n-1}+... + x + 1) = x^{2n+1} - 1 hence

    x^{2n} + x^{2n-1}+... + x + 1

 = (x^2 - (2\cos \frac{2\pi}{2n+1}) x + 1)(x^2 - (2\cos \frac {4\pi}{2n+1} )x + 1)....(x^2 -( 2\cos \frac{2n\pi}{2n+1}) x + 1)
    Offline

    18
    ReputationRep:
    (Original post by Smaug123)
    There's an infinite-descent proof of the form "suppose this fails; then we prove that there is an infinite number of points", but I don't think that proof is very nice do you have a different one in mind?
    I think we are referring to the same idea then, though in your version contradiction/descent seems like a superfluous addition. It is more "do X, if A: end, if B: do Y and restart with X. There are finitely many points, this must halt, done".

    I personally think the idea is extremely clever. Granted drawing lines isn't too pretty, but the idea is very hard to come by from the statement - not to mention that by nature of the problem, it feels overoptimistic to expect a proof that does not draw lines and look at properties of said lines. Different tastes I guess!
    Offline

    19
    ReputationRep:
    (Original post by Lord of the Flies)
    I think we are referring to the same idea then, though in your version contradiction/descent seems like a superfluous addition. It is more "do X, if A: end, if B: do Y and restart with X. There are finitely many points, this must halt, done".

    I personally think the idea is extremely clever. Granted drawing lines isn't too pretty, but the idea is very hard to come by from the statement - not to mention that by nature of the problem, it feels overoptimistic to expect a proof that does not draw lines and look at properties of said lines. Different tastes I guess!
    whats the proof then
    Offline

    18
    ReputationRep:
    (Original post by newblood)
    ...
    Spoiler:
    Show
    Pick any 2 points and draw a line \ell through them: suppose a 3rd point lies on the line (else we are done) and pick the closest point p\not\in\ell to the line, at a distance \delta say.

    Of our 3 points \in\ell a pair lies on one side of p: draw a line \ell' through p and the furthest of the pair from p. The distance \delta' between \ell' and the second point is <\delta



    It is surprising, at least to me, that this statement was only first proved in 1943/44.
    Offline

    0
    ReputationRep:
    This **** crayyyyyyyyy
    Offline

    10
    ReputationRep:
    Problem 563*

    Define a family of polynomials by:

     T_0 (x) = 1,  T_1 (x) = x

    T_{n+1} (x) = 2xT_n(x) - T_{n-1}(x) \text{ for } n \geq 1


    Prove that  \deg (T_n (x)) = n and find the coefficient of x^n in T_n (x)

    Form and prove a conjecture about the significance of T_n (\cos \theta)



    Problem 564*

    Suppose  g(x) and f(x) are two nth order polynomials such that g(x) = f(x) at n+1 distinct real values of x. Prove that f(x) = g(x).
    Offline

    17
    ReputationRep:
    (Original post by 16Characters....)
    Problem 563*

    Define a family of polynomials by:

     T_0 (x) = 1,  T_1 (x) = x

    T_{n+1} (x) = 2xT_n(x) - T_{n-1}(x) \text{ for } n \geq 1


    Prove that  \deg (T_n (x)) = n and find the coefficient of x^n in T_n (x)

    Form and prove a conjecture about the significance of T_n (\cos \theta)



    Problem 564*

    Suppose  g(x) and f(x) are two nth order polynomials such that g(x) = f(x) at n+1 distinct real values of x. Prove that f(x) = g(x).
    I always thought the Chebysheff polynomials woukld be a good theme for a STEP question; they certainly have a lot of odd properties.

    564 looks like another good 'not obvious unless you can prove it' type of question. I'll try both of these today.

    Posted from TSR Mobile
    Offline

    10
    ReputationRep:
    (Original post by Krollo)
    I always thought the Chebysheff polynomials woukld be a good theme for a STEP question; they certainly have a lot of odd properties.

    564 looks like another good 'not obvious unless you can prove it' type of question. I'll try both of these today.

    Posted from TSR Mobile
    Agreed. This was sort of the reason I was researching them actually. I had just done STEP II 1999 Q3 and was looking for a bit of practice with other "weirdly defined" polynomials.
    Offline

    17
    ReputationRep:
    (Original post by 16Characters....)
    Agreed. This was sort of the reason I was researching them actually. I had just done STEP II 1999 Q3 and was looking for a bit of practice with other "weirdly defined" polynomials.
    Have you done the question on bernoulli polynomials (87/3/10)?

    Posted from TSR Mobile
    Offline

    11
    ReputationRep:
    (Original post by 16Characters....)
    Agreed. This was sort of the reason I was researching them actually. I had just done STEP II 1999 Q3 and was looking for a bit of practice with other "weirdly defined" polynomials.
    There's a small section on orthogonal polynomials in some tripos courses, such as methods and numerical analysis.
    The questions are a little limited though, but if you're interested it may be worth a look.
    Offline

    10
    ReputationRep:
    (Original post by Krollo)
    Have you done the question on bernoulli polynomials (87/3/10)?

    Posted from TSR Mobile
    Nope, barely touched any of the pre-1993 papers yet but I'll have a look later in the week thanks.

    (Original post by joostan)
    There's a small section on orthogonal polynomials in some tripos courses, such as methods and numerical analysis.
    The questions are a little limited though, but if you're interested it may be worth a look.
    Thanks for the suggestion.
    Offline

    15
    ReputationRep:
    Solution 563*
    (Please let me know of mistakes/improvements, Im only a 'learner'!). I also apologise for the lack of LaTeX as I wasnt planning on sharing it.
    Name:  FullSizeRender.jpg
Views: 241
Size:  496.7 KB
    Maybe it was a bit of an overkill for the first part, but Im never too sure when it says to prove something which seems obvious.

    Problem 565*
    By considering the results from Problem 563, show that
    \displaystyle\int^1_{-1} \frac{T_{n}(x)T_{m}(x)}{\sqrt{1-x^{2}}}\ dx =

                                       0 for\ n\not=m

\pi for\ n=m=0, 

\frac{\pi}{2}\

                                          for n=m\not=0
    Offline

    10
    ReputationRep:
    Solution 565
    Try Q7 here for a similar question.
    Spoiler:
    Show

    Let I_{m,n} = \displaystyle \int_{-1}^{1} \frac{ T_n(x) T_m(x)}{\sqrt{1-x^2}} dx

    Letting  x = \cos u :

    I_{m,n} = 

 \displaystyle \int_{0}^{\pi} \frac{ T_n(\cos u) T_m(\cos u)}{\sin u} \sin u du



= \displaystyle \int_{0}^{\pi} \cos mu \cos nu du



= 0.5 \displaystyle \int_{0}^{\pi} \left(\cos(m+n)u + \cos (m-n)u \right) du

    Considering the case  m = n \neq 0:


     I_{m,m} = \frac{1}{2} \displaystyle \int_0^{\pi} \left (1 + \cos 2mu \right) du



 = 0.5 (\pi + 0 - 0 - 0) = \frac{\pi}{2}
    As required.

    Now considering  m = n = 0

    I_{0,0} = \frac{1}{2} \displaystyle \int_0^{\pi} 2 du 

= \displaystyle \int_0^{\pi} du = \pi
    As required

    Now for m \neq n

    I_{m,n} = \frac{1}{2}  \displaystyle \int_{0}^{\pi} \left(\cos(m+n)u + \cos (m-n)u \right) du



 =  \left[\frac{\sin (m+n)u}{m+n} + \frac{\sin (m-n)u}{m-n} \right]_{0}^{\pi} 



= 0 + 0 - 0 - 0 = 0
    As required.

    Note: I had a string of annoying LaTeX issues so did a lot of cutting and retyping. If it looks like something is missing, it probably is!
    Offline

    15
    ReputationRep:
    (Original post by 16Characters....)
    Solution 565
    Try Q7 here for a similar question.
    Spoiler:
    Show

    Let I_{m,n} = \displaystyle \int_{-1}^{1} \frac{ T_n(x) T_m(x)}{\sqrt{1-x^2}} dx

    Letting  x = \cos u :

    I_{m,n} = 

 \displaystyle \int_{0}^{\pi} \frac{ T_n(\cos u) T_m(\cos u)}{\sin u} \sin u du



= \displaystyle \int_{0}^{\pi} \cos mu \cos nu du



= 0.5 \displaystyle \int_{0}^{\pi} \left(\cos(m+n)u + \cos (m-n)u \right) du

    Considering the case  m = n \neq 0:


     I_{m,m} = \frac{1}{2} \displaystyle \int_0^{\pi} \left (1 + \cos 2mu \right) du



 = 0.5} (\pi + 0 - 0 - 0) = \frac{\pi}{2}
    As required.

    Now considering  m = n = 0

    I_{0,0} = \frac{1}{2} \displaystyle \int_0^{\pi} 2 du 

= \displaystyle \int_0^{\pi} du = \pi
    As required

    Now for m \neq n

    I_{m,n} = \frac{1}{2}  \displaystyle \int_{0}^{\pi} \left(\cos(m+n)u + \cos (m-n)u \right) du



 =  \left[\frac{\sin (m+n)u}{m+n} + \frac{\sin (m-n)u}{m-n} \right]_{0}^{\pi} 



= 0 + 0 - 0 - 0 = 0
    As required.

    Note: I had a string of annoying LaTeX issues so did a lot of cutting and retyping. If it looks like something is missing, it probably is!
    Lol yep i know what you mean, it it took a long while to type up the question to start with So are you a current student or graduate?
    Offline

    10
    ReputationRep:
    (Original post by EnglishMuon)
    Lol yep i know what you mean, it it took a long while to type up the question to start with So are you a current student or graduate?
    Year 13 lol, Joostan suggested I look at a Numerical Analysis worksheet because me and Krollo were discussing the Chebyshev polynomials. That question is the only one I am brave enough to even attempt!
    Offline

    15
    ReputationRep:
    (Original post by 16Characters....)
    Year 13 lol, Joostan suggested I look at a Numerical Analysis worksheet because me and Krollo were discussing the Chebyshev polynomials. That question is the only one I am brave enough to even attempt!
    Ah nice! Do you have any links to these worksheets? I've been having great fun on these polynomial questions. I first thought they were Bernoulli polynomials but it just turns out they have many cool properties in common. But yeah I should've know u were year 13, seen u around in the camb. Offers holders thread me thinks
    Offline

    10
    ReputationRep:
    (Original post by EnglishMuon)
    Ah nice! Do you have any links to these worksheets? I've been having great fun on these polynomial questions. I first thought they were Bernoulli polynomials but it just turns out they have many cool properties in common. But yeah I should've know u were year 13, seen u around in the camb. Offers holders thread me thinks
    Here are the Camb example sheets.

    Also as Krollo recommended on the previous page, STEP III 1987 Q10 is about the Bernoulli poylnomials.
 
 
 
Poll
Do you agree with the PM's proposal to cut tuition fees for some courses?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.