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
1answer
35 views

Proving that polynomials with rational coefficients have integer roots

Obviously, polynomials with integer coefficients will satisfy P(x)$\in$ Z or every x $\in$ Z. But how do we prove that those with rational coefficients can produce integer roots? For instance, I have ...
2
votes
0answers
16 views

Analyzing a coin tossing game with cheating

Consider a game where you toss $N$ coins, and let $H$ denote the number of heads. Let's say you win the game if $|H - N/2| \geq K$, i.e. if the number of heads deviates east least $K$ from what you ...
2
votes
1answer
64 views

Compute $\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$

I want to calculate $\sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$. No idea in my mind. Any help? Context I want to calculate the expected value of bits per symbols in adaptive arithmetic coding when the ...
0
votes
0answers
18 views

Asymptotic approximate for Binomial sum

How would you approximate the following sum in terms of n: $$\sum_{k=1}^{n} \binom{n}{k} (k-1)(a - n + k)^{-a + n - k - 1/2}(-1 - a - k + 2)^{1 + a + k - 5/2} e^{-n + 2-\frac{(n - k)}{12*a*(a - n + ...
3
votes
1answer
86 views

Prove a theorem in combinatorics

I want to show that for $k=1,...,(n-1)$ we have : $\binom{n}{k}\leq \frac{n^n}{k^k(n-k)^{n-k}}$ I have used induction on $k$, but I have not deduced the above relation.
2
votes
1answer
26 views

Calculate limit involving binomial coefficient

How can I calculate this limit. Let $p\in[0,1]$ and $k\in\mathbb{N}$. $$\lim\limits_{n\to\infty}\binom{n}{k}p^k(1-p)^{n-k}.$$ Any idea how to do it ?
0
votes
0answers
22 views

Binomial transform

how can be prove expression: $\sum \limits_{s = 0}^{2k} (-1)^s\binom{n+s}{n}\binom{n+2k-s}{n} = \binom{n+k}{k}$ by using this identity: $(1 − t)^{−n−1}(1 + t)^{−n−1}= (1 − t^2)^{−n−1},$ or how ...
1
vote
1answer
36 views

Showing the equality of two rook polynomials.

I'm reading Barbeau's Polynomials. I've done the following: Taking an arbitrary chessboard $C$ with some of the squares forbidden (with $n$ being the number of squares and $F$ the number of ...
0
votes
4answers
26 views

Help in proving an algebraic identity involving powers of binomials.

For some reason I found this equation: $(1 + x)^n - 1 = x \sum\limits_{k=0}^{n-1} (1+x)^k$ I think that this is an identity. If for instance one expands the powers and the sum for n = 4, the ...
1
vote
1answer
26 views

Proving the binomial coefficients by induction (half-done, but need help)

Defining the binomial coefficients $n \choose k$ as follows, i) for all $n \in \mathbb{N}$, $\binom{n}{0} = \binom{n}{ n} = 1$ (ii) for all $2 \leq n \in \mathbb{N}$ and for all $ 1 \leq k \leq n-1, ...
3
votes
0answers
40 views

Lucas' Theorem for $p$-adic integers?

Does Lucas' Theorem hold for $p$-adic integers? More specifically, does it specifically hold for the case that, given a $p$-adic integer: $$x = x_0 + x_1p + x_2p^2 + \cdots = \sum_{i=0}^\infty ...
3
votes
1answer
56 views

Proving a certain sum is 1 [duplicate]

I'd like to prove that, for any $M,N\in\mathbb{N}$ with $M\leq N$, and any $n\in\mathbb{N}$ with $n\leq M$, the sum: $$\sum\limits_{k=0}^n\frac{\binom{M}{k}\!\!\binom{N-M}{n-k}}{\binom{N}{n}}=1.$$ I ...
3
votes
3answers
73 views

Find $k$ given that ${14 \choose k} = {14 \choose k-4}$

Ok, so I stumbled upon the question on the title these days, when going over Apostol's Calculus I. Now, because of the placement of the question in the exercises section, I'm convinced that the book ...
1
vote
1answer
14 views

Binomial Coefficient as Sum of a Sum

Few days ago, I found this equation: $ \sum_{i=1}^n \sum_{j>i} \frac{1}{2} = {n \choose 2} \frac{1}{2} $ I didn't manage to prove it. Does anyone of you know how to prove it?
7
votes
2answers
95 views
+50

An asymptotic expression of sum of powers of binomial coefficients.

Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ ...
2
votes
2answers
50 views

The smallest $n$ for which the sum of binomial coefficients exceeds $31$

I have a problem with the binomial theorem. What is the result of solving this inequality: $$ \binom{n}{1} + \binom{n}{2} + \binom{n}{3} + \cdots +\binom{n}{n} > 31 $$
0
votes
4answers
41 views

Proof that $\sum\limits_{k = 0}^n {n\choose k} =2^n$ using Binomial Expansion Formula

HW problem here. Not sure how to even start on it. Prove that $$\sum\limits_{k = 0}^n {n\choose k} =2^n$$ Any help is appreciated. For Search purposes: (Hint: Use the binomial expansion mentioned ...
0
votes
2answers
123 views

How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$? My questions is, can I choose an $n$ randomly? For example, let's say ...
4
votes
1answer
100 views

Closed form of $\sum_{k=1}^{n}\binom{n}{k} h^{(n-k)}(0)f^{(k-1)}(0)$

Is there a closed form for: $$\sum_{k=1}^{n}\binom{n}{k} h^{(n-k)}(0)f^{(k-1)}(0)$$ where: $$h(x)=(1-x)^{\alpha}(A-Bx)^{\frac{1}{\gamma}-\alpha}$$ and ...
1
vote
2answers
69 views

combinatorial or algebraic proof of combinatorial identity

I would like to find out how to prove the following identity, assuming it is correct: $\displaystyle\sum_{r=0}^n\binom{n}{r}\binom{m+r}{l}=\sum_{r=0}^n\binom{n}{r}\binom{m}{r+l-n}2^r$ for ...
1
vote
1answer
22 views

Probability problem (Bernoulli trial)

I recently became interested in studying probability and I stumbled upon this question: There are three points: A, B and C. Exactly two paths exist between A and B and exactly two paths exist between ...
3
votes
3answers
38 views

Explanation about an identity involving inverse binomial coefficients.

Now, I was solving a this problem. It asks for summation of $$\sum\limits_{k =0}^\infty\dfrac{1}{{n+k \choose n}}$$ I solved it using this answer, the answer turns out to be $$\dfrac{n}{n-1}$$ ...
1
vote
1answer
71 views

Find summation of following series.

What will be the formula for following infinite series? $$1 + \frac{1!}{x+1} + \frac{2!}{(x+1)(x+2)}+ \cdots$$ $$ x\ge2 $$ up to infinite What pattern i got : coefficient of $ \frac{1!}{x+1}$ ...
3
votes
1answer
47 views

Proving a Binomial Identity

Can you please help me with problem 25. I need to prove that $f(n+1)=2 f(n)$, where $f(n)$ is the LHS of the expression, from there on I can do it my self. I have tried using the binominal theorem ...
2
votes
0answers
30 views

Find $f(n)$ in $\binom {2^n} {n^4} = (f(n)+ o(1))^n$

Task is to find $f(n)$ in the following equation: $\binom {2^n} {n^4} = (f(n)+ o(1))^n$ I've found that the problem is a bit over my head. I'm attaching my partial solution below: With use of the ...
3
votes
1answer
35 views

Growth of ratio of binomials polynomial or exponential?

Is the growth of $$ \dfrac{\binom{2n}{\sqrt{n}}}{\binom{n}{\sqrt{n}}} $$ polynomial or exponential (or other kind of growth) in $n$? I tried using the Stirling's approximation, which gives ...
2
votes
1answer
34 views

Evaluation of a limit of ratio of sums [closed]

How do I calculate the value of $$ \lim_{n\to \infty} \left(\frac{\sum_{r=0}^{n} \binom{2n}{2r}3^r}{\sum_{r=0}^{n-1} \binom{2n}{2r+1}3^r}\right)$$
0
votes
2answers
24 views

Proofs of identity for product of binomial coefficients

While verifying my answer to another question, I came across a problem of binomial coefficients: Does $\hspace{.2cm}\displaystyle \prod_{k=1}^{n-1}\binom{n-1}{k}=\prod_{k=1}^{n-1}k^{2k-n}$ for all ...
1
vote
1answer
73 views

Proof of an identity involving binomial coefficients

I have found numerically that the following identity holds: \begin{equation} \sum_{n=0}^{\frac{t-x}{2}} n 2^{t-2n-x}\frac{\binom{t}{n+x}\binom{t-n-x}{t-2n-x}}{\binom{2t}{t+x}} = ...
4
votes
4answers
213 views

Alternating sum of binomial coefficients multiplied by (1/k+1)

I'm trying to prove that $$\sum_{k=0}^n {n \choose k} (-1)^k \frac{1}{k+1} = \frac{1}{n+1}$$ So far I've tried induction (which doesn't really work at all), using well known facts such as ...
1
vote
4answers
57 views

How to calculate $\sum\limits_{k=0}^{n}{k\dbinom{n}{k}}$ [duplicate]

I derived this sum from a problem I have been working on. Somehow I don't know how to proceed. I only know some basics like $\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n$. Meanwhile I am reading the ...
1
vote
1answer
29 views

Product of binomial coefficients

Is there any way to simplify given expression ($j$ and $i$ are given, $n\leq \lfloor j/i \rfloor$) $$\prod_{x=1}^n \binom {j-(x-1)i} {i}$$ (e.g. in terms of factorials)? Thanks!
0
votes
1answer
32 views

Black bears and tan-colored bears catching salmon in Alaska

One of popular tourist attractions in Alaska is watching black bears catch salmon swimming upstream to spawn. Not all "black" bears are black, though- some are tan-colored. Suppose that 6 black bears ...
0
votes
0answers
51 views

Permutation and combination identity

Prove that $\displaystyle \sum_{i=0}^n \binom{n}{i}\binom{m+i}{n}=\sum_{i=0}^n \binom{n}{i}\binom{m}{i} 2^i$ for natural numbers $m,n.$ The question doesn't seem to have any direct combinatorial ...
0
votes
2answers
23 views

How can I solve for $n$ in this binomial coefficient equation

How can I solve for $n$ in this binomial coefficient equation? $${n\choose 3} = {n\choose 9}$$ When I try to expand it using factorials, I get a very, very long equation, involving $n-s$ up to $n^6$ ...
1
vote
1answer
56 views

prove that $ \binom n 2 + \binom {n-2} 2 + \binom {n-4} 2 + \dots + \binom 3 2 = \frac 1 {24} (n-1)(n+1) (2n+3) $

$$ \binom n 2 + \binom {n-2} 2 + \binom {n-4} 2 + \dots + \binom 3 2 = \frac 1 {24} (n-1)(n+1) (2n+3) $$ where n is odd. Plesase help mi with that equation.
2
votes
3answers
48 views

combinational proof for $ 1 + 2 + \cdots + n = \binom {n+1} 2 $

$$ 1 + 2 + \cdots + n = \binom {n+1} 2 $$ Please give me a help with combinational proof for this formula. Greetings for everybody and thanks in advance.
0
votes
2answers
27 views

counting the rectangles in nxn square

How many different rectangles can be seen in an $$ n \times n $$ grid like the one shown? Of course the rectangles must be at least one box wide and deep, and squares are allowed. ...
1
vote
1answer
70 views

World series lengths competition, binomial distribution.

Listed in the following table is the length distribution of World Series competion for the 58 series from 1950 to 2008 (there was no series in 1994). WORLD SERIES LENGTHS (note, the total = 58) of ...
2
votes
1answer
77 views

Proof with combinatorial argument

Show with combinatorial argument that this is equal : $$\dbinom{n}{k+1} = \dbinom{n-1}{k}+ \dbinom{n-2}{k} +...+ \dbinom{k}{k}$$ I have no idea how to do that so it would be really helpful ...
2
votes
1answer
36 views

Showing equivalence of two binomial expressions

I wish to show that $\sum_{k=0}^n {n\choose k}(\alpha + k)^k (\beta + n - k)^{(n-k)} = \sum_{k=0}^n {n\choose k}(\gamma + k)^k (\delta + n - k)^{(n-k)}$ given that $\alpha + \beta = \gamma + \delta$. ...
0
votes
0answers
22 views

Choice problem: number of pairs can be formed out of a set with odd cardinality

There are 17 languages (at a meeting) and for every two languages there is one interpreter assigned. The number of pairs we can form out of 17 languages is $\binom{17}{2} = 136$. So 136 interpreters ...
2
votes
4answers
66 views

Prove that $\sum_{k=1}^nk^2{n\choose k}^2=n^2 \binom {2n-2}{n-1}$

Please help me / give a hand with combinational prove for: $$ 1^2 \binom n 1 ^2 + 2^2 \binom n 2 ^2 + \dots + n^2 \binom n n ^2 = n^2 \binom {2n-2}{n-1}$$
1
vote
2answers
46 views

Why does $ \frac{b^n-a^n}{b-a}=\sum_{k=1}^nb^{n-k}a^{k-1}$?

Trying to work through the answer in this question: The inequality $b^n - a^n < (b - a)nb^{n-1}$
6
votes
5answers
409 views

Choice Problem: choose 5 days in a month, consecutive days are forbidden

I'm "walking" through the book "A walk through combinatorics" and stumbled on an example I don't understand. Example 3.19. A medical student has to work in a hospital for five days in January. ...
2
votes
4answers
131 views

Proving $ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $ without induction

I have to prove that: $$ \binom n 0 ^2 + \binom n 1 ^2 + \dots + \binom n n ^2 = \binom { 2n} n $$ I don't want a complete solution, but only a hint.
2
votes
2answers
40 views

Sums with squares of binomial coefficients multiplied by a polynomial

It has long been known that \begin{align} \sum_{n=0}^{m} \binom{m}{n}^{2} = \binom{2m}{m}. \end{align} What is being asked here are the closed forms for the binomial series \begin{align} S_{1} &= ...
0
votes
0answers
26 views

difference between independent binomial variables

It is well known that if $X \sim B(m, p)$ and $Y \sim B(n, p)$ are independent then $X+Y \sim B(m+n, p)$ but what is the distribution of $X-Y$? Here is what I have tried. $\Pr[X-Y = c] = \sum_{i=0}^n ...
0
votes
3answers
50 views

Alternating sum with binomial coefficients

$\sum_{k=0}^{49}(-1)^k\binom{99}{2k}$ = ? I've tried expanding the binomial coefficient in its factorial form and can't seem to get to manipulate it in a way that solves the expression. ...
0
votes
2answers
33 views

proving counting problems?

Let n >= 1 be an integer. We consider passwords consisting of n characters, each character being a digit or a lowercase letter. A password must contain at least one digit. How do I show that the ...