All Questions
65
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
0
votes
0
answers
41
views
Induction involving binomial coefficients ${n \choose k}$
Why, many times, in problems involving binomial coefficients, ${n \choose k}$, that we need induction to prove something, we use induction on $k$ instead on $n$. Since $n$ limits $k$, it seems strange ...
- 369
0
votes
1
answer
91
views
Closed form for $\sum_{k=0}^{j}\binom{n}{k}^2 x^k$
I need a closed form for the sum $$\sum_{k=0}^{j}\binom{n}{k}^2 x^k$$ where $0<x<1$
Let $y=x^{1/2}$. The above expression can be rewritten as
$$\int_0^{1 } \left(\sum_{k=0}^j \binom{n}{k}y^k e^{...
- 910
3
votes
1
answer
125
views
prove a fibonomial identity
For all $n\ge 1$, why do there exist integers $a_{i,n}$, $0\le i\le n+1$, not all zero, so that $$a_{0,n} (F_k)^n + a_{1,n} (F_{k-1})^n +\cdots + a_{n,n} (F_{k-n})^n+a_{n+1,n}(F_{k-n-1})^n = 0$$ for ...
- 1,837
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
2
votes
1
answer
104
views
Identity involving q-Pochhammer symbols -- "Normalization"
I am trying to prove the following identity involving q-Pochhammer symbols
$$ \sum_{m=0}^{n} \dfrac{1}{(c^{-1};c^{-1})_m (c;c)_{n-m}}=1$$
where $n\in \mathbb{N}$, $c\in \mathbb{R}$ and $(a;q)_n=\prod_{...
2
votes
1
answer
100
views
Proving $ \frac{(n!)^2}{n(2n)!}\sum_{k=0}^n k {n \choose k} ^2=\frac{1}{2} $ by induction [duplicate]
I'm struggling to prove the following by induction for $n\geq 1$
$$
\frac{(n!)^2}{n(2n)!}\sum_{k=0}^n k {n \choose k} ^2=\frac{1}{2}
$$
The base case works but trying to prove for $n+1$ is proving ...
- 115
1
vote
1
answer
97
views
$S_{n}$ is the sum of every third element in the $n$th row of the Pascal triangle, beginning on the left with the second element. Find $S_{100}$.
Problem:
Let $S_{n}$ be the sum of every third element in the $n$th row of the Pascal triangle, beginning on the left with the second element. Find the value of $S_{100}$.
My work:
For brevity, I ...
- 680
1
vote
1
answer
60
views
A proof for stirling numbers of the second kind... [closed]
So my Prof give me this Statement to proof and i have no idea how i could solve it tho.
$$S(k,n)=S(k−1,n−1) + n \cdot S(k−1,n)$$
My task is to prove it and as hint he said:
Use The binomial ...
- 11
1
vote
1
answer
56
views
proving an inequality based on double products and binomial
Iv been trying to prove the following inequality: let $a_1,\ldots,a_n$ be a non-increasing sequence, i.e., $a_1\geq a_2\geq \cdots \geq a_n\geq 0$ such that $\sum_i a_i=m$. Then, prove that
$$\prod_{i=...
- 413
0
votes
2
answers
63
views
A different upper bound for the binomial coefficient
I need to prove the following statement:
If $3\leq k < t$ then
\begin{equation*}
\binom{t}{k} < 2^{t-1}-k+1.
\end{equation*}
I was given the hint to prove it by induction over $t$ with $k$ ...
- 113
0
votes
0
answers
58
views
Show that $\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n$ [duplicate]
I am trying to show that $$\sum_{k=0}^n 2^{-k}{k+n \choose k}=2^n.$$
I try $n=0$:
$$
\sum_{k=0}^0 2^{-k}{k+n \choose k}=2^0{0 \choose 0}=1=2^0,
$$
and $n=1$:
$$
\sum_{k=0}^1 2^{-k}{k+n \choose k}=1+ 2^...
- 3,187
1
vote
3
answers
62
views
Show that $\sum_{k=0}^{n} \binom{n}{k} ka^k = an(a+1)^{n-1}$
Problem:
Show that $\sum_{k=0}^{N} \binom{N}{k} ka^k = aN(a+1)^{N-1}$
Attempt:
I tried using induction but got stuck.
$N=0$ implies $\sum_{k=0}^{0} \binom{0}{k} ka^k = 0$
$N=1$ implies $\sum_{k=0}^{1} ...
- 1,419
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
1
vote
1
answer
54
views
Does applying the coefficients of one row of Pascal's triangle to adjacent entries of a later row always yield an entry in the triangle?
I was wondering how to prove that in general, if I take any row of Pascal's triangle and apply all of the coefficients of that row to adjacent entries of a later row, you'll get an entry in Pascal's ...
- 1,166