/sci/ - Science & Math

[Anonymous No.6891058]

Can someone in the simplest possible terms explain what to do in an induction proof (let's assume you're proving something (you can make it up or whatever) is divisible by something else) after the first step, which is proving the case for k=1 or any other number?

[Anonymous No.6891060]

>>6891058
>divisible by something else
I meant an integer

[Anonymous No.6891815]

>>6891058
bamp

[Anonymous No.6891830]

>>6891058
You set n = n+1

then you set n = 2k if you want to show n has the factor 2

then you want to hve something that looks like 2(....) to show the shit has factor 2

[Anonymous No.6893916]

bump need a little better of an explanation than >>6891830

[Anonymous No.6893934]

>>6891058
Prove p(k) for one case of k.

Then show that if you p(k+1) is true if p(k) is true.

[Anonymous No.6893947]

>>6893916
For example: Prove p(n) = n^3+2n is divisible by 3

First we prove this is true for n=0

0^3+2(0) = 0 which is divisible by 3

Now let's assume that n^3+2n is divisible by 3.

p(n+1) = (n+1)^3+2(n+1) = n^3+3n^2+3n+1+2n+2 = (n^3+2n)+(3n^2+3n+3) = (n^3+2n)+3(n^2+n+1)

Since both terms are divisible by 3 (because w assumed in the beginning that n^3+2n is divisible by 3), their sum is divisible by 3. p(n+1) is divisible by 3.

Therefore by induction n^3+2n is divisible by 3

[Anonymous No.6893993]

>>6893947
Are you retarded? You don't use induction for that shit. n mod 3 = 0, 1, or 2
0^3+2*0=0
1^3+2*1=3=0
2^3+2*2=12=0
QED

[Anonymous No.6895204]

lesgetitbump

[Anonymous No.6895226]

The idea is that you want to prove something for the k = 1 case. This is your base. Then you want to show that if it's true for some given N, then it must be true for N + 1. Therefore since it's true for 1, then it's true for 2 (since it's true for N -> true for N + 1), then it's true for 3, etc. and it's true for all N = 1, 2, 3 ...

[Anonymous No.6896373]

>>6891058
i suck dick on teh weekends

[Anonymous No.6896382]

>>6893993
So you come into a thread about how to do an induction proof and shit on someone who gives an example of the process of proving something by induction?

Do you just lack reading comprehension or are you just trying to "wow" everyone with how "smart" you are for proving something in a way that is not relevant to the discussion?

[Anonymous No.6896388]

>>6893993
Because rigor is for fags, right?

[Anonymous No.6896393]

Okay.

So you show that what you are trying to prove works for the base case, ie for some small natural number you start at - this is usually 0 or 1.

Then you assume it's true in general, ie for n = k.

Then, you basically manipulate the equation/whatever you have in such a way that the equation is the same as the previous step, except you have (k+1) everywhere you had k.

[Anonymous No.6896406]

Not sure if your questions got answered yet but I'll try my best.

Let's say the thing you prove is A(n) where n is a natural number.

The first step is A(1), basically to kickstart your chain of proofs.

The second step is to proof this structure:
>"If A(n) is true, then A(n+1) is also true"
Note that you don't have to prove A(n) here, you already assume it.

Practically you look at A(n+1) and try to form it into A(n)+f(n), where f(n) is some other term (the + might as well be a * or a /. The point is that you mush your A(n+1) around so much that you find A(n) in there.). The you use the fact that you assumed A(n) is true (in most cases this means you can subsitute it for an equation that holds if A(n) is true) and then mush around the resulting expression so long until you see that A(n+1) also is true.

Then you have it: If A(n) is true then also A(n+1): A(1) is true (because we proved it), therefore also A(2), therefor also A(3)... etc

[Anonymous No.6896440]

>>6891058
I'm sure you'll figure out what the general idea of an induction proof is by the other replies, but its incredibly important to remember that induction only works when working with the integers.

[Anonymous No.6896444]

>>6896440
Not necessarily. You can make the induction step on any interval you want.

[Anonymous No.6896447]

>>6896444
You can do it on any countable set, although you need to do it in two directions if you start in the middle (i.e 0)

[Anonymous No.6896729]

>>6896444
Huh, maybe I'm not at that level of maths yet, but my professor fucking drilled that into our heads that induction is only used on the integers (I'm in my first foundations class right now)

[Anonymous No.6896797]

>>6896382
At least post worthwhile examples or he's going to prove anything and everything by induction like a fool.