I don't get INDUCTION!! (1 Viewer)

[live.fast]

lol but now im stuck on methodology of induction

Prove the below equation holds/does not hold for all integers ( n>0 )

(n^3) <= 2(n^2)

could someone solve this by induction please?

 

[alcalder]

Prove the below equation holds/does not hold for all integers ( n>0 )

(n^3) <= 2(n^2)

Now, if we look at this logically, when
n=1 1<=2 true
n=2 8<=8 true
n=3 27<=18 false
n=4 64<=32 false

So we are trying to prove that this is not true using induction.

However,

n³<= 2n²
If n>0 then dividing both sides by n is valid without changing the inequality sign.

n²<= 2n
n<= 2

So the statement is not true for all n>0, it is only true for 0<n<=2

Induction is not really needed here, surely.

But if it were:

Step 1: for all integers n>0

Prove n³<= 2n²

Test n =1

1<=2 true

Step 2: Assume true for n = k (We make an assumption that it is true for somewhere in the integer range)

k³<= 2k²

Step 3: prove true for n= k+1 (Then we try and prove, using our assumed truth, that the next integer also holds true. Since we have already shown that 1 is true, then k=1 is true and k+1 = 2 is true. And then if k=2 is true, then k+1=3 is true and so on for integer n>0.)

ie that

(k+1)³<= 2(k+1)²
-----------------
At this point you move to the right side of your page and work out how the above equation would look like, working from the thing are trying to prove (ie the case when n=k+1, down to something that incorporates your assumed true statement for n=k.

So, on the right side of your page you would multiply out

(k+1)³<= 2(k+1)²

k³ + 3k² + 3k + 1 <= 2k²+ 4k + 2 k³ + 3k² <= 2k²+ k + 1


Now is 3k² <= k + 1 for all integer k>0

Test k=1

3<=2 false

therefore you cannot prove that n=k+1 is true from your assumption.

This then disproves the original statement, that for all integer n>0

n³<= 2n² is false.

 

[SeDaTeD]

I don't really like how they say 'assume' true for some n=k, because that may give the wrong impression that you are saying one particalr k is true out of thin air.

let p(n) be a statement about n, eg. let p(n) = "n^2 >= n". I'm just using this to shorten the notation. Edit: Statements can be true or false.

The principle of induction is just:

If p(1) is true
AND
the statement "If p(k) is true then p(k+1) is true" is true
THEN
p(n) is true for all n>=1.

That is basically the guts of the logic behind induction. I haven't used the word assume because you seem worried by it. When you usually see "assume true for n=k then show true for n=k+1", what you are doing is showing that "IF it is true for n=k, THEN it is true for n=k+1". This statement alone is not enough to guarantee that it is true for any n, it just merely states that if there was a true for one, then it would be true for the next one. This is where proving true for n=1 comes in, to show that one particular case is true.

Induction then uses the two statements together to conclude that it is true for all n>=1.

Of course, you don't have to specifically use n=1, you can prove it true for some n=a and use induction to conclude it is true for all n >= a.

 

[live.fast]

(k+1)3<= 2(k+1)2

k3 + 3k2 + 3k + 1 <= 2k2+ 4k + 2 k3 + 3k2 <= 2k2+ k + 1

I dont get how you got the second line from the first line (above).

Now is 3k2 <= k + 1 for all integer k>0

Test k=1

3<=2 false

Are you allowed to sub in numbers like that in the 3rd step of a proof that involves induction?

 

[airie]

Basically,

IF the fact that "conditions are true for k" would imply "the conditions are true for k+1" (Note: not saying that the conditions would definitely be true for k),

AND you've proven "the conditions are true for 1",

Then by the first statement, the fact that "the conditions are true for 1" implies that "the conditions are true for 2", and "the conditions are true for 2" HOLDS since it is proven that "the conditions are true for 1";

The fact that "the conditions are true for 2" holds in turn implies that "the conditions are true for 3", which would imply the same for 4, which would imply the same for 5, ... and so on.

Therefore, the conditions are true for ALL integers greater or equal to 1.

And as SeDaTeD mentioned above, the base case does not necessarily have to be 1, but any number a, as long as it could be proven that the case for a holds true, and the fact that the case for a number holding true would DEFINITELY mean that the case for the number after it also holds true. (Then you would have proven the conditions for all integers greater or equal to a, instead of 1.)

EDIT:

Now is 3k2 <= k + 1 for all integer k>0

Test k=1

3<=2 false

Are you allowed to sub in numbers like that in the 3rd step of a proof that involves induction?

You are DISPROVING something here, not PROVING it, therefore just one counter-example is enough. Induction shouldn't be used to disprove something, it is a method of proof, not disproof, see