# Math Help - Proof by Induction

1. ## Proof by Induction

n^2 - n is even for any n >= 1

So far i have the base case:
n=1 1^2-1 = 0 and 2^2-2=2 which are both even.
then prove for n = k so k^2 - 2 for k>=1

then n= (k+1)^2 - (k+1).... having problems with further steps.

2. [LaTeX ERROR: Convert failed] .

3. Why do you have to use induction?

If $n$ is odd and $\geq 1$, then $n = 2k+1$ where $k \in \{0, 1, 2, \dots\}$ and

$n^2 - n = (2k + 1)^2 - (2k + 1)$

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

$= 2k(2k + 1)$ which is clearly even.

If $n$ is even and $>1$, then $n = 2m$ where $m = \{1, 2, 3, \dots\}$ and

$n^2 - n = (2m)^2 - 2m$

$= 2m(2m - 1)$

which is clearly even.

Therefore $n^2 - n$ is even for any $n \geq 1$.

4. Originally Posted by zaj091000
n^2 - n is even for any n >= 1

So far i have the base case:
n=1 1^2-1 = 0 and 2^2-2=2 which are both even.
then prove for n = k so k^2 - 2 for k>=1

then n= (k+1)^2 - (k+1).... having problems with further steps.
$n^2-n$ is even for $n\ \ge\ 1$

You've completed the base case...

Now you must show whether or not...

$true\ for\ n=k$ causes $true\ for\ n=k+1$

P(k)

$k^2-k$ is even

P(k+1)

$(k+1)^2-(k+1)$ is even if P(k) is true

Proof

$(k+1)^2-(k+1)=k^2+2k+1-k-1=k^2+k=\left(k^2-k)+2k$

Since 2k is even...

If P(k) is true, then P(k+1) is definately true.