二项式系数倒数和

hbghlyj

University of Rochester Math Olympiad – 2013Olympiad
4. 求数列$a_n$的极限.$$a_n=\frac{1}{\binom{n}{0}} + \frac{1}{\binom{n}{1}} + \cdots +
\frac{1}{\binom{n}{n}}$$
Google搜索"sum of reciprocals of binomial coefficients"得以下解法
对$n\ge4$,
对$2\le k\le n-2$, 我们有$\binom{n}{k}\ge\binom{n}{2}$.
\begin{align*}
\sum_{k=0}^n\frac1{\binom{n}{k}}
&=\overset{\substack{k=0\\k=n\\\downarrow\\[3pt]\,}}{2\vphantom{\frac2n}}+\overset{\substack{k=1\\k=n-1\\\downarrow\\[3pt]\,}}{\frac2n}+\sum_{k=2}^{n-2}\frac1{\binom{n}{k}}\\
&\le2+\frac2n+\frac{n-3}{\binom{n}{2}}\\
&\le2+\frac4n
\end{align*}
所以\[2+\frac2n\le a_n\le2+\frac4n\]
所以$\lim a_n=2$

---

这里$a_n$是倒数和, 没有封闭形式; 倒数交替和, 有封闭形式,见这个2017帖子
相关问题

---

这里有一个公式
\[a_n=\frac{n+1}{2^n}\left(\frac{{n+1 \choose 1}}{1} + \frac{{n+1 \choose 3}}{3} + \frac{{n+1 \choose 5}}{5} + \dots \right)\]
这里有一个类似的公式
\[a_n=\sum _{k=0}^n (n+1) B(k+1,-k+n+1)=\frac{n+1}{2^n}\sum_{k\leq n/2}\binom{n+1}{2k+1}\frac{1}{2k+1}\]
Mathematica Input:
Sum[(n + 1) Beta[k + 1, n - k + 1], {k, 0, n}]

hbghlyj

从这帖找着了The Fibonacci Quarterly, 1981
注意到\[\left(\begin{array}{l}n \\ k\end{array}\right)^{-1}=\left(\begin{array}{l}n-1 \\ k-1\end{array}\right)^{-1}-\frac{(n-k)}{(n-k+1)}\left(\begin{array}{c}n \\ k-1\end{array}\right)^{-1}\tag{*}\]
然后
Theorem 1: Let $I_n=\sum_{k=0}^n\left(\begin{array}{l}n \\ k\end{array}\right)^{-1}$. Then $I_n$ satisfies the recursion relation
\[
I_n=\frac{n+1}{2 n} I_{n-1}+1
\]and
\[
I_n=\frac{(n+1)}{2^{n+1}} \sum_{k=1}^{n+1} \frac{2^k}{k} .
\]
This corrects a slight error in [3].
Proof by Induction on $n$ : For $n=1$, we have $I_1=2$ from the definition and from the formula. We now show that the formula for $n+1$ follows from the formula for $n$ and the relation (*).
\[
I_{n+1}=\sum_{k=0}^{n+1}\left(\begin{array}{c}
n+1 \\
k
\end{array}\right)^{-1}=\left(\begin{array}{c}
n+1 \\
0
\end{array}\right)^{-1}+\sum_{k=1}^{n+1}\left(\begin{array}{c}
n+1 \\
k
\end{array}\right)^{-1} .
\]
Applying (*) to each term of the sum, we have
\[
\begin{aligned}
I_{n+1} & =1+\sum_{k=1}^{n+1}\left(\left(\begin{array}{c}
n \\
k-1
\end{array}\right)^{-1}-\frac{(n+1)-k}{(n+1-k)+1} \cdot\left(\begin{array}{l}
n+1 \\
k-1
\end{array}\right)^{-1}\right) \\
& =1+I_n-\sum_{k=0}^n \frac{n-k}{(n+1)-k}\left(\begin{array}{c}
n+1 \\
k
\end{array}\right)^{-1} .
\end{aligned}
\]
Since
\[
\frac{n-k}{(n+1)-k}=1-\frac{1}{(n+1)-k},
\]
we may rewrite our last expression as two sums:
\[
\begin{aligned}
I_{n+1} & =1+I_n-\sum_{k=0}^n\left(\begin{array}{c}
n+1 \\
k
\end{array}\right)^{-1}+\sum_{k=0}^n \frac{1}{(n+1)-k}\left(\begin{array}{c}
n+1 \\
k
\end{array}\right)^{-1} \\
& =2+I_n-I_{n+1}+\frac{1}{n+1} I_n
\end{aligned}
\]
so that
\[\tag1\label1
I_{n+1}=\frac{n+2}{2(n+1)} I_n+1
\]
and the recursion relation is established. Applying the induction hypothesis for $I_n$ yields
\[
I_{n+1}=\frac{n+2}{2(n+1)}\left(\frac{n+1}{2^{n+1}} \sum_{k=1}^{n+1} \frac{2^k}{k}\right)+\frac{n+2}{2^{n+2}} \frac{2^{n+2}}{n+2}=\frac{(n+1)+1}{2^{(n+1)+1}} \sum_{k=1}^{(n+1)+1} \frac{2^k}{k},
\]
as required

hbghlyj

由2#证明的恒等式,有
$$\sum_{k=0}^n\frac1{\binom{n}{k}}=\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k}=\frac{\sum_{k=1}^{n+1}\frac{2^k}{k}}{\frac{2^{n+1}}{n+1}}$$
由 Stolz-Cesàro 定理,
$$\frac{\frac{2^{n+2}}{n+2}}{\frac{2^{n+2}}{n+2}-\frac{2^{n+1}}{n+1}}=\frac{2}{2-\frac{n+2}{n+1}}\to 2$$

hbghlyj

In[]:= AsymptoticRSolveValue[{a[n+1]==(n+2)/2/(n+1)a[n]+1,a[1]==2},a[n],n->Infinity]
Out[]= $\displaystyle-2 \Phi (2,1,n+2)-2 n \Phi (2,1,n+2)-i \pi  2^{-n-1}-i \pi  2^{-n-1} n$
怎么出现虚数了呢

hbghlyj

猜测\[n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}\to2\]
数值:
Sum[1/Binomial[n,k],{k,1,n-1}]n/.n->1000//N
2.00402

hbghlyj

hbghlyj 发表于 2022-12-19 12:35
猜测\[n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}\to2\]

仿照4#的方法,$$n\sum_{k=1}^{n-1}\frac1{\binom{n}{k}}=\frac{\left(\sum_{k=1}^n\frac{2^k}k\right)-\frac{2^{n+1}}{n+1}}{\frac{2^{n+1}}{n(n+1)}}$$
由 Stolz-Cesàro 定理,
$$\frac{\Delta\left(\sum_{k=1}^n\frac{2^k}k\right)-\Delta\frac{2^{n+1}}{n+1}}{\Delta\frac{2^{n+1}}{n(n+1)}}=\frac{\frac{
   2^{n+1}}{n+1}-\left(\frac{2^{n+2}}{n+2}-\frac{2^{n+1}}{n+1}\right)}{\frac{2^{n+2}}{(
   n+1) (n+2)}-\frac{2^{n+1}}{n (n+1)}}=\frac{2 n}{n-2}\to2$$

hbghlyj

继续做下去:
Δ[x_]:=(x/.{n->n+1})-x;
(2^(n+1)/(n+1)-Δ[2^(n+1)/(n+1)+2^(n+2)/(n(n+1))])/Δ[2^(n+1)/(n^2(n+1))]//FullSimplify
得$\frac{4 n (n+1)}{(n-3) n-2}$, 极限是4, 所以\[n\left(n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}-2\right)\to4\]
(2^(n+1)/(n+1)-Δ[2^(n+1)/(n+1)+2^(n+2)/(n(n+1))+2^(n+3)/(n^2(n+1))])/Δ[2^(n+1)/(n^3(n+1))]//FullSimplify
得$\frac{8 n (n+1) (2 n+1)}{(n-5) n (n+1)-2}$,极限是16, 所以\[n\left(n\left(n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}-2\right)-4\right)\to16\]
(2^(n+1)/(n+1)-Δ[2^(n+1)/(n+1)+2^(n+2)/(n(n+1))+2^(n+3)/(n^2(n+1))+2^(n+5)/(n^3(n+1))])/Δ[2^(n+1)/(n^4(n+1))]//FullSimplify
得$\frac{8 n (n+1) (11 n (n+1)+4)}{n (n ((n-5) n-9)-7)-2}$, 极限是88, 所以\[n\left(n\left(n\left(n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}-2\right)-4\right)-16\right)\to88\]
(2^(n+1)/(n+1)-Δ[2^(n+1)/(n+1)+2^(n+2)/(n(n+1))+2^(n+3)/(n^2(n+1))+2^(n+5)/(n^3(n+1))+88 2^(n+1)/(n^4(n+1))])/Δ[2^(n+1)/(n^5(n+1))]//FullSimplify
得$\frac{8 n (n+1) (n (n (77 n+114)+81)+22)}{n (n+1) (n ((n-7) n-7)-9)-2}$, 极限是616, 所以\[n\left(n\left(n\left(n\left(n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}-2\right)-4\right)-16\right)-88\right)\to616\]
(2^(n+1)/(n+1)-Δ[2^(n+1)/(n+1)+2^(n+2)/(n(n+1))+2^(n+3)/(n^2(n+1))+2^(n+5)/(n^3(n+1))+88 2^(n+1)/(n^4(n+1))+616 2^(n+1)/(n^5(n+1))])/Δ[2^(n+1)/(n^6(n+1))]//FullSimplify
得$\frac{8 n (n+1) (n (n+1) (n (653 n+620)+715)+154)}{n (n (n (n ((n-7) n-20)-30)-25)-11)-2}$, 极限是5224, 所以\[n\left(n\left(n\left(n\left(n\left(n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}-2\right)-4\right)-16\right)-88\right)-616\right)\to5224\]
(2^(n+1)/(n+1)-Δ[2^(n+1)/(n+1)+2^(n+2)/(n(n+1))+2^(n+3)/(n^2(n+1))+2^(n+5)/(n^3(n+1))+88 2^(n+1)/(n^4(n+1))+616 2^(n+1)/(n^5(n+1))+5224 2^(n+1)/(n^6(n+1))])/Δ[2^(n+1)/(n^7(n+1))]//FullSimplify
得$\frac{8 n (n+1) (n (n (n (n (6497 n+15668)+21640)+17194)+7337)+1306)}{n (n+1) (n (n (n ((n-9) n-18)-32)-23)-13)-2}$, 极限是51976, 所以\[n\left(n\left(n\left(n\left(n\left(n\left(n\sum _{k=1}^{n-1} \frac{1}{\binom{n}{k}}-2\right)-4\right)-16\right)-88\right)-616\right)-5224\right)\to51976\]

hbghlyj

使用\eqref{1}可以将a[n]表示为LDE(线性差分方程)的解(见holonomic function)
a=DifferenceRoot[Function[{y,n},{y[n]==(n+1)/(2n) y[n-1]+1,y[0]==1}]];
使用GeneratingFunction求出a[n]的生成函数:
FunctionExpand[GeneratingFunction[a[n],n,x]]
输出$$\frac{2 (x+(1-x) \log (1-x)-2)}{(x-2)^2 (x-1)}$$
代入n=3验证一下
Sum[(n+1)Beta[k+1,n-k+1],{k,0,n}]/.n->3
a[3]
D[(2 (x-2+(1-x) Log[1-x]))/((-2+x)^2 (-1+x)),{x,3}]/3!/.x->0
三者都输出8/3
使用生成函数求a[n]渐近展开式:
In[]:= For[f=(2 (x-2+(1-x) Log[1-x]))/((-2+x)^2 (-1+x));n=0;S={},n<8,n++,c=Limit[f(1-x),x->1];AppendTo[S,c];f=FullSimplify[D[f-c/(1-x),x]x]];S
Out[]= {2,2,4,16,88,616,5224,51976}
和7#的结果一样于是可以把生成函数形式地写成
$$\frac{2 (x+(1-x) \log (1-x)-2)}{(x-2)^2 (x-1)}=\frac2{1-x}+\int^x_{b_1}\cfrac{\mathrm dx_1\left(\cfrac2{1-x_1}+\int^{x_2}_{b_2}\cfrac{\mathrm dx_2\left(\cfrac4{1-x_2}+\int^{x_3}_{b_3}\cfrac{\mathrm dx_3\left(\cfrac{16}{1-x_3}+\cdots\right)}{x_3}\right)}{x_2}\right)}{x_1}$$
其中$b_1,b_2,\cdots$是一些常数, $b_1$ = 1 - ProductLog[1/E]