Let $n$ be a positive integer and let $\alpha_n $ be the number of $1$'s within binary representation of $n$. Show that for all positive integers $r$, \[2^{2n-\alpha_n}\phantom{-1} \bigg|^{\phantom{0}}_{\phantom{-1}} \sum_{k=-n}^{n} \binom{2n}{n+k} k^{2r}.\]
Problem
Source:
Tags: calculus, function, number theory, combinatorics
goodar2006
29.12.2011 12:35
let's rewrite the right hand side as $\sum_{k=0}^{2n}\dbinom{2n}{k}(-n+k)^2$
$=n^2\sum_{k=0}^{2n}\dbinom{2n}{k}-2n\sum_{k=0}^{2n}k\dbinom{2n}{k}+\sum_{k=0}^{2n}k^2\dbinom{2n}{k}$
now using the three identities below:
$\sum_{k=0}^{n}\dbinom{n}{k}=2^n$
$\sum_{k=0}^{n}k\dbinom{n}{k}=n.2^{n-1}$
$\sum_{k=0}^{n}k^2\dbinom{n}{k}=n(n+1)2^{n-2}$
we get $\sum_{k=0}^{2n}\dbinom{2n}{k}(-n+k)^2=n.2^{2n-1}$. now since $\alpha_n$ is at least $1$, we have
$2^{2n-\alpha_n}|2^{2n-1}|\sum_{k=0}^{2n}\dbinom{2n}{k}(-n+k)^2$
but this argument will work for at most when $r=2$. (actually I think in that case the calculations will be very much). does anyone have an idea how to solve it?
mathocean97
28.08.2013 00:02
My solution is not great and I was hoping for maybe some combinatorial interpretation, but never found one. Anyways,
Let $\alpha(s)$ be a function from the non-negative integers to itself, and it is the sum of the digits (number of 1's) in the base 2 expansion of $s$. $\alpha(0) = 0$.
Define a sequence of functions $f_i(x)$ that satisfy $f_r(x) = \sum_{k=-n}^{n}\binom{2n}{n+k}k^{r}x^k$ for $r \ge 0$ (yes, it is $k^r$, not $k^{2r}$). It is not hard to see that the $f$ satisfy the recurrence $f_0(x) = \frac{(1+x)^{2n}}{x^n}$ and $f_{i+1}(x) = xf_i'(x)$ for $i \ge 0$.
Lemma 1: We can express $f_s(x) = \sum_{i=0}^{2n}\left(c_i \cdot \frac{\left(\prod_{j = 0}^{i-1}(2n-j)\right) \cdot (1+x)^{2n-i}}{x^{n-i}}\right)$ where ${\prod_{j = 0}^{-1}(2n-j)} = 1$ and integers $c_0, c_1, \cdots, c_{2n}$ for all integers $s \ge 0$.
Proof: The main point is to note that (' is differentiation) \[x\left( \frac{\left(\prod_{j = 0}^{i-1}(2n-j)\right) \cdot (1+x)^{2n-i}}{x^{n-i}}\right)'\]\[ = x\left(\frac{\left(\prod_{j = 0}^{i}(2n-j)\right) \cdot (1+x)^{2n-i-1} \cdot x^{n-i} - (n-i)\left(\prod_{j = 0}^{i-1}(2n-j)\right) \cdot (1+x)^{2n-i} \cdot x^{n-i-1}}{x^{2n-2i}} \right) \] \[ = \frac{\left(\prod_{j = 0}^{i}(2n-j)\right) \cdot (1+x)^{2n-i-1}}{x^{n-i-1}} - (n-i) \cdot \frac{\left(\prod_{j = 0}^{i-1}(2n-j)\right) \cdot (1+x)^{2n-i}}{x^{n-i}}\], so the result now follows easily by induction and the recurrence relation (if this isn't clear, I'll not be lazy and I'll write it out).
Lemma 2: ${2^{2n-\alpha(n)} \vert 2^{2n-i}} \cdot \prod_{j = 0}^{i-1}(2n-j)$
Proof: We write the RHS as $2^{2n-i} \cdot \frac{(2n)!}{(2n-i)!}$. Now by Legendre's Formula, \[ \upsilon_2\left(2^{2n-i} \cdot \frac{(2n)!}{(2n-i)!}\right) = \upsilon_2(2^{2n-i}) + \upsilon_2((2n)!) - \upsilon_2((2n-i)!)\] \[= 2n-i+2n-\alpha(n) - (2n-i) + \alpha(2n-i) \ge 2n - \alpha(n). \]
Now to finish, note that $f_r(1) = \sum_{k=-n}^{n}\binom{2n}{n+k}k^{r}$. So plugging in $x = 1$ to the expression in Lemma 1, Lemma 2 says that $2^{{2n} - \alpha(n)}$ divides all terms in the sum, so of course it divides $f_r(1)$.
toto1234567890
11.01.2016 16:24
If you turn this $ \ 2^{2n-\alpha_n} \huge\mid \sum_{k=-n}^{n} \dbinom{2n}{n+k}k^{2r}. $ into $ \ 2^{2n-\alpha_n} \huge\mid \sum_{k=0}^{2n} \dbinom{2n}{k}(k-n)^{2r}. $ and again to prove $ \ 2^{2n-\alpha_n} \huge\mid \sum_{k=0}^{2n} \dbinom{2n}{k}k(k-1)...k(k-r+1) $ . And now, you can easily see that $ \sum_{k=0}^{2n} \dbinom{2n}{k}k(k-1)...k(k-r+1)=r!\dbinom{2n}{r}\sum_{k=0}^{2n}\dbinom{2n-r}{k-r}=r!\dbinom{2n}{r}2^{2n-r}$ So, The rest is easy
LittleGlequius
07.05.2016 06:04
Amir Hossein wrote: Let $n$ be a positive integer and let $\alpha_n $ be the number of $1$'s within binary representation of $n$. Show that for all positive integers $r$, \[\ 2^{2n-\alpha_n} \huge\mid \sum_{k=-n}^{n} {C_{2n}}^{n+k}k^{2r}.\] My Solution: Lemma: $2^{n-\alpha_n}$ is the highest power of 2 that divides n! . Proof: Induction at $\alpha_n$ For $\alpha_n = 1$ , its easy ($n$ is a power of 2) Suppose its true for $\alpha_n = k$ Now, consider $m$ such that $\alpha_m = k+1$ $m = 2^{l} + s , 0<s<2^{l} $ Since the highest power of 2 that divides $2^{l}+i$ is equal to highest power of 2 that divides $i$ for all $i=1,2,3,...,s$, we have: Highest power of 2 that divide $m!=(2^{l})!(2^{l}+1)...(2^{l}+s)$= highest power of 2 that divides $(2^{l})!s!$. This is equal to $2^{2^{l}-1}2^{s-k}=2^{m-(k+1)}$ Induction is complete. so, it's enough to prove that $\frac{1}{2^{n}n!} \sum_{k=-n}^{n} {C_{2n}}^{n+k}k^{2r}$ has an odd denominator. Let $f(x)=\frac{(e^{\frac{x}{2}}+e^{\frac{-x}{2}})^{2n}}{2^{n}n!}$ (Carteação?) Since, $(e^{\frac{x}{2}}+e^{\frac{-x}{2}})^{2n}= \sum_{i=0}^{2n}\binom{2n}{i}(e^{\frac{x}{2}})^{2n-i}(e^{\frac{-x}{2}})^{i}= \sum_{i=0}^{2n}\binom{2n}{i}e^{x(n-i)}$=$\sum_{i=0}^{2n}\binom{2n}{i}(\frac{1}{0!}+\frac{1}{1!}(x(n-i))^{1}+\frac{1}{2!}(x(n-i))^{2}+...)$ $2^{n}n![x^{2r}]f = \sum_{i=0}^{2n}\binom{2n}{i}\frac{1}{(2r)!}(n-i)^{2r} = \sum_{i=0}^{2n}\binom{2n}{2n-i}\frac{1}{(2r)!}(n-i)^{2r} = \frac{1}{(2r)!} \sum_{k=-n}^{n}\binom{2n}{n+k}k^{2r}$, we have: $ \sum_{k=-n}^{n}\binom{2n}{n+k}k^{2r}= (2r)! 2^{n}n![x^{2r}]f=2^{n}n!(2r)!\frac{f^{2r}(0)}{(2r)!}$. Then, $\frac{1}{2^{n}n!} \sum_{k=-n}^{n} {C_{2n}}^{n+k}k^{2r}=f^{2r}(0)$ (where $f^{0}(x)=f(x)$ and $f^{k+1}(x)=\frac{d}{dx}f^{k}(x)$ for all k non-negative integer). It's enough to prove that $f^{2r}(0)$ has an odd denominator. Note that $f(x)=\frac{(e^{x}+e^{-x}+2)^{n}}{2^{n}n!}=\frac{(\frac{e^{x}+e^{-x}}{2} +1)^{n}}{n!}$. Then, $f(xi)=\frac{(cosx+1)^{n}}{n!}$ (where $i^{2}=-1$) Let $T_{m}(x)=\frac{(cosx+1)^{m}}{m!}$ for all $m$ positive integer and $T_{0}(x)=1$ . Since $T_{m}'(x)= -T_{m-1}(x)sinx$ for all $m$ positive integer, its easy prove by induction in $k$ that there exists two-variables polynomials with integers coefficients $H_{m,k,0}, H_{m,k,1}, H_{m,k,2}, H_{m,k,3}, ... ,H_{m,k,m}$ such that $T_{m}^{k}(x) = \sum_{j=0}^{m}H_{m,k,j}(sinx, cosx)T_{j}(x)$. Then, $ T_{n}^{2r}(0) = \sum_{j=0}^{n}H_{n,2r,j}(sin0, cos0)T_{j}(0) = \sum_{j=0}^{n}H_{n,2r,j}(0,1)\frac{2^{j}}{j!} $. Then $T_{n}^{2r}(0)$ has an odd denominator. Since $f(xi)=T_{n}(x)$, we have : $(-1)^{r}f^{2r}(xi) = T_{n}^{2r}(x)$, then $f^{2r}(0)$ has an odd denominator. We are Done!
KereMath
29.10.2017 14:22
Other solution without calculus?