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)

1
vote
3answers
93 views

Calculate $\sum_{k=0}^n k \binom{n}{k} p^k (1-p)^{n-k}$

For $p \in [0,1]$ calculate $$S =\sum_{k=0}^n k \binom{n}{k} p^k (1-p)^{n-k}.$$ Since $$ (1-p)^{n-k} = \sum_{j=0}^{n-k} \binom{n-k}{j} (-p)^j, $$ then $$ S =\sum_{k=0}^n \sum_{j=0}^{n-k} k ...
1
vote
2answers
103 views

Binomial Expansion.

So I had a question: Prove that for $n \geq 1$, $${n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + ...+ n{n \choose n} = n2^{n-1}$$ So my idea was to take the binomial expansion of $(1+1)^n$ which ...
2
votes
1answer
44 views

asymptotic estimate for this expression

How can I compute an asymptotic estimate for following expression? \begin{equation} A = ...
0
votes
0answers
29 views

asymptotic estimate for binomial coefficient

How can we compute the asymptotic estimate for binomial coefficient $Q = \binom{n}{s-t}$ with the $n,s \gg 1$ and $ t \ll n$ and $ t \ll s$
1
vote
1answer
33 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
1
vote
0answers
45 views

Chu-Vandermonde-like combinatorial identity

I am looking for a simple combinatorial proof of the binomial identity: $$\sum_{j=0}^n \binom{2j}{j}\binom{2n-2j}{n-j} = 4^n.\tag{1}$$ The standard way I know is to exploit the generating function: ...
1
vote
1answer
61 views

Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...
1
vote
1answer
44 views

Using the binomial expansion to solve a summation

I have to evaluate a summation from k=1 to n of k3^k(nCk) by setting x equal to the appropriate values in the binomial expansion.
1
vote
3answers
65 views

One Binomial Equation $\sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$ [duplicate]

I saw one proof using this formula: $$ \sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$$ Can anyone help explain it, thank you!
1
vote
1answer
88 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
0
votes
1answer
48 views

Probability binomial distribution and Poisson distribution

It is found that 5% of screws in a factory are found to be defective. Use the Poisson theorum and the binomial theorum to compute the probability that two or more are found to be defective if a sample ...
0
votes
0answers
35 views

Convergence of sum of binomial coefficients with negative non-integer values

I'm trying to test if the following sum converges but I have no idea how to do it: $$ \sum_{n=0}^{\infty}\binom{2\sqrt{2}-\pi}{2n} $$
17
votes
3answers
392 views

How prove this sum $\sum_{n=1}^{\infty}\binom{2n}{n}\frac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}$

show that $$\sum_{n=1}^{\infty}\binom{2n}{n}\dfrac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}=5+4\sqrt{2}\left(\log{\dfrac{2\sqrt{2}}{1+\sqrt{2}}}-1\right)$$ where ...
2
votes
0answers
56 views

How to prove these indentities? [closed]

How to prove these indentities? $\displaystyle \sum \limits_{k\geq0} {2n\choose 2k-1}{k-1\choose m-1}=2^{2n-2m+1}{2n-m\choose m-1}$ $\displaystyle \sum \limits_{k=0}^{m} {m\choose k}{n+k\choose ...
2
votes
1answer
47 views

Calculate sum wtih binomial coefficients

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
0
votes
2answers
44 views

How to calculate this sum

How do you calculate this sum $ \sum \limits_{k=1}^{n} \frac{k}{n^k}{n\choose k}$ ?
0
votes
2answers
57 views

MCA entrance question

In triangle $ABC$, the value of $\ \displaystyle \sum_{r=0}^n\ ^nC_ra^rb^{n-r}\cos(rB-(n-r)A)$ is equal to (a) $c^n$ (b) $b^n$ (c) $a^n$ (d) $0$ I have no idea how to start ...
7
votes
2answers
130 views

Does this really converge to 1/e? (Massaging a sum)

Short version: can we prove that $$\sum_{k=0}^n (-1)^k \binom{n}{k}^2 \frac{k!}{n^{2k}} \to \frac1e$$ as $n \to \infty$? Long version: First, consider $$a_n = \sum_{k=0}^n \frac{(-1)^k}{k!}$$ It is ...
1
vote
0answers
23 views

binomial coefficient divisibility properties

I'm looking for a (possibly large) list of divisibility properties of binomial coefficients. Does anyone know a good reference? For example, Graham, Knuth, and Patashnik, Discrete Combinatorics, ...
3
votes
2answers
34 views

show that these two equation holds by binomial theorem

I know the binomial theorem, but I have no idea how to simplify this. I tried to write it as (y+x)^n+(y+x)^n-(y+x)^0+(y+x)^n-(y+x)^1+...+(y+x)^n-(y+x)^(n-1), but it didnt work out.
1
vote
1answer
111 views

Binomial Distribution - independence

I have the following problem that I'm stuck on a few parts. ...
3
votes
2answers
110 views

Evaluate the summation involving binomials.

$\sum _{ i=0 }^{ 100 }{\binom{k}{i}}*{\binom{M-k}{100-i}*\frac{k-i}{M-100}}/{\binom{M}{100}}$ I wrote the first few terms but couldn't find any pattern and how to club the terms. Help.
0
votes
1answer
65 views

Function returning number of subsets of size $k$ of a set of size $n$.

I am looking for a function that returns the number of subsets of size $k$ of a set of size $n$. Ideally, the function is commonly used. I took a look at the binomial coefficient. However, there ...
0
votes
0answers
132 views

Solving sample size of hypergeometric distribution given a specific probability

I am trying to figure out how to calculate the sample size of a hypergeometric distribution, given a population, population successes, and probability. Here is the initial formula: ...
1
vote
1answer
42 views

In a lottery of $90$ numbers a man adds extra $1,2,3$

Consider a lottery where $5$ balls are chosen randomly among $90$ balls numbered from $1$ to $90$. A man cheats adding to the $90$ balls, before the draw, three more balls numbered $1,2,3$. We say ...
3
votes
3answers
130 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
2
votes
3answers
76 views

Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

I need to prove the following: If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$. I did the following steps: \begin{align} ...
0
votes
0answers
27 views

Approximation of sum with binomial summands

I am new here, so hopefully my question will be understood correctly. I have a function (originating from expected untility theory in economics) that looks the following: ...
1
vote
3answers
61 views

Prove $\sum\limits_{r=0}^{2n} r \binom{2n}{r}^2 = 2n \binom{4n-1}{2n}$

I expanded $(1+x)^{2n}$ = $\sum\limits_{r=0}^{2n} \binom{2n}{r} x^r $ Differentiating both sides, we get $2n(1+x)^{2n-1}$ = $0$ + $\binom{2n}{1}$ + $2\binom{2n}{2}x$ + $3\binom{2n}{3}x^2$ ..... ...
7
votes
2answers
218 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
3
votes
1answer
41 views

A combinatorics question on a sequence of binomial coefficents

On a past-paper of a Combinatorics exam I will be taking they ask the question: Prove that for $k$ odd and greater than 1, the sequence of numbers $\binom{k}{1}, \binom{k}{2}, ..., ...
2
votes
1answer
41 views

binomial identity involving sum of diagonal elements

It's well-known and easy to show that $\binom{k}{n} = \frac{k}{n}\binom{k-1}{n-1}$. Also, I've come across the formula $\binom{k}{n}=A\binom{k-1}{n-1}+B\binom{k-2}{n-2}$, where $A$ and $B$ are ...
3
votes
1answer
79 views

How find this sum $\sum_{k=0}^{\left[\frac{n}{2}\right]}\frac{(-1)^k\binom{n-k}{k}}{n-k}$

How find this sum $$\sum_{k=0}^{\left[\dfrac{n}{2}\right]}\dfrac{(-1)^k\binom{n-k}{k}}{n-k}$$ My try:since $$\dfrac{(-1)^k}{n-k}=\int_{-1}^{0}x^{n-k-1}dx$$ then I can't Thank you very much!
2
votes
2answers
61 views

find the coefficient of the given term when the expression is expanded by the binomial theorem

I am just trying to understand why the term is $\binom{15}8$(3p$^2$ - 2q)$^7$. I need to find the coefficient in $p^{16}q^7$ in $(3p^2 - 2q)^{15}$ So, I know that $n = 15$ and I have $a^{n - k}b^k$ ...
1
vote
1answer
31 views

I want to prove this identity involving the binomial coefficients

Can you help me prove the following identity? I know it holds because I simulated it. For positive integers $n,m,k$ and for $i=0,\ldots,n$ and for $n \leq m$ we have: $$\sum_{j=0}^i (-1)^{i+j}\binom ...
5
votes
2answers
77 views

Partial fraction expansion of $\frac{1}{x(x+1)(x+2)\cdots(x+n)}$

I try to find a partial fraction expansion of $\dfrac{1}{\prod_{k=0}^n (x+k)}$ (to calculate its integral). After checking some values of $n$, I noticed that it seems to be true that ...
3
votes
1answer
202 views

Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$

So, I wonder what is the evaluation of $$\sum_{k = 0}^{n} {n\choose k} k^m\text{,}\qquad (*)$$ where $m,n\in \mathbb{N}$. One of my tries: knowing that $$k^m = \sum_{j = 0}^{m}\text{S}(m,j)\cdot ...
0
votes
1answer
52 views

Conditions for which $n | {n \choose k}$ for all $k$

I'm studying for a number theory exam. Our review sheets offers the question: Under what conditions will $n$ divide $n \choose k$ for all 1 $ \leq k \leq n-1$? I can see that this will be true for ...
6
votes
1answer
262 views

Are these two binomial sums known? Proven generalization to the Hockey Stick patterns in Pascal's Triangle

English translation. You can see the original - deprecated - in Portuguese here Hi, I arrived at a generalization for the Hockey Stick Patterns, from our beloved Pascal's Triangle. This ...
1
vote
1answer
58 views

Gambler's ruin, probability of loss, infinite turns

A gambler starts with $\$1$ and bets $\$1$ every turn of a game, where he has the probability $p$ to obtain $\$2$ and $1-p$ to obtain nothing. If $p<1/2$, what is the probability he will eventually ...
0
votes
1answer
30 views

Binomials for getting probability of standard deviation

I have the following problem which I am stuck on the second part. Suppose that $30\%$ of all students who have to buy a text for a particular course want a new copy whereas the other $70\%$ want a ...
2
votes
1answer
64 views

Concrete Mathematics, Newton Series and Inversion

In section 5.3 of Concrete Mathematics, on the bottom of page 192, "A special case of the rule (5.45) we've just derived for Newton's series can be rewritten in the following way:" $g(n) = ...
0
votes
1answer
38 views

Binomial Distribution for defects

I'm stuck on the following problem: A batch of components has arrived at a distributor. The batch can be characterized only if the proportion of defective components is at most 0.10. ...
2
votes
0answers
39 views

Sum of Binomials times Logarithms

Is there a closed-form expression or a very good approximation for $$ \sum_{i=0}^n \binom{n}{i} \log (i+1) \,? $$ If the summands alternate, then there is a very close approximation, yet it feels ...
2
votes
1answer
39 views

Integer valued polynomials in two variables

The ring of integer valued polynomials, $\{ f \in \mathbb{Q}[x] : f(\mathbb{Z}) \subseteq \mathbb{Z} \}$ is fairly well-known to be generated as Abelian group by the binomial coefficients, $f_k(n) = ...
3
votes
3answers
119 views

Binomial theorem $(a+b)^n=\sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$ [duplicate]

I'm trying to understand the proof by induction of: $$ (a+b)^n = \sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} $$ I'm at the point of deriving the inductive step and am getting next: $$ (a+b)^{n+1} = ...
2
votes
3answers
92 views

Probability of 5 cards drawn from shuffled deck

Five cards are drawn from a shuffled deck with $52$ cards. Find the probability that a) four cards are aces b) four cards are aces and the other is a king c) three cards are tens and ...
2
votes
1answer
58 views

Using combinatorial reasoning to show $n!=\binom{n}{0}D_n+\binom{n}{1}D_{n-1}+\dots+\binom{n}{n}D_0$

How can one use combinatorial reasoning to show that $$n!=\dbinom{n}{0}D_n+\dbinom{n}{1}D_{n-1}+\dbinom{n}{2}D_{n-2}+....+\dbinom{n}{n-1}D_1+\dbinom{n}{n}D_0$$ Now $D$ stands for deranged which is a ...
5
votes
6answers
243 views

Asymptotic behavior of $\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k$

I am looking to show that $$\lim_{n \rightarrow \infty}\frac{1}{e^n}\sum_{k=1}^n \binom{n}{k} \left(\frac{ck}{n}\right)^k = 0. $$ In my application, $c = (e+1)/2 \approx 1.85914\ldots$. I have been ...
3
votes
2answers
125 views

How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

For instance is $\binom{n}{n+1}=0$ always or something else?