inductive step confusion in sum of all positive integers example

Question

I am confused with the inductive step of this very basic induction example in the book Discrete Mathematics and Its Applications:

$$1 + 2+· · ·+k = k(k + 1) / 2$$

When we apply $k+1$, the equation becomes:

$$1 + 2+· · ·+k+(k+1) = k+1(k + 1)+ 1 / 2 = (k+1)(k+2)/2$$

Now I am completely lost in the actual inductive step of the equation,

$$1 + 2+· · ·+k + (k + 1) = k(k + 1) 2 + (k + 1) = k(k + 1) + 2(k + 1) / 2 = (k + 1)(k + 2) / 2$$

As I understand it, we get

$$(k+1)(k+2)/2$$

when we substitute $k+1$ from $k$ in $k(k+1)/2$ and simplifying. How is $k(k + 1) / 2 + (k + 1)$ derived?

Can someone explain what this really means? I just simplified$ k+1(k + 1)+ 1 / 2 $to $(k+1)(k+2)/2 $it's in the book, but it suddenly becomes $k(k + 1) / 2 + (k + 1)$ and we just did the addition to turn it back to $(k+1)(k+2)/2$. How did it happen?

Answer 1

The kicker, here, is to assume $$1+\cdots+k=\frac{k(k+1)}{2}\tag{$\star$}$$ for some $k,$ then use it to prove that $$1+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}.\tag{$\heartsuit$}$$ To do so, we use $(\star)$ to substitute $\frac{k(k+1)}2$ for $1+\cdots+k,$ which turns $1+\cdots+k+(k+1)$ into $$\frac{k(k+1)}2+(k+1).$$ Then, combining over a common denominator and simplifying completes the proof of $(\heartsuit),$ thus concluding the inductive portion.

As a side note, at no point are you taking a "sum of all positive integers." Rather, you are proving that an identity involving the sum of the first $n$ positive integers is correct for any given positive integer $n$.

---

Added: Since the OP's screen reader is unable to handle rendered MathJax, I include here a plain text version.

The kicker, here, is to assume

1+...+k=k(k+1)/2

for some k, then use it to prove that

1+...+k+(k+1)=(k+1)(k+2)/2.

To do so, we use our assumption to substitute k(k+1)/2 for 1+...+k, which turns 1+...+k+(k+1) into

k(k+1)/2+(k+1).

Then, combining over a common denominator and simplifying completes the inductive portion of the proof.

Answer 2

Assume

$$1+...+k=\frac{k(k+1)}{2}$$

to calculate

$$1+...+k+(k+1)=\frac{k(k+1)}{2}+k+1=\frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2}=\frac{(k+1)(k+2)}{2}$$

completing the proof.

Answer 3

I start with the answer in plain text as the OP seem to use screen reader that can't read TeX, the TeX formatted answer follows.

As you seem to have understood you want to prove (in the induction step that)

1+2+...+k+(k+1) = (k+1)(k+2)/2

but already in the assumption in the induction step you have:

1+2+...+k = k(k+1)/2

This means that the first sum can be rewritten:

1+2+...+k+(k+1) = (1+2+...+k) + (k+1)

The first parenthesis is equals k(k+1)/2 as assumed and therefore the sum becomes k(k+1)/2 + (k+1).

Then you have to show that k(k+1)/2+(k+1) = (k+1)(k+2)/2 which would complete the induction step.

---

As you seem to have understood you want to prove (in the induction step that)

$$1+2+...+k+(k+1) = {(k+1)(k+2)\over 2}$$

but already in the assumption in the induction step you have:

$$1+2+...+k = {k(k+1)\over 2}$$

This means that the first sum can be rewritten:

$$1+2+...+k+(k+1) = (1+2+...+k) + (k+1)$$

The first parenthesis is equals $k(k+1)/2$ as assumed and therefor the sum becomes $k(k+1)/2 + (k+1)$.

Then you have to show that $k(k+1)/2+(k+1) = (k+1)(k+2)/2$ which would complete the induction step.

Answer 4

If that can help you:

$$1+2+3+4+5=\frac{5\cdot6}2,$$ 1+2+3+4+5=5.6/2

and $$1+2+3+4+5\color{green}{+6}=\frac{5\cdot6}2\color{green}{+6}=\frac{(5+2)\cdot6}2=\frac{6\cdot7}2.$$ 1+2+3+4+5+6=5.6/2+6=(5+2).6/2=6.7/2