Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By Matt Westwood
  • 1 Post By GLaw

Thread: Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?)

  1. #1
    Newbie
    Joined
    Aug 2015
    From
    Montreal
    Posts
    6

    Angry Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?)

    I'm trying to prove that xn+yn is divisible by (x+y), when x and y are integers, and n is a positive, odd integer. I previously proved that xn-yn was divisible by (x-y) with induction, so I figured a similar method would make sense here, but I end up going in circles... this is what I tried:

    Since n is an positive integer:
    xn+yn can be rewritten as x2a+1+y2a+1, where a is a positive integer.

    1) Base case (a=1)
    x3+y3 = (x+y)(x2-xy+y2), and (x2-xy+y2) is an integer, so it is divisible.

    2) Assumption (a=k)
    Assume x2k+1+y2k+1 is divisible by (x+y)

    3) Next 'step' (a=k+1)
    x2(k+1)+1+y2(k+1)+1
    =x2k+3+y2k+3
    = (x2k+1+y2k+1)(x2) - x2y2k+1 + y2k+3
    = (x2k+1+y2k+1)(x2) + (x2k+1+y2k+1)(y2) - x2k+1y2 - x2y2k+1
    = (x2k+1+y2k+1)(x2) + (x2k+1+y2k+1)(y2) - (x+y)(x2ky2) + x2ky3 - x2y2k+1
    = (x2k+1+y2k+1)(x2) + (x2k+1+y2k+1)(y2) - (x+y)(x2ky2) - (x+y)(y2kx2) + x3y2k +x2ky3 ... I tried a bunch more steps/other factors, but nothing seems to be working
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    1,281
    Thanks
    197

    Re: Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?

    It's easier to prove that $x^n - y^n$ has $x - y$ for a factor, then substitute $y \gets -y$ which gets you where you want to.

    Start with: let $\displaystyle S_n = \sum_{j = 0}^{n-1}x^{n - j - i} y^j = \sum_{j = 0}^{n-1}x^j y^{n - j - i}$

    Consider $x \times S_n$ and take the $x^n$ out of the summation (where $j = 0$):

    $\displaystyle x S_n = x^n + \sum_{j = 1}^{n-1}x^{n - j} y^j$

    Do the same with $y \times S_n$:

    $\displaystyle y S_n = y^n + \sum_{j = 1}^{n-1}x^j y^{n - j}$

    Then it's algebra on $(x - y) S_n$ to demonstrate it's equal to $x^n - y^n$.

    I've left out a few steps so as to give you the opportunity of studying it and helping you understand what's going on under the hood.
    Thanks from Wander
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member GLaw's Avatar
    Joined
    Jul 2015
    From
    Ilford
    Posts
    217
    Thanks
    113
    Do you have to use induction? If not, you can do it this way. Treat $y$ as a constant and let $f(x)=x^n+y^n$ be a polynomial in $x$ only. Then $f(-y)=0$ $\implies$ $x+y$ is a factor of $f(x)$.
    Last edited by GLaw; Aug 27th 2015 at 03:24 AM.
    Thanks from Wander
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member rebirth61213's Avatar
    Joined
    Dec 2015
    From
    Worcester, UK
    Posts
    25
    Thanks
    1

    Re: Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?

    Quote Originally Posted by GLaw View Post
    Do you have to use induction? If not, you can do it this way. Treat y as a constant and let f(x)=xn+yn be a polynomial in x only. Then f(−y)=0 ⟹ x+y is a factor of f(x).

    What if n is a positive integer, therefore f(-y) = 2y^n (and not 0)? (since a -ve number to an even power results in a +ve number?)
    Last edited by rebirth61213; Dec 29th 2015 at 01:32 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Wander's Avatar
    Joined
    Mar 2014
    From
    England
    Posts
    166
    Thanks
    93

    Re: Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?

    Quote Originally Posted by rebirth61213 View Post
    What if n is a positive integer, therefore f(-y) = 2y^n (and not 0)? (since a -ve number to an even power results in a +ve number?)
    As per the original post, we're only working with odd integer n, avoiding any such problems.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member rebirth61213's Avatar
    Joined
    Dec 2015
    From
    Worcester, UK
    Posts
    25
    Thanks
    1

    Re: Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?

    Quote Originally Posted by Wander View Post
    As per the original post, we're only working with odd integer n, avoiding any such problems.
    Ah. My apologies, I overlooked this part of the title.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie mekun's Avatar
    Joined
    Jan 2015
    Posts
    20
    Thanks
    2

    Re: Prove that x^n+y^n is divisible by x+y for any positive odd integer n (INDUCTION?

    I proved this problem before in our exam. Use the division algorithm. It is easier that way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Jul 1st 2014, 06:53 PM
  2. Positive integer not divisible by 7
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Jan 15th 2011, 05:51 AM
  3. Replies: 2
    Last Post: Jun 1st 2010, 03:49 AM
  4. Replies: 5
    Last Post: Nov 14th 2009, 04:20 AM
  5. Replies: 2
    Last Post: Oct 14th 2007, 06:32 AM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum