Proving difference of two powers using induction

Question

Prove, that $\forall n \in \mathbb{N}$ the following identity holds: $$a^n - b^n = (a-b)\sum_{k=0}^{n-1} a^k b^{n-k-1}.$$

---

For $n = 1$ we get $a^1 - b^1 = a - b$ on LHS, and on RHS we get $(a-b)\sum_{k=0}^{0}a^k b^{n-k-1} = a-b.$ Both sides are equal, so identity hold for $n = 1$.

---

Assume that for $m \in \mathbb{N}, n = m$ identity is generally true. For $m = n+1$ we get: $$(a-b)\sum_{k=0}^{m}a^k b^{m-k}.$$ Multiplying and distributing we get: $$\sum_{k=0}^{m}a^{k+1}b^{m-k} - \sum_{k =0}^{m}a^k b^{m-k+1}.$$

What shall I do after the last step? Is there some rule/identity, which I can use?

Answer 1

You can re-index the first sum in your last expression. If you decrease $k$ by one in the summand, you can pay for it by increasing the limits. So you'd get $$\sum_{k=1}^{m+1} a^kb^{m-k} - \sum_{k=0}^{m} a^kb^{m-k}.$$

Now if you separate the last term of the first sum and the first term of the second sum you have:

$$a^{m+1}b^0+ \sum_{k=1}^{m} a^kb^{m-k} - \sum_{k=1}^{m} a^kb^{m-k}-a^0b^m.$$

And the two summations cancel.

Answer 2

To prove that $$b^n-a^n =(b-a)\sum_{k=0}^{n-1}b^ka^{n-1-k}$$ It suffices to show that $$b^n-1 = (b-1)\sum_{k=0}^{n-1}b^k,$$ as follows: $$\begin{align} (b-1)\sum_{k=0}^{n-1}b^k &=b\sum_{k=0}^{n-1}b^k-\sum_{k=0}^{n-1}b^k\\ &=\sum_{k=0}^{n-1}b^{k+1}-\sum_{k=0}^{n-1}b^k\\ &=\sum_{k=1}^{n}b^{k}-\sum_{k=0}^{n-1}b^k\\ &=b^{n}-1\\ \end{align}$$

Answer 3

Using induction hypothesis for $n$, we have $$a^{n+1}-b^{n+1}=a(a^n-b^n)+(a-b)b^n=(a-b)\left[a\sum_{i+j=n-1}a^ib^j\right]+(a-b)b^n$$ $$a^{n+1}-b^{n+1}=(a-b)\left[a^n+a^{n-1}b+.....+b^n\right]=(a-b)\sum_{i+j=n}a^ib^j$$