Mathematical Induction where the base case starts above 1

[gottfried]

Homework Statement

Find all natural numbers such that 2ⁿ ≥ (1+n)², and prove your answer.

2. The attempt at a solution
I can see this is true for n=0 and n>5. I try to prove this using induction as follows
2⁰ =1≥ 1=(1+0)²
base case: 2⁶ =64≥ 49=(1+6)² so it is true for n=6
and suppose 2ⁿ ≥ (1+n)² for all n≥6 then
2ⁿ⁺² =2ⁿ2² ≥4(1+n)²=4n²+8n+4≥n²+6n+9=(n+3)²

I'm not sure if this correct because of the +2?
Would I have do to it again with a base case of 7 to ensure every number is accounted for?

 

[gottfried]

I've actually just realized this can be done with n+1 and I'm just being silly. Sorry

 

[HallsofIvy]

Yes, IF your "induction" step goes from n to n+2 you can prove the statement is true for all x greater than or equal to a by proving base cases n= a and n= a+1.

But why are you using "n+2"? If 2^n\ge (1+ n)^2 for all n\ge 6 then
2^{n+1}= 2(2^n)\ge 2(1+ n)^2= 2(1+ 2n+ n^2)= 2+ 4n+ 2n^2= (4+ 4n+ n^2)+ (n^2- 2)
\ge ((n+1)+1)^2+ n^2- 2
and since n\ge 6, n^2- 2\ge 34 which is larger than 1.

 

[gottfried]

Clearly using n+2 was a mistake but I originally used it to see if this would result in an easier inequality for me to manipulate. I see your proof and it makes sense. I didnt see it originally but my original proof works for n+1 aswell.

2ⁿ⁺¹ =2ⁿ2 ≥2(1+n)²=2n²+4n+2≥n²+4n+4=(n+2)²

But suppose I could not show this was true for n+1 does the logic for induction work if we use n+2. ie would the original proof using n+2 be sufficient although not elegant?

 

[HallsofIvy]

Yes, I answered that before:

Yes, IF your "induction" step goes from n to n+2 you can prove the statement is true for all x greater than or equal to a by proving base cases n= a and n= a+1.

 

[gottfried]

Sorry I missed that but thanks for the clarification.

 

[Office_Shredder]

and suppose 2ⁿ ≥ (1+n)² for all n≥6

A bit nitpicky, but if you're going to assume this then there's nothing left to prove