How would I prove this by induction?

[tony700]

How would I prove this by induction?

$$\sum_{k=0}^n\frac{n!}{n^kk!(n-k)!}=\frac{(n+1)^n}{n^n}$$

 

[MarkFL]

I would begin by writing the induction hypothesis as:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}\frac{1}{n^k}\right)=\left(1+\frac{1}{n}\right)^n\)

We can see this is simply a statement of a particular case of the binomial theorem. As such, we will find the following 3 identities useful:

[box=blue]\(\displaystyle {r \choose 0}=1\tag{1}\)

\(\displaystyle {r \choose r}=1\tag{2}\)

\(\displaystyle {k \choose r}+{k \choose r-1}={k+1 \choose r}\tag{3}\)

where $(k,r)\in\mathbb{N}$ and $r\le k$[/box]

So, the first thing we want to do is show the base case $P_1$ is true:

\(\displaystyle \sum_{k=0}^1\left({1 \choose k}\frac{1}{1^k}\right)=\left(1+\frac{1}{1}\right)^1\)

We can see this simplifies to:

\(\displaystyle 2=2\quad\checkmark\)

So, we restate our induction hypothesis $P_n$:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}\frac{1}{n^k}\right)=\left(1+\frac{1}{n}\right)^n\)

What do you suppose our induction step should be?