Combinatorial Proof of an Instance of the Binomial Theorem Give a combinatorial proof of the following instance of the binomial theorem. For any positive integer $k$,
$$
(k + 1)^{n} = \sum\limits_{i=0}^{n} {n\choose i} k^{i} \;.
$$
I have looked at this for some time and have no idea how to compare the two equalities.
 A: First notice that $(k + 1)^{n}$ is the number of $n$-digit integers written in base $k+1$, allowing for leading zeroes. (For example, there are $1000=(9+1)^3$ three-digit numbers in base $10$: $000, 001,\dots,$ and $999$.
Now count those same integers in a different way.
First count those that don’t use the digit zero at all. There are $k^n$ of them (because there are $k$ non-zero digits to choose from for each of the $n$ digits).
Next, count those that use exactly one zero. There are $n$ positions for the zero, and given a position for the zero, there are $k^{n-1}$ ways to fill in the other digits, so there are $n\cdot k^{n-1}$ different $n$-digit integers in base $k+1$ with exactly one (possibly leading) zero.
Now count those with exactly two zeros. There are $\binom{n}{2}$ ways to position the two zeros, and once the two zeros are in place, there are $k^{n-2}$ ways to put one of the $k$ non-zero digits in each of the other positions. 
Continuing this way up to the maximum number of zeroes in an $n$-digit number ($n$), the total number of $n$-digit numbers in base $k+1$, using any number of zeroes, is $$1\cdot k^n + n\cdot k^{n-1}+\binom{n}{2}k^{n-2}+\cdots \binom{n}{n-1}k^1 + \binom{n}{n}\cdot1$$ in all. Rewriting $n$ in the second term as $\binom{n}{1}$ and $1$ as $\binom{n}{0}$ in the first term and as $k^0$ in the last term, this sum is 
$$\binom{n}{0}\cdot k^n + \binom{n}{1}\cdot k^{n-1}+\binom{n}{2}k^{n-2}+\cdots \binom{n}{n-1}k^1 + \binom{n}{n}k^0,\mbox{ or, in reverse,}$$
$$\binom{n}{n}\cdot k^0 + \binom{n}{n-1}\cdot k^{1}+\cdots\binom{n}{2}k^{n-2}+\cdots \binom{n}{1}k^{n-1} + \binom{n}{0}k^n,$$ which is $\sum_{i=0}^n\binom{n}{n-i}k^{i}$. However, since $\binom{n}{n-i}=\binom{n}{i}$, this is also equal to $\sum_{i=0}^n\binom{n}{i}k^{i}$.
Then the total number of $n$-digit integers written in base $k+1$ is $\sum_{i=0}^n\binom{n}{i}k^{i}$, but from the very first observation, there are also $(k+1)^n$ of them, so 
$$(k+1)^n = \sum_{i=0}^n\binom{n}{i}k^{i}.$$
A: In $(k+1)^n = \underbrace{(k+1) * \cdots * (k+1)}_n$ you will get a sum of single terms like $k^l$. The idea is to calculate how many times each $k^l$ appears in the sum.
The ways of taking $l$ factors "$k$" out of a total of $n$ factors is $\binom{n}{i}$.
For example, using distributive law  $(k+1)^3 = (k+1) * (k+1) * (k+1) = k*k*k + k*k*1 + k*1*k + k*1*1 +  1*k*k + 1*k*1 + 1*1*k + 1*1*1$, where I explicitely show which term, $1$ or $k$, I take from each $(k+1)$ factor. Given that the order of the factors doesn't matter, terms like $k^2$($=1*k*k = k*1*k$) will appear several times, exactly given by the binomial coefficient.
A: You can try prove this by mathematical induction. If n=1 then  $(a+b)=\sum_{i=0}^{1} {{1}\choose{i}} a^{1-i}b^{i}$. Now we guess that is true for $n=k$ this is: 
$$(a+b)^k=\sum_{i=0}^{k} {{k}\choose{i}} a^{1-i}b^{i}$$
and now we should prove that is true for $n=k+1$. Then we can start by: 
$$(a+b)^{k+1}=(a+b)(a+b)^k= (a+b)\sum_{i=0}^{k} {{k}\choose{i}} a^{k-i}b^{i}$$
With a little algebra we can write: 
\begin{align}(a+b)^{k+1} &=&{{k}\choose{0}}a^{k+1}+\sum_{i=1}^{k} {{k}\choose{i}} a^{k+1-i}b^{i}+\sum_{i=1}^{k} {{k}\choose{i-1}} a^{k+1-i}b^{i}+{{k}\choose{k}}b^{k+1}\\
&=&{{k}\choose{0}}a^{k+1}+\sum_{i=1}^{k} \Big[{{k}\choose{i}}+ {{k}\choose{i-1}}\Big] a^{k+1-i}b^{i}+{{k}\choose{k}}b^{k+1} \\
&=&{{k}\choose{0}}a^{k+1}+\sum_{i=1}^{k} {{k+1}\choose{i}} a^{k+1-i}b^{i}+{{k}\choose{k}}b^{k+1}\\
&=& \sum_{i=0}^{k+1} {{k+1}\choose{i}} a^{k+1-i}b^{i}.\end{align}
This prove the afirmation.
A: If you look at :
$$(X+1)^n=(X+1)...(X+1) $$
Then it is a product of the sum of two terms :
$$(a_1+b_1)(a_2+b_2)...(a_n+b_n) $$
any term in the distribution will look like :
$$c_1\times c_2\times ...\times c_n $$
where $c_i$ is either $a_i$ or $b_i$. In other terms :
$$(a_1+b_1)(a_2+b_2)...(a_n+b_n)=\sum_{(c_1,...,c_n)\in \{a_1,b_1\}\times...\times \{a_n,b_n\}}c_1\times c_2\times...\times c_n $$
So developping this kind of sum always look something like this. Now in our particular case : $a_i=X$ and $b_i=1$ for all $i$. Hence the sum become :
$$(X+1)^n=\sum_{(c_1,...,c_n)\in \{X,1\}^n}c_1\times c_2\times...\times c_n $$
Now $c_1\times ...\times c_n$ for $(c_1,...,c_n)\in \{X,1\}^n$ just depends on the number of $X$ in $(c_1,...,c_n)$ let us call this number $f(c_1,...,c_n):=$ number of $X$ in $(c_1,...,c_n)$. Then : 
$$c_1\times ...\times c_n=X^{f(c_1,...,c_n)} $$
We can now write in a new form our sum :
$$(X+1)^n=\sum_{(c_1,...,c_n)\in \{X,1\}^n}c_1\times c_2\times...\times c_n=\sum_{k=0}^n\sum_{(c_1,...,c_n)\in \{X,1\}^n\text{ and } f(c_1,...c_n)=k}X^k $$
Finally :
$$(X+1)^n=\sum_{k=0}^nX^k\sum_{(c_1,...,c_n)\in \{X,1\}^n\text{ and } f(c_1,...c_n)=k}1 $$
$$(X+1)^n=\sum_{k=0}^n|\{(c_1,...,c_n)\in \{X,1\}^n|f(c_1,...c_n)=k\}|X^k $$
So it suffices to count the number of elements in $A_k$ where :
$$A_k:=\{(c_1,...,c_n)\in \{X,1\}^n|f(c_1,...c_n)=k\}$$
But it is easy to do this :
$$A_k\rightarrow \mathcal{P}_k(\{1,...,n\}) $$
$$(c_1,...,c_n)\mapsto \{1\leq i\leq n | c_i=X\} $$
has for inverse :
$$\mathcal{P}_k(\{1,...,n\})\rightarrow A_k$$
$$S\mapsto (X\chi_S(i)+(1-\chi_S(i)))_{1\leq i\leq n}  $$
So those are bijections and :
$$|A_k|=|\mathcal{P}_k(\{1,...,n\})|=\begin{pmatrix}n\\ k\end{pmatrix} $$
So :
$$(X+1)^n=\sum_{k=0}^n\begin{pmatrix}n\\ k\end{pmatrix}X^k $$
A: Here is a combinatorial proof in terms of functions: First, note that you can describe the set of partial functions from $N$ to $K$ as
\begin{align}
N \rightarrow (K \cup \{\mathsf{undefined}\})
\end{align}
where $\mathsf{undefined} \not\in K$ is a special value indicating that the function is undefined a given input. The cardinality of this set is
\begin{align}
|N \rightarrow (K \cup \{\mathsf{undefined})\}|
&= |(K \cup \{\mathsf{undefined}\})^N| \\
&= |K \cup \{\mathsf{undefined}\}|^{|N|} \\
&= (|K| + |\{\mathsf{undefined}\}|)^{|N|} \\
&= (k + 1)^n
\end{align}
On the other hand, you can also describe the set of partial functions from $N$ to $K$ as the union of the functions from subsets of $N$ to $K$:
\begin{align}
\bigcup_{S \subseteq N} (S \rightarrow K)
\end{align}
Let $\binom{N}{i}$ be the set of $i$-element subsets of $N$. Then
\begin{align}
\mathcal{P}(N) = \bigcup_{i=0}^N \binom{N}{i}
\end{align}
and thus
\begin{align}
\left| \bigcup_{S \subseteq N} (S \rightarrow K) \right|
&= \left| \bigcup_{S \in \mathcal{P}(N)} (S \rightarrow K) \right| \\
&= \left| \bigcup_{S \in \bigcup_{i=0}^N \binom{N}{i}} (S \rightarrow K) \right| \\
&= \left| \bigcup_{i=0}^{|N|} \bigcup_{S \in \binom{N}{i}} (S \rightarrow K) \right| \\
&= \sum_{i=0}^{|N|} \left| \bigcup_{S \in \binom{N}{i}} (S \rightarrow K) \right| \\
&= \sum_{i=0}^{|N|} \sum_{S \in \binom{N}{i}} |S \rightarrow K| \\
&= \sum_{i=0}^{|N|} \sum_{S \in \binom{N}{i}} |K^S| \\
&= \sum_{i=0}^{|N|} \sum_{S \in \binom{N}{i}} |K|^{|S|} \\
&= \sum_{i=0}^{|N|} \sum_{S \in \binom{N}{i}} |K|^i \\
&= \sum_{i=0}^{|N|} \left|\binom{N}{i}\right| |K|^i \\
&= \sum_{i=0}^{|N|} \binom{|N|}{i} |K|^i \\
&= \sum_{i=0}^{n} \binom{n}{i} k^i
\end{align}
Since these two ways of describing the set of partial functions from $N$ to $K$ must yield the same number of functions, we have
\begin{align}
(k+1)^n = \sum_{i=0}^n \binom{n}{i} k^i
\end{align}
