如何证明二项式系数对幂n的渐近二大θ? [英] How to prove binomial coefficient is asymptotic big theta of two to the power n?

问题描述

我被这个问题困扰.我认为这等于等于表明2m选择m对n次方来说是4的大θ，但仍然很难证明这一点.

I am stuck at this problem. I think it is equivalent to show 2m choose m is big theta of 4 to the power n, but still find difficult to prove it.

感谢@LutzL的建议.我以前曾想到过斯特林的近似.

Thanks of @LutzL's suggestion. I thought of stirling's approximation before.

推荐答案

O 部分应该很简单.从 n 中精确选择 n /2个元素是从 n 个元素中选择任意组合的特殊情况，即为每个 n 元素是否选择.

The O-part should be easy. Choosing exactly n/2 elements out of n is a special case of choosing arbitrary combinations out of n elements, i.e. deciding for each of these n elements whether to choose it or not.

Ω部分较难.实际上，

The Ω-part is harder. In fact, plotting 4ⁿ / binomial(2 n, n) for moderately large n I see no indication that this would flatten to stay below some constant. Speaking intuitively, the larger n is, the more special is the case when you take a random pick from n elements and coincidentially happen to choose exactly n/2 of them. That probability should tend to zero as n increases, meaning that 2ⁿ should always grow faster than n choose n/2. Are you certain you understood this part of your task correctly?

这篇关于如何证明二项式系数对幂n的渐近二大θ?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！