Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove the following: $\displaystyle a^{n}-b^{n} = (a-b) \sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}$.

So one could use induction on $n$? Could one also use trichotomy or some type of combinatorial argument?

share|improve this question

7 Answers 7

up vote 13 down vote accepted

I have no idea what you mean by "use trichotomy," but here is the combinatorial argument. $a^n$ counts the number of words of length $n$ on the alphabet $\{ 1, 2, ... a \}$ and $b^n$ counts the number of words of length $n$ on the alphabet $\{ 1, 2, ... b \}$. Assume $a > b$. Then $a^n - b^n$ counts the number of words of length $n$ on the alphabet $\{ 1, 2, ... a \}$ such that at least one letter is greater than $b$.

Given such a word, suppose the last letter greater than $b$ occurs at position $k+1$. Then there are $a - b$ choices for this letter, $a^k$ choices for the letters before this letter, and $b^{n-k-1}$ choices for the letters after this letter. Thus there are $(a - b) a^k b^{n-k-1}$ such words, and summing over all $k$ gives

$$a^n - b^n = (a - b) \sum_{k=0}^{n-1} a^k b^{n-k-1}$$

as desired.

share|improve this answer
1  
+1 - Very clear, thank you. –  Hans Parshall Nov 24 '10 at 1:47
    
I meant could you show that $\text{LHS} \leq \text{RHS}$ and $\text{RHS} \leq \text{LHS}$? –  PEV Nov 24 '10 at 1:54
1  
@Trevor: I don't really see the point. This is not an analytic statement, it is purely a formal algebraic statement and holds in situations where there is no order to speak of. Any proof along those lines sounds like much more effort than it's worth; those kinds of proofs are generally reserved for situations where the LHS or RHS (or both) is itself defined by what it is greater than or less than, e.g. it is some kind of supremum. –  Qiaochu Yuan Nov 24 '10 at 2:06

Someone should mention the "polynomial multiplication" or "telescoping" proof, which may be viewed as a variant of the "geometric series" method.

$$\begin{align*} (a-b)\sum_{k=0}^{n-1} a^k b^{n-1-k} &= \sum_{k=0}^{n-1} a^{k+1} b^{n-1-k} - \sum_{k=0}^{n-1} a^k b^{n-k} \\ &= \sum_{k=1}^n a^k b^{n-k} - \sum_{k=0}^{n-1} a^k b^{n-k} = a^n - b^n. \end{align*}$$

share|improve this answer

EDIT

Proof by induction

$n=1$ is valid.

Supose valid by n, then

$$a^{n+1}-b^{n+1}=a(a^{n})+b(b^{n})$$, using the hipotesis :

$$a(a^{n})+b(b^{n})=a\left[b^{n}+(b-a)\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}\right] + b\left[a^{n}-(b-a)\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}\right]=$$

$$\left[ab^{n}+(b-a)a\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}\right] + \left[a^{n}b-(b-a)b\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}\right]=$$

$$\left[ab^{n}+(b-a)\displaystyle\sum\limits_{k=0}^{n-1} a^{k+1}b^{n-1-k}\right] + \left[a^{n}b-(b-a)\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-k}\right]=$$

$$\left[ab^{n}+(b-a)\displaystyle\sum\limits_{k=0}^{n-1} a^{k+1}b^{n-1-k}+(b-a)b^{n}-(b-a)b^{n}\right] +$$ $$ \left[a^{n}b-(b-a)\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-k}-(b-a)a^{n}+(b-a)a^{n}\right]=$$

$$\left[(b-a)[\displaystyle\sum\limits_{k=0}^{n-1} a^{k+1}b^{n-1-k}+b^{n}]+b^{n+1}\right] +\left[(b-a)[\displaystyle\sum\limits_{k=0}^{n-1} a^{k}b^{n-k}+a^{n}]-a^{n+1}\right] +$$

$$\left[(b-a)\displaystyle\sum\limits_{k=0}^{n} a^{k}b^{n-k}+b^{n+1}\right] +\left[(b-a)\displaystyle\sum\limits_{k=0}^{n} a^{k}b^{n-k}-a^{n+1}\right] =$$

$$-a^{n+1}+b^{n+1}+2\left[(b-a)\displaystyle\sum\limits_{k=0}^{n} a^{k}b^{n-k}\right] =$$

Thus: $$a^{n+1}-b^{n+1}=-a^{n+1}+b^{n+1}+2\left[(b-a)\displaystyle\sum\limits_{k=0}^{n} a^{k}b^{n-k}\right] $$, then

$$2(a^{n+1}-b^{n+1})=2\left[(b-a)\displaystyle\sum\limits_{k=0}^{n} a^{k}b^{n-k}\right]$$

thus:

$$a^{n+1}-b^{n+1}=\left[(b-a)\displaystyle\sum\limits_{k=0}^{n} a^{k}b^{n-k}\right]$$

So $n+1$ is valid.

Complete the proof

share|improve this answer
2  
The inductive proof is much easier than this. It suffices to verify that (a^n - b^n)a = a^{n+1} - ab^n = (a^{n+1} - b^{n+1}) - (a - b) b^n. –  Qiaochu Yuan Nov 24 '10 at 14:15

You can apply Ruffini's rule. Here is a copy from my Algebra text book (Compêndio de Álgebra, VI, by Sebastião e Silva and Silva Paulo) where the following formula is obtained:

$x^n-a^n\equiv (x-a)(x^{n-1}+ax^{n-2}+a^2x^{n-3}+\cdots +a^{n-2}x+a^{n-1}).$

alt text

Translation: The Ruffini's rule can be used to find the quotient of $x^n-a^n$ by $x-a$:

(Figure)

Thus, if $n$ is a natural number, we have

$x^n-a^n\equiv (x-a)(x^{n-1}+ax^{n-2}+a^2x^{n-3}+\cdots +a^{n-2}x+a^{n-1})$

share|improve this answer
1  
"Ruffini's rule" is probably more famously known as Horner's rule. –  J. M. Nov 24 '10 at 11:51
    
J.M., That I didn't know. Paolo Ruffini (1765-1822) was an Italian doctor and mathematician. –  Américo Tavares Nov 24 '10 at 11:57
2  
I've heard it called "Ruffini's rule", but as I said, "Horner" is the more well-known alias. Another term you'll encounter is "synthetic division", as indeed the efficient (numerical) evaluation of a polynomial and the division of a polynomial by a linear factor is solved by one and the same algorithm. –  J. M. Nov 24 '10 at 12:07

Can we build a combinatorial argument along these lines?

Say if we have say $n$ students to be allotted in $a$ rooms with $b$ of the $a$ room being non air-conditioned. (Assume the students are distinguishable so we can order the student as $1,2,3,...,n$)

The total number of ways is $a^n$.

Suppose all students are allotted to the $b$ rooms, the number of ways is $b^n$.

If the first $n-1$ students are allotted to the $b$ rooms, and the final dude in some other room, the number of possible ways is $b^{n-1} \times (a-b)$.

Now if the first $n-2$ students are allotted to the $b$ rooms, and the remaining two students are now left. If the $(n-1)^{th}$ student chooses from the $b$ rooms then we are back to the earlier case. So the $(n-1)^{th}$ student needs to choose from the remaining $(a-b)$ rooms. Now the $n^{th}$ student can choose from any of the $a$ rooms. The number of possible ways is $b^{n-2} \times (a-b) \times a$.

In general, if the first $n-k$ students are allotted to the $b$ rooms, and the remaining $k$ students are now left. If the $(n-k+1)^{th}$ student chooses from the $b$ rooms then we are back to the previous case. So the $(n-k+1)^{th}$ student needs to choose from the remaining $(a-b)$ rooms. Now the students from $(n-k+2)$ to $n$ can choose from any of the $a$ rooms. The number of possible ways is $b^{n-k} \times (a-b) \times a^{k-1}$.

So, the total number of ways is $b^n + \displaystyle \sum_{k=1}^n b^{n-k} \times (a-b) \times a^{k-1}$.

Both the counting must add up and hence we get $a^n = b^n + \displaystyle \sum_{k=1}^n b^{n-k} \times (a-b) \times a^{k-1}$.

You could use geometric series to conclude the result as well.

The right hand side is $(a-b) b^{n-1} \displaystyle \sum_{k=0}^{n-1} (\frac{a}{b})^k = (a-b) b^{n-1} \frac{((\frac{a}{b})^n - 1)}{(\frac{a}{b})-1} = (a-b) \frac{a^n - b^n}{a-b} = a^n - b^n$

share|improve this answer
    
You beat me to it! :) –  J. M. Nov 24 '10 at 1:26
1  
The statement is just the bivariate homogenization of $\ f(a) = \sum_{i=0}^n\: a^i\ $ i.e. $\ f(a/b)\ b^n\ $ which, conversely, is dehomogenized via $ b\to 1\:$. –  Bill Dubuque Nov 24 '10 at 1:46

Yes, you could use induction on n. I don't see an easy trichotomy or combinatorial argument.

share|improve this answer

If you know the sum of a geometric sequence, then set $x=a/b$ and conclude $ x^n-1 = (x-1)(1+x+x^2+\cdots+x^{n-1}) $. Now multiply by $b^n$. (If $b=0$, then the identity is obvious.)

share|improve this answer
3  
This argument has essentially already been given twice. –  Qiaochu Yuan Nov 24 '10 at 14:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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