Proof by induction

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

j0h6ye.jpg

2a6jlnn.jpg
 

Answers and Replies

  • #2
57
0
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
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,384
1,043
I am confused by what the book is saying, can someone explain how they got the thing I circled in red?
What don't you understand? The thing circled in red is explained just to the right of that.

You're assuming that [itex]2k+1<2^k[/itex] .

It's also true that: [itex]\text{ for }\ k ≥ 2\,,\ \ 2 < 2^k[/itex]

Therefore, [itex]2k+1+2<2^k+2<2^k+2^k\,. [/itex]
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722
I am confused by what the book is saying, can someone explain how they got the thing I circled in red?

j0h6ye.jpg

2a6jlnn.jpg

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

RGV
 
  • #5
How did they decide 2 < 2k? Where did the 2 come from
 
  • #6
57
0
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
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
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
883
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
779
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
939
Top