Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Induction problems
Replies: 6   Last Post: Oct 31, 2004 12:33 PM

 Messages: [ Previous | Next ]
 Patrick Reany Posts: 224 Registered: 12/12/04
Re: Induction problems
Posted: Oct 31, 2004 12:33 PM

JosÃ© Carlos Santos &lt;jcsantos@fc.up.pt&gt; wrote in message news:&lt;2ui9uhF2bprk6U1@uni-berlin.de&gt;...
&gt; Neil L. wrote:
&gt;
&gt; &gt; Here's the whole problem. Prove that 3^n &gt; 20n, for each integer n &gt;= 4.
&gt; &gt;
&gt; &gt; so, n=4, 3^4 = 81 and 20n = 80, so 3^n &gt; 20n
&gt; &gt;
&gt; &gt; Now, assume induction hypothesis 3^k &gt; 20k, for each integer k &gt;= 4.

Not for each integer, but for some arbitrarily chosen particular
integer k. If you assume it for each integer, you've already assumed
what you're trying to prove.

&gt; &gt; We
&gt; &gt; must prove 3^(k+1) &gt; 20(k+1) We have:
&gt; &gt;
&gt; &gt; 3^(k+1) = 3(3^k)
&gt; &gt; 3^(k+1) &gt; 3(20k) (by the induction hypothesis)
&gt; &gt; 3^(k+1) &gt; 20k + 40k
&gt; &gt; 3^(k+1) &gt; 20k + 20 (since k &gt;= 4 &gt; 1/2)
&gt; &gt; 3^(k+1) &gt; 20(k+1)
&gt; &gt;
&gt; &gt; The 2nd last step is where my issue comes in. I DONT GET IT!!!
&gt;
&gt; The second step? The one that says that "3^(k+1) &gt; 3(20k)"? Well,
&gt; since 3^k &gt; 20k (by the induction hypothesis), then 3*3^k &gt; 3*(20k).
&gt;
&gt; Best regards,
&gt;
&gt; Jose Carlos Santos

Show for P(4), k = 4: 81 &gt; 80, true.

Assume the inductive hypothesis P(k): 3^k &gt; 20k for some k &gt;= 4.

Now, show that P(k+1) is true.

Assume it is actually false. That is, assume that

3^(k+1) &lt;= 20(k+1) (k &gt;= 4). (1)

Now, since

3^(k+1) / 20(k+1) &lt;= 1 (k &gt;= 4), (2)

Then

3^k &gt; 20k [3^(k+1) / 20(k+1)] (k &gt;= 4) (3)

from which we get on simplification

(k+1) / k &gt; 3 (k &gt;= 4), (4)

which is false, showing that the assumption made in (1) is false.
Therefore,

3^(k+1) &gt; 20(k+1) (k &gt;= 4). (5)

We have shown that P(k) implies P(k+1) for some arbitrarily chosen
particular integer k &gt;= 4.

Patrick

Date Subject Author
10/30/04 Neil L.
10/30/04 Jose Carlos Santos
10/30/04 Dave Seaman
10/31/04 Jose Carlos Santos
10/31/04 Patrick Reany
10/30/04 Steven
10/31/04 Bill Dubuque