K
K
KTG2016-02-01 10:38:35
Discrete Math
KTG, 2016-02-01 10:38:35

How is the proof of this example constructed?

www.mat.net.ua/mat/biblioteka/Haggarti-Discretnaya...
Page 33, example 2.13
Prove by induction that the equality 1+2+...+n = n(n+1)/2 holds for all natural n.
Solution:
Let P(n) be the predicate 1+2+...+n = n(n+1)/2.
In the case of n - 1, the left side of the equality is simply 1, and calculating the right side, we get 1 (1 + 1) / 2 = 1
Therefore, P (1) is true.
Well, OK. With this, everything is clear, framed, checked, and then?
Suppose now that the equality 1 + 2 + ... + k = k(k + 1) / 2 - holds for some natural number k.
Then
1 + 2 + ... + k + (k + 1) = (1 + 2 + ... + k) + (k + 1) = k(k + 1)/2 + (k + 1) = 1/2 * (k(k + 1) + 2(k + 1) ) = 1/2 * ( (k+2)(k+1) ) = ((k + 2)(k+1))/2
Thus, for any natural k, the implication P(k) -> P(k + 1)
is valid. Hence, by the principle of mathematical induction, the predicate P(n) has a true value for all natural n.
I didn't catch how k(k+1)/2 would be a proof of ((k+2)(k+1))/2 if it's obviously not the same???

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question