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:

$$\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]$${r \choose 0}=1\tag{1}$$

$${r \choose r}=1\tag{2}$$

$${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:

$$\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:

$$2=2\quad\checkmark$$

So, we restate our induction hypothesis $P_n$:

$$\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?