2
votes
1answer
44 views

Prove $\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}$

How to prove that $$\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}=\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}$$ ? I tried to break the right ...
3
votes
2answers
85 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$, ...
0
votes
1answer
22 views

In how many ways can you paint 90 distinct buckets?

In how many ways can you paint 90 distinct buckets, if 25 of them must be painted red, 40 of them must be painted blue, and 25 of them must be painted green? I am right to assume that these object ...
0
votes
1answer
29 views

Giving a closed expression to $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i}$

I want to prove $\sum_{i=0}^b (-1)^{b-i} \binom{b}{i}\frac{1}{a+b-i} = \frac{(a-1)! b!}{(a+b)!}$ yet I feel like I don't know how to even approach this problem. Any hints are welcome.
5
votes
5answers
112 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( ...
8
votes
1answer
389 views

Sum of Squares of Harmonic Numbers

Let $H_n$ be the $n^{th}$ harmonic number, $$ H_n = \sum_{i=1}^{n} \frac{1}{i} $$ Question: Calculate the following $$\sum_{j=1}^{n} H_j^2.$$ I have attempted a generating function approach but ...
-2
votes
1answer
39 views

Summation of Combination [closed]

PROVE $$\sum _{ t=0 }^{ r }{ { (-1) }^{ t } } {r \choose t}{ n-t \choose s}\quad =\quad { n-r \choose n-s }$$
3
votes
1answer
54 views

An equality from Representation Theory

Studying Representation Theory of finite groups I've bumped in the following identity: $$\frac{n(n+1)}{2}=\sum_{i=1}^n\frac{(2i-1)!!(2n-2i+1)!!}{(2i-2)!!(2n-2i)!!}$$ My book suggests to prove it ...
2
votes
3answers
62 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
2answers
44 views

Closed form sum for the series given below?

Does the following series have a closed form sum? $$f(n,r) = \sum_{i=0}^n \binom{r+i}{r}$$
1
vote
0answers
24 views

Necessary condition for symmetric sums

It is easy to see that if a function $f(x_1,x_2,x_3)$ can be written in the form: $$ f(x_1,x_2,x_3) = g(x_1,x_2) - g(x_1,x_3) + g(x_2,x_3) $$ for some function $g$, then we have: $$ f(x_1,x_2,x_3) - ...
1
vote
1answer
41 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.
4
votes
1answer
46 views

Nested Sum Encountered in Maclaurin Expansion of $e^{-x^2}$

In the course of working out the Maclaurin expansions of $e^{-x^2}$ and $cos(x^2)$, I ran into the following nested sum: $$ \underbrace{ \sum_{a=0}^1 \left( a \sum_{b=0}^{a+1} b \left( ...
3
votes
3answers
101 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
4answers
63 views

Exotic proofs of $\sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$

Let $p,n$ be positive integers. The following identity $\displaystyle \sum_{j=0}^{n-1}\binom{p+j}{p}=\binom{p+n}{p+1}$ may be proved by induction or by successive uses of Pascal's rule (both ...
3
votes
5answers
117 views

Computing $\sum_{i=0}^{\infty}\frac{i}{2^{i+1}}$

I came across this while trying to solve Google's boys & girls problem, and although I know now it's not the right approach to take, I'm still interested in summing ...
2
votes
2answers
75 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 ...
0
votes
1answer
35 views

Value of an iterated sum

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots ...
1
vote
2answers
46 views

How to show the identity relating to Matrix

Suppose that $$ A=\begin{bmatrix}a_{11}&a_{21}\\a_{21}&a_{22}\end{bmatrix}, \ \ B=\begin{bmatrix}d&-1\\1&0\end{bmatrix}. $$ and $$A=B^N$$ Show that $$a_{11}=\sum_{i=0}^{[N/2]}(-1)^i ...
3
votes
3answers
144 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
69 views

Why does this sum equal to (4^n -1)

How do I get to this solution? $\sum _{k=1}^n\left(\binom nk 3^{n-k}\right)=\left(4^n-1\right)$ I believe it's connected to this, which I know is true: $\sum \:_{k=1}^n\binom nk=2^n-1$
3
votes
3answers
120 views

How to count the $r$-tuples of subsets of $\{1,\dots,n\}$ that are cyclically disjoint?

I want to count the following, $$\#\{S_1,S_2,\dots, S_r\subseteq[n]\;|\; S_i\cap S_{i+1}=\emptyset \text{ for } 1\leq i\leq r-1 \mbox{ and } S_1\cap S_r=\emptyset\}=A_{n,r},$$ Then $A_{n,1}=2^n$, ...
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 ...
0
votes
1answer
29 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 ...
0
votes
2answers
64 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.
0
votes
0answers
27 views

Simplifying a combinatorial sum

Show that \begin{align} y\sum\limits_{i=1}^dx^iz^i\sum\limits_{j=1}^iq^{i-j}G_d(x,y,q\mid j) = y\sum\limits_{i=1}^d(x^iz^i+\cdots+x^dz^dq^{d-i})G_d(x,y,q\mid i) \end{align} where \begin{align} ...
1
vote
1answer
33 views

Extracting the coefficient of $x^n$ from a fraction

I need help extracting the coefficient of $x^n$ from a $\frac{1-x}{1-2x}$. So far I have that \begin{align} \frac{1-x}{1-2x} &= \frac{1}{1-2x} - x\frac{1}{1-2x}\\ &= \sum\limits_{k=0}(2x)^k ...
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 ...
1
vote
1answer
40 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
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\}$.
0
votes
1answer
45 views

How to calculate the sum of combinatorial numbers

For my work on an almost completely unrelated field I came across the following formula. I know that I have learned that all in high school. But since this is more than 15 years ago in which I never ...
7
votes
6answers
220 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
90 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 ...
0
votes
0answers
59 views

Showing that two sums are equivalent

given \begin{gather} U_d(x,y,q\mid i_1,\ldots,i_k)=\sum\limits_{n,m\geq0}x^ny^m\sum\limits_{\sigma = i_1\ldots i_k\sigma_{k+1}\ldots\sigma_m\in C_{[d]}(n,m)}q^{v(\sigma)}. \end{gather} show ...
1
vote
0answers
42 views

The sum of palindromes from 100 to 900

I'm working with palindromes from $100-999$. I'm having trouble with the step highlighted in red. Can someone explain the algebra to me? Taken from: Discrete and Combinatorial Mathematics: An ...
2
votes
1answer
35 views

What is Vandermonde's formula with multisets?

I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation? Here's the original: $$ ...
2
votes
0answers
73 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
1answer
100 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
3
votes
2answers
31 views

Find value of $n$ with given conditions

The 4-digit positive number $n$'s digit sum is $20$. The sum of the first two digits is $11$, the sum of the first and the last digit as well. The first digit is the last digit $+3$. What is the ...
4
votes
2answers
98 views

How to evaluate the sum $\sum_{k = 0}^{n}2^k {{n}\choose {k}}$ [duplicate]

How do I evaluate the sum: $$\sum_{k = 0}^{n}2^k {{n}\choose {k}}$$ I know that $2^k = {n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3}... {n \choose k}$, but I don't know how to proceed ...
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
4answers
130 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
3answers
36 views

Sum of combination equilvalence

Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
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?