1. ## Proof by Induction

I'm learning proof by induction at the moment and having some difficulties understanding. Taking the wikipedia entry for it, can someone explain the final step:

Induction Example

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

Using induction Hypothesis that P(k) holds, the left side can be rewritten:

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

It's the next part I don't get:

Algebraically:

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

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

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

Where are the first two expressions coming from on the right hand side here? :?

Cheers

BIOS

2. ## Re: Proof by Induction

Originally Posted by BIOS
$(0 + 1 + 2 .... + k + k + 1) = \frac{(k+1)((k+1) + 1)}{2}$
Using induction Hypothesis that P(k) holds, the left side can be rewritten:
$\frac{k(k+1)}{2} +(k+1)$

It's the next part I don't get:

Algebraically:

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

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

$\frac{k(k+1)}{2} +(k+1) = \frac{(k+1)((k+1) + 1)}{2}$
Where are the first two expressions coming from on the right hand side here? :?

3. ## Re: Proof by Induction

Yeah. Sorry didn't know how to highlight! Specifically the right hand side.

4. ## Re: Proof by Induction

Originally Posted by BIOS
Yeah. Sorry didn't know how to highlight! Specifically the right hand side.
In the first one the common denominator is 2.

The in the second factor out the $(k+1)$

5. ## Re: Proof by Induction

Gotcha! Thanks for the reply as always

Cheers

BIOS