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
2answers
41 views

what is the n-k derivative of $x^n$? Also, why is $n!/k! = …$

I am having troubles finding $\frac{d^{n-k}x^n}{dx^{n-k}}$ where $ k \leq n$ I believe it is equal to $n(n-1)(n-2)....k(k+1)x^k$ but htis is just from obersation, I do not know why it's that exactly. ...
-1
votes
5answers
87 views

Give a proof of ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + … + {n \choose n}^2 = {2n \choose n}$ [duplicate]

I must prove this: ${n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + ... + {n \choose n}^2 = {2n \choose n}$ But, I have no idea how to prove it or how it necessarily works. Could someone help ...
0
votes
1answer
46 views

What is the simplest way to show that ${(p-1)! \over (k)!(p-k)!}$ is an integer?

In the proof of $p$ | $\binom{p}{k}$ (p divides $\binom{p}{k}$) where $p$ is prime, what is the simplest way to show that $${(p-1)! \over (k)!(p-k)!}$$ is an integer?
0
votes
1answer
38 views

Use induction and Pascal's Identity to show that $\sum_{k=0}^{r}C(n+k,k) = C(n+r+1,r)$

I know Pascal's Identity is ${n \choose k}={n-1 \choose k-1}{n-1 \choose k}$, but I am not sure how to set up and use the proof to show that $\sum_{k=0}^{r}C(n+k,k) = C(n+r+1,r)$. Can anyone help me ...
0
votes
2answers
94 views

Give a formula for the coefficient of $x^{k}$ in the expansion of $(x+{1 \over x})^n$

I followed the binomial theorem and got this: The Binomial Theorem is: $(a+b)^{n}= \sum_{k=0}^{n} {n \choose k}{a}^{k}{b}^{n-k}$ Then let $a=x, b={1\over x}, n = n, k = k.$ I then get $\sum_{j=0}^{...
5
votes
5answers
181 views

Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.) Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for ...
1
vote
1answer
39 views

What is this matrix notation and how is it solved?

I've never taken a stats class, or linear algebra or much of anything that involves matrices. In one of my books they give me this as part of an example and it states, $$\binom{6}{4} = 15 \text{ ...
1
vote
3answers
81 views

Is there an expression for the sum of $\binom nr^2$ for each $n$? [duplicate]

Is there a standard expression for $$\sum_{r=0}^{n}\binom nr^2$$
6
votes
2answers
219 views

summation of a binomial expression that doesn't start from 0

I have the following expression: $$ \sum_{k=9}^{17}\binom{17}{k} $$ and I need to show that it's equal to: $$ 2^{16} $$ now I know that if 'k' was starting from zero and not from 9 , like this: $$ \...
0
votes
1answer
56 views

Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \binom{n}{r} = 2016$

$(1)$ Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \binom{n}{r} = 120$ $(2)$ Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \...
2
votes
0answers
29 views

Simplify binomial coefficients sum [duplicate]

Exercise requires to simplify this sum: $$\sum_{k=0}^{20} \binom{50}{k}\binom{50}{20-k}$$ Tried to figure this out with no success. I have only final answer, which is $\binom{100}{20}$. Please help ...
0
votes
2answers
49 views

Simplify the sum of binomial coefficients

The exercise requires to simplify the following expression: $$\sum_{k=0}^{25} \binom{50}{2k}$$ By finally looking at someone's answer, I know that the result should be $2^{49}$, but the following ...
1
vote
1answer
28 views

Binomial distribution, explanation formula

I have a really simple question. I can't figure out the meaning of the binomial coefficient in the case of a binomial distribution formula. I know what the formula means, and how to use it for the ...
3
votes
3answers
58 views

how to come up with this identity $\sum\limits_{i=r}^{n-k+r}{i \choose r}{{n-i} \choose {k-r}}={{n+1} \choose {k+1}}$

This identity is used in an exercise. Could you help me understand how I should reason to come up with it? Ideally, from a combinatorial point of view.
2
votes
1answer
50 views

Prove that $\frac{(2n)!}{(n!)^2}-1$ is divisible by $(2n+1)$

Prove that $$\frac{(2n)!}{(n!)^2}-1$$ is divisible by $(2n+1)\;,$ Where $n\in \mathbb{N}$ and $n>1$ $\bf{My\; Try::}$ Let $$S = \frac{(2n)!}{n!^2}-1 = \frac{2^n(2n-1)(2n-3)\cdot \cdot ........\...
0
votes
1answer
51 views

Binominal expression simplification

I need to simplify the expression $$\sum_{k = 1}^{10} k\binom{10}{k}\binom{20}{10 - k}$$ Thank you.
4
votes
3answers
79 views

Find the sum of the $\sum_{m=k}^{+\infty}\binom{m}{k}(1-p)^k\cdot p^{m-k}$

Let $0<p<1$,Find the sum $$\sum_{m=k}^{+\infty}\binom{m}{k}(1-p)^k\cdot p^{m-k}$$
5
votes
1answer
119 views

How do you find the probability of A winning if the probability of getting a favourable outcome in the $r^{th}$ turn is a function of $r$?

Problem: Two players A and B are playing snake and ladder. A is at 99 and he needs 1 to win in rolling of a dice. However, he is always allowed to re-throw the dice if 6 appears. What is the ...
0
votes
1answer
29 views

A Binomial coefficient sequence

If 'n' is a positive integer and $C_k=^nC_k$, then find the value of: $[\sum\limits_{k=1}^n\frac{k^3}{n(n+1)^2.(n+2)}(\frac{C_k}{C_{k-1}})^2]^{-1}$ [![enter image description here][1]][1] I have ...
1
vote
0answers
39 views

Does the property ${n\choose r}={n\choose n-r}$ have a name?

Due to the relation between Pascal's Triangle and the choose function in probability theory, we can deduce that $${n\choose r}={n\choose n-r}$$ because Pascal's Triangle is symmetric. This can also be ...
0
votes
1answer
69 views

Closed form for a binomial identity [closed]

$\textrm {How do I find a closed form for } \sum_{j=0}^n{} j\displaystyle\binom{j}{r} = ?$ Is this some kind of upper index summation? Any previous papers? Thank you
0
votes
4answers
160 views

How many numbers are there of 2n digits that the sum of the digits in the first half equals the sum of the digits in the second half

The question is how many number of a given number of digits 2n where the sum of the first half of the digits equals the sum of the digits in the second half. So this is for a programming problem and ...
2
votes
0answers
33 views

Can someone expain to me what's going on (binomial coefficient)?

I'm watching this proof for $\zeta(2n)$ on YouTube. This is what I can understand so far: $${s\over e^{s} -1} = \sum^{\infty}_{n=0} {\beta_n\over n!} s^n$$ Where $\sum^{\infty}_{n=0} {\beta_n\over ...
1
vote
2answers
27 views

Induction with binomial coefficient

Is mathematical Induction possible with this sigma sign? $A(k) =\sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k}$ $A(k+1) = \sum_{j=0}^{k+1} \binom{m}{j}\binom{n}{(k+1)-j} = \binom{m+n}{(k+...
1
vote
2answers
59 views

Bound on sum of combinations

I came across the following inequality $\sum_{i=0}^D \binom N i \le N^D+1$. I am not sure how to prove this. I tried to do it by induction on $D$, and started with observing the values of sum for ...
1
vote
1answer
81 views

Gaussian polynomial identities

I'd appreciate any hints for showing that these identities are true for Gaussian polynomials. I've tried to approach the problem using basic algebra but it gets messy very quickly and I've gotten ...
2
votes
1answer
81 views

Simplifying my sum which contains binomials

While dealing with compositions (ordered partitions) of integers, I found the following formula for the shifted $m$-generalized Fibonacci numbers (Wikipedia: Generalizations of Fibonacci numbers): $$F(...
-1
votes
3answers
44 views

Reducing this binomial expression [closed]

I need help for showing that: $$\sum\limits_{k=2}^{50} = k \cdot(k-1)\binom{50}{k}$$ is equal to: $$50\cdot 49\cdot 2^{48}$$ please help , thank you.
0
votes
1answer
78 views

Prove that $\binom{n}{0}\cdot \binom{2n}{n}-\binom{n}{1}\cdot \binom{2n-2}{n}+\binom{n}{2}\cdot \binom{2n-4}{n}+… = 2^n$

Prove that $$\binom{n}{0}\cdot \binom{2n}{n}-\binom{n}{1}\cdot \binom{2n-2}{n}+\binom{n}{2}\cdot \binom{2n-4}{n}+........... = 2^n$$ $\bf{My\; Try::}$ Coefficient of $x^n$ in $$\left[\binom{n}{0}(1+...
11
votes
3answers
307 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\;\sum_{j=0}^{2l-n}\binom{l}{j}$$ Ideally it should be possible to evaluate it exactly using some ...
1
vote
2answers
68 views

What is the coefficient of $x^4$ in the expansion of $\sqrt[3]{1+x}$

Here's what I tried: $$\sum_{n \ge0} {\frac{1}{3} \choose n} x^n= \sum_{n \ge0} = \frac{\frac{1}{3}!}{n!(n-\frac{1}{3})!}x^n=\sum_{n \ge0} \frac{(\frac{1}{3}-1)(\frac{1}{3}-2)\cdot ...\cdot(\frac{1}{3}...
2
votes
2answers
78 views

Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$

Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$ given that: $a_n=1/{{n}\choose{0}}+1/{{n}\choose{1}}+...+1/{{n}\choose{n}}$ The hint says to consider when $n$ is even and odd. When $n=2k$ I get: $$a_{...
1
vote
1answer
61 views

Proof of product summation of binomial coefficients

when I try to proof the sum of two independent negative binomial distribution to be negative binomial, I end up with how to proof the following identity. I try the induction but after I rearrange the ...
1
vote
2answers
96 views

In how many ways can I split 151 different objects into 3 categories?

In how many ways can I split 151 different objects into 3 categories such that no category gets absolute majority? I figured that the answer should be: ${{151+3-1}\choose{3-1}}-3{{76+3-1}\choose{...
0
votes
1answer
29 views

Negative binomial coefficient

For $r \geq 1$, $k \geq 0$ both integers, I wish to show that $$\binom{-r}{k}^{*}(-1)^{k} = \binom{r+k-1}{k}$$ (the negative binomial coefficient is the left one). By definition, $$\binom{-r}{k}^{*}(-...
1
vote
1answer
45 views

Show that $\sum_{i=\lceil\alpha n\rceil}^n {n\choose i}\le 2^{nH(\alpha)}, \alpha\in(1/2,1]$

For $1/2<\alpha\le 1$ show that $$\sum_{i=\lceil\alpha n\rceil}^n {n\choose i}\le 2^{nH(\alpha)}$$ where $H(\alpha)=-\alpha\log_{2}\alpha - (1-\alpha)\log_2 (1-\alpha)$ is the entropy. I'm ...
1
vote
2answers
43 views

Equality of two binomial coefficient containing expressions

Why is $$ \begin{align} &\sum_{k=0}^n(-1)^k\left[\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\right]2^{n-2k}\\ &=2\sum_{k=0}^{n-1}(-1)^k\binom{n-k-1}{k}2^{n-2k-1}-\sum_{k=0}^{n-2}(-1)^k\binom{n-...
0
votes
2answers
67 views

What is the multiplication of two sigmas?

Say we have two sigmas $\sum_{i=0}^n\dbinom{n}{i}x^i$ and $\sum_{i=0}^m\dbinom{m}{i}x^i$, what would be the resultant of the above? How do you, in general, multiply two sigmas?
11
votes
2answers
141 views

What are the “numerator” and “denominator” of binomial coefficients called?

Do the numbers $n$ and $k$ in the binomial coefficient $\binom nk$ have a name? For the fraction $\frac nk$ we would use numerator and denominator. But I have not seen some terminology for binomial ...
1
vote
3answers
56 views

prove that $ \binom{n-1}{0} +\binom{n}{1}+\binom{n+1}{2}+\cdots+\binom{n+k}{k+1}=\binom{n+k+1}{k+1}$

I am asked to prove that $$ \dbinom{n-1}{0} +\dbinom{n}{1}+\dbinom{n+1}{2}+\cdots+\dbinom{n+k}{k+1}=\dbinom{n+k+1}{k+1}$$ So far what I've tried ,without looking to much at the sum I've to prove ,is ...
0
votes
0answers
49 views

Simplify sum with binomials

An algorithm finds prefixes of given length k from given word with length n. It is required to find the time complexity of given algorithm. It is easy when no nodes get cut off in its recursion tree (...
2
votes
3answers
190 views

Evaluating $\int_{-\pi}^{\pi} (e^{ix} + e^{-ix})^n dx $

In an exercise following identity is used: $$ \int_{-\pi}^{\pi} (e^{ix} + e^{-ix})^n dx = \begin{cases} 0, \hspace{2.1cm} n = 2m+1 \\ 2\pi {2m \choose m}, \hspace{1cm} n=2m. \end{cases}, $$ Does ...
3
votes
3answers
114 views

Proof that $\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$ [duplicate]

The following sum came up in a combinatorial argument. I know what it equals thanks to Wolfram Alpha, but I'm not sure how to show it $$\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$$
1
vote
3answers
99 views

Is there any way to calculate the simple product of binomial coefficients

Given the sum $$ \sum_{k=0}^{m} {n \choose k} {m \choose k}, $$ where $ n > m$. Could it be somehow calculated into a shorter an nicer expression which doesn't contain the sum? Thanks in advance!
0
votes
2answers
146 views

Determine the coefficient of $x^ay^b$ in the expansion of $(1+x+y)^n$

Let $n$ be a positive integer, and let $a, b$ be integers greater than or equal to 0 such that $a+b\le n$. Determine the coefficient of $x^ay^b$ in the expansion of $(1+x+y)^n$. Give a counting ...
1
vote
1answer
45 views

Factorials/Binomial Coefficients (Finding Integer Solutions)

Question There are many integer solutions to the equation $\begin{pmatrix}n\\r\\ \end{pmatrix} = \begin{pmatrix}n+1\\r-1\\ \end{pmatrix}$ including $n = r = 1$. Find an expression ...
5
votes
1answer
73 views

A combinatorial expression is equal to a binomial coefficient squared

Problem: Prove for all natural numbers the following identity: $$\sum_{r=0}^{n}\frac{(2n)!}{(r!)^2((n-r)!)^2}=\dbinom{2n}{n}^2$$ I have just been successful in interpreting the LHS of the above as ...
1
vote
1answer
79 views

How can I evaluate $\sum_{i=0}^\infty \frac{1}{k^i} \binom{2i}{i}$

Evaluate $$\sum_{i=0}^\infty \left(\frac{\binom{2i}{i}}{k^i}\right),$$ where $k$ is a whole number. I can't figure out how to approach this question, as no binomial series has such coefficients.
0
votes
1answer
107 views

Upper bound for partial sum of binomial coefficients

I am familiar with the proof of the upper bound $\sum_{i=0}^k \binom{n}{i} \le (ne/k)^k$, but I was told that the worse bound $$\sum_{i=0}^k \binom{n}{i} \le (n+1)^k$$ has a simple combinatorial proof,...
0
votes
1answer
18 views

Retrieve position from binary number ordered by number of ones

I have binary numbers of length s. They are ordered by numbers of ones, and they can have at most j zeros. That is: first are ordered all numbers containing (s; 0) possible subsets of s numbers, next ...