# Proof by induction

1. Feb 15, 2012

### Instinctlol

I am confused by what the book is saying, can someone explain how they got the thing I circled in red?

2. Feb 15, 2012

### jaqueh

your book explains it on the side, it is using the inductive hypothesis and a fact about integers to say that (2^k+1)+2 < 2^k+2^k=2(2^k)=2^(k+1)

3. Feb 15, 2012

### SammyS

Staff Emeritus
What don't you understand? The thing circled in red is explained just to the right of that.

You're assuming that $2k+1<2^k$ .

It's also true that: $\text{ for }\ k ≥ 2\,,\ \ 2 < 2^k$

Therefore, $2k+1+2<2^k+2<2^k+2^k\,.$

4. Feb 15, 2012

### Ray Vickson

Their comments in blue tell you exactly how they got it.

RGV

5. Feb 15, 2012

### Instinctlol

How did they decide 2 < 2k? Where did the 2 come from

6. Feb 15, 2012

### jaqueh

they expanded 2(k+1), which is the thing you're trying to prove the relationship about, into (2k+1)+2 on the LHS, and then on the RHS they're just trying to make relatable to 2k+1 so they used the relationship 2 < 2k to facilitate it.

7. Feb 15, 2012

### Instinctlol

Oh I think I see it now. So when they use 2 < 2k its kinda like stating 2 = 2k so (2k+1) + 2 < 2k + 2k