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)

13
votes
6answers
269 views

Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

How would I prove $$ \sum\limits_{\vphantom{\large A}i\,,\,j\ \geq\ 0}{n-i \choose j} {n-j \choose i} =F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of ...
1
vote
3answers
40 views

Show that the coefficient of $x^i$ in $(1+x+\dots+x^i)^j$ is $\binom{i+j-1}{j-1}$

Show that $$\text{ The coefficient of } x^i \text{ in } (1+x+\dots+x^i)^j \text{ is } \binom{i+j-1}{j-1}$$ I know that we have: $\underbrace{(1+x+\dots+x^i) \cdots (1+x+\dots+x^i)}_{j\text{ times}}$ ...
6
votes
2answers
54 views

$\sum_{k=1}^n \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$

(Own) Let $n,m$ be positive integers such that $m>n$. Prove that $$\sum_{k=1}^n \sum_{a_1+a_2 + \cdots +a_k=n} \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$$ ...
2
votes
3answers
101 views

Binomial Coefficient Computation by Dividing Consecutive Terms

If I take the binomial coefficient: $$\frac{n!}{k! (n-k)!}$$ and I want to know the result of 10 choose 4 and I proceed to do the computation $$\frac{7*8*9*10}{1*2*3*4}$$ by first dividing and then ...
4
votes
2answers
208 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
6
votes
3answers
268 views

How prove this $\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $

I think the following equality is true ($p\in \mathbb{N},p\ge 2$): $$\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $$ when $p=2$, then ...
4
votes
2answers
134 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
7
votes
6answers
456 views

Closed-form expression for $\sum_{k=0}^n\binom{n}kk^p$ for integers $n,\,p$

Is there a closed-form expression for the sum $\sum_{k=0}^n\binom{n}kk^p$ given positive integers $n,\,p$? Earlier I thought of this series but failed to figure out a closed-form expression in $n,\,p$ ...
-4
votes
2answers
38 views
7
votes
2answers
243 views

Category of binomial rings

A binomial ring is a commutative ring $R$ such that (1) the additive group of $R$ is torsionfree and (2) $n!$ divides $x(x-1)\dotsc(x-n+1)$ for all $n \in \mathbb{N}$ and $x \in R$. We may then define ...
10
votes
3answers
310 views

Proof of the identity $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Prove the identity: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$
3
votes
2answers
123 views

Proving the combinatorial identity: $\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$

Let $m$ be a positive integer. I have trouble proving that $$\sum_{k=0}^m (-1)^k 2^{2k-1}\left[{m+k-1\choose 2k}+{m+k\choose 2k}\right]=(-1)^m$$ Anyone?
9
votes
2answers
228 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
5
votes
5answers
186 views

Binomial coefficients in Geometric summation

Guys please help me find the sum given below. $$\sum_{k=j}^i\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}$$ (NOTE):The two coefficients are multiplied by 2 power (k-j) I am using the formula: ...
1
vote
2answers
117 views

Calculating a recursive power term binomial sum

Could someone please help me or give me a hint on how to calculate this sum: $$\sum_{k=0}^n \binom{n}{k}(-1)^{n-k}(x-2(k+1))^n.$$ I have been trying for a few hours now and I start thinking it may ...
1
vote
3answers
102 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
9
votes
3answers
205 views

A sum with binomial coefficients

Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$
0
votes
0answers
29 views

Exponentiation of Pascal's Triangle(in matrix form)

I want to find a pattern in subsequent exponentiations of the pascal triangle shown in the form below Matrix P[K+1][K+1]: $$ \begin{matrix} \binom{0}{0} & 0 & 0 & 0\cdots ...
6
votes
3answers
420 views

Some trouble with the induction

Prove, that for any positive integer $n \geqslant 2$ we have the inequality $$ \frac{ 4^n }{ n+1 } < \frac{ (2n)! }{ (n!)^2 }.$$ For $n=2$ the inequality is true. Directly just take and ...
0
votes
3answers
55 views

Counting numbers of possible solutions

For the equation $\displaystyle x_1+x_2+x_3+x_4+x_5=n$ there are $\displaystyle \binom{4+n}{4}$ solutions. But what about the equation $\displaystyle x_1x_2x_3x_4x_5=n$ ? Assuming $\displaystyle ...
8
votes
4answers
142 views

A binomial identity from Mathematical Reflections

Here is the problem: Let $m,n$ be positive integers with $n>m$. Prove that $\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$ This ...
3
votes
1answer
104 views

Compute $(-1)^n\sum_{k=1}^n (-1)^k\frac{(k+n-1)!}{(k-1)!(k-1)!(n-k)!}$

Compute $(-1)^n\sum_{k=1}^n (-1)^k\frac{(k+n-1)!}{(k-1)!(k-1)!(n-k)!}$ Define $a_{k,m}=\frac{(-1)^{k+m}(n+k-1)!(n+m-1)!}{(k+m-1)[(k-1)!(m-1)!]^2(n-m)!(n-k)!}$ Compute ...
8
votes
2answers
182 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
14
votes
2answers
358 views

Strehl identity for the sum of cubes of binomial coefficients

In 1993 Strehl showed that $$ \sum_k\binom nk^3=\sum_k\binom nk^2\binom{2k}n. $$ I’m interested in a combinatorial proof. Upd (Jan '14). Maybe the original question was too restrictive — I'm now ...
15
votes
2answers
424 views

Show that $ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $

Show that $$ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $$ I don't know whether such identity already exists, or has been posted here before. I discovered this identity while ...
-1
votes
0answers
29 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [closed]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
5
votes
2answers
123 views

Limit involving binomial coefficient

I was trying to find the below limit. The sum can be written in a hypergeometric function but it doesn't seem to help me to find the limit. Any help will be appreciated. $$ \lim_{n \rightarrow ...
2
votes
1answer
37 views

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime. Here $v_p(k)$ denotes the largest $\alpha\in\mathbb Z_{\ge 0}$ s.t. $p^\alpha\mid k$. We have ...
13
votes
4answers
395 views

How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1 $

Show that $$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$ I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you
0
votes
1answer
24 views

number of binary strings with equal number of 0's and 1's

I am trying to count the number $S$ of binary strings with equal number of 0's and 1's. Since this boils down to picking $n$ out of $2n$ places where 0's can fall into, my ansatz is $$ S = ...
0
votes
1answer
67 views

Complexity of $\binom{n}{2}$

So: $$\binom{n}{2} = \frac{n!}{2!(n-2)!}$$ Using Stirling's approximation we have: $$\frac{\sqrt{2 \pi n}(\frac{n}{e})^n}{[\sqrt{2 \pi 2}(\frac{2}{e})^2][\sqrt{2 \pi ...
5
votes
0answers
223 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
-1
votes
1answer
37 views

Explain proof of sum equivalence

I need to prove: $$\sum_{k=1}^n k{n \choose k} 2^{k-1} = n3^{n-1}$$ I have the answer, but I can't understand how can I get from step 1 to step 2?! Step 1: $$(1+x)^n = \sum_{k=0}^n {n \choose k} ...
2
votes
1answer
70 views

Sum with binomial coefficients and integer powers

I would like to have an analytic expression for the following sum $$ G_{n,a} = \sum_{p=1}^n \frac{(-1)^p p^{2(a+n)}}{(n-p)! (n+p)!} \;. $$ I am not sure it has a closed form, but I would at least ...
2
votes
1answer
82 views

How to find coefficient of $x^{12}$ in the expansion of $(1+x+x^2+x^3+…+x^n)^4$

How to find coefficient of $x^{12}$ in the expansion of $(1+x+x^2+x^3+...+x^n)^4$ I tried this : Since $(1+x+x^2+x^3+...+x^n)$ is in GP its sum will be $(x^{n+1}+1)(x-1)^{-1}$ now ACQ we have to ...
1
vote
2answers
118 views

A Vandermonde's-like identity, new or existing?

From my effort of finding Vandermonde's-like identity, I found out that if $n \le m-2$, then $$\sum_{r=1}^{n+1} \frac{\binom{2r}{r}\binom{m+n-2r}{n+1-r}}{r+1}=\binom{m+n}{n}.$$ I am not sure if ...
1
vote
1answer
40 views

Determinant of a matrix with binomial coefficients.

Let $n \in\mathbb{N}$ and $A=(a_{ij})$ where \begin{equation}a_{ij}=\binom{i+j}{i}\end{equation} for $0\leq i,j \leq n$. Show that $A$ has an inverse and that every element of $A^{-1}$ is an integer. ...
3
votes
2answers
378 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 ...
10
votes
3answers
528 views

proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$

I'm looking for a proof of this identity: $$ 1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k} $$ I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum ...
3
votes
1answer
45 views

closed form for some binomial sum

I am trying to derive a closed form for the generating function of $a_n(x)=\sum_{k=0}^n \binom{n+k}{n}x^k, x>0, n\in\mathbb{N},$ i.e. for $G(z)=\sum_{n=0}^\infty a_n(x)z^n$. The only method I ...
10
votes
0answers
144 views

Is the given binomial sum almost everywhere negative as $K\to\infty$?

The binomial sum is as follows: $$\mathcal {L}^K(\theta)= \sum_{i=\lceil{K/2}\rceil}^K \binom{K}{i}\theta^i\left((1-\theta)^{K-i}-\frac{1}{2}(1-\theta)^{-K}(1-2\theta)^{K-i}\right)$$ which can also ...
0
votes
0answers
27 views

Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$ [duplicate]

How do we show that this identity holds for any n? Any hints or solutions? Show $\sum_{ r = 0}^{n} {(\binom n r)}^{2} = \frac{(2n)!}{(n!)^{2}}$
1
vote
3answers
48 views

Calculate sum $S=\sum_{k=0}^{n}\binom{k}m$

Calculate sum $$S=\sum_{k=0}^{n}\begin{pmatrix} k \\ m\end{pmatrix}$$ My solution if $n<m$, $S=0$ else $$S=\sum_{k=0}^{n}\binom{k}m=\sum_{k=m}^{n}\begin{pmatrix} k \\ ...
7
votes
0answers
70 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
0
votes
2answers
71 views
5
votes
3answers
328 views

proof of formula and calculation sum

Show that following formula is true: $$ \sum_{i=0}^{[n/2]}(-1)^i (n-2i)^n{n \choose i}=2^{n-1}n! $$ Using formula calculate $$ \sum_{i=0}^n(2i-n)^p{p \choose i} $$
19
votes
4answers
568 views

A three variable binomial coefficient identity

I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following: $$ \sum_{i+j+k=n} ...
6
votes
1answer
75 views

Combinatorial Interpretation of these two identities

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
1
vote
1answer
65 views

Prove the following combination? [duplicate]

I need a quick proof of the following combination $$\binom{n+1}1+\binom{n+1}2+\binom{n+1}3+\dots++\binom{n+1}{n+1}=2^{n+1}-1$$
1
vote
1answer
41 views

An identity involving the binomial theorem

While working on another problem that involved a linear system of arbitrary size $n$, I managed to empirically come up with a solution for that system. My solution is correct if and only if the ...