Mathematical Induction Question

SugarHigh

Just starting on Induction.

How does the second last line prove that the last line is true?


There is also the method on Wikipedia for the same problem


I just don't understand how that proves it. All I see is it getting rearranged.

Davidius

Well it uses the assumption that P(n) is true for n=k and uses it to conclude that P(n) is true for n=k+1 if the initial assumption is true.

Using this we see that if P(n) is true for n=1 then P(n) must also be true for n=2. However by the exact same logic if P(n) is true for n=2 then it must be true n=3 as well and so on.

Say if you set m=k+1 then you've proven P(m) is true. You can go through the same process to prove that P(m+1) is true.

Unless I'm misinterpreting your post and your problem is seeing how they arrived with the end expression.

If that's the case then it expresses the sum of the first k+1 natural numbers as the sum of the first k natural numbers plus k+1.

The goal is to show that if P(k) = k(k+1)/2 then using the assumption you can prove that P(k+1) = (k+1)((k+1)+1)/2. Note how the k in P(k) has been replaced with k+1 in P(k+1)

It's assumed that P(k) is true so the sum of the first k natural numbers would be k(k+1)/2
Add k+1 to that for P(k+1) and rearrange to show P(k+1) equals (k+1)(k+2)/2 which is equivalent to (k+1)((k+1)+1)/2

sponsoredwalk

Well, lets start from the beginning so you understand what's going on
exactly. tbh I can't understand why they always just give you the
same formula that you have posted here, out of nowhere, and expect
you to understand what's going on.

If we rederive everything from scratch it'll become clearer...

Lets say we want to find the sum of the first "n" terms...

[latex] S_n \ = \ 1 \ + \ 2 \ + \ 3 \ + \ 4 \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n [/latex]

Well, there is a trick that was suposedly developed by Gauss when he
was 8 years old in a manner similar to that we'll d now.

If we add the above sum to itself we'll get [latex] S_n \ + \ S_n \ = \ 2S_n [/latex]



[latex]+ \ ^{S_n \ = \ 1 \ + \ 2 \ + \ 3 \ + \ 4 \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n}_{S_n \ = \ 1 \ + \ 2 \ + \ 3 \ + \ 4 \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n} [/latex]

Alright, well now for the trick. Instead of just adding them this way we can
do something that seems a bit strange, we will add the bottom sum
backwards, it's still the same sum

[latex] + \ ^{S_n \ = \ 1 \ \ + \ \ \ \ \ 2 \ \ \ \ + \ \ \ \ 3 \ \ \ \ \ + \ \ \ \ 4 \ \ \ \ \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n}_{S_n \ = \ n \ + \ (n \ - \ 1) \ + \ (n \ - \ 2) \ + \ (n \ - \ 3) \ + \ ... \ + \ \ \ \ \ 4 \ \ \ \ + \ \ \ \ \ 3 \ \ \ \ \ + \ \ \ \ 2 \ \ \ \ \ + \ 1 } [/latex]

Alright, if we add this like a normal sum we'll get;



[latex] S_n \ + \ S_n \ = \ (1 \ + \ n) \ + \ (2 \ + \ n \ - \ 1) \ + \ (3 \ + \ n \ - \ 2) \ + \ (4 \ + \ n \ - \ 3) \ + \ ... \ + \ (4 \ + \ n \ - \ 3) \ +\ (3 \ + \ n \ - \ 2) \ + \ (2 \ + \ n \ - \ 1) \ + \ (1 \ + \ n)[/latex]

Or, cleaning this up;

[latex] 2S_n \ = \ (1 \ + \ n) \ + \ (1 \ + \ n) \ + \ (1 \ + \ n) \ + \ ... \ + \ (1 \ + \ n) \ + \ (1 \ + \ n) \ + \ (1 \ + \ n) [/latex]

Now, seeing as there were "n" terms in the original sum it means we had to
do n different sums so looking at this equation you'll notice that there are
"n" amount of (1 + n) terms!

We can rewrite the sum as;

[latex] 2S_n \ = \ n(1 \ + \ n) [/latex]

Dividing by 2

[latex]S_n \ = \ \frac{n(1 \ + \ n)}{2} \ = \ \frac{n(n \ + \ 1)}{2}[/latex]

So, think about it. [latex] 2S_n \ = \ n(1 \ + \ n) [/latex] is the sum of
2 1 + 2 + 3 + ... + n sums but when we divide by 2 we find the sum for
just one of them! It's a great trick!

Seeing as [latex] \frac{n(n \ + \ 1)}{2}[/latex] will give us the
answer to the sum of the first "n" terms why not ask ourselves what
the sum for (n + 1) terms will be???

[latex]S_{(n + 1)} \ = \ \frac{n(n \ + \ 1)}{2} \ + \ (n \ + \ 1) = \ 1 \ + \ 2 \ + \ 3 \ + \ 4 \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n \ + \ (n \ + \ 1)[/latex]

So, in

[latex] \frac{n(n \ + \ 1)}{2} \ + \ (n \ + \ 1) = \ 1 \ + \ 2 \ + \ 3 \ + \ 4 \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n \ + \ (n \ + \ 1)[/latex]

we see that whatever the answer is on the left hand side it will tell us
what the sum on the right hand side equals so if we algebraically solve
for the answer to that we'll get our answer, remember - induction says
that whatever n you pick if the equation holds for the (n + 1) term then
it must include all the numbers because whatever number n you pick
there will always be an (n + 1) term that the equations will hold true for.

[latex] \frac{n(n \ + \ 1)}{2} \ + \ (n \ + \ 1)[/latex]

If we multiply the [latex] (n \ + \ 1)[/latex] term by 1, a legal
mathematical action we'll be able to work with this equation.
Since [latex] \frac{2}{2} \ = \ 1[/latex] we can use this because
if we do we'll be able to add it to the freaky fraction beside it!

[latex] \frac{n(n \ + \ 1)}{2} \ + \ \frac{2}{2} \cdot (n \ + \ 1) \ = \ \frac{n(n \ + \ 1)}{2} \ + \ \frac{2(n \ + \ 1)}{2}[/latex]

[latex] \frac{n(n \ + \ 1) \ + \ 2(n \ + \ 1)}{2}[/latex]

[latex] \frac{n^2 \ + \ n \ + \ 2n \ + \ 2}{2}[/latex]

[latex] \frac{n^2 \ + \ 3n \ + \ 2}{2}[/latex]

[latex] \frac{(n \ + \ 1)(n \ + \ 2)}{2}[/latex]

So, we now know that

[latex] \frac{(n \ + \ 1)(n \ + \ 2)}{2} = \ 1 \ + \ 2 \ + \ 3 \ + \ 4 \ + \ ... \ + \ (n \ - \ 3) \ + \ (n \ - \ 2) \ + \ (n \ - \ 1) \ + \ n \ + \ (n \ + \ 1)[/latex]

If you look at what you posted, the [latex]\sum_{i=1}^{k} i[/latex] means

[latex]\sum_{i=1}^{k} i \ = \ 1 \ + \ 2 \ + \ 3 \ + \ ... \ + \ (k \ - \ 2) \ + \ (k \ - \ 1) \ + \ k[/latex]

So, looking at the [latex]\sum_{i=1}^{k + 1} i[/latex] it's asking
for the sum of the first k + 1 terms & we just use the method I described
above to find it

SugarHigh

Thanks that was very helpful.