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)

2
votes
1answer
278 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
2
votes
1answer
108 views

A combinatorial identity $\sum_{i=0}^k \binom ni \binom{-n}{k-i} =0$

Can anyone prove the following identity for me? $\sum_{i=0}^k \begin{pmatrix} n\\ i \end{pmatrix} \begin{pmatrix} -n\\ k-i \end{pmatrix}=0$ for any positive integers $n,k$. I'm pretty sure this is ...
3
votes
3answers
158 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
1
vote
1answer
111 views

Least common multiple in binomial expansion

If I sum the terms of a binomial expansion, which would be the least common multiple of all the denominators? Say $\displaystyle \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n}$ ...
3
votes
1answer
121 views

A generalization of the Vandermonde's convolution

I need to find a closed formula for the following sum: \begin{equation} \sum_{i=0}^{n}i^{k}\left(\begin{array}{c} n\\ i \end{array}\right)\left(\begin{array}{c} n^{2}-n\\ c-i \end{array}\right) ...
3
votes
3answers
303 views

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$?

What is the coefficient of the term $x^4 y^5$ in $(x+y+2)^{12}$? How can we calculate this expression ? I've applied the binomial theorem formula and got $91$ terms but I am not sure if it is right ...
1
vote
1answer
44 views

What is the coefficient of x^9 y^16 in the expansion of (7x+21y)^25

binomial(n, k) x^(n-k) y^k Given newtons binomial theorem. I believe the answer is n = 25 k = 16 ...
0
votes
1answer
26 views

Binomial Coefficients-Squares

A discrete random variable $X$ takes value $0,1,2, \ldots n$ with frequency $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Find the variance. I have calculated the mean as such ...
1
vote
1answer
34 views

Binomial Identity/Coefficient Question

So I know that the coefficient of $[x^n]$ is computed by using: $\left( \sum_{j=0}^n a_j b_{n-j} \right)$ = $[x^n]A(x)B(x)$ How is this formula used to make computations, for example, how do I ...
0
votes
5answers
611 views

Proof of a binomial identity $\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$

Prove that $$\sum_{k=0}^n {n \choose k}^{\!2} = {2n \choose n}.$$ The exercise provides the following hint: $\,\,\displaystyle{n \choose k}={n\choose n-k}$. Any help?
0
votes
2answers
80 views

Prove the identity $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$

I need to prove the following identity: $\sum_{{{\underset{k-even}{k=0}}}}^{n}{n \choose k}2^{k}=\frac{3^{n}+(-1)^{n}}{2}$ I know that - $\sum_{k=0}^{n}{n \choose k}2^{k}=3^{n}$ but don't know ...
6
votes
2answers
763 views

Proving $\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}=4^n-{2n+1\choose n+1}$

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
9
votes
4answers
366 views

Evaluate a finite sum with four factorials

Given positive integers $k, m, n$ such that $1 \leq k \leq m \leq n$. Evaluate $$ \sum^{n}_{i\mathop{=}0}\frac{1}{n+k+i}\cdot\frac{(m+n+i)!}{i!(n-i)!(m+i)!}$$ Any hints? I'm stuck on ...
2
votes
2answers
163 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
0
votes
1answer
82 views

Can this summation be simplified?

I got something like $$ a_{n} = {1 \over 4^{n + 1}}\sum_{k = 0}^{\left\lfloor n/2\right\rfloor} {n + 1 \choose 2k + 1}\left(-3\right)^{k} $$ Could this be simplified more?
2
votes
0answers
94 views

How to prove this combinatorial identity

I am wondering how to prove the following identity: $$\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}$$ It seems that I can negating the upper index of ${s \choose k-t} ...
1
vote
1answer
63 views

A combinatorial identity?

Is there a combinatorial identity for the following: $$\sum_{k=0}^{i}\binom{n}{k} $$ for arbitrary integers $n, i$ with $n > i$? If so, what is this identity called?
-1
votes
1answer
31 views

Binomials (a) 8!/6! (b) 10!/9!

I don't know the exact formula to use for this expansion I have tried to use multiple equations so therefore there must be one you can use.
5
votes
2answers
113 views

Prove that $\sqrt{8}=1+\dfrac34+\dfrac{3\cdot5}{4\cdot8}+\dfrac{3\cdot5\cdot7}{4\cdot8\cdot12}+\ldots$

Prove that $\sqrt{8}=1+\dfrac34+\dfrac{3\cdot5}{4\cdot8}+\dfrac{3\cdot5\cdot7}{4\cdot8\cdot12}+\ldots$ My work: $\sqrt8=\bigg(1-\dfrac12\bigg)^{-\frac32}$ Now, I suppose there is some "binomial ...
1
vote
1answer
44 views

Problem with raising parentheses to powers

Simply math question, lets say I have $(2x^2)^3$.Is this equal to $8x^6 , 2x^5, 2x^6$, or $8x^5$ ? It is a simple problem but what confuses me is do if I multiply the coefficient separately from the ...
2
votes
1answer
61 views

Question about balls in urns

Suppose there are $n$ balls in an urn, and $r$ of them are red. I select $m$ balls from this urn at random. What is the probability that at least $k$ of them are red? $m$ must be less than $n$, but ...
0
votes
2answers
37 views

Get polynomial function from 3 points

I need to understand how to define a polynomial function from 3 given points. Everything I found on the web so far is either too complicated or the reversed way around. (how to get points with a given ...
0
votes
3answers
133 views

Finding the Coefficient of X^9 in (1+x^3+X^8)^10

This is solved by the following approach e1 takes values 0 3 8 e2 takes values 0 3 8 .. .. .. . and finally it is said that we get 9 when we take ai=3.And the answer become 10c3. Can someone ...
4
votes
1answer
66 views

Verification of a Combinatorial Identity

I have a challenge for you combinatorial mathematicians. Is anyone willing to verify the following combinatorial identity? ...
3
votes
2answers
135 views

$\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$?

Is it true that $\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$ ? I feel that it is true because if we define $H_1 (x,r)=rx(1+x)^{r-1}$ , and $H_{m+1}(x,r)=x \dfrac d ...
5
votes
8answers
360 views

If $\,\,x+\dfrac{1}{x}=5,\,\,$ find $\,\,x^5+\dfrac{1}{x^5}$.

If $x>0$ and $\,x+\dfrac{1}{x}=5,\,$ find $\,x^5+\dfrac{1}{x^5}$. Is there any other way find it? $$ \left(x^2+\frac{1}{x^2}\right)\left(x^3+\frac{1}{x^3}\right)=23\cdot 110. $$ Thanks
1
vote
1answer
107 views

Solving Binomial Coefficients with Double Counting

I have a problem that I am trying to solve two different ways. The problem is: The following equality holds, for a positive integer $n$: $$\dbinom{2n}{2} = 2\dbinom{n}{2} + n^2$$ Show that ...
1
vote
2answers
64 views

To provide a combinatorial argument for a combinatorics equality.

Prove that, $${n \choose m}+2{n-1 \choose m}+\ldots+(n-m+1){m \choose m}={n+2 \choose m+2}$$ My work: I thought it would be better to use combinatorial argument than trying to provide a rigorous ...
0
votes
0answers
38 views

Can this binomial coefficient term be simplified?

Can this be simplified? $$\binom{n}{k}\binom{k}{j}2^{-k}$$ assuming $k \le n$ and $j \le k$? I've tried expanding it in to factorials, but other than a $k!$ term, nothing seems obvious. ...
2
votes
3answers
59 views

$2^n$ choose something

Let $m$ be a positive integer, and let $n=2^m$. Prove that the numbers $$ \binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1} $$ are all even. -Source: ASMP sample problems Counting Strategies number ...
2
votes
2answers
71 views

Counting two ways, $\sum \binom{n}{k} \binom{m}{n-k} = \binom{n+m}{n}$

prove by counting two ways: I though to prove the right hand side I would say: Let n represent a number of boys and m a number of girls. We want to choose a group of n from boys and girls. But for ...
1
vote
2answers
337 views

DICE - Rolling at least *k* on *n* six-sided dice - with a twist!

I am putting together a table of dice probabilities for a project I am working on and have found myself intimidated by a little "special case" I'm trying to work with. For determining the probability ...
3
votes
1answer
46 views

Bounding one binomial coefficient with another

For given $n$ and $m$, I am interested in finding an expression for the smallest $r$ such that the following holds: ${r \choose m} \geq \frac{1}{2} {n \choose m}$. Is such an expression, or at least ...
0
votes
1answer
95 views

Closed form of $n!\sum_{k=3}^{n-1}{{n-2}\choose{k-1}}$

$n$ is given, and it takes part in the following formula. $$n!\sum_{k=3}^{n-1}{{n-2}\choose{k-1}}$$ Is there a nicer way for expressing it? Without the summation sign?
3
votes
1answer
143 views

How find this sum of binomial coefficients $\sum_{k=0}^{n}k\binom{n+k}{k}2^k$

How Find this sum $$\sum_{k=0}^{n}k\binom{n+k}{k}2^k$$ My idea: since $$\binom{n+k}{k}k=\dfrac{(n+k)!}{n!(k-1)!}$$ and I have other idea: Consider $$f(x)=\sum_{k=0}^{n}\binom{n+k}{k}x^k$$ then ...
0
votes
1answer
60 views

$n \choose m$ as number of bijections

I saw that my former question came from a certain exercise so I'll just write it down here: It's to proof that the number of $m$-element subsets in an $n$-element set is $n \choose m$. A hint is ...
0
votes
1answer
44 views

Finding the parent of a node in recombining binomial tree

I have posted an earlier question: Finding the child node in the recombining binomial tree. Now I would like to find the parent of a node in recombining tree. The tree looks like this: Now I need ...
0
votes
1answer
74 views

Closed form for summation: $\sum\limits_{c_0+c_1+\cdots+c_n = n \atop c_n = n-i}\prod\limits_{j=0}^n{j \choose c_j}$

I am looking for a closed form for this expression: $f(n, i) = \sum\limits_{c_0+c_1+\cdots+c_n = n \atop c_n = n-i}\prod\limits_{j=0}^n{j \choose c_j}$ With the condition that $\sum\limits_{k=0}^n ...
0
votes
0answers
34 views

Can we reduce this matrix to the identity, which contains binomial elements?

We are given a function: $$f(a,b,m) = \binom{n}{b}\binom{n-b}{a}\binom{n-a-b}{m-a}$$ We can suppose we have the following $(n/2)^2 \times (n+1)$ matrix (form), that we wish to find the value for the ...
1
vote
1answer
44 views

Lower bound functional binomial r.v.

I am trying to find a bound of the type $\mathbb{E}(|B-\frac{N}{2}|) \geq C \sqrt{N}$ Where $B$ is a binomial variable with parameters $(N,\frac{1}{2})$. The bound doesn't need to be very tight in ...
1
vote
4answers
348 views

Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$.

I need to find calculate the sum Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$. Simple algebra lead to this ...
1
vote
2answers
102 views

Finding the child node in the recombining binomial tree

I am trying to program a binomial tree in Matlab. The tree looks something like this: The numbers in the picture refer to the index of the array to create a binomial tree. Problem: Value of 2 = ...
1
vote
3answers
183 views

Show that ${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$

Show that $${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$$ Please help me showing the above identity. I tried to solve it in algebraic way and in combinatoric way, but ...
1
vote
5answers
149 views

$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}=?$

I was asked to find a closed formula for the sum $$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}$$ could anyone give me an advice on how to get started?
1
vote
1answer
117 views

Convexity of Binomial Term

I am reading a book on the probabilistic method, and the following claim was made: $\dbinom{y}{n}$ is convex. Why is this the case?
0
votes
0answers
21 views

A multiple sum involving binomial coefficients.

Let $q\ge 1$ and $0 < a < b$ be integers and $\vec{p}:= \left(p_l\right)_{l=1}^q$ be a vector of real numbers. The question is to find the following sum. \begin{equation} {\mathfrak ...
6
votes
1answer
157 views

How prove binomial cofficients $\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$

How prove this $$\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$$ This equation How prove it? Thank you I want take this ...
2
votes
2answers
47 views

Is it true that $\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3} = \binom{n}{3}\binom{n-3}{k-3}$?

I was asked to find a closed formula for $$\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3}$$ To remove the $\sum$ if you will. Here's my reasoning, let's say we have a football team with $n$ players. First we ...
13
votes
3answers
357 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
1
vote
2answers
82 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...