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)

3
votes
1answer
42 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
85 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
112 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
56 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
35 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
64 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
41 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
305 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
80 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
166 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
129 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
81 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
14 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
147 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
44 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 ...
11
votes
2answers
289 views

Show that $\displaystyle\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 this $$ \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
54 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 ...
2
votes
1answer
73 views

Finding the super-mean (NOT the mean) of a set of numbers.

the super-mean is found by grouping pairs of numbers and finding the average successively until there is just one number. For example, $$(1-2-3-4-5) \to ((1+2)/2,(2+3)/2,(3+4)/2,(4+5)/2) \\ ...
1
vote
1answer
29 views

Largest K-multiple free set out of a fully ordered set

i'm struggling conceptually with this problem, i don´t know how to approach it in a clever way (without a computer, or at least without a brilliant algorithm). Mathematicians defined a k-multiple set ...
3
votes
1answer
48 views

Coefficients in Pochhammer Expansion

Can anyone tell me if there is a formula for finding the coefficient of $x^3$ in the expansion of $(3x+5)_{6}$, where $(a)_n$ denotes the Pochhammer symbol, i.e. $(a)_{n}=a\cdot(a+1)\cdots(a+n-1)$? ...
1
vote
2answers
109 views

Help proving ${n \choose k} \equiv 0 \pmod n$ for all $k$ such that $0<k<n$ iff $n$ is prime.

I can prove the $n$ is prime case: If $n$ is prime, then since $k < n$ and $n$ is prime, the factor of $n$ in the numerator won't be cancelled out. So the question boils down to Let an integer ...
0
votes
1answer
64 views

Compute a sum involving binomial coefficients

Let $0 < a < b$ and $p_1 >0$ and $p_2>0$ be integers. The question is to prove the following identity: \begin{equation} \sum\limits_{j=a}^b \left(\begin{array}{c} j \\ p_1 \end{array} ...
1
vote
2answers
78 views

Probability problem with binomial/multinomial distribution

Mary knows the answers to $20$ of the $25$ multiple choice questions on the Psychology $101$ exam, but she has skipped several of the lectures, she must take random guesses for the other five. ...
0
votes
1answer
178 views

Project Euler #453 confusion

So I decided to give a shot on the #453 project euler problem but there is something that confuses me with the numbers given. I decided to start by calculating the possible arrangements of 4 vertices ...
4
votes
2answers
270 views

maybe this sum have approximation $\sum_{k=0}^{n}\binom{n}{k}^3\approx\frac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty$

prove or disprove this $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$ this problem is from when Find this limit ...
0
votes
2answers
54 views

Prove that the set of all subsets of cardinality k of a set of cardinality n has cardinality n choose k

That title is probably very compound and confusing so here's a picture. I'm onto something here. Intuitively this makes sense. Let $A$ be a set such that $|A| = n$. If we choose the first $k$ ...
0
votes
3answers
137 views

Combinatorial proof that $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$

Prove $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$. It can be proven easily using induction and Pascal's identity, but I want some insight. The alternating sum reminds of ...
8
votes
1answer
278 views

Smallest constant in exponent so that limit of sum is $0$

I am trying to work out the smallest constant $c>0$ so that $$\lim_{n \to \infty} \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}} =0 .$$ ...
3
votes
1answer
98 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
0
votes
2answers
280 views

Binomial Theorem Practical Problem

I have been studying the 'Binomial Series', Chapter 16, Pg.125 within the Engineering Mathematics Book by John Bird. After completing this section I have attempted to complete the exercises for ...
5
votes
2answers
199 views

How prove this $\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $

I think the following equality is true ($p\in \mathbb{N},p\ge 2$): $$\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $$ when $p=2$, then ...
0
votes
1answer
60 views

General term of a series

I am trying to find the general term of the series: $$( 1 + x + ... + x^{m-1} )^k$$ I am trying to implement the KZ filter and it requires the coefficients of the above series. Here, k and m are ...
0
votes
2answers
44 views

Couple of Counting (how many ways) questions.

1.If I have a group of 10 seats reserved for people, and there are n=>10 total people, how many ways are there to choose who gets the 10 seats? for ex:If there was a definite number of people lets ...
1
vote
2answers
148 views

Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.

I've been grappling with this problem for a while but haven't solved it. Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.
0
votes
2answers
63 views

Pascal's Triangle Proof

Trying to determine a formula for the sum of the entries of the $n$th row of Pascal’s triangle, for any natural number $n$. Any proof will do as I have to determine $3$ different proofs. - So far, ...
1
vote
1answer
64 views

Binomial coefficient properties

On "theoretical computer science cheat sheet" I found a special formula which is: $$ {n \choose k} = (-1)^k {k-n-1 \choose k}$$ But when I try to expand the value of ${k-n-1 \choose k}$ I have ...
0
votes
1answer
45 views

Finding coefficient of $x^k$ in summation of binomial series

I am not able to solve this problem Find the coefficient of $x^k\;\;(k$ is greater than or equal to zero and lesser than or equal to $n$) in the expansion of $E = 1 + (1+x) + (1+x)^2 .... + (1+x)^n$ ...
3
votes
1answer
43 views

Binomial coefficient difference

I have the following difference of binomial coefficients: $$f(m)={m+n\choose n}-{m-d+n\choose n}$$ I believe the following two things should hold true: For $m$ large enough, $f(m)$ is a polynomial ...
1
vote
1answer
86 views

What is the sum of divisors of binomial&factorial

$$\sum_{m|\frac{n!}{i!(n-i)!}} m$$ Perhaps a good start is $$\sum_{m|n!} m$$ When seeing this last sum or also this one $$\sum_{m|lcm(1,2,...,n)} m$$ I sort of want to use $(n+1)n\over2$ somehow.
0
votes
2answers
88 views

Is this Newton binomial legal?

is this equation proper? $$ \binom {9} {12} = 0 $$ so if we have a binomial $$ \binom {n} {k} $$ and when $$ n<k $$ the result is 0?
4
votes
2answers
86 views

Show $\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$

As the title says... We are asked to show that $$\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$$ I tried with induction, but that seems to never work with these kind of questions. We need ...
1
vote
2answers
50 views

Number of solutions to equation - is there a better way of solving this than inclusion-exclusion?

We are asked to find the number of solutions for $a+b+c+d+e+f=20$ when $2 \leq a,b,c,d,e,f \leq 6$ Is there a better way of solving it than what I did ? because it an exam, this seems like a very ...
11
votes
3answers
307 views

Prove that $\,\,\displaystyle\inf_{n\in\mathbb N}\sum_{k=0}^{p}\lvert\sin{(n+k)^p}\rvert>0$

For any positive integer number $p$, show that $$\inf\left\{ {\left\vert\sin{(n^p)}\right\vert+\left\vert\sin{(n+1)^p}\right\vert+\cdots+ \left\vert\,\sin{(n+p)^p}\right\vert\, :\,n\in ...
1
vote
2answers
205 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
3
votes
1answer
98 views

Sum of fraction of factorials

Can anybody explain this? $$\sum\limits_{k=1}^{\frac{m-1}2}\frac{(2k)!(2m-2k)!}{(2k-1)(2m-2k-1)k!^2(m-k)!^2}=\frac{(2m)!}{(2 m-1)m!^2}$$ I did actually simplify this to: ...
1
vote
0answers
54 views

Increasing fraction of sum of binomial coeffients

Let $n$ be a positive integer. Show that the quantity $$ \displaystyle \frac{ \displaystyle \sum_{i=1}^n { n+k \choose i-1 } }{ \displaystyle \sum_{i=1}^n { n+k+1 \choose i } } $$ is ...
2
votes
1answer
129 views

Identify $\sum(-1)^{n-k}2^{2k}\binom{n+k}{2k}$

Does anybody know what the following sum evaluates to? $$ \sum_{k=0}^n{(-1)^{n-k}}2^{2k}\binom{n+k}{2k} $$
0
votes
1answer
52 views

Linear combinations of vector $\binom{n+r-1}{r-1}$ and combinations with repetitions $\binom{n+r-1}{r}$

There are $$\binom{n+r-1}{r-1} \tag{1}$$ nonnegative vectors $(x_1,x_2,\dots,x_r)$ such that $x_1+x_2+\dots+x_r=n, \ \ \ \ \ \ x_i \ge 0, \ \ \ 1 \le i \le r$ Then the number of selections of ...
0
votes
1answer
38 views

Binomial distribution convergence

Let $Y \sim\binom{n}{\pi}$ Suppose $n \rightarrow \infty$ and $\pi \rightarrow 0$ such that $n\pi \rightarrow \mu$, where $\mu$ is a constant. derive the limiting distribution of Y. $f_Y(y)= ...