Proof by induction question

  • Thread starter It_Angel
  • Start date
  • #1
6
0

Homework Statement


Prove that 3^n >= 2n+1 for all natural numbers.


Homework Equations


3^n >= 2n+1 [is bigger or equal to]


The Attempt at a Solution



3*1>=2+1
True for n=1

Assumption: 3^k>=2k+1

3^(k+1)>=2k+3
3^k*3>=2k+3
(2k+1)*3>=2k+3 <---can I just substitute 2k+1 into 3^k as per my assumption, because 3^k is bigger, and (2k+1)*3 is bigger than 2k+3? If so, is the proof complete?

Thanks in advance.
 

Answers and Replies

  • #2
34,904
6,647

Homework Statement


Prove that 3^n >= 2n+1 for all natural numbers.


Homework Equations


3^n >= 2n+1 [is bigger or equal to]


The Attempt at a Solution



3*1>=2+1
True for n=1

Assumption: 3^k>=2k+1

3^(k+1)>=2k+3
No, you can't just assert this -- you have to show it.

Use the fact that 3^(k + 1) = 3 * 3k, and use your assumption that 3^i >= 2k + 1.
3^k*3>=2k+3
(2k+1)*3>=2k+3 <---can I just substitute 2k+1 into 3^k as per my assumption, because 3^k is bigger, and (2k+1)*3 is bigger than 2k+3? If so, is the proof complete?

Thanks in advance.
 
  • #3
6
0
Sorry, still at a loss.
 
  • #4
34,904
6,647
I already provided a strategy for you.
Use the fact that 3^(k + 1) = 3 * 3k, and use your assumption that 3^i >= 2k + 1.

Did you not understand?
 

Related Threads on Proof by induction question

  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
24
Views
2K
  • Last Post
Replies
3
Views
596
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
7
Views
721
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
12
Views
728
  • Last Post
Replies
5
Views
771
Top