Tagged Questions

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

Prove $\binom{N}{k}=\frac{N^k}{k!}\left(1+O(\frac{1}{N})\right)$ when $N \rightarrow\infty$

Can someone help prove the following: $\binom{N}{k}=\frac{N^k}{k!}\left(1+O(\frac{1}{N})\right)$ when $N \rightarrow\infty$. Thanks in advance!
0
votes
1answer
19 views

Maximize parial sum of binomials

During my research I got to the point when I need to find $$ \arg \max_w \left( (n-w) \sum_{j=0}^d \binom{w}{j} \binom{2^r - (j+1) 2^{r-j-1}-2}{t} \right) $$ with respect to $w$ only (i.e. $d$, $n$, ...
1
vote
1answer
35 views

function from a Binary sequence to the Natural Numbers

I apologize if this is a duplicate question. I don't know enough terminology to thoroughly search. However, given a sequence of binary numbers $1_10_20_3...0_n$, $0_11_20_3...0_n$, ... , ...
2
votes
1answer
22 views

difficulties in a proof with binomial theorem

how can one prove, that: $\sum_{k=0}^{n}\binom{2n+1}{k}=2^{2n} $ I was trying to use the binomial theorem, but I do have difficulties with 2n+1 in the binomial coefficient. Thank you
1
vote
1answer
21 views

Apples Binomial [on hold]

"Apples are packaged automatically in 3-pound bags. Suppose that 4% of the time the bag of apples weighs less than 3 pounds. If you select bags randomly and weigh them in order to discover one ...
4
votes
1answer
31 views

Value of sum $\sum_{i=0}^n\binom{2n}{2i}(-3)^i$

What is the value of the sum $\sum_{i=0}^n\binom{2n}{2i}(-3)^i$? It looks like the binomial expansion $(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i$, but we only take every other term, and also the power is ...
0
votes
0answers
16 views

Find the largest term for the binomial expansion of (n+1/n)^(2n+1)?

For (∀n ∈ N{1,2 }). So what I have done at first to try the (Tk+1/Tk)>=1, but it gave me wrong answers, for example I got that my coefficient was negative which is absurd.
3
votes
4answers
135 views

proving an invloved combinatorial identity

How to prove following Identity? $$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$ This seems very hard to me. Any idea about how to prove it combinatorialy? ...
3
votes
1answer
50 views

Is the following limit correct? $[\lim_{n\to\infty}\binom{n}{50}(\frac2n)^{50}(1-\frac2n)^{n-50}]$

$$\lim_{n\to\infty}\binom{n}{50}\left(\frac2n\right)^{50}\left(1-\frac2n\right)^{n-50}$$ Taking $nh=1$ and $K=\binom{n}{50}\left(\frac2n\right)^{50}\left(1-\frac2n\right)^{n-50}$, we have: ...
0
votes
1answer
32 views

$\sum_{k=0}^n\binom nk x^k=\sum_{k=0}^n\binom nk x^{n-k}.$

$$\sum_{k=0}^n\binom nk x^k=\sum_{k=0}^n\binom nk x^{n-k}.$$ I want a deeper understanding of solving problems in this nature. I can´t grasp this writing way.I get confused just by looking at these ...
3
votes
2answers
100 views

How to prove that $\sum_{k=0}^n\cos(k\pi)\binom{n}{k}=0$?

$$\sum_{k=0}^n\cos(k\pi)\binom{n}{k}=0$$ I approached this problem having no idea that $\cos(k\pi)$ could be substituted so easily. I tried first to expand the sum to $n$. So I wanted to ask if ...
1
vote
0answers
14 views

How find this binomial-coefficients sum $\sum_{k_{1}+k_{2}+\cdots+k_{d}=n}\binom{n}{k_{1},k_{2},\cdots,k_{d}}^2$

Question: Assmue that $d$ is give postive integer numbers,and $$(x_{1}+x_{2}+\cdots+x_{d})^n=\sum_{k_{1}+\cdots+k_{d}=n} \binom{n}{k_{1},k_{2},\cdots,k_{d}}x^{k_{1}}_{1}x^{k_{2}}_{2}\cdots ...
0
votes
0answers
17 views

Can binomial coefficient be defined as a natural number if n is the cardinality of a countable set?

Can binomial coefficient n choose k, k less than or equal to n, be defined as a natural number if n is the cardinality of a countable set?
0
votes
3answers
19 views

Summation using cdf of binomial distribution

I'm trying to find the exact value of the following equation: $$\sum_{x=0}^{1000}\tfrac{x^{2}-x+5}{x!(1000-x)!}2^{x}7^{1000-x}$$ I've managed to convert to the following: ...
2
votes
2answers
37 views

Relation among numbers in a triangle like tartaglia:

I have a polynomial associate to a number: $$\begin{align} k&=1 &n-1\\ k&=2 &n^2-2n +2\\ k&=3 &n^3-3n^2+6n+6\\ k&=4 &n^4-4n^3+12n^2-24n+24 \end{align}$$ and in ...
1
vote
1answer
56 views

Harmonic number identity

I search for an elementary proof of the following identity: $$ \sum_{i=1}^{n-k} \frac{(-1)^{i+1}}{i}\binom{n}{i+k}=\binom{n}{k}\left(H_n-H_k\right) $$ I have found the following proof: $$ ...
3
votes
3answers
30 views

Sum of coefficients in binomial theory.

While trying to get introduced to binomial theory at university's website, I learned about the sum of binomial coefficients, and they showed me some of the features, and one of them was the pyramid of ...
0
votes
1answer
19 views

Chance of winning in a raffle

A raffle consists of 10 sheets with 10 numbers (1 to 10) on each sheet i.e. 100 chances in total. The draw is done by first selecting a sheet at random and then selecting the winning number out of the ...
1
vote
1answer
43 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
33 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
74 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 ...
3
votes
1answer
93 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
29 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
25 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
44 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
27 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
41 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
75 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
15 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?
9
votes
2answers
149 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
51 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
43 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
125 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
113 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
73 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
24 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
46 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
49 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
36 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
26 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
74 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
216 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
34 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 ...