4
votes
3answers
180 views

How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

How to closed the sum $\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$ I'm trying divide two cases $n$ odd and $n$ even. I predict that ...
5
votes
3answers
659 views

Preventing “proof by homework”?

I am doing problem 3d in the Prologue of Spivak: Prove $(a+b)^n = a^n + {n\choose1}a^{n-1}b + {n\choose2}a^{n-2}b^2 + ... + {n\choose n-1}ab^{n-1} + b^n$ I feel like my proof could pass off as ...
4
votes
0answers
76 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
0
votes
1answer
44 views

closed form for $\sum_{k=0}^{n-p}\binom{n}{k}\binom{n}{p+k}$

how to get closed form for $$\sum_{k=0}^{n-p}\binom{n}{k}\binom{n}{p+k}$$ I tried to write binominal in term of gamma function but I got no result what is your suggest to solve the problem ?
2
votes
1answer
74 views

Prove that $\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}={2n+2m+1\choose 4m+1}2^{4m-1}$

Let $n,m$ are positive integers satisfy the condition $n\ge m>0$ Prove that $\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}={2n+2m+1\choose 4m+1}2^{4m-1}$
1
vote
1answer
33 views

Simplifying Sum of Subsets

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum: $$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y ...
5
votes
2answers
97 views

The value of $\binom{50}0\binom{50}1+\binom{50}1\binom{50}2+\dots+\binom{50}{49}\binom{50}{50}$ is

The value of $\binom{50}0\binom{50}1+\binom{50}1\binom{50}2+\dots+\binom{50}{49}\binom{50}{50}$ is? I tried this: ...
1
vote
3answers
64 views

Calculate $\sum_{k=0}^n k \binom{n}{k} p^k (1-p)^{n-k}$

For $p \in [0,1]$ calculate $$S =\sum_{k=0}^n k \binom{n}{k} p^k (1-p)^{n-k}.$$ Since $$ (1-p)^{n-k} = \sum_{j=0}^{n-k} \binom{n-k}{j} (-p)^j, $$ then $$ S =\sum_{k=0}^n \sum_{j=0}^{n-k} k ...
1
vote
3answers
59 views

One Binomial Equation $\sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$ [duplicate]

I saw one proof using this formula: $$ \sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$$ Can anyone help explain it, thank you!
1
vote
1answer
82 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
14
votes
2answers
280 views

How prove this sum $\sum_{n=1}^{\infty}\binom{2n}{n}\frac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}$

show that $$\sum_{n=1}^{\infty}\binom{2n}{n}\dfrac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}=5+4\sqrt{2}\left(\log{\dfrac{2\sqrt{2}}{1+\sqrt{2}}}-1\right)$$ where ...
2
votes
0answers
47 views

How to prove these indentities?

How to prove these indentities? $\displaystyle \sum \limits_{k\geq0} {2n\choose 2k-1}{k-1\choose m-1}=2^{2n-2m+1}{2n-m\choose m-1}$ $\displaystyle \sum \limits_{k=0}^{m} {m\choose k}{n+k\choose ...
2
votes
1answer
33 views

Calculate sum wtih binomial coefficients

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
0
votes
2answers
33 views

How to calculate this sum

How do you calculate this sum $ \sum \limits_{k=1}^{n} \frac{k}{n^k}{n\choose k}$ ?
1
vote
0answers
14 views

Evaluate the summation involving binomials.

$\sum _{ i=0 }^{ 100 }{\binom{k}{i}}*{\binom{M-k}{100-i}*\frac{k-i}{M-100}}/{\binom{M}{100}}$ I wrote the first few terms but couldn't find any pattern and how to club the terms. Help.
0
votes
0answers
24 views

Approximation of sum with binomial summands

I am new here, so hopefully my question will be understood correctly. I have a function (originating from expected untility theory in economics) that looks the following: ...
7
votes
2answers
141 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
3
votes
1answer
123 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 ...
5
votes
1answer
241 views

Are these two binomial sums known? Proven generalization to the Hockey Stick patterns in Pascal's Triangle

English translation. You can see the original - deprecated - in Portuguese here Hi, I arrived at a generalization for the Hockey Stick Patterns, from our beloved Pascal's Triangle. This ...
2
votes
0answers
32 views

Sum of Binomials times Logarithms

Is there a closed-form expression or a very good approximation for $$ \sum_{i=0}^n \binom{n}{i} \log (i+1) \,? $$ If the summands alternate, then there is a very close approximation, yet it feels ...
0
votes
7answers
138 views

Calculating $\binom{1}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
3
votes
2answers
88 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 ?
3
votes
2answers
68 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...
2
votes
0answers
35 views

How to show that $\sum\limits_{k=0}^{\lfloor0.999n\rfloor}\binom{2n}{k} < \binom{2n}{n} $ holds for large n

It seems logical to me since $\binom{2n}{n}$ is in the middle of the row in pascal triangle; therefore, the largest, and for large n the sum adds only the small ones on the left. But I do not have any ...
2
votes
1answer
97 views

A combinatorial identity $\sum_{i=0}^k \binom ni \binom{-n}{k-i} =0$

Can anyone prove the following identity for me? $\sum_{i=0}^k \begin{pmatrix} n\\ i \end{pmatrix} \begin{pmatrix} -n\\ k-i \end{pmatrix}=0$ for any positive integers $n,k$. I'm pretty sure this is ...
1
vote
1answer
62 views

Least common multiple in binomial expansion

If I sum the terms of a binomial expansion, which would be the least common multiple of all the denominators? Say $\displaystyle \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n}$ ...
5
votes
2answers
265 views

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

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
0
votes
1answer
71 views

Can this summation be simplified?

I got something like $$ a_{n} = {1 \over 4^{n + 1}}\sum_{k = 0}^{\left\lfloor n/2\right\rfloor} {n + 1 \choose 2k + 1}\left(-3\right)^{k} $$ Could this be simplified more?
2
votes
0answers
76 views

How to prove this combinatorial identity

I am wondering how to prove the following identity: $$\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}$$ It seems that I can negating the upper index of ${s \choose k-t} ...
3
votes
2answers
85 views

$\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$?

Is it true that $\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$ ? I feel that it is true because if we define $H_1 (x,r)=rx(1+x)^{r-1}$ , and $H_{m+1}(x,r)=x \dfrac d ...
1
vote
2answers
50 views

To provide a combinatorial argument for a combinatorics equality.

Prove that, $${n \choose m}+2{n-1 \choose m}+\ldots+(n-m+1){m \choose m}={n+2 \choose m+2}$$ My work: I thought it would be better to use combinatorial argument than trying to provide a rigorous ...
0
votes
1answer
56 views

Closed form for summation: $\sum\limits_{c_0+c_1+\cdots+c_n = n \atop c_n = n-i}\prod\limits_{j=0}^n{j \choose c_j}$

I am looking for a closed form for this expression: $f(n, i) = \sum\limits_{c_0+c_1+\cdots+c_n = n \atop c_n = n-i}\prod\limits_{j=0}^n{j \choose c_j}$ With the condition that $\sum\limits_{k=0}^n ...
1
vote
4answers
160 views

Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$.

I need to find calculate the sum Calculate sum $\sum\limits_{k=0}k^2{{n}\choose{k}}3^{2k}$. Simple algebra lead to this ...
0
votes
4answers
78 views

$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}=?$

I was asked to find a closed formula for the sum $$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}$$ could anyone give me an advice on how to get started?
0
votes
0answers
12 views

A multiple sum involving binomial coefficients.

Let $q\ge 1$ and $0 < a < b$ be integers and $\vec{p}:= \left(p_l\right)_{l=1}^q$ be a vector of real numbers. The question is to find the following sum. \begin{equation} {\mathfrak ...
2
votes
2answers
38 views

Is it true that $\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3} = \binom{n}{3}\binom{n-3}{k-3}$?

I was asked to find a closed formula for $$\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3}$$ To remove the $\sum$ if you will. Here's my reasoning, let's say we have a football team with $n$ players. First we ...
10
votes
2answers
234 views

Show that $\displaystyle\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
2answers
37 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
0
votes
1answer
62 views

Compute a sum involving binomial coefficients

Let $0 < a < b$ and $p_1 >0$ and $p_2>0$ be integers. The question is to prove the following identity: \begin{equation} \sum\limits_{j=a}^b \left(\begin{array}{c} j \\ p_1 \end{array} ...
4
votes
2answers
234 views

maybe this sum have approximation $\sum_{k=0}^{n}\binom{n}{k}^3\approx\frac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty$

prove or disprove this $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$ this problem is from when Find this limit ...
4
votes
2answers
82 views

Show $\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$

As the title says... We are asked to show that $$\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$$ I tried with induction, but that seems to never work with these kind of questions. We need ...
1
vote
2answers
120 views

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

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
3
votes
1answer
80 views

Sum of fraction of factorials

Can anybody explain this? $$\sum\limits_{k=1}^{\frac{m-1}2}\frac{(2k)!(2m-2k)!}{(2k-1)(2m-2k-1)k!^2(m-k)!^2}=\frac{(2m)!}{(2 m-1)m!^2}$$ I did actually simplify this to: ...
1
vote
0answers
45 views

Increasing fraction of sum of binomial coeffients

Let $n$ be a positive integer. Show that the quantity $$ \displaystyle \frac{ \displaystyle \sum_{i=1}^n { n+k \choose i-1 } }{ \displaystyle \sum_{i=1}^n { n+k+1 \choose i } } $$ is ...
1
vote
1answer
56 views

Binomial coefficient manipulation

Can somebody explain why this is true? $$\sum_{k=1}^n \binom{k}{m}\frac 1k=\sum_{k=m}^n \binom{k}{m}\frac 1k$$ This manipulation is a part of an exercise, but I'm stuck at here.
3
votes
2answers
71 views

$2^n=C_0+C_1+\dots+C_n$

Could anyone give me hints for this one? $2^n=C_0+C_1+\dots+C_n$ Thats all I can say and I know tricks like integrating or differentiating both side and then put $x=1$ or what ever we need. but ...
3
votes
1answer
186 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} &= ...
2
votes
2answers
149 views

Use induction and Newton's binomial formula to show that $\binom{n}{0}+\binom{n}{1}+\cdot+\binom{n}{n}=2^n, \forall n\in \mathbb N$ [duplicate]

Use induction and Newton's binomial formula to show that: $ i)$ $ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n, \forall n\in \mathbb N$ $ ii)$ ...
2
votes
0answers
174 views

How to calculate this triple summation?

I need to calculate the following summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m-j}\choose{k-j}}}{k\choose j}r^{k-j+i}$$ I do not know if it is a well-known summation or not. ...
3
votes
1answer
98 views

How to prove that $\sum_{i=0}^{a}\frac{i\binom{a+b-c-i}{a-i}\binom{c+i-1}{i}}{\binom{a+b-1}{a}}=\frac{ac(a+b)}{b(b+1)}$

let $$b\ge c,a,b,c\in N^{+}$$ Show that $$\sum_{i=0}^{a}\dfrac{i\binom{a+b-c-i}{a-i}\binom{c+i-1}{i}}{\binom{a+b-1}{a}}=\dfrac{ac(a+b)}{b(b+1)}$$ This sum is similar to Hypergeometric distribution, ...