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
1answer
289 views

Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
7
votes
2answers
201 views

About one generating function

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
1
vote
2answers
24 views

Problem involving summation and binomial coefficient

I have been fighting with this but I'm really not getting anywhere. $$\sum_{0\leq2k\leq n}\binom{n}{2k}2^k\equiv0\pmod 3$$ $$if$$ $$n\equiv2\pmod 4$$ Hint: Consider ...
7
votes
4answers
713 views

partial sum involving factorials

Here is an interesting series I ran across. It is a binomial-type identity. $\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}}{(n-k)!}=4^{n}\cdot n!$ I tried all sorts of playing around, ...
2
votes
1answer
19 views

Relating Binomial Coefficients

This question popped up in my revision sheet, and was just wondering on how to do it (this is high-school math by the way, so nothing too complicated please) "Expand $(x+(1-x))^n$, and use this to ...
1
vote
0answers
15 views

The distribution of sum of two binomials with complement success probabilities

It is well-known that if $X$ and $Y$ are independent binomial random variables with parameters $(n_1,p)$ and $(n_2,p)$ respectively, $Z = X+Y$ has a binomial distribution with with parameters ...
2
votes
2answers
82 views

Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction

I have a problem with following equality: $$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$ And I would like to use induction in following way: Base: $$ m = n $$ And: $$ ...
3
votes
0answers
70 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
5
votes
6answers
2k views

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

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
3
votes
3answers
102 views

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ...
4
votes
0answers
64 views

Binomial triplets

Solutions to the equation $$\dbinom{a}{n}+\dbinom{b}{n}=\dbinom{c}{n}$$ I will refer to as 'Binomial triplets of order $n$'. These triplets describe simplicial $n$-polytopic numbers that can be ...
2
votes
2answers
71 views

Product rule for simplex numbers

The $n$th triangular number is defined as $T_2(n) = n(n+1)/2$, and there is an interesting product rule for triangular numbers: $$T_2(mn) = T_2(m)\,T_2(n) + T_2(m-1)\,T_2(n-1).$$ The tetrahedral ...
0
votes
1answer
29 views

Binomial Coefficients (2,1) [on hold]

What are binomial coefficients? Can someone explain. For example: (2,1). or what (2n,n) means
5
votes
3answers
81 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
3
votes
0answers
143 views

How to prove that $\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$?

How to prove this: $$\sum_{k=0}^\infty \binom{x}{x-k}\cdot\binom{x}{k-x} = 1$$ For all $x\in\mathbb R_{\ge0}$ and with $\binom{x}{r}=\frac{\Gamma(x+1)}{\Gamma(r+1)\cdot\Gamma(x-r+1)}$ It is obviously ...
3
votes
3answers
54 views

difficult problem about binomial coefficients

If $r,m,n\in \mathbb N$ so that $r\le \min \{n,m\}$, then $$\binom{n+m}{r} = \binom{n}{0}.\binom{m}{r}+\binom{n}{1}.\binom{m}{r-1}+...+\binom{n}{r}.\binom{m}{0}.$$ If $\min \{n,m\} < r$, then how ...
0
votes
0answers
13 views

Limiting Poisson distribution

Do you know a paper where the limiting joint Poisson Distribution to a Multinomial Distribution is stated? I read that for a multinomial Distribution $Mul(n, (p_i)_{i=1}^k)$, where $p_i \rightarrow ...
0
votes
0answers
36 views

Sum of independent discrete random variable

Here is my attempt of deriving the sum of independent random variable in the discrete case : $\underline{\textbf{Sum of independent random variables}}$ Let $\mathcal{C_1}, \mathcal{C_2}$ be ...
1
vote
1answer
16 views

Question concerning an example of higher derivatives and binomes

I got this exercise form OCW 18.03SC - problem 1G-5b: What is the solution of the following derivative?: $$\dfrac{d^{p+q}}{dx^{p+q}}x^p(1+x)^q$$ I used Leibniz' formula and the only non-zero term ...
2
votes
1answer
21 views

Order of Binomial addition

I was reading up a statement in probability which said that $nC_0 + nC_1 + nC_2 +\dots+ nCm$ is of order $n^m$ where $nCm$ is notation for number of combinations from a collection of $n$ taking $m$ ...
4
votes
2answers
68 views

Evaluating Combination Sums

Evaluate $$\sum_{k=0}^n{n+k\choose 2k} 2^{n-k}$$ So im not really sure how to begin with this. I would imagine we start with dividing out $2^{n}$, but not really sure much past that
3
votes
2answers
134 views

Closed form of a sum of binomial coefficients?

I have the following function: $T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same ...
6
votes
4answers
181 views

Truncated alternating binomial sum

It is easily checked that $ \sum_{i = 0}^n (-1)^i \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the truncated sum $\sum_{i=0}^{D} ...
2
votes
1answer
60 views

Find the sum of all coefficients in expansion of $(x^2+2x)^{20}$.

Find the sum of all coefficients in expansion of $(x^2+2x)^{20}$. Is there a specific method or formula for this?
3
votes
5answers
281 views

Proving the total number of subsets of S is equal to $2^n$

Student here! Just reading Liebecks Introduction to pure mathematics for fun and I made an attempt at proving the total number of subsets of S is equal to $2^n$. I realized that the total number of ...
2
votes
1answer
52 views

When does $(x+y)^n+(x-y)^n\leq(2x)^n$ hold?

With $n\in\mathbb{N}$, what is the relation between $(x+y)^n+(x-y)^n\leq(2x)^n$ and the values of $x$ and $y$? Or mathematically: $(x+y)^n+(x-y)^n\leq(2x)^n\iff$ the values of $x$ and $y$ are such ...
1
vote
0answers
28 views

What distribution does $Y$ have?

I have given $(X_1, ...,X_{n-1})$ which follow a Multinomial Distribution $\mathrm{Mul}(n, (p_1,...,p_{n-1}))$. Now, how do I model $$Y:=\sum_{i=1}^{n-1}\mathrm{Bin}(X_i, q_i)$$ What is the ...
11
votes
2answers
291 views

A conjecture including binomial coefficients

Question: $$\sum_{k=1}^{n}k\binom{2n}{n+k}=\frac n2\binom{2n}{n}$$ is true for every $n\in \mathbb N$? If this is true, then how can we prove this? When I was with playing numbers, I conjectured ...
7
votes
6answers
166 views

Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$ I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a ...
0
votes
1answer
61 views

Is this possible or hopeless to try to prove?

If I have $x_1, ..., x_k=o(n)$ and $j=O(1)$. Is it possible to prove something like: $$\sum_{i=1}^k {n \choose j} \left(\frac{x_i}{n}\right)^j \left(1-\frac{x_i}{n}\right)^{k-j} \sim {n \choose j} ...
2
votes
0answers
39 views

How to prove: $pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$

For any two distinct primes $p, q$ there is a unique integer $k$ such that: $$pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$$ Where $k$ is the smallest integer greater than $p$ that is relatively ...
0
votes
0answers
20 views

Bounding a specific function of binomial coefficients

While trying to directly prove the existence of expander graphs (e.g. http://www.cs.toronto.edu/~avner/teaching/S6-2414/TUT2.pdf), one uses the following inequality: $$\sum_{s=1}^{n/2} ...
12
votes
3answers
371 views

How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1 $

Show that $$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$ I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you
3
votes
1answer
20 views

Derivative of Binomial Coefficient wrt k

I've got $\binom{2N}{N-x}$ and I'd like to take the derivative with respect to x. I know that I can take the derivative of $\binom{n}{k}$ w.r.t. n using logarithmic differentiation, but that's not ...
0
votes
2answers
32 views

Alternative ways to write $ k \binom{n}{k} $

I am looking for a way to simplify $ k \binom{n}{k} $. I don't understand what effect the factor $k$ has on the formula. So can anyone please explain what $\ k\binom{n}{k} $ would equate to?
2
votes
2answers
46 views

Sum of products of binomial coefficients

In a proof I've come across the following identity: $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$ I see that it's right, when plugging in numbers, but I don't see the ...
3
votes
2answers
222 views

How find this sum closed form?

Have this sum have close form $$f(n)=\sum_{k=0}^{n-1}\left(\left(\sum_{i=0}^{k}(-1)^i\binom{n}{i}\right)\cdot\left(‌​\sum_{j=k+1}^{n}(-1)^j\binom{n}{j}\right)\right)$$ Maybe this sum can use ...
4
votes
2answers
100 views

How prove this sum $\sum_{k=0}^{n-1}a_{k}b_{k}=\frac{n}{2}\binom{2n}{n}$

QUestion: show that $$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\cdots+\binom{n}{n}\right)=\dfrac{n}{2}\binom{2n}{n}$$ My idea: let ...
4
votes
1answer
122 views

Probability of two independent random variables being equal

Assume that $X$ and $Y$ are two independent random variables that follow the binomial distribution of parameters $p$ (the probability of one success) and $n$ (the number of trials). I was wondering ...
0
votes
3answers
100 views

Given the sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for it?

Given a sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for this sequence? Is there any optimised approach? My approach: the given series is equal to summation of $\binom{n}{k}$ ...
1
vote
0answers
19 views

How to get a nice approximation of $f(N,s)=\sum_{k=0}^{N}{N \choose k}{k \choose s-k+N}$ when $N>>1$ and $|s|<<N$?

I need to approximate the above sum in order to calculate $\mathbb{E}(s^2)$, which is the expectation value determined by the probability density function $f$ and the position $s$. Any idea?
0
votes
1answer
23 views

For each integer $s$, how many N-tuples with possible elements $\{0, 1, -1\}$ satisfy the condition that the sum of its elements is $s$?

So, we can find the answer using the generating function: $$f(x)=(1+x+x^{-1})^N=x^{-N}\sum_{k=0}^{N}\sum_{m=0}^{k}{N \choose k}{k \choose m}x^kx^m$$ and the number of N-tuples for each integer $s$ is ...
8
votes
6answers
4k views

Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$

I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$. I suppose I could use the counting rules in probability, perhaps combination= ...
4
votes
4answers
68 views

Conjecture for product of binomial coefficient

Is it true that for any $n, k\in\mathbb N$ $$\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad?$$ I tested it for some small $k$ and $n$, but I don't know how to prove that it is true ...
0
votes
0answers
46 views

Generalized Leibniz Rule

Leibniz Rule states that, $$(f\cdot g)^{(m)}(x)=\sum_{k=0}^m \binom{m}{k} f^{(m-k)}(x)g^{(k)}(x).$$ Writing this with differentiation denoted by $D$, we might say $$D^m (fg) = \sum_{k=0}^m ...
0
votes
1answer
64 views

Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ...
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 ...
5
votes
3answers
466 views

A Binomial Coefficient Sum

In my work on $f$-vectors in polytopes, I ran across an interesting sum which has resisted all attempts of algebraic simplification. Does the following binomial coefficient sum simplify? \begin{align} ...
2
votes
4answers
129 views

How to prove that $\sum_{r=0}^n\binom{n}{r}2^r=3^n$

I need help proving that $$\sum_{r=0}^n\binom{n}{r}2^r=3^n$$ I'm thinking this should use the idea that $\binom{n}{r}=\binom{n}{n-r}$ but I'm not sure how to proceed with it. Thanks in advance!
9
votes
3answers
161 views

How to find sums like $\sum_{k=0}^{39} \binom{200}{5k}$

How do I find sums like these?-- $$S=\displaystyle\sum_{k=0}^{39} \dbinom{200}{5k}$$ that is, when there is a summation of binomial coefficients, but with jumps of some terms..?