Combinatorial proof of $(k + 1)^{n} = \sum_{i=0}^{n} {n\choose i} k^{i}$

Question

I know that by the Binomial Theorem； $$ (x+y)^n=\sum_{k=0}^n\binom{n}{k} x^{n-k} y^k $$ they should be equal. But how to prove it by Combinatorial proof?

Answer 1

Raising a sum to the n-th power can be thought of combinatorially as making the same choice n times.

Let's say you're trying to write down a string of symbols. Your choice for each symbol is to either write down one of the first k letters of the alphabet, or to draw a smiley face. If you count how many ways there are to do this by considering each of the n symbols independently, you get the left-hand side.

For the right-hand side, first decide where to put the letters and where to put the smileys, then choose what the letters are.

Hope that helps!