Proof by Induction: Proving (2n > 4n2+1) for Natural Numbers

[vikkisut88]

Homework Statement

Prove that ($$\forall$$n in the set of Natural numbers )[(n $$\geq$$ 9) $$\Rightarrow$$ (2ⁿ > 4n² + 1)]

Homework Equations

To do proof by induction you must first prove for n = 1, then assume true for n and then show for n+1

The Attempt at a Solution

So for n=1 i have RHS:2⁹ = 512 and 4.9² + 1 = 325
So (2ⁿ > 4n² + 1)] for n=1

Now assume true for n

Show for n+1: (2ⁿ⁺¹ > 4(n+1)² + 1)]
So 2 ⁿ⁺¹can also be written as 2 ⁿ . 2¹
Thus 2 ⁿ⁺¹> 4(n+1) ² + 1)] = 2ⁿ . 2¹ > [4(n+1)² + 1].2
which is the same as 2ⁿ . 2¹ > 8(n+1)² + 2

And now I'm stuck as to how to arrange this to give me the right answer

 

[HallsofIvy]

Homework Statement

Prove that ($$\forall$$n in the set of Natural numbers )[(n $$\geq$$ 9) $$\Rightarrow$$ (2ⁿ > 4n² + 1)]

Homework Equations

To do proof by induction you must first prove for n = 1, then assume true for n and then show for n+1

The Attempt at a Solution

So for n=1 i have RHS:2⁹ = 512 and 4.9² + 1 = 325
So (2ⁿ > 4n² + 1)] for n=1

Now assume true for n

Show for n+1: (2ⁿ⁺¹ > 4(n+1)² + 1)]
So 2 ⁿ⁺¹can also be written as 2 ⁿ . 2¹
Thus 2 ⁿ⁺¹> 4(n+1) ² + 1)] = 2ⁿ . 2¹ > [4(n+1)² + 1].2

No. That "thus" is what you are trying to prove!
What you KNOW is that 2ⁿ⁺¹= 2ⁿ(2)> (4n²+ 1)(2)= 8n²+ 2
Now, can you prove that that is larger than 4(n+1)²+ 1= 4n²+ 8n+ 5? 8n²+ 2> 4n²+ 8n+ 5, if and only if 4n²- 8n- 4>> 0 which is the same as n²- 2n- 1> 0. For what values of n is that true?

which is the same as 2ⁿ . 2¹ > 8(n+1)² + 2

And now I'm stuck as to how to arrange this to give me the right answer

 

[vikkisut88]

No. That "thus" is what you are trying to prove!
What you KNOW is that 2ⁿ⁺¹= 2ⁿ(2)> (4n²+ 1)(2)= 8n²+ 2

Is that last bit right? Because I multiplied it out to be 8n² + 16n + 10?

 

[vikkisut88]

Hang on, no I think i see what you were doing now...I'll just have a go :)

 

[vikkisut88]

But still... are you just rearranging this because if so how does it change to >> and why is it -4 and not -3?

 

[vikkisut88]

Okay so disregarding my previous questions for the time being, In answer to your question about for which n values does it hold true, I did it like this:

n²- 2n- 1> 0.
(n-1)² - 2 > 0
(n-1)² > 2
(n-1) > 4
n > 5

So for values greater than 5?

 

[HallsofIvy]

Yes. And since your original problem specified "$n\ge 9", ...$

 

[vikkisut88]

But i don't understand how you rearranged an equation to get n² - 2n- 1 and then once I've found which values of n this equation holds true for, how does this show 2 ⁿ⁺¹ > 4(n+1)² + 1?

 

[HallsofIvy]

I wrote before:
What you KNOW is that 2ⁿ⁺¹= 2ⁿ(2)> (4n²+ 1)(2)= 8n²+ 2
Now, can you prove that that is larger than 4(n+1)²+ 1= 4n²+ 8n+ 5?
4(n+1)²+ 1= 4(n²+ 2n+ 1)+ 1= 4n²+ 8n+ 5 and you to show that is smaller than 8n²+ 2. In other words, you want 8n²+ 2> n²+ 8n + 5 which reduces to (8- 4)n²- 8n+ (2- 5)= 4n²- 8n -3> 0. You are right. I accidently had "- 4" instead of -3 before.

It is simplest to look at the equation 4n²- 8n- 3= 0: 4n²- 8n+ 4= 3+ 4= 7 or 4(n²- 2n+1)= 4(n-1)²= 7. Solving that gives $n= 1+ \sqrt{7}/2. as the only positive value of n at which the original inequality can change from "<" to ">" That is approximately 2.3. Taking n= 2 gives 4n²- 8n -3= 16- 16- 3= -3 which is negative. Taking n= 3 gives 4n²- 8n -3= 36- 24- 3= 9 which is positive. 4n²- 8n -3> 0 is true for all n greater than 2.$