15
$\begingroup$

I am trying to find limit of the following function: $$ \lim_{n\rightarrow \infty}\frac{\sum\limits_{x = 0}^{n}\binom{n}{x}\left[1 + \mathrm{e}^{-(x+1)}\right]^{n + 1}}{\sum\limits_{x=0}^{n} \binom{n}{x}\left[1 + \mathrm{e}^{-x}\right]^{n + 1}}. $$

When I wrote a Python code for this, I saw that it converges to $1/3$.

I am not sure how to approach this. Could somebody give a pointer about how to go about it?

EDIT: I want just some positive lower bound on this. So even if limit cannot be evaluated exactly, it is okay if I get some lower bound on this.

$\endgroup$
13
+50
$\begingroup$

$\def\e{\mathrm{e}}$For $n \in \mathbb{N}_+$, denote$$ S_n = \sum_{k = 0}^n \binom{n}{k} (1 + \e^{-(k + 1)})^{n + 1},\ T_n = \sum_{k = 0}^n \binom{n}{k} (1 + \e^{-k})^{n + 1}. $$

First,\begin{align*} S_n &= \sum_{k = 0}^n \binom{n}{k} (1 + \e^{-(k + 1)})^{n + 1} = \sum_{k = 0}^n \binom{n}{k} \sum_{j = 0}^{n + 1} \binom{n + 1}{j} \e^{-(k + 1)j}\\ &= \sum_{k = 0}^n \sum_{j = 0}^{n + 1} \binom{n}{k} \binom{n + 1}{j} \e^{-(k + 1)j} = \sum_{k = 0}^n \binom{n}{k} + \sum_{k = 0}^n \sum_{j = 1}^{n + 1} \binom{n}{k} \binom{n + 1}{j} \e^{-(k + 1)j}\\ &= 2^n + \sum_{k = 0}^n \sum_{j = 0}^n \binom{n}{k} \binom{n + 1}{j + 1} \e^{-(k + 1)(j + 1)}, \tag{1} \end{align*} thus $S_n \geqslant 2^n$. Note that$$ (k + 1)(j + 1) \geqslant k + j + 1 \Longleftrightarrow kj \geqslant 0, $$ thus from (1) there is\begin{align*} S_n &\leqslant 2^n + \sum_{k = 0}^n \sum_{j = 0}^n \binom{n}{k} \binom{n + 1}{j + 1} \e^{-(k + j + 1)}\\ &= 2^n + \e^{-1} \sum_{k = 0}^n \sum_{j = 0}^n \binom{n}{k} \e^{-k} \binom{n + 1}{j + 1} \e^{-j}\\ &= 2^n + \e^{-1} \left( \sum_{k = 0}^n \binom{n}{k} \e^{-k} \right)\left( \sum_{j = 0}^n \binom{n + 1}{j + 1} \e^{-j} \right)\\ &\leqslant 2^n + \e^{-1} (1 + \e^{-1})^n (1 + \e^{-1})^{n + 1}\\ &= 2^n + \e^{-1} (1 + \e^{-1})^{2n + 1}. \end{align*} Therefore,$$ 1 \leqslant \frac{S_n}{2^n} \leqslant 1 + \e^{-1} (1 + \e^{-1}) \left( \frac{1}{2} (1 + \e^{-1})^2 \right)^n. $$ Note that $\dfrac{1}{2} (1 + \e^{-1})^2 < 1$, thus $S_n \sim 2^n$ $(n \to \infty)$.

Next,\begin{align*} T_n &= \sum_{k = 0}^n \binom{n}{k} (1 + \e^{-k})^{n + 1} = \sum_{k = 0}^n \binom{n}{k} \sum_{j = 0}^{n + 1} \binom{n + 1}{j} \e^{-kj}\\ &= \sum_{k = 0}^n \sum_{j = 0}^{n + 1} \binom{n}{k} \binom{n + 1}{j} \e^{-kj}\\ &= \sum_{k = 0}^n \binom{n}{k} + \sum_{j = 0}^{n + 1} \binom{n + 1}{j} - 1 + \sum_{k = 1}^n \sum_{j = 1}^{n + 1} \binom{n}{k} \binom{n + 1}{j} \e^{-kj}\\ &= 2^n + 2^{n + 1} - 1 + \sum_{k = 1}^n \sum_{j = 1}^{n + 1} \binom{n}{k} \binom{n + 1}{j} \e^{-kj}\\ &= 3 × 2^n - 1 + \sum_{k = 0}^{n - 1} \sum_{j = 0}^n \binom{n}{k + 1} \binom{n + 1}{j + 1} \e^{-(k + 1)(j + 1)}, \tag{2} \end{align*} thus $T_n \geqslant 3 × 2^n - 1$. Also, analogously, from (2) there is\begin{align*} T_n &\leqslant 3 × 2^n + \sum_{k = 0}^{n - 1} \sum_{j = 0}^n \binom{n}{k + 1} \binom{n + 1}{j + 1} \e^{-(k + j + 1)}\\ &= 3 × 2^n + \e \left( \sum_{k = 0}^{n - 1} \binom{n}{k + 1} \e^{-(k + 1)} \right)\left( \sum_{j = 0}^n \binom{n + 1}{j + 1} \e^{-(j + 1)} \right)\\ &\leqslant 3 × 2^n + \e (1 + \e^{-1} )^n (1 + \e^{-1})^{n + 1}, \end{align*} which analogously implies that $T_n \sim 3 × 2^n$ $(n \to \infty)$.

Therefore,$$ \lim_{n \to \infty} \frac{\displaystyle\sum_{k = 0}^n \binom{n}{k} (1 + \e^{-(k + 1)})^{n + 1}}{\displaystyle\sum_{k = 0}^n \binom{n}{k} (1 + \e^{-k})^{n + 1}} = \lim_{n \to \infty} \frac{S_n}{T_n} = \lim_{n \to \infty} \frac{2^n}{3 × 2^n} = \frac{1}{3}. $$

$\endgroup$
11
$\begingroup$

Preliminary Inequalities

Using the formula $\frac{x^{n+1}-1}{x-1}=x^n+\cdots+1$, we get $$ \begin{align} \left(1+e^{-k}\right)^{n+1}-1 &=e^{-k}\!\left(\left(1+e^{-k}\right)^n+\cdots+1\right)\\[6pt] &\le(n+1)e^{-k}\left(1+e^{-k}\right)^n\tag1 \end{align} $$ Therefore, $$ \begin{align} \sum_{k=1}^{n+1}\binom{n+1}{k}\left(\left(1+e^{-k}\right)^{n+1}-1\right) &\le\color{#C00}{\sum_{k=1}^{n+1}\binom{n+1}{k}}(n+1)\,\color{#C00}{e^{-k}}\color{#090}{\left(1+e^{-k}\right)^n}\\ &\le(n+1)\color{#C00}{\left(1+\frac1e\right)^{n+1}}\color{#090}{\left(1+\frac1e\right)^n}\\[3pt] &=(n+1)\left(1+\frac1e\right)^{2n+1}\\[9pt] &=o\!\left(2^n\right)\tag2 \end{align} $$ since $\left(1+\frac1e\right)^2\lt2$.


Application of $\boldsymbol{(2)}$ $$ \begin{align} \frac{\sum\limits_{j=0}^n\binom{n}{j}\left[1+e^{-(j+1)}\right]^{n+1}}{\sum\limits_{j=0}^n\binom{n}{j}\left[1+e^{-j}\right]^{n+1}} &=\frac{\sum\limits_{j=0}^n\binom{n}{j}\sum\limits_{k=0}^{n+1}\binom{n+1}{k}e^{-k(j+1)}}{\sum\limits_{j=0}^n\binom{n}{j}\sum\limits_{k=0}^{n+1}\binom{n+1}{k}e^{-kj}}\tag{3a}\\ &=\frac{\sum\limits_{k=0}^{n+1}\binom{n+1}{k}e^{-k}\left(1+e^{-k}\right)^n}{\sum\limits_{k=0}^{n+1}\binom{n+1}{k}\left(1+e^{-k}\right)^n}\tag{3b}\\ &=\frac{\sum\limits_{k=0}^{n+1}\binom{n+1}{k}\left(1+e^{-k}\right)^{n+1}}{\sum\limits_{k=0}^{n+1}\binom{n+1}{k}\left(1+e^{-k}\right)^n}-1\tag{3c}\\ &=\frac{\overbrace{\ \ \ 2^{n+1}\ \ \ }^{k=0}+\overbrace{2^{n+1}+o\!\left(2^n\right)}^{k\ge1}}{\underbrace{\,\ \ \ \ 2^{n\vphantom{+1}}\ \ \ \ \,}_{k=0}+\underbrace{2^{n+1}+o\!\left(2^n\right)}_{k\ge1}}-1\tag{3d}\\ &=\frac{4+o(1)}{3+o(1)}-1\tag{3e}\\[18pt] &=\frac13+o(1)\tag{3f} \end{align} $$ Explanation:
$\text{(3a)}$: Binomial Theorem
$\text{(3b)}$: Binomial Theorem
$\text{(3c)}$: algebra
$\text{(3d)}$: apply $(2)$
$\text{(3e)}$: divide numerator and denominator by $2^n$
$\text{(3f)}$: simplification

Thus, $$ \lim_{n\to\infty}\frac{\sum\limits_{j=0}^n\binom{n}{j}\left[1+e^{-(j+1)}\right]^{n+1}}{\sum\limits_{j=0}^n\binom{n}{j}\left[1+e^{-j}\right]^{n+1}}=\frac13\tag4 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.