5
$\begingroup$

A short disclaimer: I do know this question has been asked multiple times here and several answers (including combinatorics) have been given already. However, among all these posts, I did not find anywhere the answer by induction (as I have it understood) and hence, I thought to ask here for verification.

One should prove the following: $a^{n}-b^{n} = (a-b) \sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k} \quad (\star)$

Proof:

$1^{\text{st}}$ Step: For $n=1$ it holds.

Induction Step: We assume that $(\star)$ is true for $n$. In order to show, that it is also valid for $n+1$, we calculate

$a^{n+1}-b^{n+1}=a^n\cdot a-b^n\cdot b=a^n\cdot a-b^n\cdot a+b^n\cdot a-b^n\cdot b$

$=(a^n-b^n)a+b^n(a-b)\qquad \text{at this point we use } (\star)$

$=a(a-b)(a^{n-1}+ba^{n-2}+b^2a^{n-3}+\dots+b^{n-2}a+b^{n-1})+b^n(a-b)$

$=(a-b)(a^{n}+ba^{n-1}+b^2a^{n-2}+\dots+b^{n-2}a^2+b^{n-1}a+b^n)$

Does this suffice as a proof? Or, is there any mistake in the induction step that I don't see right now?

Many thanks in advance!

$\endgroup$
6
  • $\begingroup$ "Does this suffice as a proof? " No, you didn't say where you exactly used the induction hypothesis (although it is clear of course). Also the induction hypothesis is written with $\sum_k$, whereas you apply it without writing a sum symbol (which again is not important, of course, but just a bit inconsistent). $\endgroup$ Commented Nov 18, 2022 at 12:57
  • $\begingroup$ @DietrichBurde Fair enough. I'll edit $\endgroup$ Commented Nov 18, 2022 at 12:58
  • 1
    $\begingroup$ It's fine, although I don't see why you need induction: you can just expand the right-hand side of $(*)$ and cancel most of the terms to show that it equals the left-hand side. $\endgroup$ Commented Nov 18, 2022 at 13:06
  • 3
    $\begingroup$ @AdamRubinson The exercise is required to be solved by induction...in any case, thank you! $\endgroup$ Commented Nov 18, 2022 at 13:11
  • $\begingroup$ This post uses induction: math.stackexchange.com/questions/900739/… $\endgroup$ Commented Feb 16, 2023 at 2:36

0

You must log in to answer this question.

Browse other questions tagged .