Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Induction problems
Posted:
Oct 31, 2004 12:33 PM
|
|
José Carlos Santos <jcsantos@fc.up.pt> wrote in message news:<2ui9uhF2bprk6U1@uni-berlin.de>...
> Neil L. wrote:
>
> > Here's the whole problem. Prove that 3^n > 20n, for each integer n >= 4.
> >
> > so, n=4, 3^4 = 81 and 20n = 80, so 3^n > 20n
> >
> > Now, assume induction hypothesis 3^k > 20k, for each integer k >= 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.
> > We
> > must prove 3^(k+1) > 20(k+1) We have:
> >
> > 3^(k+1) = 3(3^k)
> > 3^(k+1) > 3(20k) (by the induction hypothesis)
> > 3^(k+1) > 20k + 40k
> > 3^(k+1) > 20k + 20 (since k >= 4 > 1/2)
> > 3^(k+1) > 20(k+1)
> >
> > The 2nd last step is where my issue comes in. I DONT GET IT!!!
>
> The second step? The one that says that "3^(k+1) > 3(20k)"? Well,
> since 3^k > 20k (by the induction hypothesis), then 3*3^k > 3*(20k).
>
> Best regards,
>
> Jose Carlos Santos
How about this proof:
(Proof by contradiction)
Show for P(4), k = 4: 81 > 80, true.
Assume the inductive hypothesis P(k): 3^k > 20k for some k >= 4.
Now, show that P(k+1) is true.
Assume it is actually false. That is, assume that
3^(k+1) <= 20(k+1) (k >= 4). (1)
Now, since
3^(k+1) / 20(k+1) <= 1 (k >= 4), (2)
Then
3^k > 20k [3^(k+1) / 20(k+1)] (k >= 4) (3)
from which we get on simplification
(k+1) / k > 3 (k >= 4), (4)
which is false, showing that the assumption made in (1) is false.
Therefore,
3^(k+1) > 20(k+1) (k >= 4). (5)
We have shown that P(k) implies P(k+1) for some arbitrarily chosen
particular integer k >= 4.
Patrick
|
|
|
|
