$2^{k} \mid {2k \choose 0} \cdot 3^{0} + {2k \choose 2} \cdot 3^{1} + \cdots + {2k \choose 2i} \cdot 3^{i} + \cdots + {2k \choose 2k} \cdot 3^{k}$ I have to prove this question:
$$2^{k} \,\left|\, {2k \choose 0} \cdot 3^{0} + {2k \choose 2} \cdot 3^{1} + \cdots + {2k \choose 2i} \cdot 3^{i} + \cdots + {2k \choose 2k} \cdot 3^{k}\right.$$
What i did was to get a closed form for this summation, and i haven't been able to get one. Any ideas, or is there any other method for proving this.
 A: Let's talk about some general methods.  This is a special case of the following problem: given that you understand a sequence $a_n$, how can you understand the sequence $b_n = \sum_{k=0}^n {n \choose k} a_k$?  Generating function techniques will come to your rescue.  If you let $A(x) = \sum_{n \ge 0} a_n x^n$, then
$$B(x) = \sum_{n \ge 0} b_n x^n = \sum_{n \ge 0} \sum_{k=0}^{n} {n \choose k} a_k x^n.$$
At this point we employ one of the simplest but most effective tools in generatingfunctionology, namely we exchange the order of summation.  This gives
$$B(x) = \sum_{k \ge 0} \sum_{n \ge k} {n \choose k} a_k x^n.$$
Since we want an answer in terms of $A$, it seems natural to factor $a_k x^k$ out of the inner sum.  This gives
$$B(x) = \sum_{k \ge 0} a_k x^k \sum_{n \ge k} {n \choose k} x^{n-k}.$$
Now a generatingfunctionologist will immediately recognize the inner sum as $\sum_{m \ge 0} {m+k \choose k} x^m = \frac{1}{(1 - x)^{k+1}}$.  This gives
$$B(x) = \sum_{k \ge 0} a^k \frac{x^k}{(1 - x)^{k+1}} = \frac{1}{1 - x} A \left( \frac{x}{1 - x} \right).$$
Beautiful.  Now, in this problem we are dealing with the sequence $a_{2k} = 3^k, a_{2k+1} = 0$.  This has generating function $A(x) = \frac{1}{1 - 3x^2}$, hence
$$B(x) = \frac{1}{1 - x} \left( \frac{1}{1 - \frac{3x^2}{(1 - x)^2} } \right) = \frac{1 - x}{(1 - x)^2 - 3x^2} = \frac{1 - x}{1 - 2x - 2x^2}.$$
Now, what we want to prove is that the even coefficients of $B \left( \frac{x}{\sqrt{2}} \right)$ are integral.  To extract the even coefficients we appeal to another general tool in generatingfunctionology: if $B(x) = \sum_{n \ge 0} b_n x^n$ is a generating function you want to extract the even coefficients from, then these are given by
$$\sum_{n \ge 0} b_{2n} x^{2n} = \frac{B(x) + B(-x)}{2}.$$
This is a special case of the discrete Fourier transform.  Once you know this, it is completely mechanical to verify that
$$\frac{B \left( \frac{x}{\sqrt{2}} \right) + B \left( \frac{-x}{\sqrt{2}} \right)}{2} = \frac{1 - x^2}{1 - 4x^2 + x^4}$$ 
which has integer coefficients (since the constant term of the denominator is $1$).  This is a bit tedious, but my point here is that once one has picked up a few generating function techniques most of the work in solving problems like these is automatic.
A: The expression on the right just screams "Binomial Theorem! Binomial Theorem!". It's a quick matter to figure out what to apply the Binomial Theorem to...
Added: So, how can we find out to what to apply the Binomial Theorem? Well, I can tell you what my thought process was; I'm sure there are better or more direct ones. I'm going to take $(a+b)^{2k}$; $2k$ because the binomial coefficients are $2k$-choose-something. The $a$ should be equal to $1$, because we only have the $3$'s in the expansion. Oh, wait... the power of $3$ that shows up is half the "choose-something", and in the binomial theorem, if you take $(1+b)^{2k}$, then the $2i$th term is $\binom{2k}{2i}b^{2i}$... oh, well, let's take $b=3^{1/2}$ then! The exponents will work out. Of course, then now I only have the even powers... but that's okay, because the odd powers are going to have that pesky $\sqrt{3}$ in them. So, I'm going to look at $(1+\sqrt{3})^{2k}$. Let's take it out for a spin and see if that works... Well, what do you know? It does!
Consider $(1+\sqrt{3})^{2k}$; using the binomial theorem, you get
$$(1+\sqrt{3})^{2k} = \binom{2k}{0}1^{2k} + \binom{2k}{1}1^{2k-1}3^{1/2}+\cdots + \binom{2k}{2k}3^{k}.$$
The left hand side is $(4 + 2\sqrt{3})^{k} = 2^k(2+\sqrt{3})^{k}$. This can be written uniquely as $x + y\sqrt{3}$ with $x,y\in\mathbb{Z}$, so $x$ is divisible by $2^k$. The right hand side can likewise be written uniquely as $a + b\sqrt{3}$, with $a,b\in\mathbb{Z}$, and $a$ is exactly the sum you have. So $a = x$, and $2^k$ divides $x$, giving the result you want.
