Spivak Problem 6(i): x<y => x^n < y^n

[Saladsamurai]

Homework Statement

Prove that if 0≤x<y then xⁿ < yⁿ

Homework Equations

12 properties of numbers.

The Attempt at a Solution

For the case: 0 =x < y is trivial.

So now we just need y > x > 0 :

Now, I am having a bit of trouble with this. Take the case where n=2:

x < y

so x*x < x*y AND x*y < y*y and so by transitivity x*x < y*y.

But when I upgrade to being arbitrary:

x < y

x*x^a < y*x^a AND x*y^a < y*y^a

but I cannot make the connection by transitivity.

Is there a completely different approach for this that I am overlooking?

 

[micromass]

Can your prove it with n=3??

I think you'll need to use transitivity several times.

 

[Deveno]

Homework Statement

Prove that if 0≤x<y then xⁿ < yⁿ

Homework Equations

12 properties of numbers.

The Attempt at a Solution

For the case: 0 =x < y is trivial.

So now we just need y > x > 0 :

Now, I am having a bit of trouble with this. Take the case where n=2:

x < y

so x*x < x*y AND x*y < y*y and so by transitivity x*x < y*y.

But when I upgrade to being arbitrary:

x < y

x*x^a < y*x^a AND x*y^a < y*y^a

but I cannot make the connection by transitivity.

Is there a completely different approach for this that I am overlooking?

if n is a (positive) natural number, i suggest using induction.

 

[Saladsamurai]

if n is a (positive) natural number, i suggest using induction.

He made no restrictions on n, but I am wondering if he meant to (I'll get to that later, for now I am just going with your assumption of n = 1,2,...). Because I want to preserve the flow of the text, I am not going to use induction [since a) I don't know it and b) it has not been introduced yet].

Can your prove it with n=3??

I think you'll need to use transitivity several times.

Incidentally ...no! Somehow my approach eliminated n=3 and went straight to n=4 which bothers me:

x < y => xy < y²

x < y => x² < xy

By transitivity:

x² < y²

(a) x² < y² => yx² < y³

(b) x² < y² => x³ < xy²

from (a)
x²y² < y⁴

from (b)
x⁴ < x²y²

By transitivity:

x⁴ < y⁴.

What happened to n=3 ?! Bring me a shrubbery! (Sorry )

 

[micromass]

What about this?

$x^3<x^2y$

now use that

$x^2<y^2$

(multiply both sides by y).

But you ARE going to need induction in this. I can see no other way.

 

[Saladsamurai]

What about this?

$x^3<x^2y$

now use that

$x^2<y^2$

(multiply both sides by y).

Doh! So I literally passed right over it!

But you ARE going to need induction in this. I can see no other way.

hmmm...this problem is from Chapter 1 and induction is definitely chapter 2. Maybe that is Spivak's point? That the tools from chapter 1 are insufficient to Prove everything about numbers?

 

[Deveno]

He made no restrictions on n, but I am wondering if he meant to (I'll get to that later, for now I am just going with your assumption of n = 1,2,...). Because I want to preserve the flow of the text, I am not going to use induction [since a) I don't know it and b) it has not been introduced yet].



Incidentally ...no! Somehow my approach eliminated n=3 and went straight to n=4 which bothers me:

x < y => xy < y²

x < y => x² < xy

By transitivity:

x² < y²

(a) x² < y² => yx² < y³

(b) x² < y² => x³ < xy²

from (a)
x²y² < y⁴

from (b)
x⁴ < x²y²

By transitivity:

x⁴ < y⁴.

What happened to n=3 ?! Bring me a shrubbery! (Sorry )

judging by the location of the problem in your text, n is almost certainly a positive integer, because the definition of xⁿ for more general "n" is not made until much later in the text.

for n = 3:

x³ = x(x²) < y(x²) (since x < y)

< y(y²) = y³ (from your earlier result).

EDIT: true, enough, induction is not mentioned until chapter 2, however: it is merely stated without proof, and might be something you are already expected to know (a "hand-waving" example of why it works is given. there is a good reason for this. the principle of induction is actually an axiomatic fact, unless you delve down to a deeper layer of mathematics, axiomatic set theory. even then, creating a set to which induction can be appled, requires proving the existence of an "inexhaustible set" (that is, a non-finite set) and there is no reason to logically assume such a thing exists, except for the fact that having one is pretty useful. so here, too, it is an axiomatic assumption. to sum up: induction isn't something to prove: it is something to prove things with. it's just "true" in and of itself, something that requires an act akin to "a leap of faith" to accept).

another point worth mentioning: the properties that Spivak says are missing, are quite subtle. properties P1-P12 are the defining axioms of what is known as: an ordered field. now, there are actually many, many ordered fields, some of which are bizzare, and you need not concern yourself with them at the moment. but ONE ordered field in particular, that you most likely have extensive experience with is Q, the field of all rational numbers. and the whole point of chapters 1-7 is to convince you that "something more" than just rational numbers are going to be needed, if we want to solve problems of obvious utility (having to do with: continual change).

 

[Saladsamurai]

judging by the location of the problem in your text, n is almost certainly a positive integer, because the definition of xⁿ for more general "n" is not made until much later in the text.

</snip>

Excellent point! Thank you!

Doh! So I literally passed right over it!
hmmm...this problem is from Chapter 1 and induction is definitely chapter 2. Maybe that is Spivak's point? That the tools from chapter 1 are insufficient to Prove everything about numbers?

I feel like there must be a way to do this since problem 6 (b) is basically this again! (except that x and y can be negative and n is always odd ...)

 

[Saladsamurai]

Hi Deveno I read your edit just now. What you are saying makes sense, but for some reason is not jiving with me just yet. Below I have posted problem 6 in its entirety. It really does not seem like Spivak's style to expect you use techniques or even concepts that have not been introduced yet (however poorly). In fact, it seems that his style is suggesting that you suspend most of what you know temporarily and start over from scratch. In the end, I am sure you and micromass will prove to be correct since you are the experienced ones ... it is just something that is now bothering me. Unless the idea is to somehow force you to 'use induction' without actually 'knowing' that you are using it. In other words, you have to 'come up with' induction. Does that make any sense though? Can one 'come up with' induction in some way? Is it simply a matter of making an attempt to 'exhaust' the proof by proving for all of the n=1,2,3,...N, where N is a number that you decide to be sufficient? Though that bothers me as well ... I don't think that it is as simple as that.

Here is the entire problem:

 

[Deveno]

Hi Deveno I read your edit just now. What you are saying makes sense, but for some reason is not jiving with me just yet. Below I have posted problem 6 in its entirety. It really does not seem like Spivak's style to expect you use techniques or even concepts that have not been introduced yet (however poorly). In fact, it seems that his style is suggesting that you suspend most of what you know temporarily and start over from scratch. In the end, I am sure you and micromass will prove to be correct since you are the experienced ones ... it is just something that is now bothering me. Unless the idea is to somehow force you to 'use induction' without actually 'knowing' that you are using it. In other words, you have to 'come up with' induction. Does that make any sense though? Can one 'come up with' induction in some way? Is it simply a matter of making an attempt to 'exhaust' the proof by proving for all of the n=1,2,3,...N, where N is a number that you decide to be sufficient? Though that bothers me as well ... I don't think that it is as simple as that.

Here is the entire problem:

i am familiar with the problem. since you feel it is inappropriate to use induction at the present time, you will have to use the following approach:

let n be given. so n is some fixed positive integer.
prove for k = 1,
prove for k = 2,
prove for k = 3,
prove for k = 4...

continuing in this way, we see that...(THIS is what professional mathematicians refer to as "hand-waving")...when k = n, we have the desired result.

indeed, Spivak himself writes (and i quote): "...a rigorous proof uses induction, covered in the next chapter)."

 

[Saladsamurai]

i am familiar with the problem. since you feel it is inappropriate to use induction at the present time, you will have to use the following approach:

let n be given. so n is some fixed positive integer.
prove for k = 1,
prove for k = 2,
prove for k = 3,
prove for k = 4...

continuing in this way, we see that...(THIS is what professional mathematicians refer to as "hand-waving")...when k = n, we have the desired result.

I see. This is what I was thinking. While I have your attention, let me ask you something and forgive me because I don't really know what I am talking about, but this is what is irking me about this approach (and maybe why it is hand-wavi-ness):

I know next to nothing about number theory (actually, let's just say nothing), but I think that I am correct in saying that there are some problems regarding the existence of really large prime numbers that are asked in number theory. I know that there have been computer programs running for very long periods computing bigger and bigger prime numbers. I believe that they are attempting to answer the question of existence of a 'largest' prime number. This seems like a Let k=1,2,3,4,5...and on and on type of problem. But that approach is apparently not 'good enough' since the question is still open.

Way off topic, so don't feel obliged to answer, it's probably way over my head anyway.

indeed, Spivak himself writes (and i quote): "...a rigorous proof uses induction, covered in the next chapter)."

Where do you see that? It is not in my text (4th edition). You have his phone number?

 

[Deveno]

I see. This is what I was thinking. While I have your attention, let me ask you something and forgive me because I don't really know what I am talking about, but this is what is irking me about this approach (and maybe why it is hand-wavi-ness):

I know next to nothing about number theory (actually, let's just say nothing), but I think that I am correct in saying that there are some problems regarding the existence of really large prime numbers that are asked in number theory. I know that there have been computer programs running for very long periods computing bigger and bigger prime numbers. I believe that they are attempting to answer the question of existence of a 'largest' prime number. This seems like a Let k=1,2,3,4,5...and on and on type of problem. But that approach is apparently not 'good enough' since the question is still open.

Way off topic, so don't feel obliged to answer, it's probably way over my head anyway.

there is no "largest" prime number. there is a beuatiful proof of this, which is due to Euclid (or at least he wrote it down):

suppose that there was some largest prime, the k-th prime (obviously, k is some very large positive integer).

to save on letters, let's call 2, p₁, 3 = p₂, 5 = p₃, et cetera, all the way up to p_k, our largest prime.

now consider the number N = 1 + (p₁)(p₂)...(p_k).

none of our primes p₁, p₂,...,p_k divide N.

so we have 2 possibilities:

a) N has a prime divisor larger than p_k, a contradiction, because p_k was assumed to be the LARGEST prime (N certainly doesn't have any prime divisors less than or equal to p_k).

b) N itself is prime, in which case, being larger than p_k, we also obtain a contradiction.

therefore, there is no largest prime (the set of prime numbers is infinite).

Where do you see that? It is not in my text (4th edition). You have his phone number?

ah, well, um, if i told you that, i would be breaking several forum rules at once (which prohbit outright giving answers to homework questions). or perhaps, just several infractions of the same rule simultaneously. besides, a mathematician never kisses and tells.

 

[Saladsamurai]

there is no "largest" prime number. there is a beuatiful proof of this, which is due to Euclid (or at least he wrote it down):

suppose that there was some largest prime, the k-th prime (obviously, k is some very large positive integer).

to save on letters, let's call 2, p₁, 3 = p₂, 5 = p₃, et cetera, all the way up to p_k, our largest prime.

now consider the number N = 1 + (p₁)(p₂)...(p_k).

none of our primes p₁, p₂,...,p_k divide N.

so we have 2 possibilities:

a) N has a prime divisor larger than p_k, a contradiction, because p_k was assumed to be the LARGEST prime (N certainly doesn't have any prime divisors less than or equal to p_k).

b) N itself is prime, in which case, being larger than p_k, we also obtain a contradiction.

therefore, there is no largest prime (the set of prime numbers is infinite).





ah, well, um, if i told you that, i would be breaking several forum rules at once (which prohbit outright giving answers to homework questions). or perhaps, just several infractions of the same rule simultaneously. besides, a mathematician never kisses and tells.

OMG! You are Spivak. Just Kidding...I see what you are saying! Thanks for all of your time and help!

 

[HallsofIvy]

You don't have to use induction. If the conclusion were not true, that is, if $x^n\le y^n$, then $y^n- x^n\ge 0$. But then $y^n- x^n= (y- x)(y^{n-1}+ xy^{n-2}+ \cdot\cdot\cdot+ x^{n-2}y+ x^{n-1})\ge 0$. The second term, a sum of products of non-negative numbers, is clearly non-negative so we must have $y- x\ge 0$, contradicting the hypothesis that $x\ge y$.