Wikipedia:Reference desk/Archives/Mathematics/2010 October 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 2

more combinatorics

Resolved

I am reading a book on combinatorics and am stuck on the following three problems:

• Why is the identity ${\tbinom {n-1}{k-1}}{\tbinom {n}{k+1}}{\tbinom {n+1}{k}}={\tbinom {n-1}{k}}{\tbinom {n}{k-1}}{\tbinom {n+1}{k+1}}$ called the hexagon identity?
• Compute the following sum: $\textstyle \sum _{k}{\tbinom {80}{k}}{\tbinom {k+1}{31}}$. I can reduce this to ${\frac {\tbinom {80}{30}}{31}}\textstyle \sum _{k}(k+1){\tbinom {50}{k-30}}$ and no further.
• Compute the following sum: $\textstyle \sum _{k\geq 0}{\frac {1}{k+1}}{\tbinom {99}{k}}{\tbinom {200}{120-k}}$. I want to use Vandermonde's convolution here but does it imply that this sum is ${\binom {209}{120}}\textstyle \sum _{k\geq 0}{\frac {1}{k+1}}$? What do I do next? I dont want any summation in the final result.

Can anyone help. Thanks-Shahab (talk) 07:19, 2 October 2010 (UTC)

You might like the book A=B. I'm not sure but it could be helpful for the last two problems. 67.122.209.115 (talk) 09:01, 2 October 2010 (UTC)

The binomial coefficients in the hexagon identity are corners of a hexagon in Pascal's triangle. The infinite series are actually finite sums, as $\textstyle {\tbinom {n}{k}}$=0 for k<0 and for k>n≥0. Bo Jacoby (talk) 10:19, 2 October 2010 (UTC).

Another nice book for learning how to do these manipulations is concrete mathematics. In your case, using generating functions seems a reasonable way for treating the sums. In particular, if you can write your expression in the form $\scriptstyle \sum _{k=0}^{m}a_{k}b_{m-k}$, you can see it as the coefficient of $\scriptstyle x^{m}$ in the power series expansion of the product: $\scriptstyle \left(\sum _{k=0}^{\infty }a_{k}x^{k}\right)\left(\sum _{k=0}^{\infty }b_{k}x^{k}\right)$ (this is the Cauchy product of power series). Note that the Vandermonde's identity is a special case of this. In your case, the task is not difficult (but ask again here if you meet any difficulty). You can do it in the first sum either in the original form (writing $\scriptstyle {\binom {80}{k}}={\binom {80}{80-k}}$; in this case you also need a closed expression for $\scriptstyle \sum _{k=0}^{\infty }{\binom {k}{r}}x^{k}$, which is related to the binomial series with exponent $-(r+1)$ ) or in your reduction, which is simpler to treat (then you need the simpler $\scriptstyle \sum _{k=0}^{\infty }(k+1)x^{k}$). Another possibility in order to proceed from your reduction is, make a substitution: $j:=k-30$ so $k+1=j+31$ and distribute: this leaves you with two sums, $\scriptstyle \sum _{j}{\binom {50}{j}}$ and $\scriptstyle \sum _{j}j{\binom {50}{j}}$ which is identity (6a) here. Your last sum is indeed close to the Vandermonde's identity, but the result you wrote is not at all correct (you should have done something very bad in the middle). You may write $\scriptstyle {\frac {1}{k+1}}{\binom {99}{k}}={\frac {1}{100}}{\binom {100}{k+1}}$; put $\scriptstyle j:=k+1$ so $\scriptstyle {\binom {200}{120-k}}={\binom {200}{121-j}}.$ to get the form of Vandermonde's identity--pma 15:53, 3 October 2010 (UTC)

Thanks pma. I hope you're well:). I solved both the problems.-Shahab (talk) 02:40, 6 October 2010 (UTC)

Second moment of the binomial distribution

The moment generating function of the binomial distribution is $(1-p+pe^{t})^{n}$. When I take the second derivative I get $n(n-1)(1-p+pe^{t})^{n-2}p^{2}e^{2t}+n(1-p+pe^{t})^{n-1}pe^{t}$. Substituting 0 in for t gives me $n(n-1)p^{2}+np$. Why is this not the same as the variance of the binomial distribution $np(1-p)$?--220.253.253.56 (talk) 11:34, 2 October 2010 (UTC)

See cumulant. Bo Jacoby (talk) 11:51, 2 October 2010 (UTC).

The variance is not the same thing as the raw second moment. The variance is

$E((X-\mu )^{2})\,$

where μ is E(X). The second moment, on the other hand, is

$E(X^{2}).\,$

Michael Hardy (talk) 22:30, 2 October 2010 (UTC)

Then why does the article moment (mathematics) say that the second moment is the variance?--220.253.253.56 (talk) 22:50, 2 October 2010 (UTC)

It doesn't. Algebraist 22:53, 2 October 2010 (UTC)

Moment_(mathematics)#Variance--220.253.253.56 (talk) 23:00, 2 October 2010 (UTC)

There are eighteen words in that section. You seem to have neglected to read the third. Algebraist 23:03, 2 October 2010 (UTC)

So what is a central moment and how are they calculated (can you use the moment generating function)?--220.253.253.56 (talk) 23:05, 2 October 2010 (UTC)

Central moment might help. 129.234.53.175 (talk) 15:52, 3 October 2010 (UTC)

In Moment_(mathematics)#Variance, I've now added a link to central moment. Michael Hardy (talk) 02:48, 4 October 2010 (UTC)

There is already a link to Central moment in Moment (mathematics). I think the guideline is not to link to the same article twice. -- Meni Rosenfeld (talk) 08:28, 4 October 2010 (UTC)

Where is that guideline? To me that seems unwise in long articles. Michael Hardy (talk) 19:44, 4 October 2010 (UTC)

Wikipedia:Manual of Style (linking)#Repeated links. It does mention as an exception the case where the distance is large, but here the instances are quite close in my opinion. -- Meni Rosenfeld (talk) 20:35, 4 October 2010 (UTC)

More Limits

Hello. How can I prove $\lim _{x\rightarrow \infty }x^{a}e^{-x}=0,\forall a\in \mathbb {R}$? I tried l'Hopital's rule but get $\lim _{x\rightarrow \infty }{\frac {ax^{a-1}}{e^{x}}}={\frac {\infty }{\infty }}$. Thanks very much in advance. --Mayfare (talk) 15:19, 2 October 2010 (UTC)

Forget l'Hopital's rule and try to visualise what is happening. If a < 0 then both x^a and e^-x tend to 0 as x grows, so the result is obvious. The case a=0 is also easily dealt with. If a > 0 then as x gets larger, x^a grows but e^x grows even more quickly. In fact, if x > 0, then

$e^{x}>{\frac {x^{m}}{m!}}$

where m is the next integer greater than a. So

$x^{a}e^{-x}<{\frac {m!}{x^{m-a}}}$

I'll let you take it from there. Gandalf61 (talk) 16:06, 2 October 2010 (UTC)

It might not be obvious to the questioner that exponentials grow faster than polynomials (or even what a statement like that means). Mayfare, if you want to use l'Hôpital's rule for this, imagine using it over and over until you don't get ∞/∞ any more. What is going to happen? The exponent in the numerator is going to decrease by 1 each time you use the rule, while the denominator stays the same. So what can you conclude? —Bkell (talk) 17:52, 2 October 2010 (UTC)

If the questioner does not understand that an exponential function grows faster than any polynomial, or why this is implied by

$e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}$

then they cannot understand why $\lim _{x\rightarrow \infty }x^{a}e^{-x}=0$. At best they are reproducing a method (l'Hôpital's rule) learnt by rote, without understanding. Once they do understand the behaviour of exponential functions then the result is intuitively obvious and a formal proof is easily found. Gandalf61 (talk) 09:25, 3 October 2010 (UTC)

While you can take Bkell's suggestion and work that into a proof, I would suggest using the definition of a limit directly. That is $\lim _{x\rightarrow \infty }x^{a}e^{-x}$ equals 0 if for every ε>0 there exists a δ such that if x>δ then |x^a e^^-x|<|ε|. Note that x^a and e^^-x are both eventually monotone functions. Can you solve |x^a e^x|=|ε| ? Taemyr (talk) 18:24, 2 October 2010 (UTC)

L'Hopital's rule will do it if you iterate it: a becomes a − 1, then after another step it's a − 2, and so on. After it gets down to 0 is less, the rest is trivial. However, there's another way to view it: every time x is incremented by 1, e^x gets multiplied by more than 2, whereas the numerator x^a is multiplied by less than 2 if x is big enough. Therefore it has to approach zero. Michael Hardy (talk) 22:27, 2 October 2010 (UTC)

Noticing that x^a = exp(a ln x) is useful. Then

$\lim _{x\rightarrow \infty }{\frac {a\ln x}{x}}=a\lim _{x\rightarrow \infty }{\frac {1}{x}}=0.$

Since exp(x) is an increasing function, the original product must also go to 0. —Anonymous Dissident^Talk 01:53, 3 October 2010 (UTC)

This seems highly questionable to me. Showing that the ratio of the exponents goes to zero does not prove that the ratio of the original functions goes to zero. For example consider the constant functions f(x) = 1 and g(x) = e.

$\lim _{x\rightarrow \infty }{\frac {\ln f(x)}{\ln g(x)}}=\lim _{x\rightarrow \infty }{\frac {0}{1}}=0.$

but clearly f(x)/g(x) does not go to zero. What you actually need is for the difference in the exponents to go to negative infinity, but that's not any easier to prove than the original problem. Rckrone (talk) 02:17, 3 October 2010 (UTC)

I think it does if both functions are increasing. Your counter-examples seem a little trivial, since they are constant functions (which do not change, let alone strictly increase). Perhaps you are correct in general, but in this case the result seems quite clear. —Anonymous Dissident^Talk 02:24, 3 October 2010 (UTC)

I picked a trivial counter example because it's easy to consider. Here is a case with strictly increasing functions: f(x) = (x-1)/x, g(x) = ef(x). Anyway, I was wrong before about taking logs not helping. If you consider ln(x^ae^-x), which is aln(x) - x, you can show it goes to negative infinity by arguing that the derivative a/x - 1 goes to -1. I guess that's not too bad. Rckrone (talk) 02:32, 3 October 2010 (UTC)

Okay, point well taken. —Anonymous Dissident^Talk 03:02, 3 October 2010 (UTC)

If the OP was thrown off by $a\in \mathbb {R}$ but has already proven that $\lim _{x\rightarrow \infty }x^{n}e^{-x}=0,\forall n\in \mathbb {N}$, then consider applying the squeeze theorem with g(x)=xⁿe^-x and h(x)=x^me^-x where n≤a≤m. See also floor and ceiling functions. -- 124.157.254.146 (talk) 02:52, 3 October 2010 (UTC)

And in case the OP didn't catch the remark by Rckrone above, x^a = e^{a ln(x)} so x^ae^-x = e^{a ln(x) - x} and it can be shown that a ln(x) - x → -∞ as x → +∞. -- 124.157.254.146 (talk) 05:50, 3 October 2010 (UTC)