Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

5
votes
2answers
4k views

A fair coin is tossed $n$ times by two people. What is the probability that they get same number of heads?

Say we have Tom and John, each tosses a fair coin $n$ times. What is the probability that they get same number of heads? I tried to do it this way: individually, the probability of getting $k$ ...
0
votes
1answer
565 views

binomial calculation method

I want solve this probability: For $p= 0.4$ $q=0.8$ $n= 20$ $1-P(5<x<11)$ = $1-\sum_{k=6}^{10} \binom{20}{k}(0.4)^k(0.6)^{20-k}. Wolfram Alpha -> = 0,2531$ Is calculation method ...
6
votes
1answer
2k views

Using the Taylor expansion for ${(1+x)}^{-1/2}$, evaluate $\sum_{n=0}^\infty \binom{2n}{n} a^n$

Using the Taylor expansion for $${(1+x)}^{-1/2}$$ we have $${(1+x)}^{-1/2}= \sum_{n=0}^\infty \binom{-1/2}{n} (x^n)$$ for $|x|<1$. But if $|a| <1$, how can we use the above fact to find ...
4
votes
1answer
615 views

Why is $n\choose k$ periodic modulo $p$ with period $p^e$?

Given some integer $k$, define the sequence $a_n={n\choose k}$. Claim: $a_n$ is periodic modulo a prime $p$ with the period being the least power $p^e$ of $p$ such that $k<p^e$. In other words, ...
5
votes
4answers
2k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...
3
votes
3answers
189 views

Proofs from the BOOK: Bertrand's postulate: $\binom{2m+1}{m}\leq 2^{2m}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 8: It's about the part, where the author says: $$\binom{2m+1}{m}\leq 2^{2m}$$ because ...
48
votes
2answers
3k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is ...
5
votes
1answer
382 views

How can I express $\sum_{k=0}^n\binom{-1/2}{k}(-1)^k\binom{-1/2}{n-k}$ without using summations or minus signs?

How can I express $$\sum_{k=0}^n\binom{-1/2}{k}(-1)^k\binom{-1/2}{n-k}$$ without using summations or minus signs?
0
votes
1answer
398 views

Finding number of intersections between line A and B

I was recently working through the IB HL textbook and I came across two interesting problems. Exercise 8E Question 18. Line A contains 10 points and line B contains 7 points. If all points on line ...
1
vote
1answer
164 views

On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2

Let $g_n=$ number of 2-regular graphs on $n$ vertices Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2 By a computation with the exponential generating function I think that ...
2
votes
1answer
211 views

Evaluating an expression using snake oil and convolutions gives different answers

I have to evaluate this expression $\sum \limits_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{n-k}$ using snake oil and convolutions. The problem is that I got two different results, could you help me to ...
21
votes
6answers
5k views

prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the first n even ...
2
votes
1answer
281 views

Evaluating an expression using snake oil

I have to evaluate this expression: $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{-k}$, (In the original question we had $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{k}$) this is what I have done: ...
10
votes
2answers
164 views

Prove the identity $ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$

$$ \sum\limits_{s=0}^{\infty}{p+s \choose s}{2p+m \choose 2p+2s} = 2^{m-1} \frac{2p+m}{m}{m+p-1 \choose p}$$ Class themes are: Generating functions and formal power series.
7
votes
3answers
673 views

Summation Identity: $\sum_{i=1}^ni^3 = \left( \frac{n(n+1)}{2} \right)^2$

I have to prove: $$\sum\limits_{i = 1}^n i^3 = \Bigg( \frac{n(n+1)}{2}\Bigg)^2$$ Using the following: $$n^3 = 6 {n \choose 3} + 6 {n \choose 2} + n \quad \forall n \in \mathbb{N}$$ My work is that ...
3
votes
3answers
90 views

Is this expression right? If yes how can I prove it combinatorially?

Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please
4
votes
1answer
200 views

Evaluating the sum $\sum\limits_k \ k\binom{n}{k}^2$ using generating functions

I have to evaluate this expression $\sum\limits_k \ k\binom{n}{k}^2$ using generating function. Could you help me please? Also with some hints.
3
votes
1answer
634 views

Binomial coefficient equal to $\binom nk + 3\binom{n}{k-1} + 3\binom{n}{k-2} + \binom{n}{k-3}$?

Find one binomial coefficient equal to the following expression: $$\binom nk + 3\binom{n}{k-1} + 3\binom{n}{k-2} + \binom{n}{k-3}$$ I tried to expand using the definition of $\dbinom{n}{k} = ...
1
vote
3answers
2k views

Calculate the expansion of $(x+y+z)^n$

The question that I have to solve is an answer on the question "How many terms are in the expansion?". Depending on how you define "term" you can become two different formulas to calculate the terms ...
6
votes
2answers
343 views

Prove the identity $\sum\limits_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m} $

I need to prove $$\sum_{s=0}^{\infty} {p-s \choose m}{q+s \choose q} = {p+q+1 \choose p-m} $$ using: $$(1-x)^{-m-1} (1-x)^{-q-1} = (1-x)^{-m-q-2} .$$ ok, generating function :$\frac1{(1-x)^{m+1}} = ...
2
votes
4answers
176 views

Simplify an expression to show equivalence

I am trying to simplify the following expression I have encountered in a book $\sum_{k=0}^{K-1}\left(\begin{array}{c} K\\ k+1 \end{array}\right)x^{k+1}(1-x)^{K-1-k}$ and according to the book, it ...
10
votes
1answer
224 views

Evaluating $\sum_{k=0}^n \binom{n}{k} 2^{k^2}$

Can someone please help me simplifying this sum $$\sum_{k=0}^n \binom{n}{k} 2^{k^2}$$ Wolframalpha fails (see here). Thanks in advance. The sum counts the number of (labelled) digraphs (with ...
8
votes
4answers
362 views

Why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k} = 0$?

I know that the expansion of $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k}$ equals to zero. But why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$ also equal to zero for $n \geq 2$? I've been ...
3
votes
1answer
203 views

Find $\sum\limits_{k=\frac{n+1}{2}}^n{n \choose k}$ closed form

Write $$\sum\limits_{k=\frac{n+1}{2}}^n{n \choose k}$$ in its closed form. $n \in N_{odd}$ First time to confront this kind of problem. How do I solve it? (If its a "you are asking for too ...
2
votes
2answers
736 views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
7
votes
2answers
341 views

Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$

I need to estimate the asymptotics of $$\sum_{k=0}^{n} {\binom n k}^a, \quad a>2, \quad a \in \mathbb{N}$$ In particular, I'm pretty much interested in $a=4$ case, but if the general solution ...
5
votes
3answers
221 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
0
votes
1answer
140 views

Divisibility question

Let $r$ be an integer greater than $2$. Is there a simple way of showing that $2^r$ divides $\left(\begin{array}{c} {2}^{r-2} \\ k \end{array}\right) 2^{2k}$ but it does not divide ...
5
votes
1answer
304 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
8
votes
5answers
755 views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
7
votes
3answers
1k views

Proof of a combinatorial identity: $\sum_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$ [duplicate]

Possible Duplicate: Identity involving binomial coefficients This was part of a homework assignment that I had, and I couldn't figure it out. Now it is bugging me. Can anyone help me? ...
6
votes
2answers
190 views

A resemblance between 2 binomial identities - why?

Let $F$ be any field (or even ring). The following formal power series identity (i.e., equality in $F[[x]]$) holds for any $j \ge 0$: $$(1-x)^{-j} = \sum_{i \ge 0} \binom{i +j -1}{i} x^i $$ The ...
5
votes
3answers
680 views

How can I simplify this expression involving binomial coefficients?

How can I simplify the following expression? $$\sum_{k=1}^n \binom{n}{k}^2$$
8
votes
2answers
421 views

Is there a combinatorial way to see the link between the beta and gamma functions?

The Wikipedia page on the beta function gives a simple formula for it in terms of the gamma function. Using that and the fact that $\Gamma(n+1)=n!$, I can prove the following formula: $$ ...
3
votes
1answer
247 views

Proof of identity involving binomial coefficients

I'll be happy if you could help me prove this argument with algebraic tools: $${N\choose 0}a^N+{N\choose 1}a^{N-2}+{N\choose 2}a^{N-4}+{N\choose 3}a^{N-6}+\dots = \frac{a^2+1}{a}$$ Thanks, Don
0
votes
1answer
391 views

Lattice Paths Question

You know, how we can have lattice paths, where we can move either one block north, or one block east, and we have the find all the possible ways of reaching the point (x.y) from (0,0). That is ...
6
votes
1answer
1k views

Partial sum of rows of Pascal's triangle

I'm interested in finding $$\sum_{k=0}^m \binom{n}{k}, \quad m<n$$ which form rows of Pascal's triangle. Surely $\sum\limits_{k=0}^n \binom{k}{m}$ using addition formula, but the one above ...
4
votes
3answers
375 views

Combinatorial proof for $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$?

I have to prove the following using a combinatorial proof: $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$ Ok, so here is what I have worked out so far: We ...
5
votes
2answers
960 views

Show $\sum\limits_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$

How do you prove that $\sum\limits_{n=0}^{\infty}{2n \choose n}x^n=(1-4x)^{-1/2}$? I tried to identify the sum as a binomial series, but the $4$ and the $-1/2$ puzzle me. (This series arises in ...
6
votes
1answer
315 views

Is this binomial coefficient identity known?

I stumbled across this identity involving binomial coefficients this morning: If $n$, $k$, $a$, and $b$ are positive integers and $n=a+b$, then $ \displaystyle \binom{n}{k} =\sum_{i=0}^k ...
3
votes
3answers
490 views

Water and wine mixing problem

This is a well-known problem involving a water barrel and a wine barrel, described here. The trick to solving the puzzle is that one need not make the calculations for each stage of the liquid ...
2
votes
5answers
309 views

summation of x * (y choose x) binomial coefficients

What does this summation simplify to? $$ \sum_{x=0}^{y} \frac{x}{x!(y-x)!} $$ I was able to realize that it is equivalent to the summation of $x\dbinom{y}{x}$ if you divide and multiply by $y!$, but ...
2
votes
2answers
163 views

Proving a function is a ring homomorphism

If $R$ is an integral domain with char $p$ where $p>0$ and $f:R\to R$ where $f(x)=x^p$ How would one go about showing addition is preserved? e.g. $f(a+b)=f(a)+f(b)$? Multiplication is obvious. So ...
4
votes
2answers
643 views

Why does $\sum\limits_{i=0}^k {k\choose i}=2^k$ [duplicate]

Possible Duplicate: Proving a special case of the binomial theorem Can anyone explain to me why $$\sum\limits_{i=0}^k {k\choose i}=2^k\,?$$ Thanks in advance
5
votes
3answers
228 views

A question about limit

My question is: What is the result of this limit: $\displaystyle \lim_{n \to +\infty} \frac{{n \choose n/2}}{2^n}=$ ?
8
votes
3answers
759 views

Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
12
votes
1answer
1k views

Combinatorial proof of $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$

Using the following equation: $$\sum_{k=0}^n {n \choose k}3^k=4^n$$ I need to prove that both sides of the equation solve the same combinatorial problem. It's easy to see that the right side of the ...
11
votes
5answers
419 views

How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$

Let $p \in \mathbf{N}$. I don't know how to prove that $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ and $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$ ...
1
vote
0answers
191 views

Interdependent constraints combination problem

I am trying to solve the following combination problem. You have 4 knobs or levers that have maximum values, such as 0-20, 0-30, 0-50 and 0-100. Their total values must equal an amount, say 47. Their ...
4
votes
2answers
589 views

How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?

This sum is difficult. How can I compute it, without using calculus? $$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$ If someone can explain some technique to do it, I'd appreciate it. Or advice using ...