3
$\begingroup$

I'm new to inductive proofs so I need some commentary on my proof since the book only gives a hint in the back. In "Discrete Mathematics with Applications" by Epp Third Edition in section 4.3 problem 13 states

For any integer $ n \ge 1, x^n - y^n$ is divisible by $(x - y)$ where x and y are any integers with $ x \ne y $

My Proof is as follows.

let $ Q(n) = x^n - y^n $

Then the base case is

$ Q(1) = x^1 - y^1 $

Now

$ Q(n + 1) = x^{n+1} - y^{n+1} = (x^n + y^n)(x-y)$

So now we can see $(x-y)$ is a factor and in turn divisible by $(x-y)$. I have just one hesitation. I didn't substitute from the inductive hypotheses. In every other inductive proof I've done this was a necessary step. My intuition on induction tells me that I have basically set up all of the dominoes but failed to knock down the first one (the substitution). Is this necessary for a valid proof or does this hold?

$\endgroup$
8
  • $\begingroup$ Your last equality is false. $(x^n+y^n)(x-y)=x^{n+1}+xy^n-x^ny-y^{n+1}$ $\endgroup$
    – Frank Lu
    May 19 '18 at 6:14
  • $\begingroup$ In your base case, you need to take out "$= 1 - 1 = 0 = 8(0)$". Your TA will take out partial credits when he sees it. $\endgroup$
    – Nobody
    May 19 '18 at 6:33
  • $\begingroup$ @scaaahu I'm not in school. I just do math because I want to understand Donald Knuth. But just out of curiosity why would they do that? Edit: Wait no. I see it. $\endgroup$ May 19 '18 at 6:37
  • $\begingroup$ What do you mean by "why would they do that?" do what? $\endgroup$
    – Nobody
    May 19 '18 at 6:40
  • $\begingroup$ @scaaahu Why would they mark me off. But never mind I see the error now. $\endgroup$ May 19 '18 at 6:45
7
$\begingroup$

Your factorisation is incorrect. Use $x^{n+1}-y^{n+1}=x(x^n-y^n)+y^n(x-y)$.

$\endgroup$
2
  • $\begingroup$ So if I'm understanding you correctly the substitution happens inside the term $ x(x^n - y^n) $ which would be $x(x-y) + y^n(x-y)$ ? Then I could proceed to factor or am I missing a factoring technique in my tool belt? $\endgroup$ May 19 '18 at 6:26
  • $\begingroup$ You do indeed use the inductive step to verify $x-y|x^n-y^n$, although the expression you wrote after that isn't right. $\endgroup$
    – J.G.
    May 19 '18 at 7:17
3
$\begingroup$

Non-Inductive Proof (or so I thought).


Proof: Suppose there exists $z$ such that $$x^n-y^n = z(x-y).$$ This would imply that $z=\dfrac{x^n-y^n}{x-y}$. Now, here comes the trick: $$\frac{x^n-y^n}{x-y} = \frac{x^{n-1}(x-y)+yx^{n-1}-y^n}{x-y}=x^{n-1}+y\left(\frac{x^{n-1}-y^{n-1}}{x-y}\right).$$ Continuing in the same way, it follows that $$x^{n-1}+y\left(\frac{x^{n-1}-y^{n-1}}{x-y}\right)=x^{n-1}+yx^{n-2}+y\left(\frac{x^{n-2}-y^{n-2}}{x-y}\right)=\cdots$$ to which a pattern can be noticed, namely, $$z=\sum_{k=1}^nx^{n-k}y^{k-1}\tag*{$\bigcirc$}$$


I decided to not do an inductive proof in order to explore a different way of tackling this problem :)

Edit: Turns out, it is an inductive proof, but it just skips the base case and is differently worded than usual. Credit to @J.G. who pointed that out :)

$\endgroup$
6
  • 2
    $\begingroup$ That's still induction. $\endgroup$
    – J.G.
    May 19 '18 at 8:05
  • $\begingroup$ @J.G. what do you mean? I have not used a base case, inductive hypothesis, or an inductive step. I just cleverly rewrote the numerator. $\endgroup$
    – Mr Pie
    May 19 '18 at 8:08
  • 1
    $\begingroup$ "It terminates like this" is your inductive hypothesis. $\endgroup$
    – J.G.
    May 19 '18 at 8:11
  • $\begingroup$ @J.G. hah... I didn't realise. Looks like it is an inductive proof. Is there a way of proving the assertion with-out the use of induction, do you know? $\endgroup$
    – Mr Pie
    May 19 '18 at 8:13
  • 2
    $\begingroup$ I don't think so. I'm sure someone would suggest "use the factor theorem", but the proof of that probably requires induction on the degree of polynomials. My favourite on-SE discussion of what constitutes induction is math.stackexchange.com/a/1359020 $\endgroup$
    – J.G.
    May 19 '18 at 8:20
2
$\begingroup$

Following the suggestion by J.G., for the induction step we assume true that

  • $Q(n) = x^{n} - y^{n} = p_{n-1}(x)\cdot (x-y)$

were $p_{n-1}(x)$ is a polynomial of degree $n-1$ then

  • $Q(n+1) = x^{n+1} - y^{n+1} = x\cdot(x^n-y^n)+y^n(x-y)=x\cdot\,\color{red}{p_{n-1}(x)\cdot(x-y)}+y^n(x-y)=p_n(x)\cdot(x-y)$
$\endgroup$
3
  • $\begingroup$ I don't quite follow the notation you are using. Epp simply uses the variable r when using the inductive hypotheses for divisibility. Would this also be valid if? so then I think I proved it successfully on paper just before I logged on today. $ xr(x-y) + y^n(x-y) = (xr+y^n)(x-y) $ $\endgroup$ May 19 '18 at 22:01
  • $\begingroup$ Also Epp states that r is an integer. Sorry. $\endgroup$ May 19 '18 at 22:08
  • $\begingroup$ @PossiblyDakota $p_{n-1}(x)$ and $p_n(x)$ are just polynomials of degree $n−1$ and $n$ in $x$ and $y$ thus they can be also indicated as some integer $r_1$ and $r_2$. It is a minor issue in the proof. $\endgroup$
    – user
    May 19 '18 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.