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

-
Think about $(a+b)^m+(a-b)^m$. –  Robin Chapman Oct 26 '10 at 14:10

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.

-
Thats my problem. First why did you consider $(1+\sqrt{3})$. I agree you need, the powers of three and even powers. I couldn't think of $\sqrt{3}$ at all. –  anonymous Oct 26 '10 at 14:55
@Chandru1: I've added a paragraph on why I thought to consider $1+\sqrt{3}$. Whether this is enlightening, or makes me look silly, I don't know. –  Arturo Magidin Oct 26 '10 at 17:27
Arturo, your explanations are anything but silly, and I, at least, like how you write your answers. –  Ｊ. Ｍ. Oct 26 '10 at 23:04

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.

-
In addition to Wilf, it might not be a bad idea to give a second reference. I wrote down most of the generating function tricks I know in the following pdf: web.mit.edu/~qchu/Public/TopicsInGF.pdf –  Qiaochu Yuan Oct 26 '10 at 20:34

HINT$\ \$ Specialize $\rm\ a = 1,\ b = 3 \$ below and then apply the binomial theorem to the RHS

$\rm\quad\quad\quad\quad\ \ \ 2\:|\:a-b\ \Rightarrow\ 2\:|\:(a\pm\sqrt b)^2\ \:in\ \: \mathbb Z[\sqrt b]\ \Rightarrow\ 2^k\ |\ (\:a+\sqrt b)^{2k} + (\:a-\sqrt b)^{2k}\:\ in\ \:\mathbb Z$

i.e. the sum is the trace of the $\rm\:$k'th power of an even quadratic integer so it is divisible by $\rm\:2^k\:$.

As in your similar recently posted problems the key is to recognize the sum as a slight perturbation of a well-known sum. Here one notices that the given sum is the even bisection of the binomial expansion of power of a quadratic integer, which immediately yields the result as above.

-
Thanks Bill! –  anonymous Oct 26 '10 at 16:23