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
4answers
136 views

Find $\sum_{r=0}^{2n}\frac{r}{r+2}\binom{2n}r\;.$

Find $$\sum_{r=0}^{2n}\frac{r}{r+2}\binom{2n}r\;.$$ I got $$\frac{2^{2n+1}(2n^2+n+1)-1}{(2n+1)(2n+2)}$$ but the answer is $$\frac{2^{2n+1}(2n^2-n+1)-2}{(2n+1)(2n+2)}$$ Thanks for the help...
6
votes
1answer
218 views

Combinatorial Identity $ \sum_{k=1}^n (-1)^{k-1} \cdot q^{\frac{k(k-1)}{2}} \cdot \frac{\prod_{i=n-k+1}^n(1-q^i)}{\prod_{i=1}^k(1-q^i)} = 1 $

I have to validate the following identity which is defined: $$ \sum_{k=1}^n (-1)^{k-1} \cdot q^{\frac{k(k-1)}{2}} \cdot \frac{\prod_{i=n-k+1}^n(1-q^i)}{\prod_{i=1}^k(1-q^i)} = 1 $$ where ...
2
votes
1answer
78 views

Combinatorics - finding coefficients when summing over permutations of permutations

I have $N$ 2-tuples. Each tuple* can either be up, in which case it has components $(a,b)$, or it can be down, in which case it has components $(c,d)$. Given that exactly $N_\mathrm{up}$ of these ...
0
votes
0answers
43 views

Analytical solution for binomial equation

Suppose that the random variable $X \sim \operatorname{Binomial}_{n,p}$, and suppose we have $p' \in [0,1]$. I have been asked to solve for the least $n$ such that $P(X \leq 2) = p'$. It was ...
11
votes
3answers
741 views

Binomial Identity $\sum\binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$

I'm looking for a reference with the proof of the following binomial identity: $$\sum_{k=0}^n \binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$$ I've looked in a number of textbooks that have a ...
2
votes
1answer
63 views

combinatorics - number of ways to choose r out of n (with inclusion-exclusion)

Quick question. Out of a set of $n$ apples, we are given that $m$ are delicious. Show that the number of different combinations to choose $r$ apples that contain all of the delicious ones is given by ...
3
votes
2answers
217 views

combinatorics - fixed point permutations

Simple question but I just need a little tip to finish it. we are given $A=\{1,2,3...,2n-1,2n\}$ the set of all integers between and including $1$ and $2n$. We are asked how many different ...
11
votes
3answers
642 views

Prove the lecturer is a liar…

I was given this puzzle: At the end of the seminar, the lecturer waited outside to greet the attendees. The first three seen leaving were all women. The lecturer noted " assuming the attendees are ...
3
votes
1answer
176 views

Pascal Triangle general formula

I'm working on a presentation on the Binomial Theorem for my Algebra 2 class and while writing Pascal's Triangle, I came across one of the properties that I haven't seen in a while. That being ...
1
vote
1answer
108 views

Two team playoff question, homework help

I am working through my college text book (mathmatical statistics freund/walpole) trying to refresh my stat skills. Its been a couple years... I would sure appreciate any pointers on an exercise ...
0
votes
1answer
94 views

Relation between Binomial coefficient and Stirling number of second type

Is that true, that for every n,k such that $$k>1$$ we have the inequality $${n \choose k} \leq {n \brace k}$$?
4
votes
3answers
165 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
1
vote
1answer
79 views

Express number of ways integer can be written as coefficient in generating series

Question: "Express the number of ways that an integer $n$ can be written as a sum of a cube of an integer $s\ge-1$ plus the fourth power of an integer $t$ plus the square of an odd integer $r$ as a ...
10
votes
2answers
137 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
3
votes
0answers
59 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
2
votes
2answers
629 views

Closed form expression for unusual sum of binomial coefficients

How do I get a closed form expression for $\sum_{i=c}^{n} i\binom{i}{c}$? Note that the index ranges over the upper values of the binomial, not the lower. I know computer algebra systems can give me ...
10
votes
5answers
578 views

factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

The successive difference of powers of integers leads to factorial of that power. I think this is the formula $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$ But I found no proof on internet. Please ...
2
votes
1answer
88 views

Is anyway to prove this: $\prod_{k=1}^{n}(a_{k})< (1/n^n)*(\sum_{k=1}^{n}(\sqrt{1+a_{k}*a_{k+1}}))^n$

$$ \prod\limits_{k=1}^{n}a_{k} < {1 \over n^{n}}\left(\,\sum_{k = 1}^{n}\,\sqrt{1+a_{k}\,a_{k+1}\,}\,\right)^n $$ ak and n are positive real number greater than 0. EDIT: a_{k+1} becomes a_{1} ...
1
vote
2answers
59 views

series sum of binomial co-efficients

$C_r$ stands for $_nC_r$ We have to show that $ \frac{C_0}{1} -\frac{C_1}{5} + \frac{C_2}{9} +\ldots+ (-1)^n\cdot\frac{C_n}{4n+1} = \frac{4^n\cdot n!}{1.5.9\ldots(4n+1)}$ What I have done : ...
1
vote
1answer
99 views

Binomial distribution . Heads and Tails

Consider a coin with P(Heads) = 2/ 3 . We toss this coin 100 times (assume that the tosses are independent). Determine the probability that we get exactly 45 tails out of the 100 tosses. First, ...
14
votes
2answers
461 views

Strehl identity for the sum of cubes of binomial coefficients

In 1993 Strehl showed that $$ \sum_k\binom nk^3=\sum_k\binom nk^2\binom{2k}n. $$ I’m interested in a combinatorial proof. Upd (Jan '14). Maybe the original question was too restrictive — I'm now ...
1
vote
0answers
33 views

Shortest ways in a grid above the angle bisector

Suppose, you have a grid with the side lengths n and m and the angle bisector from the upper left corner to the bottom side. To walk along the lines from A to B, there are $\binom{n + m}{n}$ shortest ...
0
votes
2answers
137 views

Combinatorial proof with binomial coefficients

I need to prove this with combinatorial arguments. I don't know how to start. $$ \sum_{j = r}^{n + r - k}{j - 1 \choose r - 1}{n - j \choose k - r} = {n \choose k}\,, \qquad\qquad 1\ \leq\ r\ \leq\ ...
2
votes
0answers
55 views

Bound for squarefree binomial coefficients

Numerical tests up to $x=2000$ seem to suggest that the number of squarefree binomial coefficients is bounded at $\dfrac{112x^{\ y}}{239^{\ y}}$: where ...
4
votes
1answer
155 views

Squarefree binomial coefficients.

At $n=23$, all binomial coefficients are squarefree. Is this the largest value for $n$ where this is the case? Edit A plot up to $n=50$: A plot up to $n=500$: plotted against $n+1$ and ...
1
vote
1answer
28 views

List of length $x$, with letters $A$ and $B$, how many ways? (Basic Combinatorics Question)

I was tasked with finding the number of possible ways of writing a sequence with the following conditions: Sequence has a length $x$, where $x$ is even Sequence consists of the letters $A$ and $B$ ...
11
votes
10answers
715 views

Show that $ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$

I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$ Thanks in advance for any help.
1
vote
4answers
353 views

${1\over{n+1}} {2n \choose n} = {2n \choose n} - {2n \choose n-1}$

I need to prove that $${1\over{n+1}} {2n \choose n} = {2n \choose n} - {2n \choose n-1}$$ I started by writing out all the terms using the formula ${n!\over{k!(n-k)!}}$ but I can't make the two ...
1
vote
1answer
63 views

Why is $ 2\binom nm^2<n^{2m}$?

$\forall n\geq2 \forall m\geq2,$ $$ 2\binom nm^2<n^{2m}.$$ Why is the above inequality, which is equivalent to $ \binom nm<\frac{n^m}{\sqrt 2}$, true?
1
vote
3answers
86 views

Why is this binomial coefficient bounded thus?

Source: Miklos Bona, A Walk Through Combinatorics. $$ \forall k\geq 2,\binom{2k-2}{k-1}\leq4^{k-1}.$$ The RHS is the upper bound of the Ramsey number $R(k,k)$. How can I prove the inequality ...
1
vote
0answers
148 views

Is there a closed form formula for the Bernoulli numbers?

A while ago I found this algorithm. Today I read in wikipedia that Euler zig zag numbers can be used for computing the Bernoulli numbers. This Mathematica program computes the Euler zig zag numbers ...
4
votes
2answers
130 views

Evaluate $\sum\limits_{k=2}^n \frac{n!}{(n-k)!(k-2)!} $

Question is to Evaluate $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!} $$ What i have done so far is $$\sum_{k=2}^n \frac{n!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n \frac{(n-2)!}{(n-k)!(k-2)!}=n(n-1)\sum_{k=2}^n ...
4
votes
2answers
100 views

Proofs from the Book - need quick explanation

I've been recently reading this amazing book, namely the chapter on Bertrand's postulate - that for every $n\geq1$ there is a prime $p$ such that $n<p\leq2n$. As an intermediate result, they prove ...
2
votes
1answer
65 views

Maximum of a sequence $\left({n\choose k} \lambda^k\right)_k$

Is there an expression for the maximum of a sequence $\left({n\choose k} \lambda^k\right)_k$ (i.e. $\max_{k\in\{0,\ldots,n\}}{n\choose k}\lambda^k)$ in terms of elementary functions of $n$ and ...
2
votes
2answers
69 views

Why is $\binom{a}{n}=(-1)^{a}\frac{\sin(n\pi)}{(a+1)\binom{n}{a+1}\pi}$?

Why is $\displaystyle\binom{a}{n}=(-1)^{a}\frac{\sin(n\pi)}{(a+1)\binom{n}{a+1}\pi}$? (A particular case popped up as an alternative formulation in WolframAlpha while operating with binomials. Any ...
1
vote
2answers
55 views

prove that for $n \ge 4, {{2n}\choose{n}} \ge n\cdot2^n$

Prove that for $n \ge 4$ $${{2n}\choose{n}} \ge n\times2^n$$ I tried like that: $T_4$: ${{8}\choose{4}} = 70 \ge 4\times2^4$ = 64 so it's ok $T_{n+1}$: $$\frac{(2n+2)!}{(n+1)!)(n+1)!} \ge ...
2
votes
0answers
81 views

Upper bound for tail of binomial expansion

Let $P,R,T$ be integer constants with $PR$ much greater than $T$. Suppose I flip a coin $PR$ times, each time (independent of other times) getting heads with probability $1/P$. The probability that I ...
8
votes
3answers
357 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
3
votes
2answers
286 views

Sums of central binomial coefficients

Are there closed forms for $$\sum^n_{i=0} \binom{2i}{i}$$ and $$\sum^n_{i=0} \binom{2i}{i}^2$$? Also, how can these sums be approximated?
0
votes
2answers
39 views

Alternative ways to write $ k \binom{n}{k} $

I am looking for a way to simplify $ k \binom{n}{k} $. I don't understand what effect the factor $k$ has on the formula. So can anyone please explain what $\ k\binom{n}{k} $ would equate to?
1
vote
1answer
3k views

binomial distribution(overbooking plane tickets)

I am having trouble with binomial distribution and this problem: an airplane has 200 seats, but 202 tickets are sold. Assume passengers do not show up with a probability of .03 independently. What is ...
0
votes
2answers
101 views

How can I compute this sum of binomial

Is there any way to compute the following sum: $\displaystyle{ \sum_{\ell = {n + 1 \over{\vphantom{\LARGE A}2}}}^{n}{n \choose \ell}5^{n - \ell}}$ where $n$ is odd. Thank you.
1
vote
1answer
75 views

Prove the following combination? [duplicate]

I need a quick proof of the following combination $$\binom{n+1}1+\binom{n+1}2+\binom{n+1}3+\dots++\binom{n+1}{n+1}=2^{n+1}-1$$
0
votes
2answers
246 views

Combinatorics identity algebraic proof

Prove that: $$\sum _{k=1}^nk\binom{n}{k}^2=n\binom {2n-1}{n-1}$$ I tried to prove it using induction: For n+1: $$ \begin{align*} \sum \:_{k=1}^{n+1}k\binom{n+1}{k}^2 &= \sum ...
3
votes
2answers
196 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?
1
vote
1answer
79 views

proving and Identity combinatorially

prove the Identity: (n-k)$\binom nk$ = n$\binom {n-1}k$ I have proven it algebraically but now I need to prove it combinatorially ( count something in two ways). Here is my attempt: theorem: ...
4
votes
1answer
210 views

Sum involving binomial coefficient

I want to analyse the following expression for $x \geq 0$: $$ \sum_{k = 0}^n (-1)^{k+n} \binom{n+k}{2k} x^k $$ I expect and want to prove that for $x \geq 4$, the expression tends to infinity as $n ...
3
votes
5answers
669 views

Proof of binomial coefficient formula.

How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$? This is an accepted fact in every book but i couldn't find a ...
3
votes
3answers
82 views

undetermined coefficients. What am I doing wrong?

I am having some trouble to solve the following differential equation for the undetermined coefficient: $$ y''+2y'+y=xe^{-x} $$ I have been watching some videos on youtube and done some reading but ...
1
vote
2answers
143 views

A Vandermonde's-like identity, new or existing?

From my effort of finding Vandermonde's-like identity, I found out that if $n \le m-2$, then $$\sum_{r=1}^{n+1} \frac{\binom{2r}{r}\binom{m+n-2r}{n+1-r}}{r+1}=\binom{m+n}{n}.$$ I am not sure if ...