How can mathematical induction prove Gauss’s formula for the sum of the first n integers?

"A famous story tells of Carl Friedrich Gauss, perhaps the most brilliant mathematician of all time, getting in trouble one day as a schoolboy. As punishment, he was sentenced to tedious work: adding together all the numbers from 1 to 100. To his teacher’s astonishment, he came up with the correct answer in a moment, not because he was quick at adding integers, but because he recognized a trick. The first number on the list (1) and the last (100) add up to 101. So do the second number (2) and the second-to-last (99). So do 3 and 98, and so do 4 and 97, etc., all the way up to 50 and 51. So really what you have here is 50 different sums of 101 each, so the answer is 50 × 101 = 5050. In general, if you add the numbers from 1 to x, where x is any integer at all, you’ll get x⁄2 sums of x + 1 each, so the answer will be x(x + 1)⁄2. Now, use mathematical induction to prove that Gauss was right, i.e., that ∑ᵢ₌₁ˣ i = x(x + 1)⁄2 for all numbers x. First we have to cast our problem as a predicate about natural numbers. This is easy: we say let P(n) be the proposition that ∑ᵢ₌₁ⁿ i = n(n + 1)⁄2. Then, we satisfy the requirements of induction:\n\n1. base case. We prove that P(1) is true simply by plugging it in. Setting n = 1 we have 1 = 1(1 + 1)⁄2 = 1.\n\n2. inductive step. We now must prove that P(k) ⇒ P(k + 1). Put another way, we assume P(k) is true, and then use that assumption to prove that P(k + 1) is also true.\n\nLet’s be crystal clear where we’re going with this. Assuming that P(k) is true means we can count on the fact that 1 + 2 + 3 + ··· + k = k(k + 1)⁄2. What we need to do, then, is prove that P(k + 1) is true, which amounts to proving that 1 + 2 + 3 + ··· + (k + 1) = (k + 1)((k + 1) + 1)⁄2. Very well. First we make the inductive hypothesis, which allows us to assume: 1 + 2 + 3 + ··· + k = k(k + 1)⁄2. The rest is just algebra. We add k + 1 to both sides of the equation, then multiply things out and factor it all together. Watch carefully:\n\n1 + 2 + 3 + ··· + k + (k + 1) = k(k + 1)⁄2 + (k + 1) = ½k² + ½k + k + 1 = ½k² + ³⁄₂k + 1 = (k² + 3k + 2)⁄2 = (k + 1)(k + 2)⁄2 = (k + 1)((k + 1) + 1)⁄2.\n\n3. conclusion. Therefore, ∀ n ≥ 1 P(n)."