Beginner Logic & Mathematical Induction Question

Printable View

September 16th 2011, 09:41 PM
demelode

Beginner Logic & Mathematical Induction Question

Hello, first time poster here. I've recently entered a Discrete course at my university and the professor does not exactly line up with my style of learning. I like to believe that I learn by example, and he's more of a "here's the rules, and now I let you go".

So I was wondering if you could assist me with this one question, and from there I'd be good. Here it is:

Prove that for any real number $r$ , if $0 < r < 1$ , then for all positive integers $n$ and $m$ , if $n < m$ , then $r^n$ > $r^m$ . Use mathematical induction.

First off, I understand the general concept that since r is a positive real number less then 1, that the larger it's exponent, the smaller the calculated number will be. I also vaguely understand the idea of a predicate, which I believe is required for the concept of mathematical induction, being that first I must prove the base case, then a general case, then the step after any general case. What confuses me however, is just the general application of all this, specifically since I think this question involves a predicate with multiple variables, something I have not dealt with yet.

If anyone were to be able to walk me through this question, I would be very grateful! Thank you.
September 16th 2011, 10:43 PM
Prove It

Re: Beginner Logic & Mathematical Induction Question

Quote:

Originally Posted by demelode

Hello, first time poster here. I've recently entered a Discrete course at my university and the professor does not exactly line up with my style of learning. I like to believe that I learn by example, and he's more of a "here's the rules, and now I let you go".

So I was wondering if you could assist me with this one question, and from there I'd be good. Here it is:

Prove that for any real number $r$ , if $0 < r < 1$ , then for all positive integers $n$ and $m$ , if $n < m$ , then $r^n$ > $r^m$ . Use mathematical induction.

First off, I understand the general concept that since r is a positive real number less then 1, that the larger it's exponent, the smaller the calculated number will be. I also vaguely understand the idea of a predicate, which I believe is required for the concept of mathematical induction, being that first I must prove the base case, then a general case, then the step after any general case. What confuses me however, is just the general application of all this, specifically since I think this question involves a predicate with multiple variables, something I have not dealt with yet.

If anyone were to be able to walk me through this question, I would be very grateful! Thank you.

Induction is not needed here...

If $\displaystyle 0 < r < 1$ , then you can write $\displaystyle r = \frac{1}{s}$ , where $\displaystyle s > 1$ .

So $\displaystyle r^n = \left(\frac{1}{s}\right)^n = \frac{1}{s^n}$ and $\displaystyle r^m = \frac{1}{s^m}$ .

We should also note that since $\displaystyle s > 1$ , $\displaystyle s^m$ and $\displaystyle s^n$ are positive.

Now if $\displaystyle n < m$ , then

$\displaystyle \begin{align*} s^n &< s^m \\ 1 &< \frac{s^m}{s^n} \\ \frac{1}{s^m} &< \frac{1}{s^n} \\ r^m &< r^n \end{align*}$

Q.E.D.
September 16th 2011, 11:25 PM
CaptainBlack

Re: Beginner Logic & Mathematical Induction Question

Quote:

Originally Posted by demelode

Hello, first time poster here. I've recently entered a Discrete course at my university and the professor does not exactly line up with my style of learning. I like to believe that I learn by example, and he's more of a "here's the rules, and now I let you go".

So I was wondering if you could assist me with this one question, and from there I'd be good. Here it is:

Prove that for any real number $r$ , if $0 < r < 1$ , then for all positive integers $n$ and $m$ , if $n < m$ , then $r^n$ > $r^m$ . Use mathematical induction.

First off, I understand the general concept that since r is a positive real number less then 1, that the larger it's exponent, the smaller the calculated number will be. I also vaguely understand the idea of a predicate, which I believe is required for the concept of mathematical induction, being that first I must prove the base case, then a general case, then the step after any general case. What confuses me however, is just the general application of all this, specifically since I think this question involves a predicate with multiple variables, something I have not dealt with yet.

If anyone were to be able to walk me through this question, I would be very grateful! Thank you.

First we observe that it is sufficient to prove that if $0<r<1$ then for any positive integer $k$ that $1>r^k$ .

You start with the base case k=1, where 1>r^k by the condition that 0<r<1.

Now assume that for some $k\ge 1$ that $r^k<1$ , we now need to prove that this implies $1>r^{k+1}$ .

Then by the induction hypothesis and as $r>0$ we have:

$r^{k+1}=r r^k<r<1$

as required. Hence we may conclude by mathematical induction that when $0<r<1$ that $r^k<1$ for any positive integer $k$ .

CB
September 17th 2011, 12:38 AM
demelode

Re: Beginner Logic & Mathematical Induction Question

Quote:

Originally Posted by Prove It

Induction is not needed here...

If $\displaystyle 0 < r < 1$ , then you can write $\displaystyle r = \frac{1}{s}$ , where $\displaystyle s > 1$ .

So $\displaystyle r^n = \left(\frac{1}{s}\right)^n = \frac{1}{s^n}$ and $\displaystyle r^m = \frac{1}{s^m}$ .

We should also note that since $\displaystyle s > 1$ , $\displaystyle s^m$ and $\displaystyle s^n$ are positive.

Now if $\displaystyle n < m$ , then

$\displaystyle \begin{align*} s^n &< s^m \\ 1 &< \frac{s^m}{s^n} \\ \frac{1}{s^m} &< \frac{1}{s^n} \\ r^m &< r^n \end{align*}$

Q.E.D.

I appreciate the effort you have provided me, but in this particular case, the goal is to do the question only through induction, even if there is different and/or better ways of solving it.

Quote:

Originally Posted by CaptainBlack

First we observe that it is sufficient to prove that if $0<r<1$ then for any positive integer $k$ that $1>r^k$ .

You start with the base case k=1, where 1>r^k by the condition that 0<r<1.

Now assume that for some $k\ge 1$ that $r^k<1$ , we now need to prove that this implies $1>r^{k+1}$ .

Then by the induction hypothesis and as $r>0$ we have:

$r^{k+1}=r r^k<r<1$

as required. Hence we may conclude by mathematical induction that when $0<r<1$ that $r^k<1$ for any positive integer $k$ .

CB

I see what you've done here. I however don't believe it answers the full scope of the question. I don't think it is enough to prove that, in this case, $r^n$ and $r^m$ must be $< 1$ , but also the question hits on the issue of their relationship, ie. if $n < m$ then $r^n$ > $r^m$ . Unless I missed something in your reply, I don't see that answered.

Do the two if's found within my original statement suggest that this question is a two parter, where you have just completed the first. ie. prove both $r^n$ and $r^m$ are $< 1$ , then prove their relationship?

If there was a misunderstanding, it's definitely my fault, so here's the exact question I was given (I summarized earlier):

The exercise is to prove that for any real number, if $0 < r < 1$ , then for all positive integers $n$ and $m$ , if $n < m$ , then $r^n$ > $r^m$ . I want you to use mathematical induction in your solution (so for this problem, tehcniques from Calculus will not be allowed), so your first step is to find out what predicate to use.
September 17th 2011, 05:02 AM
HallsofIvy

Re: Beginner Logic & Mathematical Induction Question

What Captain Black is using is that, for positive r, $r^n> r^m$ if and only if $1> r^{m-n}$ . Since m> n, m-n is a positive integer.

Once you have proved, as Captain Black suggests,that $1> r^k$ for any positive integer k, your result follows.
September 17th 2011, 05:13 AM
demelode

Re: Beginner Logic & Mathematical Induction Question

Ah! I now understand. Thank you all for helping me!