All Questions
12
questions
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
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
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
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
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
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
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
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
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
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
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
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