0

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?

Amir
  • 445
lightning_missile
  • 491
  • 1
    Using $/$ to express rational functions makes it very hard to read. Instead, I recommend using $\frac{k(k+1)}{2}$ for $\frac{k(k+1)}{2}$ or $\dfrac{k(k+1)}{2}$ for $\dfrac{k(k+1)}{2}$. – Cameron Buie Nov 18 '15 at 11:47
  • What is it that you don't get? That $k(k+1)/2+(k+1) = (k+1)(k+2)/2$? – skyking Nov 18 '15 at 12:16
  • @skyking do you mind writing the equations in your comments in text format? I can't read it right now. Thanks. – lightning_missile Nov 18 '15 at 12:25
  • That's odd (I can read), however the equation was k(k+1)/2+(k+1)=(k+1)(k+2)/2. – skyking Nov 18 '15 at 12:31
  • @skyking yes I understand that, you added k()/2 to k+1. But when you do p(k+1) you substitute k+1 to k, so k(k+1)/2 becomes k+1(k+1)+1/2 and to simplify (k+1)(k+2)/2. There I got (k+1)(k+2)/2. I don't understand how 1(k+1)/2+(k+1) got into the picture. – lightning_missile Nov 18 '15 at 12:43

4 Answers4

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.

Cameron Buie
  • 102,994
1

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.

skyking
  • 16,654
0

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.

Peter
  • 84,454
0

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