# Proof by Induction

• Oct 11th 2011, 07:01 AM
BIOS
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

$\displaystyle (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:

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

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

Algebraically:

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

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

$\displaystyle \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
• Oct 11th 2011, 07:12 AM
Plato
Re: Proof by Induction
Quote:

Originally Posted by BIOS
$\displaystyle (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:
$\displaystyle \frac{k(k+1)}{2} +(k+1)$

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

Algebraically:

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

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

$\displaystyle \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? :?

• Oct 11th 2011, 07:13 AM
BIOS
Re: Proof by Induction
Yeah. Sorry didn't know how to highlight! Specifically the right hand side.
• Oct 11th 2011, 07:17 AM
Plato
Re: Proof by Induction
Quote:

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 $\displaystyle (k+1)$
• Oct 11th 2011, 07:22 AM
BIOS
Re: Proof by Induction
Gotcha! Thanks for the reply as always ;)

Cheers

BIOS