How to prove an identity containing binomial coefficients 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.
 A: 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?$
A: 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$
A: $\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
A: 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.
