How does Induction make sense? 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 /wsr/ - Worksafe Requests

You are currently reading a thread in /wsr/ - Worksafe Requests

Thread images: 2

Anonymous

How does Induction make sense? How does it work? 2016-02-07 14:44:15 Post No. 51612

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

How does Induction make sense? How does it work? 2016-02-07 14:44:15 Post No. 51612

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

How does Induction make sense? How does it work?
Anonymous
2016-02-07 14:44:15
Post No. 51612
[Report]

I somewhat get the gist of it:

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))

>>

>>51612

This is the equation I am referring to in b)

>>

>>51612

By induction you check if some formula is true by essentially chuging in all consecutive numbers.

You start with n=1 or 0 and then check next numbers. It's somewhat like recurrence where each step is dependant on the previous one.

If every bunny from 1 to n is white and you can show that this implies that n+1st bunny is white as well then all bunnies are white. Note that this is different from what you said.

1+2+...+n+n+1=(1+2+...+n)+n+1

And you use induction basis to sum in parentheses.

>>

>>51624

That makes more sense then.

And the n+1 is like a reference of the index spot then and not the chosen value for n?

>>

>>51630

In this case it's both

>>

>>51633

thanks a lot for the help

>>

>>51635

To be even more clear, in the induction step you prove:

If X holds for n then X holds for n+1 for an ARBITRARY n >= n0 (n0 ist the base case, usually 1).

You know that X hold for 1 (base case). Then the induction step says that X holds for 1+1 = 2. Then the induction step says that X holds for 2+1 = 3, and so on, ad infinitum.

The last step (the "and so on" part, that X holds for any natural number n>=n0) is actually an axiom.

----

In your example the base case is trivial.

In the induction step you assume that the claim holds for n:

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

In the proof of the implication you need to find where to apply this part. In such examples (sums or products up to n where n is the variable used in the induction) you simply move the highest summand / factor outside of the sum / product:

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

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

Note that (n+1) is the summand for i=n+1, that may be a little misleading.

Now you can use the induction hypothesis and replace the sum as in your pic >>51614

>>

>>51612

Second example:

n=1:

sum for i from 1 to 1 of i^2 = 1^2 = 1

1(1+1)(2+1)/6 = 1

Induction step:

Assume that for an arbitrary n,

sum for i from 1 to n of i^2 = n(n+1)(2n+1)/6

Then s = sum for i from 1 to n+1 of i^2 = sum for i from 1 to n of i^2 + (n+1)^2

Now you use the assumption and replace the sum

s = n(n+1)(2n+1)/6 + (n+1)^2

You need to prove that s = (n+1)(n+1+1)(2(n+1)+1)/6 = (n+1)(n+2)(2n+3)/6 by doing basic operations.

s = n(n+1)(2n+1)/6 + (n+1)^2

= ((n+1)/6)( n(2n+1) + 6(n+1) )

= ((n+1)/6)( 2n^2 + 7n + 6 )

= (n+1)(n+2)(2n+3)/6 qed

Thread images: 2

Thread DB ID: 502606

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