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)

7
votes
3answers
723 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
92 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
5
votes
2answers
223 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
678 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
361 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
178 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
370 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
205 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 ...
4
votes
2answers
816 views

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

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
346 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
226 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
145 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
327 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
821 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
2k 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
195 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
791 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
454 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
250 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
412 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
395 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
1k 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
329 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
536 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
326 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
164 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
655 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
236 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
850 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
425 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
193 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
628 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 ...
5
votes
2answers
275 views

Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths

How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$? I have to prove it using lattice paths, it should be related to Catalan numbers The $n$th ...
2
votes
1answer
1k views

Proving that $n \choose k$ is an integer [duplicate]

Possible Duplicate: Proof that a Combination is an integer I can't think how to prove that ${n\choose k} \in\mathbb{Z}$. I've played with it for a while, using the factorial definition for ...
5
votes
2answers
152 views

An identity on the number of trees

Let $T_n$ be the number of labelled trees on $n$ vertices, then $$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$ Using this question, I was able to prove that $$ T_n= \frac{n}{2} \ ...
9
votes
2answers
334 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
7
votes
4answers
657 views

Why does this expected value simplify as shown?

I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is: ...
6
votes
3answers
1k views

Inductive proof for the Binomial Theorem for rising factorials

I want to proove the following equality containing rising factorials $$(x+y)^\overline{n}\overset{(*)}{=}\sum_{k=0}^n\binom{n}{k}x^\overline{k}y^\overline{n-k}.$$ For $n=1$ this equality is ...
10
votes
1answer
773 views

Sum of product of binomial coefficient

Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$ I tried to use the multinomial theorem, but it doesn't seem applicable.
2
votes
2answers
346 views

How to prove the binomial coefficient identity $\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$ by induction?

$$\binom{n}{c}+ \binom{n}{c+1}= \binom{n+1}{c+1}$$ How can I prove using induction for all values of $n$ and $c$? I have no idea how to start it. Please help!
14
votes
2answers
5k views

Approximating the logarithm of the binomial coefficient

We know that by using Stirling approximation: $\log n! \approx n \log n$ So how to approximate $\log {m \choose n}$?
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
1
vote
2answers
848 views

A Combinations Problem Involving Days Of the Week

I'am reading through Engineering Math by Ken Stroud/Dexter Booth and in page 274 under Combinations. Here's the situation. Assuming that you have a part-time Job in the weekday evenings where you ...
24
votes
6answers
1k views

Proofs of $\lim\limits_{n \to \infty} \left(H_n - 2^{-n} \sum\limits_{k=1}^n \binom{n}{k} H_k\right) = \log 2$

Let $H_n$ denote the $n$th harmonic number; i.e., $H_n = \sum\limits_{i=1}^n \frac{1}{i}$. I've got a couple of proofs of the following limiting expression, which I don't think is that well-known: ...
0
votes
1answer
168 views

Is my argument wrong? (A combinatorial exercise)

How many ways are there to arrange $m$ distinct flags on a row of $r$ flagpoles? The order of the flags on the flagpoles (from top to bottom) matters. My argument is: I have $mr$ points and I have to ...
1
vote
1answer
83 views

A “fast” approach to compute $\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$ [duplicate]

Possible Duplicate: How to find a closed formula for the given summation I am looking for a fast/best approach to compute $$\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$$ For ...