Intereting Posts

pseudo-primality and test of Solovay-Strassen
Evaluate the Sum $\sum_{i=0}^\infty \frac {i^N} {4^i}$
Prime ideal and nilpotent elements
Improving Von Neumann's Unfair Coin Solution
What is the best base to use?
For any set of formulas in propositional logic, there is an equivalent and independent set
Is $\mathbb{R}$ an algebraic extension of some proper subfield?
Normal operators in Hilbert spaces
Is $\cot(z)-\frac1z$ bounded on a given circle?
Why is this a characterization of isogenies of elliptic curves? (From Silverman)
Characteristic time?
Explanation of method for showing that $\frac{0}{0}$ is undefined
What is the use of moments in statistics
Flatlander on torus
In a one-to-many relationship, how to find the minimum set of “ones” needed to get all of the “manys”?

I’m studying for a midterm and need some help with proving summation using the binomial theorem.

$\sum\limits_{k=0}^n {n \choose k} 2^k = 3^n$

This is what I’m thinking so far: In the binomial theorem we set x = 0, and y = 2, so:

- A conjecture including binomial coefficients
- Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)
- Sum of combinations of the n by consecutive k
- Is the numerator of $\sum_{k=0}^n \frac{(-1)^k}{2k+1}\binom{n}{k}$ a power of $2$?
- How many solutions are there to the equation $x + y + z + w = 17$?
- How to prove $\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m$?

$3^n = (x+y)^n = \sum\limits_{k=0}^n {n \choose k} y^k$

$ = \sum\limits_{k=0}^n {n \choose k} 2^k$

Am I getting this correct so far or completely wrong?

Any help would be appreciated. Thanks.

- Combinatorial Proof
- How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?
- Proving binomial coefficients identity: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$
- Computing the coefficient in a large polynomial
- Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$
- Sums of binomial coefficients
- Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$
- Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$
- Does this really converge to 1/e? (Massaging a sum)
- Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.

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

- Does infinity and zero really exist?
- Expectation of an Absolute Value that is the Standard Normal?
- Does every positive rational number appear once and exactly once in the sequence $\{f^n(0)\}$ , where $f(x):=\frac1{2 \lfloor x \rfloor -x+1} $
- Easiest way to solve $y''+y=\frac{1}{\cos x}$
- In $T1$ space, all singleton sets are closed?
- How does one calculate $\sum\limits_{n=1}^\infty\frac{\mathrm{pop}(n)}{n(n+1)}$?
- A strong Hausdorff condition
- Maximal ideals of some localization of a commutative ring
- What are dirichlet characters?
- Associativity of Tensor Product
- $f,g$ continuous from $X$ to $Y$. if they are agree on a dense set $A$ of $X$ then they agree on $X$
- Proving Two Sets are Equal – Infinite Sets – Example
- Number of simple paths between two vertices on an $n \times m$ square-grid graph?
- Surprising Generalizations
- Use Little Fermat Theorem to prove $341$ is not a prime base $7$