Induction // How does it work?

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

You are currently reading a thread in /sci/ - Science & Math

Thread images: 3

Anonymous

Induction // How does it work? 2016-02-07 14:56:16 Post No. 7840762

[Report] Image search: [iqdb] [SauceNao] [Google]

Induction // How does it work? 2016-02-07 14:56:16 Post No. 7840762

[Report] Image search: [iqdb] [SauceNao] [Google]

I somewhat get the gist of:

1. You take a base case and prove that what you try to claim holds for this base case (usually index 1)

2. In the induction step you use a hypothesis as premise (that your claim holds for n)

3. You prove that it also holds for n+1 and therefore for all numbers

But I don't get...

a) the logic behind "let's just assume it counts for all numbers till an arbitrarily chosen index n" and if the claim holds there, it therefore must be true for all numbers following after that.

If I take a sample of 1 to n bunnies to see which of them are white for example, by induction logic, all bunnies must therefore be white?

b) the induction step. Take the first exercise in the pic for example.

Base case n=1:

On the left side: 1 (only 1 summand)

On the right side: 1(1+1)/2 = 1

Induction step:

Sum from i=1 to n+1 of (i)

= Sum from i=1 to n of (i) + (n+1)

^Why is this equation correct?

For n=3 for example, the sum from index 1 to 3+1 aka n+1 equals 20 (1+3+6+10).

But then why is this the same as the sum of

index 1 to 3 plus (n+1)?

That would be: 14 (1+3+6 + (3+1))

>>

You prove it's true for 1. You also proved that if it's true for n, it's true for n+1. Therefore it is true for 2. By the same reasoning, it is true for 3. Etc.

>>

Dominoes and memes

>>

>>7840762

>a) the logic behind "let's just assume it counts for all numbers till an arbitrarily chosen index n" and if the claim holds there, it therefore must be true for all numbers following after that.

>If I take a sample of 1 to n bunnies to see which of them are white for example, by induction logic, all bunnies must therefore be white?

You're forgetting step 3 that you listed earlier.

If P is your property to be proved, P(n) MUST imply P(n+1), and you have to prove that it does, else you can't induct. In your example, 5 white bunnies does not imply 6 white bunnies.

>>

>>7840762

>a) the logic behind "let's just assume it counts for all numbers till an arbitrarily chosen index n" and if the claim holds there, it therefore must be true for all numbers following after that.

That's not how it works.

You want to prove [math]\forall n \geq n_0 [/math] [math] \phi(n) [/math]. You do this by proving

1) [math] \phi(n_0) [/math]

2) [math] \phi(n) \Rightarrow \phi(n+1) [/math]

>>

>>7840791

Somebody just got out of intro to proofs and feels smart when he spams unnecessary formalism

>>

>>7840762

>the logic behind "let's just assume it counts for all numbers till an arbitrarily chosen index n" and if the claim holds there, it therefore must be true for all numbers following after that.

The domino analogy might help you here. Otherwise, try swapping the first two steps:

1. Assume that P(n) holds and prove P(n+1).

2. Prove that P(0) holds.

Now whichever m you choose, you can prove that P(m) holds. For instance, you want to see if P(3) holds. Since you know that P(0) holds and

[math]P(n) \implies P(n+1)[/math], then P(1) holds, too. Similarly for P(2) and P(3).

>If I take a sample of 1 to n bunnies to see which of them are white for example, by induction logic, all bunnies must therefore be white?

You're confusing philosophical induction and mathematical induction. Mathematical induction is in fact a deductive reasoning method. In your example, the bunnies have no relations whatsoever, the properties of one don't depend on the previous.

>>

File: Screenshot from 2016-02-07 16-22-55.png (36 KB, 871x189)
Image search:
[iqdb]
[SauceNao]
[Google]

36 KB, 871x189

>having problems with induction

Just drop out, if you can't grasp something this simple, you won't be of any use whatsoever later on.

>>

>>7840798

please kill yourself

Thread images: 3

Thread DB ID: 513043

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's