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

How can I prove this inequality for $n\geq 2$?

How can I prove this inequality for all natural numbers $n\geq 2$? ${2n\choose n}>\frac{4^n}{n+1}$ I've tried induction but that was a dead end.
-1
votes
1answer
24 views

Prove $\sum_{k=0}^n {n\choose k} = 2^n$ and $\sum_{k=0}^n (-1)^{k} {n\choose k}=0$ for $n \ge 1$

$\sum_{k=0}^n {n\choose k} = 2^n$ and $\sum_{k=0}^n (-1)^{k} {n\choose k}=0$ how to prove this statement holds for any $n \ge 1$ ? I am not sure how this released to $(x+y)^n$
1
vote
0answers
28 views

Prove: ${n\choose 0}{m\choose k}+{n\choose 1}{m\choose {k-1}}+…+{n\choose k}{m\choose 0}={{m+n}\choose k}$ [duplicate]

Prove: ${n\choose 0}{m\choose k}+{n\choose 1}{m\choose {k-1}}+...+{n\choose k}{m\choose 0}={{m+n}\choose k}$ Is it possible to use Pascal's identity or writing binomial coefficients with factorials?
3
votes
2answers
24 views

Attempting to Prove a lower bound for the Binomial Coefficient [duplicate]

The inequality I am having a problem with is as follows: Let $1\leq k\leq n$, where $n,k$ are natural numbers. Prove that $\binom{n}{k}\geq(\frac{n}{k})^k$ I have proven already the inequality ...
0
votes
2answers
23 views

Binomial Coefficient for m + M [duplicate]

I need to prove that : $$\binom{m+M}{n}= \sum_{i=0}^n \binom{m}{i}\binom{M}{n-i}$$ without expanding. I started by seperating the left hand side to get: $$\binom{m+M}{n} = ...
0
votes
2answers
26 views

Find sum of binominal formula and prove it

I have hard time with finding sum of this: $$ \sum_{k=1}^{n}k{n\choose k} $$ Please help! Prferably with some good hints.
2
votes
1answer
72 views

Closed-form formula to evaluate $\sum_{k = 0}^{m} \binom{2m-k}{m}\cdot 2^k$

Inspired by this question I'm trying to prove that $$\lim_{m \to \infty} \sum_{k = 0}^{m} \frac{m! (2m-k)!}{(m-k)!(2m)!}\frac{x^k}{k!} \approx e^{\frac{x}{2}}$$ So I needed to find the value of ...
0
votes
3answers
48 views

Proving an inequality involving binomial coefficient

What is the best way of proving inequalities including binomial coefficients in general? Lets look at this example: $$\frac{n^k}{k^k}\leq\binom{n}{k}\leq\frac{n^k}{k!}$$ What I started with is: ...
0
votes
3answers
134 views

Evaluating:$\sum_{n=0}^\infty\frac1{\binom{2n}{n}}$ [closed]

How to evaluate: $$\sum_{n=0}^\infty\frac1{\binom{2n}{n}}$$ $\binom{n}{r}$ is the binomial coefficient. If possible, present different methods as well.
2
votes
1answer
53 views

Lottery tickets and the binomial coefficient

A ticket in a lottery consists of 7 of the first 36 positive integers. Questions: 1. Show that the number of possible tickets are $\pmatrix{36\\ 7}$. My answer: To get the number of ways to choose ...
4
votes
1answer
56 views

Divisibility of a number $N$ by $4,7,9$

Let $$N=\binom{20}{7}-\binom{20}{8}+\binom{20}{9}-\binom{20}{10}+\binom{20}{11}-\binom{20}{12}+.......-\binom{20}{20}.$$ Then $N$ is divisible by $\bf{Options::}\;\;:: (a)\; 4\;\;\;\;\;\; ...
0
votes
0answers
33 views

Format of Binomial Coefficient vs Multinomial Coefficient

It would not be unreasonable to assume that a special case of the multinomial coefficient is the binomial coefficient where there are only two terms. Why is the binomial coefficient written ...
0
votes
1answer
42 views

Flaw in proof involving binomial theorem

Suppose we have $-1 < x < 0$, also an irrational $r$. We have three claims: $x^r$ is not defined on $\mathbb{R}$(pretty obvious right) $(1+x)^r$ is defined on $\mathbb{R}$(once again, pretty ...
0
votes
2answers
37 views

Sum over binomial coefficients

Define $$ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $$ for some fixed constant $c$ (say, $0<c<1/2$). What are the asymptotics of $f_c(n)$ as $n\to\infty$? It seems that this should be ...
0
votes
1answer
25 views

Concept Check: Number of ways to have a single pair in a 5-hand deck?

Combinations haven't quite clicked for me yet. The logic behind them doesn't make a lot of sense to me. My question is, why is the answer to this $$_{13} C_{1}\cdot _{4} C_{2} \cdot _{12} C_{3} \cdot ...
7
votes
3answers
173 views

Prove inequality with binomial coefficient: $6 + \frac{4^n}{2 \sqrt{n}} \le \binom{2n}n$

I have to prove inequality, where $n \in N$ $$6 + \frac{4^n}{2 \sqrt{n}} \le {2n \choose n}$$ I have checked and it is true when $n\ge4$, however I have no idea how I should start. Can anyone give a ...
0
votes
0answers
35 views

Another Generalization of Chu–Vandermonde Identity $\sum_{|\alpha|=n}{n\choose\alpha}^2=?$

Chu-Vandermonde identity states $$\sum_{k=0}^n{{n\choose k}^2}=\sum_{k=0}^n{{n\choose k}{n\choose{n-k}}}={2n\choose n}$$ The proof is inspired by expanding $(1+x)^n(1+x)^n$ to two kinds of series and ...
7
votes
4answers
151 views

Prove: ${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-…(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$

Prove: $${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-...(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$$ $(2n+1)!!$ is a factorial of odd integers, ...
3
votes
1answer
63 views

Why does ${3 \choose 1}$ equal to the coefficient of $x^1$ in the function $(1+x)^3$?

There are three containers, each one can hold exactly one element. Thus there are exactly ${3 \choose 1}$ combinations without repetition to put 1 element into those three containers. This coincides ...
0
votes
1answer
29 views

Prove the equation with binomial sum

Prove: $\sum\limits_{k=0}^{n}{{\alpha+k}\choose k}={{\alpha+n+1}\choose n},\alpha\in\mathbb{R},k\in\mathbb{N}$ $${{\alpha+n+1}\choose n}=\frac{(\alpha+n+1)!}{n!(\alpha+1)!}$$ ...
1
vote
2answers
79 views

Proving a binomial identity

Prove that ($k\le m$) $$\sum_{j=k}^m(_{2m+1}^{2j+1})(_k^j)=\frac{2^{2(m-k)}(2m-k)!}{(2m-2k)!k!} , (k\le m)$$ Please help me with this identity, I've spent a lot of time on it but didn't solve the ...
0
votes
1answer
15 views

Can't understand step in proof of Lucas's Theorem

I am having trouble understanding why the "Hence $p$ divides . . . " part follows. This is from the Wiki article on Lucas's Theorem. Help appreciated! If $p$ is a prime and $n$ is an integer with ...
0
votes
0answers
61 views

A sum of binomial coefficients

I know the following identity according to wiki (the one before eq (9)) $$\sum_{k=m}^n {k\choose m}={n+1\choose m+1}$$ Is there an identity for the following sum? $$\sum_{k=m}^n {k\choose m}^2$$ ...
1
vote
4answers
18 views

Show that $\binom{n}{k} \frac{1}{n^k}\leqslant \frac{1}{k!}$ holds true for $n\in \mathbb{N}$ and $k=0,1,2, \ldots, n$

$$\binom{n}{k} \frac{1}{n^k}\leqslant \frac{1}{k!}$$ How would I prove this? I tried with induction, with $n$ as a variable and $k$ changing, but then I can't prove for $k+1$, can I? Is there a ...
-1
votes
1answer
53 views

Proof by induction (Involving sets and factorials)

For all $k$, $n\in{\Bbb{N_0}}$ such that $k ≤ n$ we define: $\binom{n}{k}:=\frac{n!}{k!(n-k)!}\in{\Bbb{Q}}$ I am trying to do a proof by induction for this question. (a) Show that $\binom{n}{k} = ...
1
vote
3answers
116 views

If the coefficient of $x^{50}$ in the expansion of $(1+x)^{1000}+2x(1+x)^{999}+3x^2(1+x)^{998}$…

Problem : If the coefficient of $x^{50}$ in the expansion of $(1+x)^{1000}+2x(1+x)^{999}+3x^2(1+x)^{998} +\cdots +1001x^{1000}$ is $\lambda$ then the value of $\frac{1952! 50!}{1001!}\lambda$ ...
1
vote
2answers
56 views

lower bound on $\sum_{i=0}^{k}\binom{n}{i}$ for $k<n$

Given two positive numbers $n,k$ s.t. $k<n$, an upper bound for $\sum\limits_{i=0}^{k}\binom{n}{i}$ is $\frac{2n^k}{k!}$. Are there any known lower bounds as well? (in particular when $k=2^x-1$ and ...
10
votes
2answers
311 views

Proving that $\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b$

Prove that for all positive integers $b$ that $$\sum_{a=1}^{b} \frac{a \cdot a! \cdot \binom{b}{a}}{b^a} = b.$$ My idea is induction, but I cannot figure stuff out on the inductive step.
2
votes
2answers
55 views

Proof of a sum with binomial coefficients $\sum_{k=1}^n (-1)^{k+1}{\binom nk}\frac{1}{k} = 1 + \frac{1}{2} + \ldots +\frac{1}{n}$ [duplicate]

I need to prove: $$\sum_{k=1}^n (-1)^{k+1}{n \choose k}\frac{1}{k} = 1 + \frac{1}{2} + \ldots +\frac{1}{n}$$ for $n \in \mathbb N$ I should use mathematical induction. So, I've tried going simply ...
2
votes
2answers
54 views

An Identity Involving Narayana Numbers

Let $N(n,m)$ denote the Narayana number defined by $$N(n,m)=\frac{1}{n}{n\choose m}{n\choose m-1}.$$ Let $$A(n,k,\ell)=\sum_{\substack{i_0+i_1+\cdots+i_k=n\\ ...
0
votes
1answer
32 views

Transforming and identity for $n \choose k$ with the “committee and chair” trick

I am not sure if this equality has a more formal name, but it is informally called the "committee and chair" trick from Ross. It is: $$k {m \choose k} = m {m-1 \choose k-1}$$ I saw it applied in the ...
2
votes
2answers
90 views

How to use the method of undetermined coefficients to get complex version of binomial expansion?

Show that if $|z|<1$, and $\alpha\in\mathbb{C}$, then $(1+z)^{\alpha}=\sum\limits_{n=0}^\infty {\alpha\choose n}z^n$, where $${\alpha\choose n}=\frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}$$ I ...
1
vote
0answers
35 views

Asymptotic binomial ratios

I am in need of asymptotic version of $$\frac{ \displaystyle \binom{n^{1-s}}{n^s}}{\displaystyle \binom{n}{n^{s}}}$$ where $n\in\Bbb N$ and $s\in\big(0,\frac12\big)$ and $$\displaystyle \frac{ ...
1
vote
0answers
80 views

Find the closed expression for binomial sum [duplicate]

I need help in finding closed expression for the following sum: $a_n = \sum\limits_{k=0}^n (-1)^k \binom{2n - k}{k}$. By inspecting the first several elements of the sequence I came up with the ...
5
votes
2answers
63 views

Prove: $1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+…+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$

Prove: $\displaystyle 1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+...+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$ I used induction: For $n=1$ equality holds. For ...
0
votes
0answers
51 views

$2k$ as a lower bound for the largest prime divisor of binomial coefficient $\binom{n}{k}$

$$ n-p(n)\lt k\lt \frac{p(n)}{2} \implies p_{n,k} \gt 2k \tag A$$ $$ \begin{eqnarray} 1\le k\le n-p(n) \\ n\ge 11\end{eqnarray} \bigg\rbrace \implies p_{n,k} \ge 2k \tag B$$ $n$ is an ...
2
votes
2answers
56 views

Find three consecutive entries of a row of Pascal triangle that are in the ratio of 1 : 2 : 3

Find three consecutive entries of a row of Pascal triangle that are in the ratio of 1 : 2 : 3 This means that: $$\begin{align} 2\binom{n}{k} =\binom{n}{k+1}\\ 3\binom{n}{k} =\binom{n}{k+2}\\ ...
0
votes
0answers
29 views

Correct coefficients of the fourth power of a sum

Consider the following summation raised to the power $4$: $$S^4 = \left(\sum_{i=1}^{n} x_i\right)^4$$. Clearly this can be expanded as $$ S^4 = \sum_{i=1}^{n} x_i^4 + \sum_{i \ne j} a x_i x_j (x_i ...
4
votes
2answers
112 views

How can I prove this limits result?

When I did exercises in probability theory I found this limits as follows and verified it with Mathematica 8.0, and also noticed when $p=\dfrac12$ it shows that $\displaystyle ...
0
votes
2answers
48 views

Finding a closed form for the recursively defined function using the substitution method.

This is a question from a problem set I had to do for one one of my courses. The following recursively defined function is given \begin{equation*} T(n) = \begin{cases} 1, & if \ n=0 \\ 4, & ...
2
votes
1answer
77 views

(Combinatorial) proof of an identity of McKay

Lemma 2.1 of this paper claims that for integer $s>0$ and $v \in \mathbb{N}$, we have $$ \sum_{k=1}^s \binom{2s-k}{s} \frac{k}{2s-k} v^k (v-1)^{s-k} = v \sum_{k=0}^{s-1} \binom{2s}{k} \frac{s-k}{s} ...
1
vote
0answers
36 views

Recurrence relationships and a “weighted Pascal's triangle”

I was thinking about this problem a few days ago and in the process I came up with what I can best describe as a two-dimensional recurrence relationship. It seemed obvious to me that this was ...
2
votes
2answers
102 views

A sum including binomial coefficients

I would like to prove the following equality: $$\sum_k (-1)^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}=\sum_{k=0}^{n-2}\binom{2n-k-2}{n-1}\binom{n-2}{k}$$ but the power over two and the switch on the ...
9
votes
7answers
671 views

Proof of the Hockey-Stick Identity: $\sum_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's the name of this identity? Is it the identity of the Pascal's triangle ...
2
votes
3answers
100 views

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$. Writing out several terms, I think the answer is $1/(n+1)$, but I'm struggling to prove this. I would greatly appreciate it if someone ...
1
vote
1answer
96 views

Prove by induction $\sum _{i=1}^n\left(-1\right)^{i+1}\:\binom{n}{i}\:\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$ [duplicate]

$$\sum _{i=1}^n\left(-1\right)^{i+1}\:\binom{n}{i}\:\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$ Can someone give me a hint on how to give the proof, I am stuck when I am proving it for ...
0
votes
1answer
36 views

Prove that sum of product of binomial coefficients is equal to 0 [duplicate]

Show that $\sum\limits_{k = 0}^{n} (-1)^k C_n^k C_{3n-k-1}^{2n-k} = 0$ for any $n > 0$. I've tried to prove it by induction, but it turns out to be not so easy. I bet there is some natural ...
1
vote
1answer
58 views

Sum of Binomials Coefficients multiplied by the harmonic numbers

I am interested in solve the next sum: $\sum_{i=1}^{N} {N \choose i} i^{-G}$ for $G \geq 1$. Some ideas? Thank you in advance by your help!
0
votes
1answer
34 views

Function involving combinations and conditions: {1, 2} → {1, 2, 3}

Can someone help me understand this problem? Apparently the total number of functions is 6. $$ ={2 + 3 -1 \choose 2} $$ $$ ={4 \choose 2} $$ $$ =6$$ I'm pretty confused so any detail of the problem ...
0
votes
0answers
62 views

Simplify a double sum

i want to simplify the following sum to obtain an expression without sums: $$\frac{1}{q^{k-1}}\sum_{p=0}^{k-1}{\sum_{r=0}^p{\binom{k-2r-1}{p-r}(-1)^pq^{2(k-p-1)}}}$$ I already try to interchange ...