I just came up with the following identity while solving some combinatorial problem but not sure if it's correct. I've done some numerical computations and they coincide. $$\lim_{n\to \infty}{\frac{1}{2^n}\sum_{k=0}^{n}\binom{n}{k}\frac{an+bk}{cn+dk}}\;\stackrel?=\;\frac{2a+b}{2c+d}$$ Here $a$, $b$, $c$, and $d$ are reals except that $c$ mustn't $0$ and $2c+d\neq0$. I wish I could explain how I came up with it, but I did nothing but comparing numbers with the answer then formulated the identity, and just did numerical computations.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Sign up
Sign up
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
|
|
||||
|
|
|
The reason this is true is that the binomial coefficients are strongly concentrated around the mean, when $k \sim \frac{n}{2}$. Using some standard concentration inequalities (Chernoff is strong, but Chebyshev's inequality sufficies too), you can show that for any constant $c > 0$, $2^{-n} \sum_{ k \in [0, (1/2 - c ) n ] \cup [(1/2 + c)n, n]} \binom{n}{k} \rightarrow 0$ as $n \rightarrow \infty$. Hence in your limit, the only terms that survive are when $k \sim \frac{n}{2}$, in which case you can cancel the $n$ throughout and get the right-hand side. For the limit to hold, you clearly need $2c + d \neq 0$. You would also need $c \neq 0$, as otherwise the $k = 0$ term of the sum will present difficulties. |
|||||||||
|
|
$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\color{#f00}{\lim_{n\to \infty}\,{1 \over 2^{n}} \sum_{k = 0}^{n}{n \choose k}{an + bk \over cn + dk}} = \lim_{n\to \infty}\,{1 \over 2^{n}} \sum_{k = 0}^{n}{n \choose k}\pars{an + bk}\int_{0}^{1}t^{cn + dk - 1}\,\,\,\dd t \\[3mm] = &\ \lim_{n\to \infty}\,{1 \over 2^{n}}\int_{0}^{1}t^{cn - 1}\bracks{% an\sum_{k = 0}^{n}{n \choose k}\pars{t^{d}}^{k} + b\sum_{k = 0}^{n}{n \choose k}k\pars{t^{d}}^{k}}\dd t \end{align} However, $\ds{\sum_{k = 0}^{n}{n \choose k}\xi^{k} = \pars{1 + \xi}^{n} \quad\imp\quad \sum_{k = 0}^{n}{n \choose k}k\,\xi^{k} = n\xi\pars{1 + \xi}^{n - 1}}$. Then, \begin{align} &\color{#f00}{\lim_{n\to \infty}\,{1 \over 2^{n}} \sum_{k = 0}^{n}{n \choose k}{an + bk \over cn + dk}} = \\[3mm] = &\ \lim_{n\to \infty}\,{1 \over 2^{n}}\int_{0}^{1}t^{cn - 1}\bracks{% an\pars{1 + t^{d}}^{n} + bn\,t^{d}\pars{1 + t^{d}}^{n - 1}}\dd t \\[3mm] = &\ \color{#f00}{\lim_{n \to \infty}\braces{\vphantom{\LARGE A}% {n \over 2^{n}}\bracks{\vphantom{\Large A}a\,\mathrm{f}_{n}\pars{cn,d} + b\,\mathrm{f}_{n - 1}\pars{cn + d,d}}}} \end{align} $$ \mbox{where}\quad \begin{array}{|c|}\hline\\ \ds{\quad\mathrm{f}_{n}\pars{\mu,\nu} \equiv \int_{0}^{1}t^{\mu - 1}\pars{1 + t^{\nu}}^{n}\,\dd t\quad} \\ \\ \hline \end{array} $$
|
||||
|
|
