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
68 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
114 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
24 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 ...
9
votes
3answers
303 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
60 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
109 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
56 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
76 views

Binomial Expression

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
210 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
33 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
33 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
78 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
184 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
114 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
44 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
58 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
117 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
70 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
76 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
79 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
72 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
202 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
27 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
121 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
83 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
11
votes
2answers
293 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 ...
0
votes
3answers
116 views

Binomial expansion question. easy!

I'm trying to do the binomial expansion of $(x-2)^{1/2}$. How do you do it? As far as I'm aware the expansion only works for $(1+x)^n$. How could I get it in that form? Thanks.
1
vote
1answer
40 views

Help with this hard recurrence relation question

Please help with this. Suppose $\{a_n\}$ satisfies $$a_n=(n+1)a_{n-1}-(n-2)a_{n-2}-(n-5)a_{n-3}+(n-3)a_{n-4},$$ and $a_0=a_1=1,a_2=a_3=0$. Please sort out the general form of $a_n$. I guess $a_n$ ...
0
votes
2answers
21 views

Question about Binomial Distribution

The chance of a rose flower blooming is .28. You are going to plant 5 rose flowers, what are the chances of 4 of them blooming? I was thinking the answer would be 35% since 28%x5=140 and 140/4=35. ...
1
vote
1answer
23 views

Generalization of Binomial Coefficients Congruence

It is well known and not hard to prove that $\binom{pA}{pB}\equiv\binom{A}{B}\mod p$ where $p$ is a prime. Now, how can we extend to show that this congruence holds $\mod p^2$. Finally, can we extend ...
2
votes
2answers
37 views

A binomial random number generating algorithm that works when $ n \times p $ is very small

I need to generate binomial random numbers: For example, consider binomial random numbers. A binomial random number is the number of heads in N tosses of a coin with probability p of a heads ...
1
vote
1answer
69 views

Estimation solving for binomial k?

Hello all trying to do an estimation problem at work and wondering if I'm on the right track! I'm running a study and its on the internet. I'm trying to determine how many people I need to show an ...
0
votes
0answers
27 views

Binomial expansion, the greatest term…

My question is related to binomial expansion, and more precisely the greatest term in expansion. Is it right that the formula for finding the greatest term is $$T_k\ge T_{k+1}$$? Now going to the ...
4
votes
1answer
194 views

Binomial Summation

The sum $$ 1 + {n \choose 1}\cos \theta + {n \choose 2}\cos 2\theta + \cdots+ {n \choose n}\cos n\theta $$ is? I try to write this as the real part of $(1 + \cos \theta + i\sin \theta)^n$ but then ...
1
vote
2answers
36 views

Proving this binomial identity

I'm required to prove the following binomial identity: $$\sum\limits_{k=0}^l {n \choose k} {m \choose l-k} = {n+m \choose l}$$ I tried various arrangements but reached nowhere. Finally I turned to ...
1
vote
2answers
44 views

Let $C=\dfrac{1}{k}\left [\binom{2k-1}{k}-1 \right ]$ where $k \ge 3$. Show that $C\ge 3$.

I have a problem: Let $C=\dfrac{1}{k}\left [\binom{2k-1}{k}-1 \right ]$ where $k \ge 3$. Show that $C\ge 3$. Any help will be appreciated! Thanks!
0
votes
2answers
30 views

Prove that $^nC_0+^{n+1}C_1+^{n+2}C_2+…+^{n+k}C_k = ^{n+k+1}C_{n+1}$ for $k\ge1$ [closed]

Prove that $^nC_0+^{n+1}C_1+^{n+2}C_2+.....+^{n+k}C_k = ^{n+k+1}C_{n+1}$ for $k\ge1$
4
votes
1answer
87 views

How to compute the sum $\sum_{r=0}^n \frac{(-1)^r}{{n \choose r}}$

Consider the sum $$\sum_{r=0}^n \frac{(-1)^r}{{n \choose r}}.$$ I know the sum is zero when $n$ is odd (pretty simple). The sum is $2-\frac{2}{2 + n}$ when $n$ is even. Can somebody provide a proof ...
0
votes
0answers
27 views

how to compute the variance of the random variable Y in binomial distribution?

sorry to bother but I just saw some slides provided by the harvard university. One of those show the binomial distribution with the VAR(Y)=$\frac{\pi(1-\pi)}{N}$ Im bit confused because usually I see ...
1
vote
0answers
49 views

Approximation of the following mathematical formula

I have the following mathematical expression which I need to simplify: $$\mu^2\sum_{x=0}^{n}\left(\frac{\theta}{\mu}\right)^x\frac{1}{H_x}{n+a\choose x}$$ $\mu$, $\theta$, $D$, and $a$ are ...
1
vote
4answers
41 views

Binomial coefficient equivalence

Can someone explain to me why these 2 formulas are equivalent? (n \choose k) = (n \choose n-k)
6
votes
1answer
96 views

Help with a Binomial Identity: $\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = 2^{n+1}$

The following is a problem from the 5th edition of Niven's An Introduction to the Theory of Numbers: Problem 23 of Section 1.4 asks us to prove that $$\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = ...
1
vote
0answers
28 views

Binomial coefficients(Concrete mathematics 5.39)

I have no idea what I could do with this problem. I tried to substitute, but failed.. Hope someone can help
1
vote
0answers
35 views

How find the sum $2\sum_{k=1}^{\infty}\sum_{i=0}^{2k-1}\frac{\binom{2k}{i}\cdot B_{i}\cdot(m-1)^{2k-i}}{2k(2k-1)m^{2k-1}}$

Find the sum $$2\sum_{k=1}^{\infty}\sum_{i=0}^{2k-1}\dfrac{\binom{2k}{i}\cdot B_{i}\cdot(m-1)^{2k-i}}{2k(2k-1)m^{2k-1}}$$ where $B_{i}$ is Bernoulli numbers. my idea: since ...
1
vote
1answer
69 views

1Prove that limit n tends to infinity $1 + 2 \sum_{k=0}^n1/\binom{n}{k} = e^2$

Prove that limit n tends to infinity $1 + 2 \sum_{k=0}^n1/\binom{n}{k} = e^2$ I have not been able to proceed ..tried many things like ratio of nck and nc(k+1)...also opened it.!! Not able to ...