Prove 2^n > 1/2(n+1)² is true help

[L²Cc]

i have understood step one (the easiest, hehehe)
If n=4, then LHS (left hand side) = 16
RHS (right hand side) = 12.5
16>12.5
Hence P4 is true...
but then when it comes to step 2, I am confused, I am used to proving sequences by mathematical induction, and, here, there doesn't seem to be a sequence in the first place...!

 

[radou]

i have understood step one (the easiest, hehehe)
If n=4, then LHS (left hand side) = 16
RHS (right hand side) = 12.5
16>12.5
Hence P4 is true...
but then when it comes to step 2, I am confused, I am used to proving sequences by mathematical induction, and, here, there doesn't seem to be a sequence in the first place...!

$$2^n > \frac{1}{2}(n+1)^2$$

For n = 1, you have 2 > 2.

 

[L²Cc]

$$2^n > \frac{1}{2}(n+1)^2$$

For n = 1, you have 2 > 2.

Sorry, n>3

 

[radou]

Sorry, n>3

Ok, not sure about this one, but, as you already showed, it is true for n = 4. Further on, we assume it is true for some k:
$$2^k > \frac{1}{2}(k+1)^2$$ ...(1)

We have to proove that it is true for k + 1:
$$2^{k+1} > \frac{1}{2}(k+2)^2 = \frac{k^2}{2}+ 2k + 2$$

So, we can multiply both sides of (1) with 2 to obtain:
$$2^k \cdot 2 > \frac{1}{2}(k+1)^2\cdot 2 \Rightarrow$$
$$2^{k+1} > (k+1)^2 = k^2+2k+2$$, which implies
$$2^{k+1}>\frac{k^2}{2}+ 2k + 2$$.

 

[L²Cc]

hmm, why are you multiplying both sides by two?

 

[radou]

hmm, why are you multiplying both sides by two?

To obtain $$2^{k+1}$$ on the left side. Anyway, as I said, I'm not a hundred percent sure about this one, so maybe better wait for someone else to comment.

 

[L²Cc]

hmm...if you add 2 on one side, you have to add it on the other...all right ill wait, although i don't think anyone will comment, I've been posting mathematical induction questions, and it's quite rare when people do actually answer...

 

[radou]

hmm...if you add 2 on one side, you have to add it on the other...all right ill wait, although i don't think anyone will comment, I've been posting mathematical induction questions, and it's quite rare when people do actually answer...

What do you mean by 'add 2 on one side'? Each side was multiplied with 2.

 

[L²Cc]

sorry i meant multiply!
when we let k=k+1, isn't that only applicable for a sequence, here we're dealing with something completely different, there's no sequence...we just have to prove it...im really confused!

 

[radou]

sorry i meant multiply!
when we let k=k+1, isn't that only applicable for a sequence, here we're dealing with something completely different, there's no sequence...we just have to prove it...im really confused!

Well, you shouldn't think of any sequences. It's the principle of mathematical induction. We assumed that the statement was true for some natural number k, and we prooved that it is true for k+1. Therefore, we conclude that the statement is true for every natural number n > 3.

 

[L²Cc]

ok i see what you are coming at, but i don't know whether the multiplication part is correct, although at the end Pn happens to be true (if we are to use your method: 2^k+1>1/2([k+1]+1)). Usually, in mathematical induction, you add 2^k+1 to the RHS because you are proving that the sum is applicable for the k+1th term...multiplying two to either sides does not seem logical? (that's only my point of view).

 

[radou]

... Usually, in mathematical induction, you add 2^k+1 to the RHS because you are proving that the sum is applicable for the k+1th term...multiplying two to either sides does not seem logical? (that's only my point of view).

There is no 'logic' in that sense here. You're talking about forms of induction proofs which apply for sequences, sums, etc. Maybe you need more examples - for instance, look at example 3 in this link: http://library.thinkquest.org/10030/11matind.htm".

 

[L²Cc]

yeah that's helpful although they go into too much detail! your's makes sense, thanks radou! take care.

 

[L²Cc]

We have to proove that it is true for k + 1:
$$2^{k+1} > \frac{1}{2}(k+2)^2 = \frac{k^2}{2}+ 2k + 2$$

So, we can multiply both sides of (1) with 2 to obtain:
$$2^k \cdot 2 > \frac{1}{2}(k+1)^2\cdot 2 \Rightarrow$$
$$2^{k+1} > (k+1)^2 = k^2+2k+2$$, which implies
$$2^{k+1}>\frac{k^2}{2}+ 2k + 2$$.

how does 2^{k+1} > (k+1)^2 = k^2+2k+2 imply this 2^{k+1}>\frac{k^2}{2}+ 2k + 2 ? I think you skipped a step?

 

[radou]

how does 2^{k+1} > (k+1)^2 = k^2+2k+2 imply this 2^{k+1}>\frac{k^2}{2}+ 2k + 2 ? I think you skipped a step?

I didn't. $$k^2+2k+2 > \frac{k^2}{2}+2k+2$$. If you have a relation b1 > b2, then the relation a > b1 implies a > b2, too.

 

[L²Cc]

all right, sorry for the late reply. once again, thank you radou!