How can you prove Spivak's Calculus problem without using induction?

[dabd]

Homework Statement

I am attempting to solve the problems in chapter 1 - Basic Properties of Numbers from Spivak's book.

Problem 1(v) asks the student to prove that
x^n - y^n = (x - y)(x^(n - 1) + (x^(n - 2))y + ... + x(y^(n - 2)) + y^(n - 1))

Homework Equations

The Attempt at a Solution

I solved it by using induction, but induction is not taught until later in the book.
I assume you can solve the exercises solely using the material in the previous chapters, or the hints in the exercise.
After repeatedly applying P9 (distributive law of multiplication) it is obvious that all the terms cancel, except for the first and the last, but proofs with elipses (..) don't strike me as rigorous. So, how can you prove this without using induction?

Thanks

 

[AlephZero]

If you multiply out the right hand side, all the terms cancel in pairs except x^n and y^n. That doesn't involve induction.

You can't explicitly write all the terms in the general case, so you are forced to use some notation like "...". You could write something like
$$(x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i$$
if you feel "..." is a too informal, but remember the main point of notation is to communicate, not to be rigorous for its own sake.

 

[dabd]

If you multiply out the right hand side, all the terms cancel in pairs except x^n and y^n. That doesn't involve induction.

You can't explicitly write all the terms in the general case, so you are forced to use some notation like "...". You could write something like
$$(x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i$$
if you feel "..." is a too informal, but remember the main point of notation is to communicate, not to be rigorous for its own sake.

Thanks for the reply.
Do you think it is incorrect to use induction in this proof? I agree it is more direct to expand the right hand side, though.
BTW, I am a newbie here, where do I find help for the tex notation for writing formulas in posts like you did with the summation?

Thanks.

 

[AlephZero]

Can you explain how you used induction to prove this? Then somebody can comment on what you did.

Induction is a perfectly acceptable way to proove things, unless you are doing a homework question which explicitly says "don't use it" of course.

Re Tex, look at the "sticky" threads on the forums, one of them is an introduction to Latex. Also, if you click on a Latex image in a post, you get a pop-up window showing the source code, which is a good learning tool as well a help when doing cut-and-paste editing.

 

[dabd]

Can you explain how you used induction to prove this? Then somebody can comment on what you did.

Induction is a perfectly acceptable way to proove things, unless you are doing a homework question which explicitly says "don't use it" of course.


Re Tex, look at the "sticky" threads on the forums, one of them is an introduction to Latex. Also, if you click on a Latex image in a post, you get a pop-up window showing the source code, which is a good learning tool as well a help when doing cut-and-paste editing.

Here is my induction proof attempt:
$$Let P(n) = x^{n} - y^{n} = (x - y)(x^{n-1} + x^{n-2}y + \dots + x y^{n-2} + y^{n-1})$$

$$For n = 1$$:
$$The equality is trivial.$$
$$P(1) = x^{1} - y^{1} = (x - y)$$

$$if P(n) is true then$$
$$P(n+1) = (x - y)(x^{n} + x^{n-1}y + \dots + x y^{n-1} + y^{n}) =$$
$$(x - y)(x^{n} + y(x^{n-1} + \dots + x y^{n-2} + y^{n-1})) =$$
$$(x - y)x^{n} + y(x-y)(x^{n-1} + \dots + x y^{n-2} + y^{n-1}) =$$
$$(x - y)x^{n} + y P(n) =$$
$$(x - y)x^{n} + y(x^{n} - y^{n}) =$$
$$x^{n+1} - y^{n+1}$$
QED

(Sorry but I couldn't format the post properly.
I will read the sticky thread about LaTex when I have more time.)

 

[ZioX]

Use ^{n-1} to get the whole thing superscripted.

 

[dabd]

Use ^{n-1} to get the whole thing superscripted.

How do I put line breaks? I get all equalities on the same line...

 

[AlephZero]

That looks OK - though it seems like more work than just multiplying the terms and cancelling them.

A few of LaTex tips BTW:

(1) Things like superscripts and subscripts will only contain a single character unless you use { } brackets. The { and } don't appear in the generated equation. In other words, x^n-1 and x^{n-1} mean different things, and you wanted x^{n-1}.

(2) If you have several lines of equation, use several different TeX expressions. Otherwise, the result is too wide to fit on the page.

(3) You don't need to use "*" for multiplication, TeX will format the equation in the conventional maths style without it.

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

I also fixed a typo in your original proof

 

[dabd]

That looks OK - though it seems like more work than just multiplying the terms and cancelling them.

A few of LaTex tips BTW:

(1) Things like superscripts and subscripts will only contain a single character unless you use { } brackets. The { and } don't appear in the generated equation. In other words, x^n-1 and x^{n-1} mean different things, and you wanted x^{n-1}.

(2) If you have several lines of equation, use several different TeX expressions. Otherwise, the result is too wide to fit on the page.

(3) You don't need to use "*" for multiplication, TeX will format the equation in the conventional maths style without it.

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

I also fixed a typo in your original proof

Thanks :-)

 

[razored]

If you multiply out the right hand side, all the terms cancel in pairs except x^n and y^n. That doesn't involve induction.

You can't explicitly write all the terms in the general case, so you are forced to use some notation like "...". You could write something like
$$(x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i$$
if you feel "..." is a too informal, but remember the main point of notation is to communicate, not to be rigorous for its own sake.

I am having the same problem. Is there an easier way to write it without i's ? You wrote : $$(x-y)\sum_{i=0}^{n-1}x^{n-1-i}y^i$$ When I did the proof, I simply wrote the that the ... signifies the middle terms that are simply inverses of each other and cancel out.