Induction // How does it work?
- Home
- Board: /sci/ - Science & Math
- Reading: Induction // How does it work?
We respect your right to privacy. You can choose not to allow some types of cookies. Your cookie preferences will apply across our website.
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.
>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
