2
$\begingroup$

$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i$

(a) I want to find a formula for the above and then prove it by induction. But there is two variable right those are $m$ and $n$. I know that this is true, however I have no idea how to get there. Any hints or ideas on how I should tackle this one?

all this means that

$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i=\sum_{j=0}^n\sum_{i=0}^n\left((m-2)^i\binom{n}i\right)^j\binom{n}j$

3 Answers 3

4

This is a consequence of the binomial theorem, which says that

$(x+y)^n=\sum_{k=0}^n\binom{n}kx^ky^{n-k}\;,\tag{1}$

Set $x=m-1$ and $y=1$, and $(1)$ becomes $m^n=\sum_{k=0}^n\binom{n}k(m-1)^k\;,\tag{2}$ without using induction at all.

Applying this twice, you get

$m^n=\sum_{k=0}^n\binom{n}k(m-1)^k=\sum_{k=0}^n\binom{n}k\sum_{i=0}^k\binom{k}i(m-2)^i\;,$

which can also be written $\sum_{k=0}^n\sum_{i=0}^k\binom{n}k\binom{k}i(m-2)^i\;;$

note, though, that this is a bit different from your second formula.

Here is another proof of $(2)$, also not using induction. Imagine that there are $n$ children in a doughnut shop that sells $m$ kinds of doughnut, and each child buys one doughnut. Since each of the $n$ children can choose any of the $m$ types, they can make their choices in $m^n$ different ways.

Now we’ll use a different method to count the number of ways in which they can choose their doughnuts. One of the kinds of doughnut on offer is plain doughnuts. Suppose that $k$ of the $n$ children do not buy plain doughnuts (and of course the other $n-k$ do buy plain doughnuts). Each of these $k$ children buys one of the $m-1$ fancy varieties of doughnut, so they have $(m-1)^k$ ways to make their choices. Thus, for each $k$ from $0$ through $n$ there are $(m-1)^k$ ways for a particular set of $k$ children to choose fancy doughnuts while the other $n-k$ children buy plain doughnuts. There are $\binom{n}k$ different sets of $k$ children, so for each $k$ from $0$ through $n$ there are $\binom{n}k(m-1)^k$ ways to choose the $k$ children who want fancy doughnuts and let them choose their doughnuts. Since any number of the kids can want the fancy doughnuts, the total number of ways that they can pick their doughnuts is $\sum_{k=0}^n\binom{n}k(m-1)^k\;,$ where the $k$-th term of the sum counts the number of ways if exactly $k$ of the kids want fancy doughnuts.

3

This follows from the binomial theorem: $m^n=(m-1+1)^n=\sum_{i=0}^n \binom{n}{i} (m-1)^i.$

If you really want to do this by induction on $n$, here's your induction step: \begin{align} m^{n+1} &= m\sum_{i=0}^n \binom{n}{i} (m-1)^i \\ &= (m-1+1) \sum_{i=0}^n \binom{n}{i} (m-1)^i \\ &= \sum_{i=0}^n \binom{n}{i} (m-1)^{i+1} + \sum_{i=0}^n \binom{n}{i} (m-1)^i \\ &= \sum_{i=0}^{n+1} \binom{n}{i-1} (m-1)^i + \sum_{i=0}^{n+1} \binom{n}{i} (m-1)^i \\ &= \sum_{i=0}^{n+1} \left[\binom{n}{i-1}+\binom{n}{i}\right] (m-1)^i \\ &= \sum_{i=0}^{n+1} \binom{n+1}{i} (m-1)^i \\ \end{align}

2

Here is a combinatorial proof:

Consider the set of "words" of length $n$ over the alphabet $[m]:=\{1,2,\ldots,m\}$. There are $m^n$ such words.

You can create an arbitrary word by choosing $n-i$ cells, $\ 0\leq i\leq n$, where the letter $m$ should be written and then filling the $i$ empty cells with arbitrary letters from $[m-1]$. The choice is possible in ${n\choose n-i}={n\choose i}$ ways, and for each such choice there are $(m-1)^i$ ways to fill the empty spaces.

Summing it all up you get the stated formula.