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
0answers
17 views

binominal inequality - checking

I have to show that $\displaystyle \binom{n}{k}<\binom{n}{l}$ for $\displaystyle 0 \le k <l \le\frac{n}{2}$ where $n,k,l$ are an integers. I think I solved it but I'm not sure if my approach is ...
11
votes
4answers
2k views

Elementary central binomial coefficient estimates

How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ? Does anyone know any better elementary estimates?
7
votes
3answers
121 views

How to prove the following limit: $\lim_{n \to +\infty} 4^n\left[\sum_{k=0}^n (-1)^k{n\choose k}\ln (n+k)\right]=0$?

How to prove the following limit: $$\lim_{n \to +\infty} 4^n\left[\sum_{k=0}^n (-1)^k{n\choose k}\ln (n+k)\right]=0?$$
6
votes
3answers
116 views

Inequality $\binom{2n}{n}\leq 4^n$

I would like to prove the following inequality, for $n=0,1,2,...$, $$ \binom{2n}{n}\leq 4^n.$$ I already proved it by induction, and I'm looking for another proof.
9
votes
1answer
93 views

Consecutive terms in Pascal's Triangle

is it known whether or not there are infinitely many pairs of consecutive terms in this sequence: http://oeis.org/A006987 ? The sequence is the list of numbers expressible in the form ...
0
votes
0answers
16 views

Transformation of a sum

I want to prove the following or a similar result: For $1\le k \le n$ \begin{align}&1-\sum\limits_{j=k+1}^n\binom nj(1-x)^jx^{n-j}~~~~~~(1)\\ ...
3
votes
1answer
214 views

Approximating hypergeometric distribution with poisson

I'm am currently trying to show that the hypergeometric distribution converges to the Poisson distribution. $$ \lim_{n,r,s \to \infty, \frac{n \cdot r}{r+s} \to \lambda} \frac{\binom{r}{k} ...
1
vote
1answer
19 views

Function related to Harmonic numbers, the Pascal triangle, Logarithmic integral and the Polylogarithm.

What function satisfies the following: Let the matrix: $$\displaystyle T = \left(\begin{matrix} 1&0&0&0&0&0&0&\cdots \\ 1&1&0&0&0&0&0 \\ ...
1
vote
3answers
57 views

Show that $ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $?

I can't resolve this exercise and I need a tip. $$ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $$ where $ n \geq s $.
4
votes
4answers
96 views

Solve for $n$, where $n$ is a positive integer

I have $$ {n \choose 2} = 21 $$ and as the title mentions I have to solve for $n$, but so far all I have managed to get to is $$n^2 -n =42 $$ and from there I'm completely lost. Any hints would ...
2
votes
1answer
166 views

probability of rolling at least $n$ on $k$ 6-sided dice

Is there a simple form for the probability of rolling at least $n$ on $k$ 6-sided dice? Of course you can do it by recursion (see here). But is there a way to do it with just a few binomial ...
3
votes
7answers
2k views

How do I compute binomial coefficients efficiently?

I'm trying to reproduce [Excel's COMBIN function][1] in C#. The number of combinations is as follows, where number = n and number_chosen = k: $${n \choose k} = \frac{n!}{k! (n-k)!}.$$ I can't use ...
1
vote
3answers
939 views

Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$

I'm repeating material for test and I came across the example that I can not do. How to calculate this sum: $\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?
1
vote
3answers
138 views

Using Binomial Theorem to prove the following [duplicate]

$$\large\sum_{j=0}^n (-1)^j {n\choose j}={n\choose 0}-{n\choose 1}+.....+\pm{n\choose n}=0 $$ I'm confused by the last part of the equation $\pm$. it seems imply that the sum would be equal to 0 no ...
3
votes
6answers
599 views

How do I begin proving this binomial coefficient identity: ${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
3
votes
5answers
339 views

Evaluating even binomial coefficients

Can someone give me a hint how to evaluate $$ \binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)},$$ where $o(n)$ is $n$ if $n$ is even and $n-1$ otherwise ?
1
vote
1answer
46 views

Finding the coefficient of $x^{46}$ in an expression

In this problem, I found that the answer is the coefficient of $x^{46}$ in $\left(\displaystyle\sum_{r=0}^{3} x^r \right)^6\left(\displaystyle\sum_{r=0}^{8} x^r \right)^4$ Is there possibly a way to ...
2
votes
4answers
883 views

Fermat's Combinatorial Identity: How to prove combinatorially?

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$ I don't have much experience with combinatorial proofs, so I'm grateful for all the hints. (Presumptive) ...
1
vote
3answers
55 views

Find $a_1$ given that $(1+x)^{100} = \sum_{i=0}^{100} a_ix^i$

If $(1+x)^{100} = \sum_{i=0}^{100} a_ix^i$, then $a_1$ is .. The options are $1$, $2$, $99$ or $100$. I'm sure the problem is trivial, but I just don't understand what is meant.
5
votes
2answers
61 views

Challenge: How to prove this identity between bi- and trinomial coefficients?

This question is the continuation of its predecessor. Using the convention that trinomial coefficients $$ \binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1! k_2! k_3!} $$ are zero if $k_i<0$ or $\sum_i k_i\neq ...
2
votes
0answers
25 views

Evaluate $ \sum\limits_{j \in \mathbb{Z}_{\geq 0}} {n \choose r+kj}$ where $n,k$ are fixed

Is there a general way/technique to evaluate $ \sum\limits_{j \in \mathbb{Z}_{\geq 0}} {n \choose r+kj}$ in terms of $r$, where we consider $n$ and $k$ fixed natural numbers and $n > k$? (here, ...
2
votes
2answers
36 views

Proof of Pascal' identity

The identity $$\binom{x+1}{k}-\binom{x}{k}=\binom{x}{k-1}$$ is claimed to hold (using the binomial polynomials, considered as lying in $\mathbf{Q}[x]$) for $k$ at least $1$. Proof: by the usual ...
7
votes
5answers
706 views

Proof of $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$?

How do I prove that $$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$ I saw this in a book discussing generating functions.
1
vote
0answers
24 views

Algorithm for determining whether certain numbers appear in Pascal's triangle

Is there any easy characterisation for the numbers which appear in Pascal's triangle that ARE NOT $\dbinom{n}{1}$, $\dbinom{n}{n-1}$? Is there a fast way to determine if some number (given its prime ...
3
votes
0answers
48 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
3
votes
1answer
228 views

Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$

So, I wonder what is the evaluation of $$\sum_{k = 0}^{n} {n\choose k} k^m\text{,}\qquad (*)$$ where $m,n\in \mathbb{N}$. One of my tries: knowing that $$k^m = \sum_{j = 0}^{m}\text{S}(m,j)\cdot ...
2
votes
1answer
139 views

Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. ...
2
votes
2answers
137 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
-1
votes
0answers
20 views

Simplifying a sum with factorials and permutation counts

I am able to simplify it to a form of summation $$\frac{{n\choose r}}{K {a\choose b}}$$ but not able to proceed any further.
1
vote
4answers
41 views

Why is $\sum\limits_{b=1}^{t-1} {t \choose b} 2^{t-b} = (3^t - 2^t - 1)$

Why is $$\sum\limits_{b=1}^{t-1} {t \choose b} 2^{t-b} = (3^t - 2^t - 1)$$ Thanks.
7
votes
4answers
297 views

Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$ I know that $$2^n = ...
10
votes
3answers
338 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
12
votes
5answers
1k views

Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially

I have to give a combinatorial proof of $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$ I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have ...
4
votes
3answers
2k views

Using Binomial Theorem to prove identity

I need to prove the following using the binomial theorem $${n \choose k} = {n-2 \choose k} + 2{n-2 \choose k-1} + {n-2 \choose k-2}$$ The binomial theorem states $$(1+x)^n = \sum_{k=0}^n {n \choose ...
6
votes
3answers
129 views

Help with a Binomial Identity: $\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = 2^{n+1}$

The following is a problem from the 5th edition of Niven's An Introduction to the Theory of Numbers: Problem 23 of Section 1.4 asks us to prove that $$\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = ...
1
vote
2answers
39 views

Factorial as a sum. Insight appreciated

I recently posted an answer to a question about ways to express the factorial function as a sum. I posted the following formula, which I discovered several years ago and I haven't seen anywhere else: ...
2
votes
1answer
37 views

Find coefficient of $x^3$ in (2+x) ^(3/2)/(1-x)

I can expand $\dfrac{(2+x)^{3/2}}{1-x}=(1+x+x^2+\ldots)\left({3/2\choose0}+{3/2\choose1}(x+1)+{3/2\choose2}(x+1)^2+\ldots\right)$, but that doesn't seem to lead anywhere.
3
votes
3answers
94 views

Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$ \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
1
vote
1answer
34 views

Meaning of coefficients when multiplying together $(1+x^a)(1+x^b)(1+x^c)\cdots$?

I know that when you multiply out $(1+x)^n$, the coefficient of $x^a$ tells you how many ways you can pick a of the brackets to use the x from to make $x^a$. I was wondering whether there is a meaning ...
-2
votes
1answer
48 views

Number after binomial coefficient

What does the number 2 mean in this picture? link Thanks. Sorry I'm not a math expert. I need this to make a program in C to generate a trinomial triangle for a guy who asked it on StackOverflow ...
12
votes
3answers
327 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove this $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
6
votes
2answers
477 views

How to solve 0.5 choose 4?

I was solving this problem for homework. It says, in the problem, that if n is positive you use the generalized definition of binomial coefficients. In my case, n is positive so I just plugged n= 0.5 ...
2
votes
1answer
53 views

How prove this sum $\sum\limits_{n=k}^{\infty}\dbinom{n}{k}\left(\dfrac{-z}{1-z}\right)^n$

prove or disprove $$\sum_{n=k}^{\infty}\binom{n}{k}\left(\dfrac{-z}{1-z}\right)^n= (1-z)(-z)^k$$ my try: since ...
1
vote
1answer
50 views

How to evaluate the finite sum $\sum_{k=0}^n{\alpha \choose k}^2\lambda^k$

Is there a close form expression for the series \begin{equation} \sum_{k=0}^n{\alpha \choose k}^2\lambda^k,\quad \alpha ~ \text{is non-integer} \end{equation} As far as I know, there is an identity ...
2
votes
1answer
47 views

Binomial coefficients inequality

It seems to me that there should be a simple way to prove that $$ \binom{n}{s+1+a} + \binom{n}{a} \leq \binom{n}{s} $$ For $s > n/2$ and $a < n-s$. However it looks like I'm missing it. Any ...
1
vote
1answer
48 views

Binomial Congruence (mod 5) Identity

I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% ...
14
votes
4answers
388 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ I don't know how to prove this at all. Could you show me how ...
5
votes
2answers
103 views

Evaluation of $\sum_{k=0}^n{n\choose k}^2u^k$

I am trying to evaluate the finite sum \begin{equation} f(u)=\sum_{k=0}^n{n\choose k}^2u^k,\quad 0<u\le1 \end{equation} In an first attempt, I think of the generating function \begin{equation} ...
1
vote
2answers
104 views

Proof that $\dfrac{1}{e^x}=e^{-x}$ without converting it to $e^{x}e^{-x}=1$.

I want to show that $\dfrac{1}{e^x} = e^{-x}$ from the Taylor expansion of $e^x$. To express $\dfrac{1}{e^x}$ as a power series, I let: $$ \left(\dfrac{1}{0!}x^0 + \dfrac{1}{1!}x^1 + ...
4
votes
3answers
160 views

Closed form of a sum of binomial coefficients?

I have the following function: $T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same ...