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
