Solved

# verifying the inequality using induction

Posted on 2006-06-11
310 Views
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
Question by:rcanter
• 3
• 2

LVL 37

Accepted Solution

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

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

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

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

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

## Featured Post

Question has a verified solution.

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

### Suggested Solutions

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
Windows 10 is mostly good. However the one thing that annoys me is how many clicks you have to do to dial a VPN connection. You have to go to settings from the start menu, (2 clicks), Network and Internet (1 click), Click VPN (another click) then fi…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.