3
$\begingroup$

This question already has an answer here:

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

Yep it's absolutely correct. You could have treated it as

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

$\endgroup$
2
$\begingroup$

Yep, that's just fine.

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.