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)

12
votes
3answers
307 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.
1
vote
1answer
37 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
384 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
80 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
101 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
156 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 ...
0
votes
1answer
44 views

How to evaluate $\sum_{k=0}^{n} \alpha^k \binom{n}{k}$?

I am trying to show that the function that satisfies $f^\prime(x)=f(x)$ with $f(0)=1$ behaves in an exponential way (in other words, I want to justify writing it as $e^x$). I need to show that: $$ ...
3
votes
3answers
53 views

Sum of products of binomial coefficients

In a proof I've come across the following identity: $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$ I see that it's right, when plugging in numbers, but I don't see the ...
3
votes
2answers
115 views

how to prove $\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$ without induction?

$$\sum_{k=0}^{m}\binom{n+k}{n}=\binom{n+m+1}{n+1}$$ how to prove it without induction? I tried with several way but I failed anybody help me ?
6
votes
2answers
172 views

Prove $(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j} $

I stumbled upon the identity $$(1-x)^{2k+1} \sum\limits_{n\ge 0}\binom{n+k-1}{k}\binom{n+k}{k} x^n = {\sum\limits_{j\ge 0} \binom{k-1}{j-1}\binom{k+1}{j} x^j}. $$ The right-hand side is a polynomial. ...
3
votes
3answers
120 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
1
vote
1answer
31 views

I want to prove this identity involving the binomial coefficients

Can you help me prove the following identity? I know it holds because I simulated it. For positive integers $n,m,k$ and for $i=0,\ldots,n$ and for $n \leq m$ we have: $$\sum_{j=0}^i (-1)^{i+j}\binom ...
3
votes
2answers
270 views

This question involves Pascal's Triangle & Binomial Theorem. Full Question

Could anyone please help me on the following problem: Factorize the expression $P(n)=n^x-n$ for $x=2,3,4,5$ Determine if the expression is always divisible by the corresponding $x$. If divisible use ...
4
votes
4answers
231 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 = ...
2
votes
1answer
275 views

Manipulation of Geometric Series and Binomial Theorem

I was just hoping to confirm that the following manipulations make sense: Say I begin with $\frac{1}{(1-x)^n}$. Then we have $(1-x)^{-n} = $$\sum$ $-n\choose k$ $(-x)^k$ = $\sum$ $(-1)^k$ $n+k-1 ...
2
votes
2answers
23 views

Appromixation of binomial coefficient for large numbers

In the context of writing a program for sortition, I would like to know if the entropy of my input random variable in large enough to potentially produce all outcome of my sortition problem. Let say ...
9
votes
3answers
390 views

Binomial Identity $\sum\binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$

I'm looking for a reference with the proof of the following binomial identity: $$\sum_{k=0}^n \binom{2n+1}{2k+1}\binom{m+k}{2n} = \binom{2m}{2n}$$ I've looked in a number of textbooks that have a ...
8
votes
4answers
209 views

Prove that $\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$

Prove that $$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$ What should I do for this equation? Should I focus on proving ...
2
votes
1answer
25 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
2
votes
3answers
388 views

Evaluate a sum with binomial coefficients

$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$ I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$ ...
2
votes
2answers
55 views

Alternating sum of binomial coefficients is equal to zero [duplicate]

Prove without using induction that the following formula:$$\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ is valid for every $n\ge1$. Progress For each odd $n$ we can use the ...
2
votes
2answers
71 views

How to prove $n! > n^a$ for all $a\in \mathbb{R}$ (for sufficiently large $n$)?

I've encountered a proof which claims $n! > n^2$ for sufficiently large $n$. I tried using induction to prove it for an arbitrary $a$: $n! > n^a$. Lets assume the claim is true for $n$: $n! ...
3
votes
2answers
271 views

Sum of product of binomial coefficients $ = (-1)^n$

Based on the binomial expansion of $(1+x)^n$, show that: $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n$$ This is a question from a very old high school exam paper I came across. It ...
1
vote
2answers
59 views

What is the function given by $\sum_{n=0}^\infty \binom{b+2n}{b+n} x^n$, where $b\ge 0$, $|x| <1$

For a nonnegative integer $b$, and $|x|<1$, what is the function given by the power series $$ \sum_{n=0}^\infty \binom{b+2n}{b+n} x^n. $$ For $b=0$, this post shows $$ \sum_{n=0}^\infty ...
9
votes
4answers
279 views

Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i ...
6
votes
4answers
139 views

How prove this inequality $(1+\frac{1}{16})^{16}<\frac{8}{3}$

show that $$(1+\dfrac{1}{16})^{16}<\dfrac{8}{3}$$ it's well know that $$(1+\dfrac{1}{n})^n<e$$ so $$(1+\dfrac{1}{16})^{16}<e$$ But I found this $e=2.718>\dfrac{8}{3}=2.6666\cdots$ ...
1
vote
1answer
24 views

Verification of binomial coefficient congruence $\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$

Let $j\ge 1$ be an integer and $p$ prime. Is it true that $$\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$$ My work No, take $j>p$, then the RHS is zero, while the LHS need not be $\equiv 0$. For ...
1
vote
3answers
289 views

Sum of the series $\sum_{k=0}^{r}(-1)^k.(k+1).(k+2).\binom{n}{r-k} $

for $n>3$, The sum of the series $\displaystyle \sum_{k=0}^{r}(-1)^k.(k+1).(k+2).\binom{n}{r-k} = $ where $\displaystyle \binom{n}{r} = \frac{n!}{r!.(n-r)!}$ My try:: I have expand the ...
0
votes
0answers
22 views

is binomial congruence given in article true or false?

I'm just reading a paper which, on its page 3, Application 8, claims the following: $$\binom{k+sp}{j}\equiv\binom{k}{j}\pmod{p}$$ where $p\ge 1$, $s\ge 1$, $k\ge 1$ and $p\not\mid j$ (actually, it ...
3
votes
1answer
371 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
1
vote
3answers
55 views

Showing that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$

I'm trying to prove that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$. I figured induction was the way to go, so I tried. This is what I've accomplished so far: Proved ...
5
votes
2answers
10k views

Negative Exponents in Binomial Theorem

I'm looking at extensions of the binomial formula to negative powers. I've figured out how to do $n \choose k$ when $n < 0 $ and $k \geq 0$: $${n \choose k} = (-1)^k {-n + k - 1 \choose k}$$ So ...
-1
votes
2answers
51 views

Squared binomial paradox?

When you square this $$(5-2)^2$$ you will get 49 $$ 5^2 - 2 * 5 * (-2) + (-2)^2$$ $$25 + 20 + 4 = 49$$ but if you do it like this (5-2) * (5-2) you will get 9 $$ 5(5-2) - 2(5-2)$$ $$25-10-10+4$$ ...
6
votes
5answers
249 views

Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?

I have run across the following multinomial series: $$ \sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} $$ Here, $d>1$. This seems like a formula which has either a well-known identity, ...
1
vote
3answers
25 views

refactoring binomial with negative power

I am reading Calculus Made Easy where in Chapter IV: $$(x+dx)^{-2}$$ Is refactored as: $$x^{-2}\left(1+\frac{dx}x\right)^{-2}$$ Could someone give me an insight into this refactoring? I can see from ...
11
votes
4answers
2k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
1
vote
1answer
317 views

A Curious Binomial Coefficient Sum

Let $k, l \leq n$ be non-negative integers. Does the following identity simplify? \begin{align} \sum_{j = 0}^{k} \binom{k}{j} \binom{j + n -l + 1}{n} = \binom{n - l + 1}{n} ...
0
votes
1answer
30 views

The sum of the product of two binomial coefficients

This is really phsycics related question with mathematics behind it. In my physics book there's the following relation: ...
8
votes
3answers
121 views

Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$

This result, $$\prod_{k=1}^{\infty} \big\{\big(1+\frac1{k}\big)^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$$ is in a paper by Hirschhorn in the current issue of the Fibonacci Quarterly (vol. ...
1
vote
2answers
40 views

Problem involving summation and binomial coefficient

I have been fighting with this but I'm really not getting anywhere. $$\sum_{0\leq2k\leq n}\binom{n}{2k}2^k\equiv0\pmod 3$$ $$iff$$ $$n\equiv2\pmod 4$$ Hint: Consider ...
7
votes
1answer
315 views

Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
7
votes
2answers
204 views

About one generating function

Initially, I have the following problem: find $$\sum_{k=0}^{n+1}(−1)^{n−k}4^k{n+k+1 \choose 2k}.$$ I thought, if I found the function $g_n(x) = \sum_{k=0}^{n}{n+k \choose 2k}x^k$, the answer would be ...
7
votes
4answers
722 views

partial sum involving factorials

Here is an interesting series I ran across. It is a binomial-type identity. $\displaystyle \sum_{k=0}^{n}\frac{(2n-k)!\cdot 2^{k}}{(n-k)!}=4^{n}\cdot n!$ I tried all sorts of playing around, ...
2
votes
1answer
19 views

Relating Binomial Coefficients

This question popped up in my revision sheet, and was just wondering on how to do it (this is high-school math by the way, so nothing too complicated please) "Expand $(x+(1-x))^n$, and use this to ...
1
vote
0answers
15 views

The distribution of sum of two binomials with complement success probabilities

It is well-known that if $X$ and $Y$ are independent binomial random variables with parameters $(n_1,p)$ and $(n_2,p)$ respectively, $Z = X+Y$ has a binomial distribution with with parameters ...
2
votes
2answers
90 views

Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction

I have a problem with following equality: $$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$ And I would like to use induction in following way: Base: $$ m = n $$ And: $$ ...
3
votes
0answers
75 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
5
votes
6answers
2k views

Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
3
votes
3answers
122 views

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ...
4
votes
0answers
66 views

Binomial triplets

Solutions to the equation $$\dbinom{a}{n}+\dbinom{b}{n}=\dbinom{c}{n}$$ I will refer to as 'Binomial triplets of order $n$'. These triplets describe simplicial $n$-polytopic numbers that can be ...