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)

0
votes
0answers
64 views

What's the interpretation of $\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$?

I'm having problems with finding the combinatorial interpretation of this sum: $$\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$$ Can anyone help, please?
1
vote
1answer
37 views

How prove $\sum_{k=0}^{2m}\binom{2m+1}{k}\cdot 2^k\cdot B_{k}=0$

we know Bernoulli number such identity $$\sum_{k=0}^{n}\binom{n+1}{k}B_{k}=0$$ see:Bernoulli number identity show that $$\sum_{k=0}^{2m}\binom{2m+1}{k}\cdot 2^k\cdot B_{k}=0$$ where $B_{n}$ ...
4
votes
2answers
196 views

Generating function of binomial coefficients ${n\choose5}$

How to prove easily this identity for (almost classical) series with binomial coefficients: $$ \sum_{n=5}^\infty \dfrac{\binom{n}{5}}{2^{n+1}} = 1 . $$ Thank you. Any smart proof would be much ...
3
votes
2answers
72 views

Root of the polynomial $x(x-1)(x-2)\cdots(x-K)=C$

Is there an analytic way to obtain the highest root of the polynomial $x(x-1)(x-2)\cdots(x-K)=C$ in terms of $K$ and $C$? The integer $K \ll x$ and the constant $C$ are known. The other way to ask ...
1
vote
1answer
38 views

Equality of binomial coefficients

I have seen that the following equations are equal, but are wondering how this is shown ${n \choose m} \cdot 1 \cdot 3 \cdots (2m-1)\cdot 1 \cdot 3 \cdots (2n-2m-1) = \frac{n!}{2^n} {2m \choose m} ...
4
votes
1answer
70 views

Extracting a coefficient from a generating function

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ ...
0
votes
2answers
30 views

Probability of special configuration of ones in a binary string

Consider the sequence $(X_i)_{1 \leq i \leq L}$ of i.i.d. random variables, where $X_1 \in \{0,1\}$ and $P(X_1 =1) = p$. For a $k \in \mathbb{N}$ define the event $A_{k,L}$ as "all ones in the ...
0
votes
2answers
60 views

Largest term in binomial expansion of $(1+n)^k$

The binomial expansion of $(1+n)^k$ is $$(1+n)^k=1+\binom{k}{1}n+\binom{k}{2}n^2+\cdots+\binom{k}{k}n^k.$$ If $n=1$, then the term in the middle is the largest, i.e. when $i=\lfloor k/2\rfloor$ and ...
1
vote
1answer
30 views

How find this sum $\sum_{j=0}^{\infty}\binom{m+2j}{m}t^{2j},0<t<1$

Let $m$ is give postive integer numbers, Find the sum $$\sum_{j=0}^{\infty}\binom{m+2j}{m}t^{2j},0<t<1$$ if this not have closed form,and can you use Special function ?
1
vote
1answer
53 views

How to simplify $F(x)=\sum_{n}^{\infty}\sum_{k}^{\infty}{n-k-1\choose k}x^n$?

This generating function is equivalent to $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$ where $F_n$ is a fibonacci number. To show this, I need to simplify the above generating function with ...
2
votes
1answer
47 views

Number of nodes with an even number of children in an ordered tree (AKA Plane Planted Tree)

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function Problem at hand: For a plane ...
1
vote
0answers
47 views

Closed form expression sum-product of binomials

Is it possible to find a closed form expression for $$\sum_{j=1}^a\sum_{i=1}^{b} {i+j-1\choose j} {i+j-1\choose i},$$ where $a \geq 1$, and $b \geq 1$ are integers. I couldn't apply any type of ...
0
votes
0answers
10 views

Confidence intervals for bernoulli trials over a cyclic time series

I have a time series with observations of 0 or 1 observed yearly for approx. 20 years. The time series is cyclic and I want to find a CI for the probability p over the cycle (mean). Unfortunately I ...
12
votes
1answer
247 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
0
votes
1answer
40 views

Is it possible to get a formula for this summation

The binomial sum $$s_n=\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots+\binom{2n}{n}$$ I tried solving through recurrence, but unable to find one.
0
votes
0answers
59 views

$\sum_{k=1}^{n}\dfrac{(-1)^{k+1}}{k}{n\choose k}=\sum_{k=1}^n\dfrac{1}{k}$

If $n$ is a positive integer, then the above identity holds. I tried to solve this question using generating function. $$A(x)=\sum_n\left(\sum_{k=1}^n\dfrac{1}{k}\right)x^n=-\dfrac{\log(1-x)}{1-x}$$ ...
3
votes
3answers
53 views

Recurrence relation for product of binomial coefficients

We all know the standard recurrence relation for binomial coefficients: $$ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$ Is there any finite-step recurrence relation one can write down for a ...
1
vote
2answers
54 views
1
vote
1answer
67 views

Binomial Coefficient Even or Odd? [duplicate]

How to check whether the value of binomial coefficient nCr is even or odd ?
1
vote
3answers
85 views

Why is $\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even? [duplicate]

Why is $\displaystyle\sum\limits_{k=0}^{n}(-1)^k\binom{n}{k}^2=(-1)^{n/2}\binom{n}{n/2}$ if $n$ is even ? The case if $n$ is odd, is clear, since ...
2
votes
1answer
73 views

simplifying a triple sum of products of binomial coefficients

Right now I have a horribly-looking triple sum ($x,y,z$ are non-negative integers and $x+y+z=N$): $$ W_{12}(x,y)=\frac{x}{N}\sum_{l=0}^{x-1}\sum_{l'=0}^{y}\sum_{l''=0}^{z}{x-1 \choose ...
2
votes
1answer
115 views

Combinatorial proof involving reciprocals

This is a follow-up to this question: show that if $n$ is a positive integer then $$\sum_{k=1}^{n}\frac{(-1)^{k+1}}{k}\binom{n}{k} =\sum_{k=1}^{n}\frac{1}{k}\ .$$ I was able to answer the question by ...
0
votes
0answers
28 views

Efficient way to compute the binomial using $(2^k+1)^{k+1}$

The following web page: "http://introcs.cs.princeton.edu/java/78crypto/" (at Exercise 28) effectively says that: "Pascal's triangle. One way to compute the $n$-th row of Pascal's triangle (for $n ...
10
votes
3answers
340 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
0
votes
2answers
64 views

How many coefficients are in the expansion $(x + y + z)^{10}$

I need to find the number of coefficients in the expansion $(x + y + z)^{10}$. I had this exercise on a recent assignment. The answer I gave is: $3^{10} = \binom {3 + 10 - 1}{10} = \binom{12}{10} = ...
1
vote
3answers
45 views

convergence of a sum of binomials

how can I show this converges to zero for some constant C as large as you need? $$\lim\limits_{n\rightarrow\infty} \sum\limits_{k=C\sqrt{ n\log(n)}}^{n}{n \choose k } 2^{-n}$$
3
votes
1answer
87 views

How to calculate the sum of binomials? [closed]

I want to prove below: n is natural number. $$\sum_{k=1}^n k \binom{2n}{n+k} =\frac{1}{2}(n+1) \binom{2n}{n+1}$$ Please tell me above proof.
1
vote
2answers
120 views

Binomial representation

We already know that we can represent this binomial as the following: $$(a+b)^K=\sum _{n=0}^K \binom{K}{n} b^n a^{K-n};$$ where $\binom{K}{n} = \frac{K!}{n! (K-n)!}$ I want to know if this ...
0
votes
4answers
58 views

Binomial coefficient proof

Prove that for any $0\lt r\lt n$ we have $$\binom nr=\binom{n-1}{r-1}+\binom{n-1}r.$$ How do prove this and what step do i take in order for it to be true?
0
votes
1answer
79 views

Binomial Expression [duplicate]

Please give me feedback on my answer to this question. Question: For all $ n\geq1:\binom{2n}{0}+\binom{2n}{2}+\binom{2n}{4}+\cdots+\binom{2n}{2k}+\cdots+\binom{2n}{2n} $ is equal to $ ...
8
votes
4answers
223 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
0
votes
0answers
35 views

help with a double summation with binomial coefficients

I was stuck in showing the following derivation step in a book. $\sum \limits_{c=1}^{d} \sum \limits_{j=1}^{c} \binom{c}{j} \binom{d}{c}(-1)^{d-c}\delta_{j}^{2} = \sum \limits_{j=1}^{d} \{ \sum ...
0
votes
1answer
40 views

Binomial Theorem on a Ring with Order 2

Say I have a Ring with set $G$ and binary operations $+$ and $\times$. If $G$ has order 2 under addition (meaning $A+A=0,\forall A\in G$, where $0$ is the additive identity), how can I reproduce the ...
2
votes
0answers
55 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
2
votes
2answers
86 views

Sum of products of binomial coefficient $-1/2 \choose x$

I am having trouble with showing that $$\sum_{m=0}^n (-1)^n {-1/2 \choose m} {-1/2 \choose n-m}=1$$ I know that this relation can be shown by comparing the coefficients of $x^2$ in the power series ...
3
votes
3answers
207 views

Integral with binomial coefficient

Is it possible to evaluate this integral without using the gamma function $$ \int_0^1 {a \choose b}x^b(1-x)^{a-b} dx$$ It looks a little like part of binomial theorem, but I don't have an idea how to ...
5
votes
1answer
90 views

An inverse binomial summation.

I am looking for a closed form for this summation: $$ \sum_{j=1}^m\frac{r^{-j}}{j{m\choose j}} = \sum_{j=1}^m\frac{r^{-j}}{m{m-1\choose j-1}} = \frac1{rm} \sum_{k=0}^{m-1}\frac{r^{-k}}{{m-1\choose k}} ...
8
votes
3answers
128 views

Asking About Binomial Sum Related to Fibonacci

How would I prove $$ \sum\limits_{i,j\ge 0} {n-i \choose j} {n-j \choose i}=F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of Fibonacci numbers? Thank you very ...
1
vote
1answer
48 views

How do you calculate a binomial distribution with k > R as opposed to k = R

I'm given the formula: $\displaystyle P(X = k; n, p) = \binom {n}{k} * p^k * q^{n-k}$ And we need to work out the binomial coefficient by hand, instead of using C(n,r). So I have a question: "Some ...
3
votes
3answers
59 views

How find this sum $\sum_{k=0}^{p}t^k\binom{n}{k}\binom{m}{p-k}$

Find the closed form $$\sum_{k=0}^{p}t^k\binom{n}{k}\binom{m}{p-k}$$ since $$\binom{n}{k}\binom{m}{p-k}=\dfrac{n!}{(n-k)!k!}\cdot\dfrac{m!}{(p-k)!(m-p+k)!}$$ then I can't
3
votes
0answers
125 views

Proving $\sum_{k=1}^{n}\binom{n-1}{k-1}{\binom{n+k}{k}}^{-1}=\frac 12$ combinatorially

Question : How can we prove the following equations combinatorially? $$\begin{eqnarray}\sum_{k=1}^{n}\frac{\binom{n-1}{k-1}}{\binom{n+k}{k}}&=&\frac ...
0
votes
2answers
74 views

Evaluate the sum $\sum_{0\leq j < k\leq n}\binom{n}{j}\binom{n}{k}$

Could someone give me a hint on how to do this? I believe I know what the answer to be (I computed some low values and checked on OEIS). However, I was hoping someone would be able to explain to me ...
2
votes
2answers
77 views

Combinatorial proof of $n! = {n\choose k}k!(n-k)!$

Can someone give me some insight on the proof of $$n! = {n\choose k}k!(n-k)!$$ I understand algebraically why they are equal but I'm having trouble seeing what the right side is actually saying. On ...
4
votes
0answers
80 views

Why does this sum of binomial coefficient ratios equal 1?

In the course of doing some calculations comparing unrepeatable sets of event trials, I ended up with the following identity. If my reasoning and my math are correct then this ought to be true, and ...
3
votes
1answer
82 views

Combinatorial proof of $k\binom{n}{k} = n\binom{n-1}{k-1}$ [duplicate]

I'm trying to prove this combinatorially. $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ I know the first step is to relate a question to the equation. My question was if you have $n$ friends how many ways can ...
4
votes
5answers
208 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
4
votes
1answer
28 views

Properties of cumulative binomial distribution

Let $F\left(k, n, p\right) = \sum_{i=1}^k\binom{n}{i}p^i\left(1-p\right)^{n-i}$ denote the cumulative binomial distribution function. If $F\left(k, n, p\right)-F\left(k, n, p'\right) \geq ...
6
votes
0answers
125 views

Solution of $\large\binom{x}{n}+\binom{y}{n}=\binom{z}{n}$ with $n\geq 3$

I found this question in an old problem set. There's no hint or solution mentioned. For $n \geq 3$, prove or disprove the existence of $(x,y,z) \in \mathbb N^3, ...
4
votes
2answers
122 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