Induction

[Manifold]

Hello!

We've got the following to prove by induction:

a) [math]2n+1\le{2^n}[/math]

b) [math]n^2\le{2^n}[/math]

(It is assumed that 0 is a natural number)

 

a) This inequality is not valid for [math]n=1,2[/math], so to prove the inequality one has to show its validity for all [math]n\ge{3}[/math]:

1) [math]A(3):7\le{8}[/math] (true)

2) Assume that [latex]A(n)[/latex] is true.

[math]A(n+1): 2(n+1)+1\le{2^{n+1}}[/math]

[math]2(n+1)+1=(2n+1)+2\le{2^n+2}\le{2^{n+1}}[/math], since for [math]2^n+2\le{2^{n+1}}[/math] we have [math]n\ge{1}[/math]

 

Is there a difference if I make the induction step this way?:

2)[math]A(n+1): 2(2n+1)\le{2^{n+1}}[/math], so to prove A(n) we must show that [math]2n+3\le{4n+2}[/math], which is also true for [math]n\ge{1}[/math]

The thing that disturbs me is that if we assume 0 to be a natural number the last inequalities in 2) in both cases do not hold...but I think this case doesn't play a role since we are to prove it for n greater 3...does it?

 

b) This inequality is invalid for all [math]n=3[/math], so to show that the inequality is valid we must show that it is valid for all [math]n\ge{4}[/math]

1) [math]A(4)=16\le{16}[/math] (true)

2) Assume that [math]A(n)[/math] is true.

[math]A(n+1): (n+1)^2\le{2^{n+1}}[/math]

[math](n+1)^2=n^2+2n+1\le{2^n+2n+1}\le{2^{n+1}}[/math]. The last inequality in this string is equivalent to [math]2n+1\le{2^n}[/math], which was proved in a).

 

Here, equally, the same question...Is there a difference if I do it this way?:

2) [math]A(n+1): 2n^2\le{2^{n+1}}[/math]

[math](n+1)^2=n^2+2n+1\le{n^2+3n-3}\le{n^2+n^2-3}\le{2n^2}[/math]

[matt grime]

That doesn't appear to make sesne.

 

Firstly, induction goes: given P(n) then P(n+1).

 

Thus you must start with assuming n^2 < 2^n and deducing (n+1)^2<2^(n+1), however your first line of the proof is to write out the thing you wish to prove as if it were true, which is not how one does a proof. I also see no explanation of how you deduce A(n+1) from A(n) just a series of inequalities at the end of which you decide n>1.

 

 

It is sufficient to prove that (n+1)^2 < 2n^2, for then (n+1)^2<2n^2<2.2^n =2^(n+1) by induction on n. That is it suffices to show n^2-2n-1 = (n-1)^2 -2>0, which is true for all n>2 and we are done (the initial case is obviously true)

[Manifold]

Ok, thanks Matt Grime!

 

Wow, Jesus, this was our first class on induction at university and our exercise group all solved the task the way I did, so it appears that we all have a wrong solution! Very funny!

 

From your post I could not get whether a) was alright... but anyway...

First I find it now confusing that "Assume that A(n) is true" is a wrong sentence to start the induction step, since our prof says it exactly in the same way.

 

Second, didn't I show that (n+1)^2<=2n^2 with the string of inequalities?...

In my first attempt for b) for example I used A(n): n^2<=2^n is equivalent n^2+2n+1<=2^n+2n+1, which is true according to one of the order axioms. I actually use them throughout,... in the secon case in b) I used the fact that n^2<=n^2 and 2n+1<=3n-1 and again the order axiom: from a<=b and c<=d follows a+c<=b+d.

The same thing with a). Here if we assume A(n) i.e. 2n+1<=2^n we can write 2n+1+2<=2^n+2 (again order axioms) and 2^n+2<=2^n+2^n since 2<=2^n.

I can't see why this argumentation should be wrong.

[matt grime]

I did not say "assume A(n) is true" is wrong.

 

i said that writing the statement of A(n+1) as the first line in the proof as if it were true is wrong. it is bad mathematics to do that. you start at A(n) and deduce A(n+1), that's how proofs like this go.

 

i didn't check through what your strings of symbols without explanations in the first post might or might not mean. if you don't explain the steps then you can not expect anyone to mark them for correctness.

[matt grime]

here let me indent and clarify:

 

a) This inequality is not valid for [math]n=1,2[/math], so to prove the inequality one has to show its validity for all [math]n\ge{3}[/math]:

1) [math]A(3):7\le{8}[/math] (true)

2) Assume that [latex]A(n)[/latex] is true.

[math]A(n+1): 2(n+1)+1\le{2^{n+1}}[/math]

 

 

why have you written this? this is what we want to deduce, but you shouldn't write it here as if it were true

[math]2(n+1)+1=(2n+1)+2\le{2^n+2}\le{2^{n+1}}[/math], since for [math]2^n+2\le{2^{n+1}}[/math] we have [math]n\ge{1}[/math]

 

 

 

Here I don't particularly have the energy to follow what you're doing, and more importantly you don't even say what you're doing or why.