Prove $\sum\binom{n}{k}2^k = 3^n$ using the binomial theorem

Not quite if $x=0$ and $y=3$ then you would have $3^n=y^n$ which is not what you want. If you set $x=0$ and $y=2$ you would have $2^n = y^n$.

Compare this with the general binomial theorem,

$$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k}y^k $$

Notice that if $x=1$ and $y=1$ we have,

$$ 2^n = \sum_{k=0}^{n} {n \choose k} $$

Notice that if $x=6$ and $y=-4$ we have,

$$(2)^n = \sum_{k=0}^{n} {n \choose k} 6^{n-k}(-4)^k $$

• What values could $x$ and $y$ have in order to get a $3^n$ on the left?
• What values could $x$ and $y$ have in order to get a $2^k$ in the summation?

If you can find values for $x$ and $y$ which satisfy both those questions then you have solved the problem.

Further Motivation:

You correctly guessed x=1 and y=2.

As far as I know there is no formal algorithmic approach that will solve this type of problem. This is in fact a great tool for teaching problem solving skills because it involves thinking about a problem from different angles without an initially clear path to the solution.

When looking at a problem you should first write it down and examine every piece. We had $$ 3^n = \sum_{k=0}^n { n \choose k } y^k $$

The first thing which strikes me when looking at this is that we have binomial coefficients. This suggests that we may find greater insight by looking at the binomial theorem.

$$ (x+y)^n = \sum_{k=0}^n { n \choose k } x^{n-k} y^k $$

Comparing the statement of the binomial theorem to our problem we notice that both have a summation with binomial coefficients equal to the power of a number. First let us compare the results of the respective summations.

$$ 3^n \qquad (x+y)^n $$

We see that in one case we have the number $3$ raised to the $n$'th power and in the other case we have the number $x+y$ raised to the $n$'th power. We suspect that these numbers will have to be the same for the binomial theorem to be useful in solving the problem. However there are two degrees of freedom in the second number in the form of the variables $x$ and $y$ this means there is not a unique $(x,y)$ pair which will produce a $3$ when added together. Note (-1,4),(0,3),(1,2),(103,-100), etc. all add to three.

This means that we have only partially determined the solution by comparing the results of the summations. To narrow it down to a solution we compare the summands.

$$ {n \choose k } 2^k \qquad { n \choose k } x^{n-k}y^k $$

Both terms have identical binomial coefficients which means that we can ignore them. One has powers of a single number, $2$, the other has powers of our variables $x$ and $y$. We notice that $2$ and $y$ are both raised to the $k$ whereas $x$ is raised to the $n-k$. This suggests to us that it may be useful to associate $y$ with $2$. If we did this we could say that we believe $y=2$ but are not yet confident of the value $x$ should have.

Thinking back we remember that one of the pairs of possible $x$ and $y$ values was $(1,2)$ this is hopeful since it identifies $y=2$ as we desire. If $x=1$ doesn't cause any problems we will have solved the problem.

Examining the binomial theorem with $(1,2)$ we see that,

$$ (x+y)^n = \sum_{k=0}^n { n \choose k } x^{n-k} y^k $$

$$ (1+2)^n = \sum_{k=0}^n { n \choose k } (1)^{n-k} (2)^k $$

$$ 3^n = \sum_{k=0}^n { n \choose k } (2)^k $$

Which is the identity we wanted to establish.

At this point we know the path through the woods. The solution is : Evaluate the binomial theorem for $x=1$ and $y=2$ and the result is the desired identity. This is logically impeccable but contains non of the thought that was necessary to produce it. One advantage of this is that if we are lucky enough to guess the right (x,y) we can solve the problem even if we didn't have a good reason for coming up with the ordered pair. The disadvantage is that we don't learn anything about solving other problems when we see just the bare solution.

You learn to think this way by solving a lot of problems without clearly marked paths to the solution. If you are interested in learning more about how to think in this way you should read "How to Solve It" by George Polya.

You are almost there - the value of $x$ should be 1 rather than 2, so that we get (essentially what you already have written):

$$3^n = (1+2)^n = \sum_{k=0}^n \binom{n}{k} 1^{n-k} 2^k = \sum_{k=0}^n \binom{n}{k} 2^k.$$