# Find, $\sum_{k=0}^{n}4^k \binom{n}{k}$ [duplicate]

Reading through my textbook I came across the following problem, and I am looking for some help solving it. I believe I have done the workings correctly but I just wanted to make sure as it seemed a little to easy. Find, $$\sum_{k=0}^{n}4^k \binom{n}{k}$$ Consider the expansion $(1+x)^n$ using binomial theorem. $$(1+x)^n = \sum_{k=0}^{n} x^k \binom{n}{k}$$ Then substitute $x = 4$. That should lead you to the answer $5^n$. Therefore $$\sum^{n}_{k=0}4^k\binom{n}{k} = 5^n$$

## marked as duplicate by J.-E. Pin, Ethan Bolker, Community♦Feb 7 '18 at 14:17

• You are correct! Well done. – Jonathan Feb 6 '18 at 23:49
• thats correct yes – Isham Feb 6 '18 at 23:50

$$\sum_{k=0}^n \binom {n}{k} 4^k=\sum_{k=0}^n \binom {n}{k} 1^{n-k} 4^k=(1+4)^n=5^n$$
There's also a nice combinatorial argument here: say you wanted to split $n$ objects up into $5$ labeled categories. Clearly, you could just do it; there are $5^n$ ways to do so.
Alternatively, you could choose the bucket of items that will belong to categories $1-4$; declare that all remaining items belong to category $5$. Then, if there are $k$ items for buckets $1-4$, there are $4^k$ ways to make the individual assignments. This leads to $\sum_{k=0}^{n}\binom{n}{k}4^k$ total arrangements.
Since $5^n$ and $\sum_{k=0}^{n}\binom{n}{k}4^k$ count the same thing, they must be equal.