Results 1 to 3 of 3

Math Help - Factorization induction proof.

  1. #1
    Member Ruun's Avatar
    Joined
    Mar 2009
    From
    North of Spain
    Posts
    129
    Thanks
    13

    Factorization induction proof.

    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]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2009
    Posts
    68
    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.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Ruun's Avatar
    Joined
    Mar 2009
    From
    North of Spain
    Posts
    129
    Thanks
    13
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Abstract prime factorization proof
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: September 16th 2010, 06:52 PM
  2. QR factorization proof
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 18th 2010, 07:50 PM
  3. Replies: 2
    Last Post: March 4th 2010, 01:49 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum