HSC 2012 MX2 Marathon (archive) (1 Viewer)

karnbmx · Jul 12, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Might as well bring this back to life.

Prove that the polynomial

$p(x)=\sum_{k=0}^{2n} \frac{x^k}{k!}$

has no real roots. (Where n is a non-negative integer.)

I don't know if this is right, but I'll give it a shot.

$P(x) = p(x)=\sum_{k=0}^{2n} \frac{x^k}{k!}$
Expanding, we get:

$P(x) = 1 + x + \frac{x^2}{2!} + \frac{x^4}{4!} + .... + \frac{x^2^n}{2n!}$

Thus for P(x) to be zero, the terms after 1 must add up to -1. Hence:

$x + \frac{x^2}{2!} + \frac{x^4}{4!} + .... + \frac{x^2^n}{2n!} = -1$

BUT, there is no real value of x for which the above sum can possibly equal to -1. Therefore, there are no real roots for P(x).

EDIT: say. if you put x = -2, the value of the sum will be a limit that approaches -1, but never reaches -1. this would be the same for all x = m, where the sum will approach m + 1.

seanieg89 · Jul 12, 2012

Re: 2012 HSC MX2 Marathon

Not quite, the polynomial does not contain only even powers...some justification would be needed to say that the sum of the nonconstant terms can never be -1. (I also do not understand what you are saying about limits.)

A hint: One way to do it is by induction.

karnbmx · Jul 12, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Not quite, the polynomial does not contain only even powers...some justification would be needed to say that the sum of the nonconstant terms can never be -1. (I also do not understand what you are saying about limits.)

A hint: One way to do it is by induction.

Alright, I'll have to think about it then. :S

Godmode · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Might as well bring this back to life.

Prove that the polynomial

$p(x)=\sum_{k=0}^{2n} \frac{x^k}{k!}$

has no real roots. (Where n is a non-negative integer.)

Let's see if this works...

$p(x) = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... + \frac{x^{2n}}{2n!}$

We know that n is an integer, so 2n must be even. Therefore, p(x) is an even polynomial, as it has a degree of 2n.
From the fundamental theorem of algebra, we also know that there are 2n roots of p(x), therefore we have an even number of roots.

Now the product of all roots (which I am going to call: $\alpha_{i}$ ) is

$\prod_{i=1}^{2n} \alpha_{i} = \alpha_{1}\alpha_{2}\alpha_{3} \times... \times \alpha_{2n} = (-1)^{2n} \frac{a_{2n}}{a}$

Where a and a_2n are the coefficients of the first and last term respectively (I flipped p(x) around so the x^2n/2n! is the first term)
We know that the a_2n/a must't have a negative 1 out the front, because p(x) is even. For example, look at a quadratic or quartic. The product of roots being c/a and e/a respectively.

Subbing in values for a and a_2n:

$\prod_{i=1}^{2n} \alpha_{i} = (1) \times\frac{1}{\frac{1}{2n!}} = 2n!$

Now if we take a look at the sum of roots taken 2n-1 at a time (i.e. the product divided by a single root) we find that:

$\sum_{j=1}^{2n} \frac{\prod_{i=1}^{2n} \alpha_{i}}{\alpha_{j}} = -\frac{a_{2n-1}}{a_{1}} =-2n!$

As a_2n = a_(2n-1) = 1.

Now, if we take a closer look at the above sum, we find it can be expressed as:

$\begin{align*} \sum_{j=1}^{2n} \frac{\prod_{i=1}^{2n} \alpha_{i}}{\alpha_{j}} &= \frac{\prod_{i=1}^{2n} \alpha_{i}}{\alpha_{1}} + \frac{\prod_{i=1}^{2n} \alpha_{i}}{\alpha_{2}} + ... + \frac{\prod_{i=1}^{2n} \alpha_{i}}{\alpha_{2n}} \\ &= \frac{2n!}{\alpha_{1}} + \frac{2n!}{\alpha_{2}} + ... + \frac{2n!}{\alpha_{2n}} \\ &= -2n! \end{align*}$

Cancelling the 2n!, we get

$\frac{1}{\alpha_{1}} + \frac{1}{\alpha_{2}} + ... + \frac{1}{\alpha_{2n}} = -1$

now:

$\text{Let} \: \alpha_{i} = \beta_{i}^2 \\ \text{Now, we are going to Substitute} \: \beta_{i} \: \text{for} \: \alpha_{i}} \\ \\ \text{i.e.} \: \frac{1}{\beta_{1}^2} + \frac{1}{\beta_{2}^2} + ... + \frac{1}{\beta_{2n}^2} = -1$

In order for this statement to be true, $\beta_{i}$ must be complex.

i.e. $\beta_{i} = c + di , \text{Where c, d} \in \mathbb{R}$

This means that $\alpha_i = (c + di)^2 = c^2 - d^2 + 2icd$

In order for $\alpha_i$ to be complex, both c and d =! 0.
d =! 0 is obvious, as $\beta_{i}$ would not be complex if d = 0.

Now, we must show that c =! 0

$\text{Assume} \: c = 0 \\ \therefore \: \alpha_{i} = -d^2\\ \text{Now,} \: \frac{1}{-d_{1}^2} + \frac{1}{-d_{2}^2} + ... + \frac{1}{-d_{2n}^2} = -1$
(Where each d_i belongs to its respective $\alpha_i$ )

Cancelling the negative sign,

$\frac{1}{d_{1}^2} + \frac{1}{d_{2}^2} + ... + \frac{1}{d_{2n}^2} = 1$

Although this looks plausible, d^2 > 1 for it to hold true.

i.e. d < -1 & d > 1 , but d is still not equal to 0

Now, as

$\alpha_i = -d_i^2$

We can substitute this back into the original sum.

$\begin{align*} 0 = p(-d_i^2) &= \sum_{k=0}^2n \frac{(-d_i^2)^k}{k!} \\ &= 1 -d_i^2 + \frac{-d_i^4}{2!} + \frac{-d_i^6}{3!} + ... + \frac{-d_i^4n}{2n!} \end{align*} \\ \therefore \: d_i^2 + \frac{d_i^4}{2} + \frac{d_i^6}{6} + ... + \frac{d_i^4n}{2n!} = 1$

Now, in order for this expression to hold true, d^2 < 1 or -1< d<1.

However, we already know that d^2 > 1. This leads us to a contradiction; how can d^2 be both less than and greater than 1? This means that our initial assumption, c = 0 is false.

As c, d =! 0, This means that $\alpha_i$ is complex.

$\therefore \: p(x)$ has no real roots.

.
.
.
.
.
.

This goddamn better be right, I spent all night on this...

EDIT: Hang on, I don't think I can sub in d^2 into p(x) like that, the even powers will cancel the negative sign

seanieg89 · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

Also, the sum of the squares of the reciprocals of the \beta_i's being negative does not imply that every \beta_i has nonzero imaginary part, it only implies that SOME of the \beta_i's have nonzero imaginary part.

Eg (i*sqrt(2))^2+1^2=-1<0 even though 1 is real.

Godmode · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

Damn, guess I will have to start again lol

Does the fact that the limit of the sum as 2n approaches infinity = e^x have anything to do with the question?

seanieg89 · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

Nope, at least not the way I did it.

(And I don't see how that fact would be helpful. Remember, for a fixed n, this polynomial will resemble e^x less and less the further you get from x=0, so the properties of the function e^x have little bearing here.)

Godmode · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

Well, at least I know it can be solved now.

Is it worth looking into the conjugates of each complex root?

bleakarcher · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Might as well bring this back to life.

Prove that the polynomial

$p(x)=\sum_{k=0}^{2n} \frac{x^k}{k!}$

has no real roots. (Where n is a non-negative integer.)

If n is a non-negative integer, then n>=0. But say we find P(x) for n=0, we find that P(x)=0. This has infinite roots. Maybe you mean for all positive integers n, or is there something wrong with my logic?

Edit: P(x)=1 for n=0. Sorry, disregard.

seanieg89 · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

Godmode said:
Well, at least I know it can be solved now.

Is it worth looking into the conjugates of each complex root?

It's not what I did but it might lead somewhere

.

RealiseNothing · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Might as well bring this back to life.

Prove that the polynomial

$p(x)=\sum_{k=0}^{2n} \frac{x^k}{k!}$

has no real roots. (Where n is a non-negative integer.)

Trivially, for $x \geq 0$ it has no real roots due to the '1' being out the front of the expression, meaning it can never equal 0. So we only have to show that for $x < 0$ the statement is true.

Essentially what we want to prove is that $\frac{x^{2n}}{(2n)!} > |\frac{x^{2n-1}}{(2n-1)!}|$ for all $x < 0$

Edit: fixing something up.

seanieg89 · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

Not quite, you are adding the two terms x^{2n}/(2n)! and x^{2n-1}/(2n-1)!. You would need the SUM of these to be positive for negative x to make your argument work. (Or equivalently you could show that their difference is positive for positive x).

And in fact this is not the case. It is easy to show that p'(0)=1, so the poly definitely gets a bit smaller as you move to the left of the origin. If what you are claiming is true, then the poly would have a minimum value of 1 at the origin.

RealiseNothing · Jul 13, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Not quite, you are adding the two terms x^{2n}/(2n)! and x^{2n-1}/(2n-1)!. You would need the SUM of these to be positive for negative x to make your argument work. (Or equivalently you could show that their difference is positive for positive x).

And in fact this is not the case. It is easy to show that p'(0)=1, so the poly definitely gets a bit smaller as you move to the left of the origin. If what you are claiming is true, then the poly would have a minimum value of 1 at the origin.

Yep I just realised that.

seanieg89 · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

seanieg89 said:
Might as well bring this back to life.

Prove that the polynomial

$p(x)=\sum_{k=0}^{2n} \frac{x^k}{k!}$

has no real roots. (Where n is a non-negative integer.)

Perhaps time for a hint...the derivatives of this polynomial look quite similar to it! A sign that some sort of induction will work.

asianese · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

I'm not gonna latex something out and spend ages (like last night==) on it but I may have something if it is induction.

I wrote p(x) out as a sum to x^2k/(2k)!

Try the case for n=0, p(x)=1 which has no real roots

Assume that p(x) has no real roots for n=k, such that

p(x) = x^0/0! + x^1/1!+...+x^k/k! +... + x^2k/(2k)! has no real roots

Try the case for n=k+1

RTP: P(x) (new polynomial with extra term) = x^0/0! + x^1/1!+...+x^k/k! +... + x^2k/(2k)! + x^2k+1/(2k+1)! has no real roots.

Notice that P'(x) = 1+x/1!+...+x^k-1/(k-1)!+...+x^2k-1/(2k-1)!+x^2k/(2k)!.

Hence P(x)=P'(x)+x^2k/(2k)!

Now we know that P'(x)=p(x) and hence from our assumption, there are no real roots to P'(x).

The term x^2k/(2k)! is an even polynomial (and is completely positive so there is no worry about flipping into the x axis), and so that if this is added to a polynomial with no real roots, P'(x)=p(x), then the new polynomial (P(x)) will still have no real roots.

Hence p(x) has no real roots for n, non negative integer by mathematical induction

I thought about things like y=x^2+1 and if you add a even power you'll still get something with no real roots. lol probably soooo off track

seanieg89 · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

Careful, you are not adding just one term to the poly every time n goes up by one.

asianese · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

Hmm why is that?

seanieg89 · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

Because 2(n+1)=2n+2

.

asianese · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

HAHA wow. wowza. lolol sorry hahaa

barbernator · Jul 15, 2012

Re: 2012 HSC MX2 Marathon

<a href="http://www.codecogs.com/eqnedit.php?latex=P(x)=\sum_{r=1}^{2n}\frac{x^{r}}{r!}\\ P'(x)=\sum_{r=1}^{2n-1}\frac{x^{r}}{r!}\\ P''(x)=\sum_{r=1}^{2n-2}\frac{x^{r}}{r!}\\ We~will~now~show~by~induction~that~P(x)~has~no~real~roots.\\ Let~n=1~to~show,\\ P(x)=\frac{x^2}{2}@plus;x@plus;1\\ P'(x)=x@plus;1=0,~x=-1\\ P(-1)=\frac{1}{2}.~\therefore ~for~n=1,~P(x)~has~no~real~roots\\ P''(x)=1.~\therefore ~the~function~is~concave~up.\\ Assume~that~P(x)~has~no~real~roots~for~n=k.\\ i.e.~\sum_{r=1}^{2k}\frac{x^{r}}{r!}> 0\\ To~prove~true~for~n=k@plus;1\\ TBP:~P(x)=\sum_{r=1}^{2k@plus;2}\frac{x^{r}}{(r)!}> 0\\ LHS=\sum_{r=1}^{2k@plus;2}\frac{x^{r}}{(r)!}\\ =\sum_{r=1}^{2k}\frac{x^{r}}{r!}@plus;\frac{x^{2k@plus;1}}{(2k@plus;1)!}@plus;\frac{x^{2k@plus;2}}{(2k@plus;2)!}\\ taking~the~second~derivative\\ P''(x)=\sum_{r=1}^{2k}\frac{x^{r}}{r!}>0.\\ this~isnt~correct~cos~it~isnt~showing~that~the~min~stat~point~is~>~0~but~i~dunno~where~to~go." target="_blank"><img src="http://latex.codecogs.com/gif.latex?P(x)=\sum_{r=1}^{2n}\frac{x^{r}}{r!}\\ P'(x)=\sum_{r=1}^{2n-1}\frac{x^{r}}{r!}\\ P''(x)=\sum_{r=1}^{2n-2}\frac{x^{r}}{r!}\\ We~will~now~show~by~induction~that~P(x)~has~no~real~roots.\\ Let~n=1~to~show,\\ P(x)=\frac{x^2}{2}+x+1\\ P'(x)=x+1=0,~x=-1\\ P(-1)=\frac{1}{2}.~\therefore ~for~n=1,~P(x)~has~no~real~roots\\ P''(x)=1.~\therefore ~the~function~is~concave~up.\\ Assume~that~P(x)~has~no~real~roots~for~n=k.\\ i.e.~\sum_{r=1}^{2k}\frac{x^{r}}{r!}> 0\\ To~prove~true~for~n=k+1\\ TBP:~P(x)=\sum_{r=1}^{2k+2}\frac{x^{r}}{(r)!}> 0\\ LHS=\sum_{r=1}^{2k+2}\frac{x^{r}}{(r)!}\\ =\sum_{r=1}^{2k}\frac{x^{r}}{r!}+\frac{x^{2k+1}}{(2k+1)!}+\frac{x^{2k+2}}{(2k+2)!}\\ taking~the~second~derivative\\ P''(x)=\sum_{r=1}^{2k}\frac{x^{r}}{r!}>0.\\ this~isnt~correct~cos~it~isnt~showing~that~the~min~stat~point~is~>~0~but~i~dunno~where~to~go." title="P(x)=\sum_{r=1}^{2n}\frac{x^{r}}{r!}\\ P'(x)=\sum_{r=1}^{2n-1}\frac{x^{r}}{r!}\\ P''(x)=\sum_{r=1}^{2n-2}\frac{x^{r}}{r!}\\ We~will~now~show~by~induction~that~P(x)~has~no~real~roots.\\ Let~n=1~to~show,\\ P(x)=\frac{x^2}{2}+x+1\\ P'(x)=x+1=0,~x=-1\\ P(-1)=\frac{1}{2}.~\therefore ~for~n=1,~P(x)~has~no~real~roots\\ P''(x)=1.~\therefore ~the~function~is~concave~up.\\ Assume~that~P(x)~has~no~real~roots~for~n=k.\\ i.e.~\sum_{r=1}^{2k}\frac{x^{r}}{r!}> 0\\ To~prove~true~for~n=k+1\\ TBP:~P(x)=\sum_{r=1}^{2k+2}\frac{x^{r}}{(r)!}> 0\\ LHS=\sum_{r=1}^{2k+2}\frac{x^{r}}{(r)!}\\ =\sum_{r=1}^{2k}\frac{x^{r}}{r!}+\frac{x^{2k+1}}{(2k+1)!}+\frac{x^{2k+2}}{(2k+2)!}\\ taking~the~second~derivative\\ P''(x)=\sum_{r=1}^{2k}\frac{x^{r}}{r!}>0.\\ this~isnt~correct~cos~it~isnt~showing~that~the~min~stat~point~is~>~0~but~i~dunno~where~to~go." /></a>

EDIT: the r=1 are supposed to be r=0.

HSC 2012 MX2 Marathon (archive) (1 Viewer)

Member

Well-Known Member

Member

Activated

Well-Known Member

Activated

Well-Known Member

Activated

Active Member

Well-Known Member

what is that?It is Cowpea

Well-Known Member

what is that?It is Cowpea

Well-Known Member

Σ

Well-Known Member

Σ

Well-Known Member

Σ

Active Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)