Factorization induction proof.

**Ruun** · October 22nd 2009, 10:23 AM

Hi, I'm trying to proove the following by induction. I think I'm done, but how satisfactory would this proof be for a mathematician?

Thanks for your time.

$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})$ . If we set $n=1$ it is satisfied, so we suppose it is true for some $n \in \mathbb{N} > 1$ . Then, for $n+1$

$x^{n+1}-y^{n+1}=xx^n-yy^n=x[(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})+y^n]-yy^n$
$=x(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})+xy^n-yy^n$
$=x(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})+y^n(x-y)$
$=(x-y)[(x^{n}+x^{n-1}y+...+x^{2}y^{n-2}+xy^{n-1})+y^n]$

**proscientia** · October 22nd 2009, 10:44 AM

Suppose

$x^n-y^n\ =\ (x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1})\ \ldots\ \fbox1$

is true. Multiplying through by $x$ gives

$x^{n+1}-xy^n\ =\ (x-y)(x^n+x^{n-1}y+\cdots+x^2y^{n-2}+xy^{n-1})\ \ldots\ \fbox2$

while multiplying $\fbox1$ by $y$ gives

$x^ny-y^{n+1}\ =\ (x-y)(x^{n-1}y+x^{n-1}y^2+\cdots+xy^{n-1}+y^n)\ \ldots\ \fbox3$

$\fbox2+\fbox3$ gives

$x^{n+1}+y^{n+1}+x^ny-xy^n\ =\ (x-y)(x^n+2\left[x^{n-1}y+x^{n-2}y^2+\cdots+x^2y^{n-2}+xy^{n-1}\right]+y^n)$

But

$x^ny-xy^n$

$=\ xy(x^{n-1}-y^{n-1})$

$=\ xy(x-y)(x^{n-2}+x^{n-3}y+\cdots+xy^{n-3}+y^{n-2})$

$=\ (x-y)(x^{n-1}y+x^{n-2}y^2+\cdots+x^2y^{n-2}+xy^{n-1})$

Hence the extra terms on both sides should cancel, giving the result we need.

Important note: Because we assumed the result to be true for both $n$ and $n-1$ in order to prove it true for $n+1,$ the whole proof by induction should be completed by showing that the result is true for both $n=1$ and $n=2.$ (Showing that it is true for just $n=1$ is not good enough.)

**Ruun** · October 22nd 2009, 11:12 AM

Hi, thanks for your post.

As you used that the result is true for $n-1$ it's necessary to show that it is true for both $n=2$ and $n=1$ , but it will be in general for $n$ , $n+1$ and $n+2$ for some $n \in \mathbb{N}$ isn't it?

Thread: Factorization induction proof.

LinkBack

Thread Tools

Display

Factorization induction proof.

Similar Math Help Forum Discussions

Abstract prime factorization proof

QR factorization proof

[Factorization] Factorization of Square factors

Mathemtical Induction Proof (Stuck on induction)

Proof with algebra, and proof by induction (problems)

Search Tags