All Questions
48
questions
0
votes
3
answers
88
views
Evaluate using combinatorial argument or otherwise :$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$
Evaluate using combinatorial argument or otherwise $$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}\left(j\binom{n}{i}+i\binom{n}{j}\right)$$
My Attempt
By plugging in values of $i=0,1,2,3$ I could observe that ...
- 9,599
3
votes
4
answers
163
views
Proving $\sum_{i=0}^n (-1)^i\binom{n}{i}\binom{m+i}{m}=(-1)^n\binom{m}{m-n}$
I am trying to prove the following binomial identity:
$$\sum_{i=0}^n (-1)^i\binom{n}{i}\binom{m+i}{m}=(-1)^n\binom{m}{m-n}$$
My idea was to use the identity
$$\binom{m}{m-n}=\binom{m}{n}=\sum_{i=0}^n(-...
- 87
4
votes
3
answers
121
views
Show $\sum_{i=0}^n{i\frac{{n \choose i}i!n(2n-1-i)!}{(2n)!}}=\frac{n}{n+1}$
How can this identity be proved?
$$\sum_{i=0}^n{i\frac{{n \choose i}i!n(2n-1-i)!}{(2n)!}}=\frac{n}{n+1}$$
I encountered this summation in a probability problem, which I was able to solve using ...
user1253495
0
votes
0
answers
52
views
How can I prove that $ \sum_{k=1}^{n}\frac{k\cdot P(n,k)}{n^{k+1}} = 1$? [duplicate]
The answer is difficult to me, I cannot figure out how to compute it.
$\sum_{k=1}^{n}\frac{k\cdot P(n,k)}{n^{k+1}}=1$
If someone can explain some technique to do it, I'd appreciate it. I tried to ...
- 1
0
votes
1
answer
51
views
Simplifying Expressions involving Sigma
After reviweing the solutions to a question involving the Biomial Theorem, I arrived at a step, where i was unsure how it occured.
Specifically, i was confused about the logic of:
k=0 -> k=1
n-1 -&...
0
votes
1
answer
77
views
find the smallest possible value of m so that there are real numbers $b_j$ satisfying $f_9(n) = \sum_{j=1}^m b_j f_9(n-j)$ for $n>m$
For an integer n, let $f_9(n)$ denote the number of positive integers $d\leq 9$ dividing n. Suppose $m$ is a positive integer and $b_1,b_2,\cdots, b_m$ are real numbers so that $f_9(n) = \sum_{j=1}^m ...
- 2,031
0
votes
2
answers
56
views
Rewriting $\sum_{{i,j=0}\:\:i\ne j}^n \binom{n}{i}\:\:\binom{n}{j}$ [duplicate]
Solve $$\sum_{{i,j=0}\:\:i\ne j}^n \binom{n}{i}\:\:\binom{n}{j}$$ This was a contest math problem which I was not able to solve.
My work: I was very unsure about how to approach this question. In my ...
- 860
1
vote
3
answers
177
views
calculate :$2000 \choose 2000$+....+$2000 \choose 8 $+$2000 \choose 5$+$2000 \choose 2$
my attempt:
let's put $2000 \choose 2000$+...+$2000 \choose 1001 $+...+$2000 \choose 8 $+$2000 \choose 5$+$2000 \choose 2$=$A+B$
with $A$=$2000 \choose 2000$+...+$2000 \choose 1001 $
and
$B$=$2000 \...
user1069990
4
votes
3
answers
760
views
Probability you end dice rolling sequence with 1-2-3 and odd total number of rolls
Here's a question from the AIME competition:
Misha rolls a standard, fair six-sided die until she rolls 1-2-3 in that order on three consecutive rolls. The probability that she will roll the die an ...
- 1,415
2
votes
1
answer
403
views
Simplifying the alternating sum of n squares
This question is based on a curious problem from Donald Knuth's The Art of Computer Programming, exercise 7 to chapter 1.2.1. It's stated as the following:
Formulate and prove by induction a rule for ...
- 848
2
votes
0
answers
78
views
value of $\frac{\sum_{k=0}^r{n\choose k}{n-2k\choose r-k}}{\sum_{k=r}^n {n\choose k}{2k\choose 2r} {(\frac{3}{4})}^{(n-k)}({\frac{1}{2}})^{2k-2r}}$ .
The question requires us to find the value of $\frac{\sum_{k=0}^r{n\choose k}{n-2k\choose r-k}}{\sum_{k=r}^n
{n\choose k}{2k\choose 2r} {\left(\frac{3}{4}\right)}^{(n-k)}\left({\frac{1}{2}}\right)^{...
- 97
3
votes
2
answers
67
views
Is this combinatorics summation equality true?
Recently I came upon the following equality, for natural numbers $n,k$ such that $n\ge k\ge0$:
$$\binom nk=\sum_{m=0}^{\min(k,n-k)}\binom km\binom{n-k}m$$
First of all, is this equality even true? It ...
- 2,846
2
votes
0
answers
60
views
Finding a formula for a sum that involves binomial coefficients
Is there a formula for this sum:
$$ \sum_{j=0}^k {n \choose j} {n \choose k-j} (-2)^j \left(-\frac13 \right)^{k-j} ?$$
It reminds me to Vandermonde's identity; but as you can see there is a slight ...
- 897
1
vote
2
answers
75
views
Finding a nice solution to $\sum_{a,b,c\ge 1, a+b+c=9}\frac{9!}{a!b!c!}=18150$
I am trying to find a nice way to solve for
$$\sum_{a,b,c\ge 1, a+b+c=9}\frac{9!}{a!b!c!}=18150$$
I managed to solved it (and verified by computer) by doing manually (on paper) on $7$ cases and got a ...
- 13
1
vote
3
answers
338
views
Question involving the sum $\sum_{k=0}^n(-1)^k\binom nk^2$
I've been tasked to prove the following equation is true:
$$\sum_{k=0}^n(-1)^k\binom nk^2=\begin{cases}0&\text{if }n\ \text{is odd}\\\displaystyle(-1)^m\binom{2m}m&\text{if }n=2m,m\in\mathbb ...
- 2,846
4
votes
2
answers
151
views
Choosing one of each letter from a string of repeated "ABCD"s such that it is in order of "ABCD"
Question: Given a string of letters with $n$ repeated "ABCD"s (ABCDABCD...ABCD n times), how many ways are there to choose one 'A', one 'B', one 'C' and one 'D' such that when the chosen letters are ...
- 546
0
votes
1
answer
146
views
Proving that $\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{{n \choose 2k}\cdot 3^{n-2k}}=2^{n-1}(2^n+1) $
Prove that $$\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{{n \choose 2k}\cdot 3^{n-2k}}=2^{n-1}(2^n+1)\,.$$
Can somebody help me prove this identity?
- 43
3
votes
1
answer
432
views
Find the sum $S=\sum\limits_{k=1}^{n} {4k-1 \choose k}$
Find the sum $S=\sum\limits_{k=1}^{n} {4k-1 \choose k}$
I tried using the Pascal's identity to get $S=\sum\limits_{k=1}^{n} {4k \choose k}-{4k-1 \choose k-1}$ ,but it is not really telescopic.
Any ...
user321656
0
votes
2
answers
51
views
How can I use $\sum_{j=0}^{\infty} z^j=\frac{1}{1-z}$ to find a closed form expression for $\sum_{j=0}^{\infty} jz^j$?
How can I use $\sum_{j=0}^{\infty} z^j=\frac{1}{1-z}$ to find a closed form expression for $\sum_{j=0}^{\infty} jz^j$?
I have shown $\sum_{j=0}^{\infty} z^j$ by considering $S(z)=\sum_{j=0}^{\infty} ...
- 12.1k
2
votes
1
answer
327
views
Expansion Using Multinomial Theorem
I was hoping someone could help me find an analytic expression for the $x^{2k}$ term of
$$\bigg(\frac{\sin{x}}{x}\bigg)^{2g-2} = \big(1-\frac{x^{2}}{3!} + \frac{x^{4}}{5!} + \ldots\big)^{2g-2}$$
...
- 2,563
5
votes
2
answers
396
views
Finite sum with inverse binomial
I am looking for a closed-form for this summation:
$\sum_{b=1}^q\frac{b}{{q\choose b}}$
I looked at tables (Prudnikov-Brychkov book) of binomial sums but I couldn't find the result. WolpramAlpha ...
- 141
3
votes
0
answers
287
views
$f(8) \geq 1$ and $f(n)\geq 2f(\lceil \frac n2-n^{2/3} \rceil)$. Can we deduce $\exists C>0: f(cn) \geq n$?
Let $f : \Bbb N \to \Bbb N$ be a nondecreasing function that satisfies $f(8) \geq 1$ and $f(n)\geq 2f(\lceil \frac n2-n^{2/3} \rceil)$. Can we deduce that there exists some positive constant $c$ such ...
- 929
1
vote
0
answers
64
views
Equality of sums of sequences [duplicate]
We have two sequences $(a_n)$ and $(b_n)$, of positive integers, such that, $1\leq a_1,...,a_m\leq n$, $1\leq b_1,...,b_n\leq m$ prove that there exist $p\leq q$, $r\leq s$ such that,
$$\sum_{i=p}^{q} ...
- 5,719
0
votes
2
answers
130
views
Combinatorics on numbers.
Find the integer $n$ which has the following property: If the numbers from $1$ to $n$ are all written down in decimal notation the total number of digit written down is $1998$. What is the next higher ...
- 3,381
2
votes
2
answers
2k
views
Find the sum $\sum_{n=2}^{\infty} \frac{\binom n2}{4^n} ~~=~~ \frac{\binom 22}{16}+\frac{\binom 32}{64}+\frac{\binom 42}{256}+\cdots$.
The sum
$$\sum_{n=2}^{\infty} \frac{\binom n2}{4^n} ~~=~~ \frac{\binom 22}{16}+\frac{\binom 32}{64}+\frac{\binom 42}{256}+\cdots$$
has a finite value. Use what you know about generating functions to ...
- 1,221
1
vote
1
answer
664
views
Find the value of n if:
$$\sum_{k=0}^n (k^{2}+k+1) k! = (2007).2007!$$
How to approach this problem? In need of ideas. Thank you.
- 105
-2
votes
6
answers
247
views
Simplify $\binom nr+ 4\binom n{r+1} + 6\binom n{r+2} + 4\binom n{r+3}+\binom n{r+4}$ [closed]
For $$4\le r \le n,$$
$${n \choose r}+4{n \choose {r+1}}+6{n \choose {r+2}}+4{n \choose {r+3}}+{n \choose {r+4}}$$ equals
1. $${n+4}\choose{r+4}$$
2.$${n+4}\choose{r}$$
3.$${n+3}\choose{r-1}$$
4.$${n+...
- 105
7
votes
1
answer
1k
views
Roots of unity filter, identity involving $\sum_{k \ge 0} \binom{n}{3k}$
How do I see that$$\sum_{k \ge 0} \binom{n}{3k} = (1 + 1)^n + (\omega + 1)^n + (\omega^2 + 1)^n,$$where $\omega = \text{exp}\left({2\over3}\pi i\right)$? What is the underlying intuition behind this ...
- 1,072
3
votes
1
answer
301
views
Kronecker Delta Equal to a Certain Summation
I have been trying to proof this equation $$\sum_{i\le s\le j} \frac{(-1)^{s-i}}{(s-i)!(j-s)!}=\delta_{ij}$$ for all $i$,$j$ natural, $i \le j$, where $\delta_{ij}$ is the Kronecker delta.
For $i=j$...
- 452
24
votes
5
answers
687
views
What is $\sum_{r=0}^n \frac{(-1)^r}{\binom{n}{r}}$?
Find a closed form expression for $$\sum_{r=0}^n \dfrac{(-1)^r}{\dbinom{n}{r}}$$
where $n$ is an even positive integer.
I tried using binomial identities, but since the binomial coefficient is in the ...
user196761
6
votes
3
answers
750
views
Algebraic proof that $\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$
I'm looking for an algebraic proof of this identity for $n, k \in \mathbb{N}$:
$$\sum\limits_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}$$
So far, I've turned the left hand side of the equality into ...
- 163
4
votes
1
answer
2k
views
Confused between cyclic sum and symmetric sums.
four variables $a, b, c, d$ are given, what is the symmetric and cyclic sum?
I thought:
$$\sum_{cyc} ab = ab + ac + ad + bc + bd + cd$$
And
$$\sum_{sym} ab = 2(ab + ac + ad + bc + bd + ...
- 11.2k
2
votes
2
answers
174
views
How to show that $ \sum_{i=0}^n\binom{n}{i}(-1)^i\frac{1}{m+i+1}=\frac{n!m!}{(n+m+1)!} $
How would one show that
$$
\sum_{i=0}^n\binom{n}{i}(-1)^i\frac{1}{m+i+1}=\frac{n!m!}{(n+m+1)!} ?
$$
Any hint would be appreciated.
Note: I tried to recognize some known formula, but since I don't ...
- 4,198
1
vote
2
answers
136
views
Question about Binomial Sums [duplicate]
Prove that for any $a \in \mathbb{R}$
$$\sum_{k=0}^n (-1)^{k}\binom{n}{k}(a-k)^{n}=n!$$
I rewrote the sum as
$$\sum_{k=0}^n \left((-1)^{k}\binom{n}{k} \sum_{i=0}^n (-1)^{i}a^{n-i} k^{i} \right)$$
...
- 5,719
9
votes
1
answer
15k
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 identity:$$\binom{n}{k}=\binom{n}{n-...
- 99
5
votes
1
answer
218
views
An inverse binomial summation.
I am looking for a closed form for this summation:
$$
\sum_{j=1}^m\frac{r^{-j}}{j{m\choose j}} = \sum_{j=1}^m\frac{r^{-j}}{m{m-1\choose j-1}} = \frac1{rm} \sum_{k=0}^{m-1}\frac{r^{-k}}{{m-1\choose k}}
...
- 1,221
1
vote
1
answer
127
views
On $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$ [duplicate]
How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $ n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)
- 8,387
4
votes
2
answers
569
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 ...
- 1,221
9
votes
3
answers
2k
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.
(...
- 1,221
5
votes
2
answers
2k
views
Sum of derangements and binomial coefficients
I'm trying to find the closed form for the following formula
$$\sum_{i=0}^n {n \choose i} D(i)$$
where $D(i)$ is the number of derangement for $i$ elements. A derangement is a permutation in which ...
- 129
5
votes
2
answers
150
views
Sum of series ${n\choose 2a}{a\choose 0}+ {n\choose {2a+2}}{{a+1}\choose 1} + {n\choose {2a+4}}{{a+2}\choose 2} + \ldots$
I wanted to check the rationality of the cosine function for some rational multiples of $\pi$. And I found out that, $\cos(n \cdot\arccos x)$ generates a polynomial in $x$ whose co-efficients have the ...
- 2,264
7
votes
1
answer
239
views
Closed-form expression for $\sum_{n=1}^{k} (-1)^{n+1}n^2(n^2-1)\binom{2k}{k-n}$?
Wolframalpha tells me that
$$\sum_{n=1}^{k} (-1)^{n+1}n^2(n^2-1)\binom{2k}{k-n}=0$$ for $k>2$
However I have not been able to come up with a proof and I simply don't see how to do it. Does anyone ...
user63566
4
votes
5
answers
467
views
Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem?
Can this identity be derived from the binomial theorem?
$$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$$
I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it by ...
- 1,302
3
votes
1
answer
223
views
Factorial Identity - True or False?
Let $x$ and $y$ be positive integers.
Then, is
\begin{align}
\frac{x^{xy}}{(xy)!} = \sum_{k_1+...+k_x = xy} \frac{1}{(k_1)!...(k_x)!}
\end{align}
true, where $k_1$, ..., $k_x$ are all positive ...
- 680
3
votes
2
answers
301
views
Simplify $\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$
I am trying to simplify an expression involving summation as follows:
$$\sum_{i=0}^{n-1} { {2n}\choose{i}}\cdot x^i$$
where $n$ is an integer, and $x$ is a positive real number.
At a first glance,...
- 1,027
0
votes
9
answers
6k
views
Prove $3^n = \sum_{k=0}^n \binom {n} {k} 2^k$
Let $n$ be a nonnegative integer. Prove that
\begin{align}
3^n = \sum_{k=0}^n \dbinom{n}{k} 2^k .
\end{align}
I know that $2^n = \sum\limits_{k=0}^n \dbinom{n}{k}$, but how to integrate the $2^k$ ...
- 19
10
votes
2
answers
4k
views
How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?
This sum is difficult. How can I compute it, without using calculus?
$$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$
If someone can explain some technique to do it, I'd appreciate it.
Or advice ...
- 3,563
24
votes
5
answers
10k
views
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$
I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
- 15.5k