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
98 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 ...
4
votes
1answer
109 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
2answers
62 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 ?
2
votes
2answers
92 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
61 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
72 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
35 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
58 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
63 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
81 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
27 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?
0
votes
4answers
61 views

Simplifying a fraction with binomial coefficients [closed]

I'm trying to do a simple combination but seem to forget the shortcut. It is $${\binom{6}{2}+\binom{4}{2} \over \binom{10}{2}}$$ Now finding the answer on my calculator is easy, the problem is that I ...
9
votes
2answers
192 views

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
57 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
68 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
161 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
147 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
101 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
33 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
4answers
62 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
83 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
56 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
34 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
45 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
61 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)$$
1
vote
2answers
45 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
91 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}} = ...
5
votes
4answers
405 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
70 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
34 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
74 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
2answers
37 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
60 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
65 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
41 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
150 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
140 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
43 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$. ...
2
votes
4answers
82 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
56 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}$
7
votes
5answers
468 views

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

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
363 views

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

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.
3
votes
2answers
60 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} &= ...
1
vote
0answers
43 views

difference between independent binomial variables [duplicate]

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
70 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
38 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 ...
2
votes
2answers
130 views

Estimating sum with binomial coefficients

Lately when I was estimating complexity of some algorithm I came across this sum: $$\sum_{k=0}^n \binom {n}{k} \binom {n-k}{k}$$ Is it possible to find a closed-form expression for this sum, or at ...
-2
votes
2answers
109 views

Using Newton's binomial theorem to prove that a sum evaluates to $36^n-26^n$ [duplicate]

Using Newton's binomial theorem to argue that: $n \ge 1$ $$36^n - 26^n = \sum_{k=1}^{n}\binom{n}{k}10^k \cdot 26^{n-k}$$ my argument $$(26+10)^n = ...
0
votes
1answer
48 views

Use Leibniz' formula to show that the $(2n)$th derivative of $(2x^2 + 3x +1)sinx$ is $(-1)^n(2x^2+3x-8n^2+4n+1)sinx+(-1)^{n+1}(8nx+6n)cosx$ wrt $x$

If I let $f=f(x)=sinx$ and $g=g(x)=2x^2+3x+1$ and $D=$ First derivative wrt $x$, $D^2=$ Second derivative wrt $x$ and $D^n=$ $nth$ derivative wrt $x$ then, Leibniz' formula states that $\displaystyle ...
2
votes
3answers
105 views

What is wrong with this calculation of $\binom{\frac{1}{2}}{k}$?

The reason I ask this question is that I want to show that: \begin{equation*} \binom{\frac{1}{2}}{k} = -2\frac{1}{k}\binom{2k-2}{k-1}\left(-\frac{1}{4} \right)^k \end{equation*} \begin{align*} ...