Author Topic: TT's Maths Thread (Read 133136 times) Tweet Share

kamil9876 · « **Reply #135 on:** November 22, 2009, 02:56:02 pm »

yeah they tried to pack everything into one sentences. "all coefficents are integers of the polynomials", "the polynomials themselves are of degree at least one". You need some constant term obviously since you can only get the +3 at the end from multiplying two constants.

TrueTears · « **Reply #136 on:** November 22, 2009, 07:13:48 pm »

Oh right nevermind I misread the sentence sigh.

Also kamil when you said:

Quote

Ok so first case assume $p \leq q$ , in other words the first polynomial(with constant $\pm 3$ ) has bigger or equal degree.

Shouldn't it be $p \ge q?$

kamil9876 · « **Reply #137 on:** November 22, 2009, 07:26:13 pm »

nah I should've said the second polynomial has bigger or equal degree, ie just focus on $p \leq q$ .

TrueTears · « **Reply #138 on:** November 23, 2009, 05:10:59 am »

Thank you SOOOO much kamil, I finally get this question! Been stuck on it for several days

Just gonna type up this question formally. Including the 2nd case.

So assume that $f(x)$ can be factorised into 2 polynomials with integer coefficients.

$f(x) = p(x)q(x) = (x^p + a_{p-1}x^{p-1} + a_{p-2}x^{p-2} +...+a_2x^2 + a_1x+a_0)(x^q + b_{q-1}x^{q-1} + b_{q-2}x^{q-2} +...+b_2x^2 + b_1x+b_0)$

Now $a_0b_0 = 3$ .

Assume $a_0 = \pm 3 \implies b_0 = \pm 1$ or $a_0 = \pm 1$ and $b_0 = \pm 3$

Now the 2 factors can not be linear. Why?

When $p(x)$ is linear then $(x+a_0)q(x) = f(x)$

But $a_0 = \pm 3$ or $\pm 1$ but none of these equal $0$ when subbed into $f(x)$ . Thus there can be no linear factors.

Now for all $n>2$ the coefficient of the $x$ term in $f(x)$ must be $0$ .

Thus $a_1b_0 + a_0b_1 = 0$

Take the first case $a_0 = \pm 3$ and $b_0 = \pm 1$

$(\pm 1)a_1 + (\pm 3)b_1 = 0$

$\pm a_1 = \mp 3b_1$

This means $a_1$ and $a_0$ are multiples of $3$ .

Doing some experimenting:

When $n = 4$ , that means the coefficient of $x^2$ is also $0$ .

Thus $a_2b_0 + a_1b_1 + a_0b_2 = 0$

Thus $\pm a_2 = -(a_1b_1 + a_0b_2)$ (since $b_0 = \pm 1$ )

Since $a_1$ and $a_0$ are both multiples of $3$ we can factor out a $3$ leaving $a_2 = -3(\mbox{some positive integer})$

Which means $a_2$ is also a multiple of $3$ .

Now a few things can be noticed:

1. The subscript of a and b both add to up the power of the term we need to the find the coefficient of.

2. Continuing this we find that $a_3, a_4...$ are also multiples of $3$ .

This means if we can prove that all of the coefficients of $p(x)$ are multiples of $3$ then we can use contradiction to show that $p(x)$ can not exist as the coefficient of $x^p$ is $1$ which is not a multiple of $3$ .

Say we want to find the coefficient of $x^m$ term in $f(x)$ where $0 < m \le p$ . (I'm restricting the domain only up to $p$ because we just require to prove the coefficients of $p(x)$ are multiples of $3$ .)

Now consider the polynomial $p(x)$ where $m \le p < n-1$ (In other words, the lowest degree of $p$ is $m$ and it must be strictly smaller than $n-1$ or else $q(x)$ would be a linear factor)

Using the pattern we saw earlier in the experimenting to find an equation for the coefficient of $x^m$ yields:

$a_0b_m + a_1b_{m-1} + a_2b_{m-2} + ... + a_{m-1}b_1 + a_mb_0 = 0$

Now we can use strong induction to prove $a_m$ is a multiple of $3$ .

First Case: When $p \le q$

Base Case

when $m = 1$

$a_0b_1 + a_1b_0 = 0$

We have already proved earlier using this that $a_1$ is a multiple of $3$ .

Inductive Hypothesis

Assume all $a_0, a_1, a_2 ... a_{m-1}$ are multiples of $3$ .

Proof

Since $a_0, a_1, a_2 ... a_{m-1}$ are multiples of $3$ then the equation can be rewritten into:

$3(S) + a_mb_0 = 0$ (Factoring out a $3$ , while calling the integer sum inside the bracket $S$ )

But $b_0 = \pm 1$

$\therefore 3S \pm a_m = 0$

$3S = \mp a_m$

Therefore by induction, $a_m$ is also a multiple of $3$ .

Second Case: When $p>q$ .

Why consider this case? Let's pick a random value of $p$ , say $p = 6$ and $q = 3$ .

Now say we wanted to find the coefficient of $x^m$ where $m = 4$ .

Then the equation would be: $a_0b_4 + a_1b_3 + a_2b_2 + a_3b_1 + a_4b_0 = 0$

However $b_4$ does not exist as the highest power of $q$ is $3$ so there is no such thing as the coefficient of $x^4$ for $q(x)$ .

This causes a problem, so we need to change our general equation a bit.

This is where I am stuck. lolz

kamil9876 · « **Reply #139 on:** November 23, 2009, 02:29:17 pm »

you can say that $b_4=0$ since the x^4 coefficent of a polynomial of degree 3 can be considered as 0.

therefore in general equating the x^m coefficent for $m\leq p<n-1$ gives:
$<br />a_0 b_m + a_1 b_{m-1} ... + a_m b_0 = 0$

which gives:

$a_0 b_m + .... a_{m-1} b_1=\pm a_m$

now since by the inductive hypothesis each $a_i$ is a multiply of 3 for $i<m$ , the sum on the left hand side will be a sum of multiple of 3's hence a multiple of 3. (whether or not certain terms are 'non-existant' doesn't change the fact that the LHS must be a multiple of 3, or more conviently the non-existant terms can be considered as terms that equal 0, which is a multiple of 3 hence the argument is complete).

And so basically the argument is exactly the same as before, giving our desired contradiction.

Over9000 · « **Reply #140 on:** November 23, 2009, 05:16:50 pm »

Quote from: TrueTears on November 23, 2009, 05:42:36 pm

Found a pretty neat way for Q1.

Quote
1. Let $p(x)$ be a polynomial with integer coefficients satisfying $p(0) = p(1) = 1999$ . Show that $p(x)$ has no integer zeros.

Assume $p(x)$ does have integer zeros.

Thus $p(x)=(x-s)q(x)$

where s is an integer root and $q(x)$ is a polynomial with integer coefficients.

$p(0) = (0-s)q(0)$

$1999 = (-s)q(0)$

Now notice that $1999$ is prime.

We require $q(0)$ to be an integer. This means $s = -1$ and $q(0) = 1999$ or $s = 1$ and $q(0) = -1999$

$p(1) = (1-s)q(1)$

$1999 = (1-s)q(1)$

Subbing in $s = -1 \implies q(1) = \frac{1999}{2}$

Subbing in $s = 1 \implies 0 = 1999$

However these results are impossible thus by contradiction there exists no integer zeros for $p(x)$ .

Thats quite an elegant way to go about that question TT.

TrueTears · « **Reply #141 on:** November 23, 2009, 05:24:29 pm »

Also just realised that Perron's Criterion can be used for:

Quote

Let $f(x) = x^n + 5x^{n-1} + 3$ where $n > 1$ is an integer. Prove that $f(x)$ cannot be expressed as the product of two polynomials, each of which has all its coefficients integers and degree at least $1$ .

Perron's Criterion states that: for any polynomial $P(x) = x^n + a_{n-1}x^{n-1} + a_{n-2}x^{n-2} +... + a_{1}x + a_0$ with integer coefficients and $a_0 \neq 0$ , if $|a_{n-1}| > 1 + |a_{n-2}| + ... + |a_1| + |a_0|$ then $P(x)$ is irreducible over $\mathbb{Z}$ .

Applying that here. We see that $5 > 1+0+0+...+3 \implies 5>4$

Thus Perron's Criterion shows that $f(x)$ is irreducible over $\mathbb{Z}$ .

However is there an elementary way of proving Perron's Criterion?

I feel bad just applying it without any solid proof ^.^

TrueTears · « **Reply #142 on:** November 23, 2009, 05:34:58 pm »

Quote from: kamil9876 on November 23, 2009, 02:29:17 pm

you can say that $b_4=0$ since the x^4 coefficent of a polynomial of degree 3 can be considered as 0.

therefore in general equating the x^m coefficent for $m\leq p<n-1$ gives:
$<br />a_0 b_m + a_1 b_{m-1} ... + a_m b_0 = 0$

which gives:

$a_0 b_m + .... a_{m-1} b_1=\pm a_m$

now since by the inductive hypothesis each $a_i$ is a multiply of 3 for $i<m$ , the sum on the left hand side will be a sum of multiple of 3's hence a multiple of 3. (whether or not certain terms are 'non-existant' doesn't change the fact that the LHS must be a multiple of 3, or more conviently the non-existant terms can be considered as terms that equal 0, which is a multiple of 3 hence the argument is complete).

And so basically the argument is exactly the same as before, giving our desired contradiction.

Ohhh right I see, so it doesn't matter which is non-existant or not, all you really have to say is that they exist as 0. Thus it doesn't affect the factoring out the 3 on the LHS. Right?

TrueTears · « **Reply #143 on:** November 23, 2009, 05:42:36 pm »

Found a pretty neat way for Q1.

Quote

1. Let $p(x)$ be a polynomial with integer coefficients satisfying $p(0) = p(1) = 1999$ . Show that $p(x)$ has no integer zeros.

Assume $p(x)$ does have integer zeros.

Thus $p(x)=(x-s)q(x)$

where s is an integer root and $q(x)$ is a polynomial with integer coefficients.

$p(0) = (0-s)q(0)$

$1999 = (-s)q(0)$

Now notice that $1999$ is prime.

We require $q(0)$ to be an integer. This means $s = -1$ and $q(0) = 1999$ or $s = 1$ and $q(0) = -1999$

$p(1) = (1-s)q(1)$

$1999 = (1-s)q(1)$

Subbing in $s = -1 \implies q(1) = \frac{1999}{2}$

Subbing in $s = 1 \implies 0 = 1999$

However these results are impossible thus by contradiction there exists no integer zeros for $p(x)$ .

TrueTears · « **Reply #144 on:** November 23, 2009, 11:51:53 pm »

Can anyone tell me what I'm doing wrong with this question?

Let $a_1, a_2 ... a_n$ be a sequence of positive numbers. Show that $(a_1+a_2+...+a_n)\left(\frac{1}{a_1} + \frac{1}{a_2} + ... + \frac{1}{a_n}\right) \ge n^2$ .

So we require $\left[\sum_{i=1}^n (a_i)\right]\left[\sum_{k=1}^n \left(\frac{1}{a_k}\right)\right]$ .

First there will be $n^2$ terms in total after we expand the 2 brackets.

We can see that $\frac{a_1}{a_1} + \frac{a_2}{a_2} + ... + \frac{a_n}{a_n} = 1+1+...+1$

Which means there will be $\mbox{n}$ groups of $1$ .

What about the rest of the terms? Ie, the remaining $n^2-n$ terms.

A bit of experimenting quickly yields a pattern:

Consider expanding all the terms which do not produce the number $1$ .

$\frac{a_1}{a_2} + \frac{a_1}{a_3} +...+\frac{a_1}{a_n} + \frac{a_2}{a_1} + \frac{a_2}{a_3} +...+\frac{a_2}{a_n} + \frac{a_3}{a_1} + \frac{a_3}{a_2} + ... + \frac{a_3}{a_n} + ...+ \frac{a_n}{a_1} + \frac{a_n}{a_2} + \frac{a_n}{a_3}+...$

Rearranging leads to:

$\frac{a_1}{a_2} + \frac{a_2}{a_1} + \frac{a_1}{a_3} + \frac{a_3}{a_1} + \frac{a_2}{a_3} + \frac{a_3}{a_2} + \frac{a_1}{a_n} + \frac{a_n}{a_1} + \frac{a_2}{a_n} + \frac{a_n}{a_2} + \frac{a_3}{a_n} + \frac{a_n}{a_3}$

All of these terms are in the form of $\frac{a_i}{a_k} + \frac{a_k}{a_i}$ pairs where $k>i$

Now using AM-GM on one of these pair yields:

$\frac{\frac{a_i}{a_k} + \frac{a_k}{a_i}}{2} \ge \sqrt{\left(\frac{a_i}{a_k}\right)\left(\frac{a_k}{a_i}\right)}$

$\therefore \frac{a_i}{a_k} + \frac{a_k}{a_i} \ge 2$

So each pair has a minimum value of $2$ .

Thus the remaining $(n^2-n)$ terms has a minimum value of $2(n^2-n)$

Thus totally we have $(n)(1) + 2(n^2-n) = 2n^2-n$

However the proof is $n^2$ only... where did that extra $\mbox{n}$ and $2n^2$ come from?

humph · « **Reply #145 on:** November 24, 2009, 12:00:06 am »

Quote from: TrueTears on November 23, 2009, 11:51:53 pm

So each pair has a minimum value of $2$ .

Thus the remaining $(n^2-n)$ terms has a minimum value of $2(n^2-n)$

Maybe I'm missing something here, but if each pair has minimum value of $2$ , then "on average" each term is $1$ . Because there are $n^2-n$ terms, so $(n^2-n)/2$ pairs, each with minimum value $2$ , so we should have that the remaining $n^2-n$ terms has a minimum value of $2 \cdot (n^2-n)/2 = n^2 - n$ .

Quote from: TrueTears on November 23, 2009, 11:51:53 pm

Thus totally we have $(n)(1) + 2(n^2-n) = 2n^2-n$

So this should be $(n)(1) + (n^2-n) = n^2$ , as required.

TrueTears · « **Reply #146 on:** November 24, 2009, 12:02:50 am »

LOL opps how the hell did I miss that! Silly me =.=

Thanks humph.

TrueTears · « **Reply #147 on:** November 24, 2009, 06:49:36 pm »

Some inequality questions: (These will be revolving around AM-GM, Cauchy-Schwarz and Chebyshev's inequality)

~~1) $1+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!} + ... < 3$~~

~~2) For which integer $\mbox{n}$ is $\frac{1}{n}$ closest to $\sqrt{1000000} - \sqrt{999999}$ ?~~

3) Show that $\sqrt{a_1^2 + b_1^2} + \sqrt{a_2^2 + b_2^2} + ... + \sqrt{a_n^2 + b_n^2} \ge \sqrt{(a_1+a_2+...+a_n)^2 + (b_1+b_2+...+b_n)^2}$ for all real values of the variables. Furthermore, give a condition for equality to hold.

~~4) Prove that $0 \le yz+zx+xy-2xyz\le \frac{7}{27}$ where $x,y,z$ are non negative real numbers for which $x+y+z=1$~~

Many thanks guys!

For Q 1. Taylor series can be used.

Since $e = 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + ... + \frac{1}{n!}$

And since $e \approx 2.7$

That means the sum must be smaller than $3$ .

But are there any other ways of doing this?

kamil9876 · « **Reply #148 on:** November 24, 2009, 07:54:04 pm »

q1 is nice, rather than using the known value for e, you can work out an upper bound for it by pretending you have no clue what it is:

first of all notice that n!>2^n for all n>2. proof:

we're basically comparing:

1*2*3*4*5*6*7.....*n
2*2*2*2*2*2*2.....*2

ie notice that factor for factor, the top row has greater numbers.

actually, make that $n!>2^{n-1}$ as it is more useful (ie just ignore the first colunm)
therefore:

$\sum_{n=0}^{\infty} \frac{1}{n!}=1+\sum_{n=1}^{\infty}\frac{1}{n!}<1+\sum_{n=1}^{\infty}\frac{1}{2^{n-1}}=3$

i.e: it is a very useful strategy to compare things to the geometric sequence, or other known sequences or even things that look like right hand rectangle approximations to integrals.

TrueTears · « **Reply #149 on:** November 24, 2009, 10:03:38 pm »

So how did you think of $n! > 2^{n-1}$ ?

That's like a needle in a haystack for me

Finding a sum to infinity which yields 3...

Is that just experience or...?

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 133136 times) Tweet Share

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Over9000

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

humph

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Recent Posts

User:
Password: