Induction

[bodensee9]

Hello:

Can someone provide hints on the following? I am supposed to show that

x^n - y^n is divisible by (x-y), where x and y are integers and y < x.

I got to where I would need to show that

x^(n+1) - y^(n+1) = some K*(x-y).

But I am not sure what to do next?

By brute force I think the division would need to be in the form of x^n + yx^(n-1) ... + y^(n-1)

but how would I show something like that?

Thanks!!

[Dick]

You seem to have a pretty good idea of what the quotient K should be. For example x^3-y^3=(x-y)*(x^2+xy+y^2). Multiply the right side out, x*(x^2+xy+y^2)-y(x^2+xy+y^2)=x^3+x^2y+xy^2-(yx^2+x^2y+y^3). Notice how the extra terms cancel in pairs? Can you generalize that to n>3, as you said almost correctly K=x^(n-1)+x^(n-2)y+x^(n-3)y^2+...+x*y^(n-2)+y^(n-1).

[bodensee9]

oh got it.

I think the middle term would be like + x*y^n - x*y^n and then I can make the equation into

x*(x^n - y^n) + y^n*(x-y) and since x and y are integers, I am done.

Thanks!

[statdad]

What does


x^{n+1} - y^{n+1} = \left(x^{n+1} - x^n\right) + \left(x^n - y^n\right) + \left(y^n - y^{n+1} \right)


do for you?

[Dick]

Yes, the middle terms cancel like that. But there are generally quite a few of them. I don't get the second line at all. x and y don't have to be integers. I hope you understand this better than you are explaining it.

[Dick]

What does


x^{n+1} - y^{n+1} = \left(x^{n+1} - x^n\right) + \left(x^n - y^n\right) + \left(y^n - y^{n+1} \right)


do for you?

Beats me. How does that help? Just curious.