Question

I'm doing some induction problems but i'm getting stuck when I have inequations and not equations.
For example:

3^n >= 2^(n+1) + 1 ,for n Natural \{1}

p(2) = 9 >= 9

Hypotheses: 3^n >= 2^(n+1) + 1

Thesis: (I don't get part of it so if you could explain the all process I would be glad)

3^(n+1) = 3^n * 3 >= 3( 2^(n+1) +1) =
2^(n+1) * 3 + 3 >= 2^(n+1)*3 + 1 = 2^(n+2) +1

Thanks

Answer 1

OK, I'm not sure exactly where you are stuck (is this an example that you're trying to follow?).... but... let's take it one step at a time. you have that:

\(\large 3^n >= 2^{n+1} + 1\)

And now, you want to prove that GIVEN THAT IT HOLDS FOR n, show that it holds for n+1. So in other words, need to prove that:

\(\large 3^{n+1} >= 2^{n+2} + 1\) and in that proof, you can USE that \(\large 3^n >= 2^{n+1} + 1\).

So now, starting at \(\large 3^{n+1} \), what can we say about it??

\(\large 3^{n+1} = 3^n * 3 \) why? Rules of exponents

\(\large 3^n * 3>= 3( 2^{n+1} +1)\) why? because \(\large 3^n >= 2^{n+1} + 1\) (assumption of the inductive proof)

\(\large 3( 2^{n+1} +1)= 2^{n+1} * 3 + 3 \) why? distribution

\(\large 2^{n+1} * 3 + 3>= 2^{n+1}*3 + 1 \) why? because 3>1

\(\large 2^{n+1}*3 + 1 = 2^{n+2} +1\) why? Rules of exponents

So: \(\large 3^{n+1} >= 2^{n+2} + 1\)

Answer 2

Thank you very much. Yes I was trying to follow the example and the part I was not getting was the: 2(n+1)∗3+3>=2(n+1)∗3+1 the rest I had understood.
So they just do it because it's true? I was hoping it had other explanation. Once again thank you very much

Answer 3

Well, there is a general property of natural numbers that:

if A>B then C+A>C+B

you should be able to use that.... you probably proved it, earlier in the book. lol :)

Answer 4

Yes i got it, and yes i had proved it before. but while I was doing the exercises I couldn't quite get it, and when I went and re-read the example I wasn't getting it. But now I do, thanks