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
2answers
50 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
29 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
184 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
41 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 ...
8
votes
4answers
167 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, $$(2n+1)!!=\frac{(2n)!}{2^...
3
votes
1answer
71 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
30 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)!}$$ $$\sum\limits_{k=0}^{n}{...
1
vote
2answers
81 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
22 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
64 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
59 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
123 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
314 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
63 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
62 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\\ j_0+j_1+\cdots+j_k=\ell}}\,\prod_{t=0}^kN(...
0
votes
1answer
37 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
110 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
39 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
72 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 $n=k\colon$...
0
votes
0answers
61 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 integer, $...
2
votes
2answers
69 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}\\ \end{...
0
votes
0answers
35 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
152 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 p^n\sum_{k=0}^{n-1}\...
0
votes
2answers
53 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
99 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
59 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
112 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 ...
11
votes
7answers
1k 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
102 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
103 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 p(n+...
0
votes
1answer
40 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
66 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
35 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
1answer
23 views

Compute: binomial coefficients

Compute from Left-Side: $$ {2p \choose p} -{2p \choose p-1} = {(\frac {1}{p+1})} {2p \choose p}$$ This is the answer $$ ={2p \choose p} -{2p \choose p - 1}$$ $$=\left(\frac{(2p!)}{(p!) (p!)}\right)...
0
votes
0answers
35 views

Number Theory: \binom{p-1}{k} \equiv (-1)^k \pmod{p}

I have this problem assigned for homework: Prove that if $p$ is an odd prime and $k$ is an integer satisfying $1<k<p-1$, then $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$. I've come up with a proof ...
4
votes
3answers
106 views

Bounding a sum of binomial coefficients

I would like to bound the sum $$ \phi(n,k) = {n \choose k} + 2 {n-1 \choose k} + 3 {n-2 \choose k} + \cdots + (n-k+1) {k \choose k} $$ I'm trying to get a handle on how big this sum is. Specifically, ...
1
vote
3answers
31 views

For f(x) = ((3x+7)^8)((4x-5)^3) , find f'(x) and use this answer to find the value(s) of x at which the graph of f(x) has a horizontal tangent line

I know that $f'(x) = (24(3+7)^7)*(4x-5)^3+((3x+7)^8)*12(4x-5)^2$, but is there any easier way to find the horizontal tangent line without expanding the terms using pascal's triangle and solving for x ...
3
votes
0answers
40 views

How to prove this $p^{j-\left\lfloor\frac{k}{p}\right\rfloor}\mid c_{j}$

Let $p$ be a prime number and $g\in \mathbb{Z}[x]$. Let $$\binom{x}{k}=\dfrac{x(x-1)(x-2)\cdots(x-k+1)}{k!} \in \mathbb{Q}[x]$$ for every $k \geq 0$. Fix an integer $k$. Write the integer-valued ...
-5
votes
2answers
94 views

Pascal Triangle Ball Conundrum [closed]

Imagine we have a Pascal Triangle Pin Board: A ball is dropped, and at every pin it has an equal chance of falling left or right. If we drop $32$ balls, what is the probability that the final ...
0
votes
1answer
45 views

Write $1001$ as a binomial coefficient $\binom n k$ with $n ≤ 20$

I have this question involving the binomial theorem and have the answer but trying to understand properly how to get there. In the solutions the first step in the solution is to write $1001 = 7\cdot ...
0
votes
2answers
39 views

Find the coefficient of $x^3$ in the expansion of $(1+x)^3(2+x^2)^{10}$

The coefficient of $x^3$ in the expansion of $(1+x)^3(2+x^2)^{10}$ is (A) $2^{14}$ (B) $31$ (C) $3\choose{3}$ $+$ $10\choose{1}$ (D) $3\choose{3}$ $+2$$10\choose{1}$ (E)$3\choose{3}$$10\choose{1}$...
0
votes
3answers
41 views

Computing binomial coefficients

Compute from Left-Side: $$ {n \choose p} {n-p \choose k-p} = {n \choose k-p \quad p \quad n-k } = {n \choose k} {k \choose p}$$ So i started computing until: $$ ={n \choose p} {n-p \choose k-p}$$ ...
2
votes
0answers
74 views

Greatest Common Divisors in columns and rows of Pascal Triangle

Let $n$ and $k$ be integers such that $n\ge3$ and $k\ge 2$ and $g(n)$ is the prime gap where $n$ lies $$k\le g(n)+2\implies \gcd\left(\binom{n+j}{k} , j\in \{ 1,k-1 \} \right)\gt1$$ $\binom{n+j}{...
3
votes
3answers
114 views

Asymptotic of a sum involving binomial coefficients

Could you help me to find an asymptotic for this sum? $$ \sum_{k=0}^{n - 1} (-1)^k {n \choose k} {3n - k - 1 \choose 2n - k} = {n \choose 0} {3n - 1 \choose 2n} - {n \choose 1} {3n - 2 \choose 2n - 1}...
0
votes
2answers
33 views

Are these expressions (Gamma function and binomial) identical for $n\in \mathbb Z$

For $n\in \mathbb Z$ and $n\ge 0$, prove that: $$\frac{2\sqrt{\pi}\,\Gamma(\frac{1}{2}+n)}{\Gamma(n+1)}=\frac{\pi}{2^{2n-1}}\binom{2n}{n}$$ I started to prove. We now that $\Gamma(\frac{1}{2})=\...
1
vote
1answer
75 views

Proving binomial summation identity using generating functions

An exercise for class requires me to prove the following identity using generating functions: $$\sum_{k=0}^{m/2} (-1)^k {n \choose k} {n+m-2k-1 \choose n-1} = {n \choose m}$$ for all $m \leq n$ and $m$...
2
votes
2answers
66 views

If $a + b + c + d = 45$, how many combinations are there of $a,b,c$, and $d$ if $a \le 5$ and $b \le 3$?

I'm stumped on binomial coefficients and counting problems in discrete math. To be clear, this is not the same problem I'm having to do for homework. I changed the numbers around, but had to include ...