Elementary Theory of Numbers
conrad
by LeVeque.
One of the problems is as follows:
Show that if n is a positive integer and
x is a real number larger than -1,
then (1 + x)^n > 1 + xn
My question is this: the proofs by induction
rely on the peano postulates or the
well-ordering axiom which can be derived
from the peano postulates(from my understanding).
The peano postulates relate to the set of natural
numbers. Therefore, how should x, being a real
number, be handled in such an inductive proof?
--
conrad
Joshua Cranmer
> Show that if n is a positive integer and
> x is a real number larger than -1,
> then (1 + x)^n > 1 + xn
>
> My question is this: the proofs by induction
> rely on the peano postulates or the
> well-ordering axiom which can be derived
> from the peano postulates(from my understanding).
>
> The peano postulates relate to the set of natural
> numbers. Therefore, how should x, being a real
> number, be handled in such an inductive proof?
Induct on n, not x.
You're trying to show
For all real x > -1 and integer n > 0, p(x, n) <=>
For all integer n > 0, (For all real x > -1, p(x, n)) <=>
For all integer n > 0, q(n) (^ where q(n) is this ^)
If you can show q(1) and q(n) inductively, then you can show your
original statement.
Arturo Magidin
The inductive proof relates to the exponents n for which a particular
proposition holds. That is, you have a subset of N,
S = { n in N : P(n) holds}
and you are trying to show that S = N.
The fact that P(n) is a condition that is defined in terms of real
numbers is really no obstacle to applying induction. In point of fact,
it can all be expressed ultimately in terms of the natural numbers
(within ZF, at least), since we can define real numbers and their
properties in terms of, for example, Dedekind Cuts. These in turn rely
on the notion of rational numbers, which can be defined entirely in
terms of integers. And the integers can be defined entirely in terms
of the natural numbers. So the statement (1+x)^n > 1+nx could be
expressed entirely in terms of natural numbers (though it would be
rather large and complicated statement).
In the end, however, that is really immaterial. You have a certain
property P(n), which will or will not hold for each integer n. This
defines a subset of N, to which you can apply induction. Neither
Peano's Fifth postulate (which merely states that S will be equal to
all of N if 0 is in S and if for every n, n in S implies n+1 in S),
nor the Axiom of Separation in ZF (which you might need to invoke to
justify claiming that S is a subset of N) put any conditions on P(n).
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
quasi
wrote:
Regard x as fixed, and do induction on n.
quasi
William Elliot
> Show that if n is a positive integer and
> x is a real number larger than -1,
> then (1 + x)^n > 1 + xn
>
That is false for n = 1.
(1 + xn)(1 + x) = 1 + x(n + 1) + x^2
quasi
<ma...@hevanet.remove.com> wrote:
>On Sat, 4 Oct 2008, conrad wrote:
>
>> Show that if n is a positive integer and
>> x is a real number larger than -1,
>> then (1 + x)^n > 1 + xn
>>
>That is false for n = 1.
For n = 1, the inequality is an equality.
The strict inequality holds for n > 1.
quasi
G. A. Edgar
<qu...@null.set> wrote:
Did you check x=0 on that?
>
> quasi
--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/
toni...@walla.com
**************************************************************
By the way, this rather known inequality is also known as Bernoulli's
inequality.
Regards
Tonio
quasi
<ed...@math.ohio-state.edu.invalid> wrote:
>In article <9d5he4pl67a3gl5kn...@4ax.com>, quasi
><qu...@null.set> wrote:
>
>> On Sun, 5 Oct 2008 00:07:55 -0700, William Elliot
>> <ma...@hevanet.remove.com> wrote:
>>
>> >On Sat, 4 Oct 2008, conrad wrote:
>> >
>> >> Show that if n is a positive integer and
>> >> x is a real number larger than -1,
>> >> then (1 + x)^n > 1 + xn
>> >>
>> >That is false for n = 1.
>>
>> For n = 1, the inequality is an equality.
>>
>> The strict inequality holds for n > 1.
>
>Did you check x=0 on that?
I guess I was a little too strict.
quasi
William Elliot
> <ed...@math.ohio-state.edu.invalid> wrote:
> ><qu...@null.set> wrote:
> >> <ma...@hevanet.remove.com> wrote:
> >> >On Sat, 4 Oct 2008, conrad wrote:
> >> >
> >> >> Show that if n is a positive integer and
> >> >> x is a real number larger than -1,
> >> >> then (1 + x)^n > 1 + xn
> >> >>
> >> >That is false for n = 1.
> >>
> >> For n = 1, the inequality is an equality.
> >> The strict inequality holds for n > 1.
> >
> >Did you check x=0 on that?
> I guess I was a little too strict.
>
se...@btinternet.com
> (1 + xn)(1 + x) = 1 + x(n + 1) + x^2
A typo? Try:
(1 + xn)(1 + x) = 1 + x(n + 1) + x + x^2.n
conrad
which is in the subject line. My current knowledge
of math extends to first semester calculus.
I'm reading through LeVeque's book in my spare
time. Therefore, I don't really have a means
to check my understanding of number theory
except through mediums such as this.
I am working through the first chapter
and covering proofs by induction.
The next section of chapter 1 is on
indirect proofs. I mention all this so that
the reader doesn't have to make
assumptions about my mathematical
knowledge and can therefore respond
in the most helpful way.
I have the following problem:
Show that every integer greater than 1
can be represented as a product of one
or more primes.
Now, I'm trying to think about this
problem in terms of the peano postulates
(specifically the fifth postulate and
the well-ordering axiom). My problem
seems to be on how I should represent
a general number with some number of
prime numbers.
Prime number: any number divisible only
by itself and 1.
Let P(n) be the sentence n = p_k * ... * p_0
Where n is the integer and p_k * ... * p_0
represents the prime factors.
P(2) is 2 = 2
P(3) is 3 = 3
P(4) is 4 = 2 * 2
My problem is formulating it in general
for n and showing that the truth of
P(n) implies the truth of P(n + 1)
Is my approach wrong? How should I
formulate the problem such that
it almost answers itself(I hope that
made sense)?
--
conrad
conrad
I didn't see this post from google
groups and reposted with a different
problem because I had solved
the initial problem I posted
about. But now my original
post has appeared and my new post
is a subthread of that. Strange.
--
conrad
William Elliot
<blah, blah la de da snipped>
> Prime number: any number divisible only by itself and 1.
>
> Let P(n) be the sentence n = p_k * ... * p_0
> Where n is the integer and p_k * ... * p_0
> represents the prime factors.
>
> P(2) is 2 = 2
> P(3) is 3 = 3
> P(4) is 4 = 2 * 2
>
> My problem is formulating it in general
> for n and showing that the truth of
> P(n) implies the truth of P(n + 1)
>
> Is my approach wrong?
Yes.
> How should I formulate the problem such that
> it almost answers itself?
LOL
Rob Johnson
Neither:
(1 + nx) (1 + x) = 1 + (n + 1) x + n x^2
>= 1 + (n + 1) x
Note that the inequality [ (1 + x)^n >= 1 + n x ] is true for n = 0
as well.
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
Tim Smith
<89553e78-c957-4acb...@79g2000hsk.googlegroups.com>,
I'm going to give you a general hint. This is a hint that I suspect
will cause most of the mathematicians reading this to furrow their brows
and cast severe virtual frowns of disapproval in my general direction.
Note also that I don't think I have LeVeque's book (damn...I really need
to get my library sorted...it never recovered from moving 16 months
ago...I genuinely have no idea whether or not I have that book!). From
what you write, though, it sounds like he follows a pattern that many
other "elementary" books follow.
That pattern is to have a first chapter that covers fundamentals, that
starts at a very low level, with axioms for the integers, some set
theory, and so on.
This first chapter is often the most difficult chapter in the book, as
it requires ignoring most of what you've learned in your prior study of
mathematics. You might think you've proved something, and then realize
you've assumed that 3 > 2 or something like that, which has not yet been
proved with the tools you have available at that point in the book. 3 >
2 might turn out to be a deep theorem at that point.
The funny thing is, most of the time when books follow this pattern
(well, other than books whose subject is foundations of mathematics or
similar things!), it turns out that you can just *skip* the first
chapter. Go right to chapter 2, or whichever chapter starts covering
what you actually think of when you think of the stated subject of the
book. There's usually nothing proved in that first, low level, chapter
that you didn't already know from prior mathematical study. You should
at some point acquire a firm grounding in the construction of the
integers, the rationals, and so on--but when you decide you want to
study that, not because some book on another subject decided to start
from the very beginning for completeness.
I'm *not* saying there is not value to be found in the first chapter.
There is great value there. It's just that you generally don't need it
for the particular subject of the book--the understanding of the
integers and rational numbers that you got from your prior calculus
course, and from any algebra you've done, is probably good enough.
Note that this is a general observation about many math books. I don't
know if it applies to the book you are reading. I'm guessing it might,
based on your mention of Peano postulates.
--
--Tim Smith
Bill Dubuque
>
> I have the following problem: Show that every integer > 1
> can be represented as a product of one or more primes.
Lookup "strong induction". Then, if n > 1 is not prime,
it splits into proper factors n = mk. By strong induction
the smaller m, k have prime factorizations. Append them.
--Bill Dubuque
Arturo Magidin
Yes; or rather, limited. Your P(n) is much too weak.
Try instead:
P(n): every positive k, 2<=k<=n, can be written as a product of
primes.
That is: your induction hypothesis is not just "n can be written as a
product of primes", but "every number up to n can be written as a
product of primes". (This is sometimes called "complete" or "strong"
induction; it is equivalent to the usual induction in the context of
Peano's Axioms).