Solved

verifying the inequality using induction

Posted on 2006-06-11
5
320 Views
Last Modified: 2012-06-27
I have a question about verifying the inequality using induction.

2N + 1<or =  2^N,       N = 3, 4,....      

So far, I have the basis
2(3) + 1 < or = 2^3
6 + 1 < or = 8                                    
7 < or = 8

Trying to do the induction step and it is not making much sense. I am assuming that since I am using 3 in the basis, I am using n+3 in the inductive? The problem I think I am having the most trouble with is the power of.
This is what I have, although I am sure it is completely incorrect.

2(n+3) + 1 < or = 2^n+3
2n + 6 + 1 < or = 2^n+3
2n + 7 < or = 2^n+3

0
Comment
Question by:rcanter
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
5 Comments
 
LVL 37

Accepted Solution

by:
Harisha M G earned 500 total points
ID: 16881566
Hi, you have proved it for N=3. Now, put N=N+1, and prove that

2(N+1) + 1 <=  2^(N+1)

Now, you have

2N + 1 <=  2^N

Multiply both sides by 2

4N + 2 <= 2^(N+1)

2(N+1) + 2N <= 2^(N+1)

Since N is positive, 2N is also positive. Also, N >= 3. Hence, 2N >= 6 and obviously 2N >= 1, so we can write,

2(N+1) + 1 <= 2(N+1) + 2N <= 2^(N+1)

Removing the intermediate term,

2(N+1) + 1 <= 2^(N+1)

Hence the proof


---
Harish
0
 

Author Comment

by:rcanter
ID: 16881572
U are awesome!!! Thanks so much!!!
One quick question, just so that I understand.  Even that I used S(3) for the basis, I am using S(n+1) for the inductive?
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 16881587
rcanter, yes. You used S(3) because it is given in the problem itself that N = 3,4...

As I told in the previous question, you need to prove it that the (in)equality holds for atleast one value, which in case if it is not given, will be taken generally as 1
0
 

Author Comment

by:rcanter
ID: 16881614
I am not understanding how this could be proven.
2N + 1 <=  2^N

Multiply both sides by 2     ***why am i multiplying by 2?***

4N + 2 <= 2^(N+1)

2(N+1) + 2N <= 2^(N+1)     **why wouldnt this be 2(n+1) + 1? how did 2n figure in?**

Since N is positive, 2N is also positive. Also, N >= 3. Hence, 2N >= 6 and obviously 2N >= 1, so we can write,

2(N+1) + 1 <= 2(N+1) + 2N <= 2^(N+1)

Removing the intermediate term,

2(N+1) + 1 <= 2^(N+1)

Hence the proof
0
 
LVL 37

Expert Comment

by:Harisha M G
ID: 16881703
you need to get N+1 in either side and then prove the other side
0

Featured Post

[Webinar] How Hackers Steal Your Credentials

Do You Know How Hackers Steal Your Credentials? Join us and Skyport Systems to learn how hackers steal your credentials and why Active Directory must be secure to stop them. Thursday, July 13, 2017 10:00 A.M. PDT

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

729 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question