Intereting Posts

Prove by induction that $\sum_{i=1}^{2^n} \frac{1}{i} \ge 1+\frac{n}{2}, \forall n \in \mathbb N$
Is it possible to determine if you were on a Möbius strip?
Action of $S_7$ on the set of $3$-subsets of $\Omega$
Why $(\mathbb Q\times\mathbb Q)/(\mathbb Z\times{=})$ is not homeomorphic to $(\mathbb Q/\mathbb Z)\times(\mathbb Q/{=})$?
I still forget concepts even after answering numerous math problems
Injective, surjective and bijective for linear maps
Non-Decreasing Digits
Similar matrices and field extensions
Generalised Binomial Theorem Intuition
Is a height one ideal in a UFD principal?
On inequalities for norms of matrices
compact Hausdorff space and continuity
Help me to simplify $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}$
Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$.
Proof by Induction: $\sum_0^nx^i=(1-x^{n+1})/(1-x)$

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?

- Functional equation $P(X)=P(1-X)$ for polynomials
- Confused about the $\pm$ sign?
- What's $(-1)^{2/3}\; $?
- How to understand proof of a limit of a function?
- Integer solutions of the equation $x^2+y^2+z^2 = 2xyz$
- construct polynomial from other polynomials

- Computing $x^{2017}+\frac1{x^{2017}}$ given the value of $x+\frac1x$.
- Is this Batman equation for real?
- What is the square of summation?
- Rationalize $\left(\sqrt{3x+5}-\sqrt{5x+11} -\sqrt{x+9}\right)^{-1}$
- Domain of a function
- The number of ones in a binary representation of an integer
- An elegant way to solve $\frac {\sqrt3 - 1}{\sin x} + \frac {\sqrt3 + 1}{\cos x} = 4\sqrt2 $
- Equation of angle bisector, given the equations of two lines in 2D
- Please guide me to draw this : graph of $x \geq 5$ and $y \geq 5$
- How do you define functions for non-mathematicians?

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.

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*}$$

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

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}).$

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})$

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

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$

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.)

- Prove: The weak closure of the unit sphere is the unit ball.
- Why abstract manifolds?
- Let $X$ be a Moore space and $e(X)=\omega$. Is it metrizable?
- Invariance of strategy-proof social choice function when peaks are made close from solution
- Why is gradient the direction of steepest ascent?
- Is every sub-lattice of $\mathcal P(X)$ isomorphic to a sub-lattice of $\mathcal P(X')$ containing singleton sets?
- Can the Jacobi symbol be defined for negative numbers?
- Let $H$ be a normal subgroup of index $n$ in a group $G$. Show that for all $g \in G, g^n \in H$
- The commutator subgroup of a quotient in terms of the commutator subgroup and the kernel
- Evaluating $\int_a^b \arccos\left(x\,/\sqrt{(a+b)x-ab\,}\,\right)\,\mathrm {d}x$ assuming $0<a<b$
- volume of a truncated cone that is not a frustum
- What is the difference between Cartesian and Tensor product of two vector spaces
- Space of Complex Measures is Banach (proof?)
- Is it possible to use mathematical induction to prove a statement concerning all real numbers, not necessarily just the integers?
- Show that there is a positive integer $n$ such that $G \cong \ker(\phi^{n}) \times \phi^{n}(G)$