How to prove an identity containing binomial coefficients

Question

I am trying to prove the identity $$\sum_{k=1}^n (3^k - 1) \binom{n}{k} = 4^n - 2^n$$ where $\binom{n}{k}$ is the binomial coefficient n over k or n choose k.

Answer 1

Hint

Note that

$$b^n+\sum_{k=1}^n \binom{n}{k}a^kb^{n-k}=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}=(a+b)^n. $$

What do you get if $a=3$ and $b=1?$ What if $a=b=1?$

Answer 2

Given $\displaystyle \sum^{n}_{k=1}\left(3^k-1\right)\cdot \binom{n}{k} = \sum^{n}_{k=1}3^{k}\cdot \binom{n}{k}-\sum^{n}_{k=1}\binom{n}{k}$

Now Using the formula

$\displaystyle \bullet \; (1+x)^n = \binom{n}{0}x^{0}+\binom{n}{1}x^{1}+......\binom{n}{n}x^n.........(1)$

Now Put $x=3\;$ in $(1)\;,$ We get $\displaystyle 4^n = 1+\sum^{n}_{k=1}\binom{n}{k}3^{k}$

and Put $x=1$ in $(1)\;,$ We get $\displaystyle 2^n = 1+\sum^{n}_{k=1}\binom{n}{k}$

So we get $\displaystyle \sum^{n}_{k=1}\left(3^k-1\right)\cdot \binom{n}{k} = (4^n-1)-(2^n-1) = 4^n-2^n$

Answer 3

$\sum_{k=1}^n (3^k - 1) \binom{n}{k} =\sum_{k=1}^n3^{k}\binom{n}{k}-\sum_{k=1}^n\binom{n}{k}=4^{n}-2^{n}$ note that $(x+1)^k=\sum_{k=1}^nx^k\binom{n}{k}$ if we substitute x=3 and x=1 we get the result

Answer 4

Extended HINT: Suppose that you want to count the $n$-digit strings that use only the digits $1,2,3$, and $4$ and that do not consist entirely of $1$s and $2$s, i.e., that have at least one $3$ or $4$. There are $4^n$ $n$-digit strings using the allowable digits; how many of them are ‘bad’ (fail to contain a $3$ or a $4$)? How many does that leave that are good (meet all of the requirements)?

Now suppose that $\sigma$ is one of the strings that we want to count. It must have at least one $3$ or $4$, so in particular it must have at least one digit that is not a $1$. Suppose that it has $k$ digits that are not $1$s; there are $\binom{n}k$ ways to choose the positions of these $k$ digits. What can these $k$ digits be? Then can be any of the $3^k$ sequence of digits from the set $\{2,3,4\}$ except the one that consists entirely of $2$s. Thus, there are $3^k-1$ possible choices for these $k$ digits.

Now just put the pieces together to finish the combinatorial proof of the identity.