Is my short induction proof correct?

  • #1
837
50

Homework Statement


"Prove: ##∀n∈ℕ##, ##3^n>n^2##

Homework Equations




The Attempt at a Solution


(1) We will prove that ##3^n>n^2## at ##n=1##
##3=3^1>1=1^2##

(2) Now assume that ##3^k>k^2## for some ##k>1##
(3) We will prove that ##3^{k+1}>(k+1)^2## or ##3⋅3^k>k^2+2k+1##
Note that ##k^2+2k^2+1=3k^2+1≥k^2+2k+1##, and as such, ##3⋅3^k≥3k^2+3>3k^2+1≥k^2+2k+1##. So ##3^{k+1}>3k^2+1≥(k+1)^2##.

I'm basically ambivalent as to whether to insert that extra term in the inequality: ##3k^2+1##, not knowing whether it is equal to, less than, or greater than ##3^{k+1}##. Can someone check my work, please? Thanks.
 
Last edited:

Answers and Replies

  • #2
34,305
5,946

Homework Statement


"Prove: ##∀n∈ℕ##, ##3^n>n^2##

Homework Equations




The Attempt at a Solution


(1) We will prove that ##3^n>n^2## at ##n=1##
##3=3^1>1=1^2##

(2) Now assume that ##3^k>k^2## for some ##k>1##
(3) We will prove that ##3^{k+1}>(k+1)^2## or ##3⋅3^k>k^2+2k+1##
Note that ##k^2+2k^2+1=3k^2+1≥k^2+2k+1##, and as such, ##3⋅3^k≥3k^2+3>3k^2+1≥k^2+2k+1##. So ##3^{k+1}>3k^2+1≥(k+1)^2##.

I'm basically ambivalent as to whether to insert that extra term in the inequality: ##3k^2+1##, not knowing whether it is equal to, less than, or greater than ##3^{k+1}##. Can someone check my work, please? Thanks.
The induction step boils down to showing that ##3k^2 > (k + 1)^2##. It's easy enough to prove the equivalent statement ##3k^2 - (k + 1)^2 > 0##.
 
  • #3
837
50
Let's see...

##3k^2-k^2-2k-1=2k^2-2k-1=2k(k-1)-1>0## for ##k>0##?
 
  • #4
34,305
5,946
Let's see...

##3k^2-k^2-2k-1=2k^2-2k-1=2k(k-1)-1>0## for ##k>0##?
Almost. 2k(k - 1) - 1 > 0 for k > 1.
If k = 0, you have 0(-1) - 1 < 0, and if k = 1, you have 2(0) - 1 < 0.
 

Related Threads on Is my short induction proof correct?

  • Last Post
Replies
3
Views
932
  • Last Post
Replies
1
Views
925
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
1
Views
967
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
1
Views
850
  • Last Post
Replies
4
Views
2K
Replies
3
Views
750
  • Last Post
Replies
0
Views
1K
Top