# Proof by induction

1. Nov 15, 2008

### vikkisut88

1. The problem statement, all variables and given/known data
Prove that ($$\forall$$n in the set of Natural numbers )[(n $$\geq$$ 9) $$\Rightarrow$$ (2n > 4n2 + 1)]

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

3. The attempt at a solution
So for n=1 i have RHS:29 = 512 and 4.92 + 1 = 325
So (2n > 4n2 + 1)] for n=1

Now assume true for n

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

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

Last edited: Nov 15, 2008
2. Nov 15, 2008

### HallsofIvy

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

Last edited: Nov 15, 2008
3. Nov 15, 2008

### vikkisut88

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

4. Nov 15, 2008

### vikkisut88

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

5. Nov 15, 2008

### vikkisut88

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

6. Nov 15, 2008

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

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

So for values greater than 5?

7. Nov 15, 2008

### HallsofIvy

Staff Emeritus
Yes. And since your original problem specified "[itex]n\ge 9", ...

8. Nov 15, 2008

### vikkisut88

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

9. Nov 16, 2008

### HallsofIvy

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

It is simplest to look at the equation 4n2- 8n- 3= 0: 4n2- 8n+ 4= 3+ 4= 7 or 4(n2- 2n+1)= 4(n-1)2= 7. Solving that gives [itex]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 4n2- 8n -3= 16- 16- 3= -3 which is negative. Taking n= 3 gives 4n2- 8n -3= 36- 24- 3= 9 which is positive. 4n2- 8n -3> 0 is true for all n greater than 2.