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

1. ## 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

2. ## 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.

3. 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)$.

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

Originally Posted by GLaw
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?)

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

Originally Posted by rebirth61213
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.

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

Originally Posted by Wander
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.

7. ## 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.

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# prove that x^n-y^n is divisible by x-y

Click on a term to search for related topics.