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
3answers
160 views

Is there a closed-form formula for sum of “odd combinations”?

So, I was trying to come with a formula for the sum of below series: ${2^n \choose 1}+{2^n \choose 3}+...+{2^n \choose 2^n - 1}$ Thank you.
1
vote
1answer
18 views

What can you conclude about the first moment of a variable given the 3rd moment exists and is finite

Suppose you are given a random variable $X$ and told that $E[X^3]$ exists and finite. Can you conclude that $E[X]$ exists and is finite? What about $E[X^2]$? How would you argue rigorously whether ...
6
votes
4answers
1k views

Probability that given a 1000 page book with 1000 misprints, a page will have 3 misprints.

Setting A book of 1000 pages contains 1000 misprints. Estimate the chances that a given page contains at least three misprints. Solution My solution is ...
4
votes
1answer
43 views

Simplifying $\sum_{j=k}^{n}\binom{j}{k}/(2^{k-1})$

While doing an exercise (computing an expected value), I encountered an expression that looks like this. Is there a simpler formula? $$ \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} $$ If it wasn't ...
7
votes
5answers
313 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
0
votes
3answers
42 views

Proving a formula with binomial coefficient

Is this formula true? How can I prove it? $$\sum_{s=0}^{n-1}\binom{n-1}{s}2s =2^{n-1}(n-1)$$ Thanks!
0
votes
1answer
28 views

Identity of sum of binomial coefficients

I'm struggling to understand the following derivation where $n$ is a positive integer. $$ \sum_{\ell=0}^n {n \choose \ell} 2^\ell \log 2^\ell = n \sum_{\ell=0}^{n-1} {n-1 \choose \ell} 2^{\ell+1}. $$ ...
0
votes
0answers
11 views

Proving that $\Phi_{t*}[\mathbb{Y},\mathbb{Z}]=[\Phi_{t*}\mathbb{Y},\Phi_{t*}\mathbb{Z}]$

Let $\mathbb{X}$ be a vector field on $\mathbb{R}^n$. Let $\Phi_t$ denote the flow of $\mathbb{X}$. You are given that $\displaystyle L^j_{\mathbb{X}}[\mathbb{Y},\mathbb{Z}]=\sum_{k=0}^{j} ...
1
vote
1answer
78 views

How to prove this Catalan number identity

Catalan number is $\displaystyle C_n= \frac{1}{n+1}\binom{2n}{n}$. How to prove that $$C_{2n-1} = \sum_{k=0}^{n-1}\left(\binom{2n-1}{n-k-1}-\binom{2n-1}{n-k-2}\right)^2$$ for $n\geq 1$. Thank you.
4
votes
3answers
120 views

How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?

The following combinatorial identity have been verified via maple, but I can not prove it. Who can prove it without WZ mehtod? $$\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose ...
1
vote
2answers
102 views

How prove this identity$\sum_{k=0}^{n}\binom{2k}{k}\binom{n+k}{2k}(s-t)^{n-k}t^k=\sum_{k=0}^{n}\binom{n}{k}^2s^{n-k}t^k$

Today I see a paper,and this author say it is easy to have this identity.But I take sometimes to prove it,and I can't prove it. show this following identity holds for any real $s$ and $t$ and any ...
0
votes
0answers
24 views

Why we can use normal distribution to approximate binomial distribution when n is large enough?

Prove why we can use normal distribution to approximate binomial distribution when n is large enough. Hint: Try to read something on bernoull ...
0
votes
2answers
24 views

Generating functions and central binomial coefficient

How would you prove that the generating function of $\binom{2n}{n}$ is $\frac{1}{\sqrt{1-4y}}$? More precisely, prove that( for $|x|<\frac{1}{4}$ ): ...
3
votes
0answers
70 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
2
votes
1answer
27 views

If $a_n = \sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ for $n \geq 0$ …

Problem: If $a_n =\sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ for $n \geq 0$ then find the value of $a_0+a_1+a_2+\cdots \infty$ My approach: $a_n = \sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ $= ...
2
votes
0answers
39 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...
1
vote
1answer
42 views

Growth of binomial coefficient

I am interested in the growth of the binomial coefficient ${n\choose n^a}$ for some fixed $a\in (1/2,1]$. Of course, for $a=1$ the binomial constantly equal to $1$. For $a<1$, computations suggest ...
1
vote
2answers
46 views

Probability involving bread and jam!

SO, I drop a piece of bread and jam repeatedly. It lands either jam face-up or jam face-down and I know that jam side down probability is $P(Down)=p$ I continue to drop the bread until it falls jam ...
0
votes
1answer
12 views

Lie derivatives of vector fields and the binomial expansion

Given the Jacobi identity $[\mathbb{X},[\mathbb{Y},\mathbb{Z}]]+[\mathbb{Y},[\mathbb{Z},\mathbb{X}]]+[\mathbb{Z},[\mathbb{X},\mathbb{Y}]]=0$ and that the Lie derivative of a vector field is ...
1
vote
1answer
43 views

Finite natural summation that leads to double exponential results

We know that $$f(n)=\sum_{i=0}^n\binom{n}{i}=2^n$$ and $$g(n)=\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}.$$ Are there any finite natural sums that lead to $2^{2^n}$ or $2^n2^{2^{n-1}}$ results other than ...
2
votes
4answers
45 views

A finite binomial sum

Is their an exact expression for the following sequence involving binomial coefficients $$\sum_{i=0}^n i\binom{n}{i}?$$
1
vote
1answer
24 views

Multinomial identity - guidance needed

I need hints on a direction to proove that $$\displaystyle\prod_{k=1}^{n} {{k+1\choose2}\choose k} ={{n+1\choose2}\choose1,2,3.....,n}$$ Any ideas?
1
vote
0answers
19 views

Closed form for binomial coefficient series

If $6|n$, is there a closed form for $$\sum_{t=\frac{n}{2}}^n\binom{\frac{n^2}{3}}{t}\binom{\frac{2n^2}{3}}{n-t}?$$
0
votes
4answers
37 views

proof of summation using $\displaystyle \binom{n}{r}$

Prove that $\sum_{r=0}^{n} \binom{n}{r}2^r = 3^n$ for $n \in \mathbb P$. "Hint: give me an argument having to do with the number of strings of length $n$ with $3$ symbols."
2
votes
2answers
79 views

How many positive integer solutions are there to the equation $(a + b + c + d) < N$?

Here's my attempt: My thinking is that this is the same as finding all the non-negative $a, b, c, d$ such that $a + b + c + d = M$ where $M \in \{0, 1, ..., N - 4\}$. Which further reduces to a stars ...
0
votes
0answers
32 views

Closed Form for a Sequence

I have come across this sequence $$a_0 = -2, a_1 = 5, a_2 = -28, a_3 = 255$$ and, in general $$a_n = -\frac{1}{2}\bigg(\sum_{i=1}^n \binom{2n+4}{2i}a_{n-i} + \binom{2n+4}{2n+1}\bigg)$$ I've tried ...
0
votes
1answer
46 views

A binomial inequality

I've tried both expanding the binomials as well as trying to deduce something from the hypergeometric distribution, but I don't see how to prove: $${N\choose n}^{-1}\sum_{i\geq j}{M\choose ...
3
votes
2answers
49 views

Average number of trials until drawing $k$ red balls out of a box with $m$ blue and $n$ red balls

A box has $m$ blue balls and $n$ red balls. You are randomly drawing a ball from the box one by one until drawing $k$ red balls ($k < n$)? What would be the average number of trials needed? To ...
0
votes
2answers
32 views

Ratio of 2 Sums of products of binomial coefficients

I want to prove that for $k \ even, 0 \leq k<n, n\in \mathbb{N}$: $-\frac{1}{(2n-3-k)(k+2)}\sum \limits_{i=0}^{k} \frac{(-1)^{i} 2^{i} (2n-2-i)!}{(n-1-i)!i!(k-i)!}=\sum \limits_{i=0}^{k+2} ...
0
votes
1answer
35 views

prove binomial multiplication less than 1

please show me how to prove the following. Given $m >= n,n\geq2$ prove $\binom mn$ $\cdot \frac{1}{n^m} < 1$ ------UPDATE-------- Given the inequalities: $(\frac{m}{n})^n \le \binom mn \le ...
1
vote
1answer
20 views

Binomial Formula conversion

I saw an answer in stackoverflow about binomial here The answerer provide some nice explanation how can binomial can be calculated by pascal triangle. But I'm still not sure how to convert this ...
1
vote
1answer
39 views

Number of overlapping columns

Consider an $m \times n$ matrix $A$ with $m<n$. It is well-known that number of ways of choosing $k$ columns out of $n$ from $A$ is $\binom{n}{k}$, where ($k<m<n$). What is the number of ways ...
2
votes
1answer
38 views

Combinatorics: Number of Six-Card Hands That Can Be Dealt from r Combined Decks

I am having trouble solving this combinatorial problem dealing with the number of different card hands possible from multiple decks of identical cards. Here is the exact question: Use a combinatorial ...
1
vote
2answers
112 views

Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?

I have the sum $$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$ but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try ...
1
vote
0answers
20 views

binomial coefficient and recurrence relation [duplicate]

any hints on how to solve the recurrence relations for the following binomial coefficient \begin{equation} {n \choose k}=\begin{cases} 1, & \text{if $k\in\{0,n\}$}.\\ {n-1 \choose ...
0
votes
1answer
21 views

Binomial distribution “matix of results”

I am having trouble understanding the formal definition of the binomial distribution. $$f(k;n,p) = \Pr(X = k) = {n\choose k}p^k(1-p)^{n-k}$$ Or rather how I "transform" the definition to suit my ...
1
vote
1answer
44 views

Using Stirling's formula to uniformly bound Bernoulli success probabilities

In this paper, the authors say that for any $\gamma \in [1/2,1)$, there is a positive constant $B=B(\gamma)$ such that for any $n$, $$ \sum_{n\gamma\leq k \leq n} \binom{n}{k} \leq B n^{-1/2}2^{n ...
5
votes
2answers
49 views

Proof by induction, or without it if possible?

I was given a task to prove: $$ \frac{1}{(x+1)(x+2)\ldots(x+n)}=\frac{1}{(n-1)!}\sum_{i=1}^n\binom{n-1}{i-1}\frac{(-1)^{i-1}}{x+i} $$ I am almost 100% sure this is best solved by induction but to be ...
3
votes
3answers
159 views

A specific kind of probabilistic proof for central binomial coefficients

I'm looking for a specific kind of proof of the statement $$ \lim_{n\to\infty} \frac1{4^n}\binom{2n}{n} = 0 $$ I know how to show this using Stirling's formula; I have seen the very nice elementary ...
-1
votes
2answers
28 views

consider a class of 9 students. The instructor wants to divide the students into three disctinct study groups [closed]

Consider a class of 9 students. The instructior wants to divide the students into three distinct study groups. Count the number of ways the instructor can accomplish this, if there are. a) Exactly ...
6
votes
1answer
77 views

Combinatorial Interpretation of a Binomial Identity

The original post due to David Peterson is here. How to establish the following Binomal identity combinatorially: $$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = ...
18
votes
1answer
590 views

How to prove a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
4
votes
2answers
82 views

Show that $\sum\limits_{i=0}^{n/2} {n-i\choose i}2^i = \frac13(2^{n+1}+(-1)^n)$

While doing a combinatorial problem, with $n$ being even, I came up with the expression $$\sum_{i=0}^{n/2} {n-i\choose i}2^i$$ for which I used wolfram to get a closed form expression of ...
1
vote
8answers
51 views

Binomial coefficient proof for ${n\choose m-1}+{n\choose m}={n+1\choose m}$

I need to prove the following: ${n\choose m-1}+{n\choose m}={n+1\choose m}$, $1\leq m\leq n$. With the definition: ${n\choose m}= \left\{ \begin{array}{ll} ...
1
vote
3answers
29 views

${n\choose m}={n\choose n-m}$ Proof

I need to prove the following: ${n\choose m}={n\choose n-m}$ With the definition: ${n\choose m}= \left\{ \begin{array}{ll} \frac{n!}{m!(n-m)!} & \textrm{für ...
4
votes
4answers
71 views

Proof $\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod{p}$

Proof that if $p$ is a prime odd and $k$ is a integer such that $1≤k≤p-1$ , then the binomial coefficient $$\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod p$$ This exercise was on a test and I could ...
3
votes
2answers
66 views

If $(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$ then …

If $$(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$$ then find : $\sum^{16}_{r=0} a_{3r} =$ My approach : let (1+x) =t therefore, $(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$ =$(1+x+x^2)^{25} = ...
1
vote
1answer
25 views

Prove of an addition theorem for the general binomial coefficients

Prove that: $\sum_{k=0}^n \binom{s}{k} \binom{t}{n - k} = \binom{s + t}{n}$ for all $s, t \in\Bbb C $, $n \in N\cup {0}$. That's pretty much all I'm given, and therefore, I haven't come quite far ...
-2
votes
0answers
25 views

Identities involving binomial coeffcient [duplicate]

Show that $\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+ \cdots +\binom{n}{k}=\binom{n+1}{k+1}$ for all natural numbers $k\leq n$.
-1
votes
1answer
47 views

Coefficeient of $x^k$ in $(1+x)^n$ when $n<0$

I know this is a very basic question. But I simply cannot derive the final answer. We have the alternate form of binomial theorem if we want to deal with negative exponents. ...