# Mathematical Induction where the base case starts above 1

1. Aug 19, 2013

### gottfried

1. The problem statement, all variables and given/known data
Find all natural numbers such that 2n ≥ (1+n)2, 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
20 =1≥ 1=(1+0)2
base case: 26 =64≥ 49=(1+6)2 so it is true for n=6
and suppose 2n ≥ (1+n)2 for all n≥6 then
2n+2 =2n22 ≥4(1+n)2=4n2+8n+4≥n2+6n+9=(n+3)2

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?

Last edited: Aug 19, 2013
2. Aug 19, 2013

### gottfried

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

3. Aug 19, 2013

### HallsofIvy

Staff Emeritus
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.

4. Aug 19, 2013

### 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.

2n+1 =2n2 ≥2(1+n)2=2n2+4n+2≥n2+4n+4=(n+2)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?

5. Aug 19, 2013

### HallsofIvy

Staff Emeritus

6. Aug 19, 2013

### gottfried

Sorry I missed that but thanks for the clarification.

7. Aug 19, 2013

### Office_Shredder

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