All Questions
32
questions
2
votes
0
answers
114
views
Proof identities (i)$\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\frac{2^{n+1}-1}{n+1}$ and (ii) $\sum_{k=0}^{m}\binom{n+k}{k}=\binom{n+m+1}{n+1}$
I'm really having trouble with this assignment. You have to prove the following identities for $m, n ∈ \mathbb{N}$ including $0$.
(i)$\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\frac{2^{n+1}-1}{n+1}$
(ii)...
- 21
1
vote
1
answer
114
views
Derivation for identities involving Stirling Numbers and Binomial Coefficients
Looking for a combinatorial derivation of the identities:
$${n\brack l+m} {l+m\choose l}
= \sum_k {k\brack l} {n-k\brack m} {n\choose k}$$
&
$${n\brace l+m} {l+m\choose l}
= \sum_k {k\brace l} {n-...
- 133
0
votes
0
answers
20
views
Proving pCr is divisible by p where p is prime and 1 ≤ r ≤p-1 by induction [duplicate]
There is solution of this problem. But i am trying to prove this by using induction and here is my try.
Initial step: The statement is true for r=1, as $\binom{p}{r}=\binom{p}{1}=p$.
Induction step:...
- 587
3
votes
0
answers
75
views
Binomial Coefficients Proof [duplicate]
I want to prove the claim that for all $n\geq 1,$ we have
$${n\choose r} > {n\choose r+1}$$ if and only if
$$n-1 \geq r > \frac{1}{2}(n-1).$$
Assume first that $${n\choose r} > {n\choose r+1}....
- 310
0
votes
1
answer
117
views
Prove that $\sum_{k=0}^{n-1}\frac{n-k}{n}{2n \choose k}=\frac{1}{2}{2n \choose n}$
I have tried splitting this sum into $$\sum_{k=0}^{n-1}\frac{n-k}{n}{2n \choose k}=\sum_{k=0}^{n-1}{2n \choose k}-\frac{1}{n}\sum_{k=0}^{n-1}k{2n \choose k}=\frac{2^{2n}-{2n \choose n}}{2}-\frac{1}{n}\...
- 33
3
votes
1
answer
129
views
Compute the sum $\sum_{k=0}^{n} (-1)^k \binom{n}{k}^3$
I have to calculate $\sum_{k=0}^{n} (-1)^k \binom{n}{k}^3$. I proved that for odd $n$ this sum equals to $0$ ($\binom{n}{k}$ and $\binom{n}{n-k}$ cancel each other out), but I have no idea how to ...
- 582
1
vote
1
answer
82
views
definition of stirling numbers
Here is a definition without partition about Stirling numbers of second kind.
"Let $S(n,k)$ be Stirling numbers of second kind.
$1 \leq k \leq n$, and let $k$ and $n$ be positive integers. Let $h(...
- 421
1
vote
2
answers
136
views
Upper bound for sum of binomials $\sum_{k=0}^{d}{N-1\choose k}$
I am interested to find a proof for the following upper bound.
$$\sum_{k=0}^{d}\begin{pmatrix}N-1\\k\end{pmatrix} \leq \frac{2N^d}{d!}$$
for $N\geq 3d$. I have tried to bound the sum by $(d+1)$ times ...
- 99
2
votes
3
answers
765
views
Hockey Stick Identity Summation Proof
I'm working on a math problem that asks us to prove the following: $$ \text{For all $j,n \in \mathbb{N},$} \sum_{k=0}^n {k \choose j}(n-k) = {{n+1}\choose{j+2}} $$
It is a spinoff of the hockey stick ...
- 21
2
votes
4
answers
885
views
Proving $ \sum _{k=0} ^m \binom nk \binom{n-k}{m-k} = 2^m \binom {n}{m}$.
Give an algebraic and a combinatorial proof for the following identity:
$$ \sum _{k=0} ^m \binom nk \binom{n-k}{m-k} = 2^m \binom {n}{m}.$$
For the combinatorial argument, use the analogy ...
- 115
1
vote
1
answer
137
views
Stirling Numbers of first kind $s(n,k)$
Stirling Numbers, $s(n,k)$ are defined as the permutation of $[n]$={$1,2,...,n$} of having $k$ cycles,
why is it/how can you prove $s(n,1)=(n-1)!$ and $s(n,n)=1$
and
$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,...
- 327
9
votes
1
answer
1k
views
Catalan numbers - algebraic proof of the recurrence relation
I would like to prove following recursive relation for the Catalan numbers:
$$\tag{1}
C_0=1,\quad C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}\text{, for }n\ge 1
$$
without combinatoric arguments, only ...
- 748
1
vote
1
answer
55
views
Proof $C_h = \binom{2^h-2}{2^{h-1}-1} C_{h-1}^2$ can be written non-recursively as $C_h = \frac{(2^h-1)!}{\prod_{k=1}^h (2^k-1)^{2^{h-k}}}. $
I have to proof A056972 by induction. It says that the recurrence relation.
$$
C_h = \binom{2^h-2
}{2^{h-1}-1} C_{h-1}^2.
$$
Can be expressed as
$$
C_h = \frac{(2^h-1)!}{\prod_{k=1}^h (2^k-1)^{2^{h-...
- 1,311
5
votes
2
answers
398
views
Proof $\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$ where $f_n$ is the n-th Fibonacci-number
In our combinatorics script it is written, that
$$\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$$ where $f_n$ is the n-th Fibonacci-number.
Apparently this can be proven through the generating function ...
- 307
1
vote
5
answers
1k
views
Proof of $\sum_{k=0}^m \binom{n}{k}(-1)^k = (-1)^m \binom{n-1}{m}$ for $n > m \geq 0$
Let $n > m \geq 0$ be integers.
How can one prove the following equation?
$$\sum_{k=0}^m \binom{n}{k}(-1)^k = (-1)^m \binom{n-1}{m}$$
According to our script we have to use the following: $(X \...
- 307