2
votes
1answer
50 views

Sums of binomial coefficients

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
2
votes
2answers
33 views

The sum of binomial coefficients up to $k\le n/4$ does not exceed the $k$th coefficient

How would you prove the following (for when $k\leq\frac{n}{4}$)? $$\sum_{i=0}^{k-1} \binom ni \le \binom nk$$
5
votes
5answers
110 views

Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $

I need any hint with calculating of the sum $$ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}. $$ Maple give the strange unsimplified result $$ I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( ...
1
vote
2answers
34 views

Gosper's Identity $\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1 $

The page on Binomial Sums in Wolfram Mathworld http://mathworld.wolfram.com/BinomialSums.html (Equation 69) gives this neat-looking identity due to Gosper (1972): $$\sum_{k=0}^n{n+k\choose ...
0
votes
0answers
17 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)\\ ...
2
votes
3answers
61 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 $.
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
66 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 ...
1
vote
1answer
39 views

$\sum_{k+M = 0}^n {n \choose k} {n-k \choose m} = 3^n$ help with combinatorial reasoning

$\sum_{k+M = 0}^n {n \choose k} {n-k \choose m} = 3^n $ I have worked the cases for $n=2$, $n=3$, and $n=4$ by hand and it appears to be true. $n=2$: $${2\choose 0}{2\choose 0} + {2\choose ...
1
vote
4answers
42 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.
1
vote
3answers
141 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 ...
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: ...
3
votes
3answers
99 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 ...
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
2answers
72 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
78 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! ...
1
vote
2answers
44 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 ...
3
votes
3answers
141 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 ...
2
votes
2answers
94 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
3answers
55 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 ...
0
votes
1answer
69 views

Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ...
2
votes
1answer
77 views

A double sum with combinatorial factors

Let $n$, $p$ and $j$ be integers. As a byproduct of some other calculations I have discovered the following identity: \begin{equation} \sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} ...
3
votes
1answer
38 views

How to simplify a sum with binomial coefficients multiplied by $k^3/2^k$?

The sum is $$\sum_{k=5}^{\infty}\binom{k-1}{k-5}\frac{k^3}{2^{k}} $$ The first thing I thought of was the binomial coefficient. So I re-indexed it ...
1
vote
3answers
92 views

Simplifying $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}$

In trying to simplify my answer to a problem posted recently, I am trying to show that $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}=8\binom{24}{4}$. I know that ...
1
vote
0answers
59 views

A sum with binomial coefficients in the numerator and denominator.

I am struggling with a combinatorial sum as apart of a long statistical-mechanics derivation. I would appreciate any help. I seek the result of the following summation, for integer $\ell,n$, and ...
0
votes
1answer
28 views

Probability $\sum_{j=n+1}^{2n+1} {M \choose m+1}{M-m-1 \choose j-m-1}/{N \choose j} $

I have a prob. problem: A school has $N$ students in which $M$ students are leader (of each class in school), and $N>M$. There are $2n+1$ balls in the black box including $n+1$ blue balls and $n$ ...
1
vote
1answer
57 views

An upper bound and simplification for expression

I would like to find the upper bound (or simplification) of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}{n+1\choose j}{n \choose i}/{2n+1 \choose j+i}$$ where ...
1
vote
2answers
169 views

How find this sum $\sum_{i=0}^{2n}\binom{2n}{2i}\binom{2i}{i}y^{2i}$

Find the sum close form $$f(x)=\sum_{i=0}^{2n}\dfrac{\binom{2n}{2i}\binom{2i}{i}x^{2i}}{2^{2i}}$$ if we let $$\dfrac{x}{2}=y$$ then $$f(y)=\sum_{i=0}^{2n}\binom{2n}{2i}\binom{2i}{i}y^{2i}$$ ...
0
votes
2answers
63 views

Simplify the expression of binom

Any one knows how to simplify this expression or finding upper bound of this expression: $$\sum_{j=1}^{n+1}\sum_{i=0}^{j-1} a^{j+i} {j+i \choose i}$$ where $0<a<1$ is constant. Thanks a lot.
1
vote
1answer
32 views

Upper bound of $\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}$

I would like to find max (or sup.) of the sum: $$S=\sum\limits_{j=1}^{n+1} \sum\limits_{i=0}^{j-1}{n+1 \choose j}{n \choose i}.$$ I found $S\le \frac{1}{\sqrt{\pi n}}.2(n+1).4^n$ but It seems it's ...
5
votes
3answers
88 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
3
votes
1answer
73 views

Upper bound of $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
7
votes
6answers
209 views

Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$ I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a ...
3
votes
2answers
89 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
2
votes
0answers
49 views

Sum and binomials

I have this sum ...
6
votes
2answers
174 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. ...
1
vote
2answers
82 views

Partial sum of binomial

I 'm trying to figure out a closed form solution for the following summation: $\sum_{j=0}^{\omega} j{n \choose j}p^{j}(1-p)^{n-j}$ where $\omega < n$ Is there any closed form solution?
10
votes
3answers
200 views

How to find sums like $\sum_{k=0}^{39} \binom{200}{5k}$

How do I find sums like these?-- $$S=\displaystyle\sum_{k=0}^{39} \dbinom{200}{5k}$$ that is, when there is a summation of binomial coefficients, but with jumps of some terms..?
1
vote
0answers
42 views

Sum involving binomial coefficients

Exist a closed form for $$\left(-1\right)^{N}\underset{i=1}{\overset{N}{\sum}}\left(-1\right)^{i}\dbinom{N}{i}\dbinom{N+i}{i-1}\,\frac{1}{2i+1}?$$ I think I've to use in some way the formula of the ...
4
votes
0answers
146 views

Proving an equation involving binomial coefficients

Prove that $$\sum_{q=0}^v \binom{v}{q}\frac{q!}{v^{q+1}} = \sum_{q=0}^{v-1} \binom{v-1}{q} \frac{(q+2)!}{v^{q+2}}$$ Thanks. Below are what I have tried: Approach 1: $$\sum_{q=0}^{v-1} ...
2
votes
1answer
48 views

Identity with binomials [duplicate]

Does there exist a closed formula for $$\underset{n=1}{\overset{N-1}{\sum}}\dbinom{N+n}{n}?$$ I've searching on wikipedia but I haven't found this kind of sum.
2
votes
0answers
71 views

Sum of product of binomial coefficients and exponential function

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
0
votes
0answers
26 views

Simplification of a power weighted alternating binomial sum

Given positive integers $T$, $n$ and $m$ and real number $p$ with $0< p < 1$, how can I simplify the following binomial sum: $$ \sum_{k=m}^{\lfloor ...
1
vote
1answer
27 views

Proving an identity involving binomial coefficients and fractions

I've been trying to prove the following formula (for $n > 1$ natural, $a, b$ non-zero reals), but I don't know where to start. $$\sum_{j=1}^n \binom{n-1}{j-1} \left( \frac{a-j+1}{b-n+1} \right) ...
3
votes
2answers
75 views

Integer sum as binomial coefficient

What's the rule for expressing integer sums as binomial coefficients? That is, for $p=1$ it is $$\sum_{n=1}^N n^p = {{N+1}\choose 2} $$ What is it for higher powers?
1
vote
1answer
24 views

A sum of Laguerre polynomials

I'm looking to find a closed-form expression for the sum $$S = \sum_{n=0}^N e^{-x/2} L_n^{0}(x),$$ where $L_n^{0}$ is the $n$th Laguerre polynomial. Using the formula $$L_n^{\alpha}(x) = \sum_{m=0}^n ...
3
votes
4answers
128 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
0
votes
0answers
64 views

What's the interpretation of $\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$?

I'm having problems with finding the combinatorial interpretation of this sum: $$\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$$ Can anyone help, please?
1
vote
1answer
30 views

How find this sum $\sum_{j=0}^{\infty}\binom{m+2j}{m}t^{2j},0<t<1$

Let $m$ is give postive integer numbers, Find the sum $$\sum_{j=0}^{\infty}\binom{m+2j}{m}t^{2j},0<t<1$$ if this not have closed form,and can you use Special function ?