Questions tagged [binomial-coefficients]
Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.
2
votes
0answers
20 views
Explanation of the Wolstenholme theorem proof
I recently came accross the Wolstenholme theorem which says that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod {p^{3}}$$
On wikipedia, it gives a combinatorial proof of this theorem that involves ...
1
vote
4answers
53 views
Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$
Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
1
vote
4answers
65 views
What is the coefficient of $x^{11}$ in $(3x-9)^{19}$?
I am currently studying for finals, and I do not know how to do this problem from my study guide. I have tried to watch a few YouTube videos and I know that I will end up with $3x^{11} \times (-9)^8$, ...
1
vote
2answers
36 views
sum of $\sum^{n}_{k=0}(-1)^k\cdot \frac{\binom{n}{k}}{\binom{k+3}{k}}$
Finding sum of $\displaystyle \sum^{n}_{k=0}(-1)^k\cdot \frac{\binom{n}{k}}{\binom{k+3}{k}}$
Try: Using
$$\int^{1}_{0}x^m\cdot (1-x)^ndx = \frac{m!\cdot n!}{(m+n+1)!}=\frac{1}{(m+n+1)\binom{m+n}{n}}...
-1
votes
1answer
15 views
Let n belongs to +ve integer and $(1+x+x^2)^n=\sum_{r=0}^{2n} {a_rx^r}$ prove that: $a_r=a_{0<r<2n}$
Let n belongs to +ve integer and $$(1+x+x^2)^n=\sum_{r=0}^{2n} {a_rx^r}$$ prove that: $$a_r=a_{2n-1},{0<r<2n}$$ as well as prove that $$\sum_{r=0}^{ n-1} a_r=\frac{1}{2}(3^n-a_n)$$. I tried to ...
4
votes
0answers
35 views
Root of a plynomial in (0,1)
Define $$f_K(x)=\sum_{i=K+1}^{2K} \binom{2K}{i}x^{i-1}(1-x)^{2K-i}.$$ How to show that $qf_K(x)-f_K(1-x)$ has exactly one real root in $(0,1)$ for any $q > 0$ and $K \geq 1$. The proof for $q=1$ ...
21
votes
2answers
2k views
A simple finite combinatorial sum I found, that seems to work, would have good reasons to work, but I can't find in the literature.
I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors ...
1
vote
3answers
56 views
value of $k$ in binomial expression
If $\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{4}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k.$ Then $k$ is
Iam trying to simplify it
$\displaystyle \...
0
votes
0answers
19 views
Proof Ideas - Strong Induction, Pascal's Triangle and Fibonacci Numbers
I'm looking for attributes/characteristics/properties to prove about Pascal's Triangle or the Fibonacci numbers. Preferably something that requires a strong induction proof that is on the same level ...
2
votes
4answers
47 views
Prove that $(1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2$ when $0\leq x\leq 1$ and $n\geq2$
Reading a book I saw this inequality
$$
(1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2
$$
when $0\leq x\leq 1$ and following the author it descended from the inclusion-exclusion principle. I don't understand ...
0
votes
2answers
38 views
Proving that $\sum_{k=0}^n{(-1)^k\over k+1}\binom{n}{k}={1\over n+1}$
I would like if possible to have a proof of yet another theorem of Binomial Coefficients. This time it is $$\sum_{k=0}^n{(-1)^k\over k+1}\binom{n}{k}={1\over n+1}$$
This arises in a proof of the ...
1
vote
0answers
60 views
Proof of a Binomial expression summation
Let $x,y$ be probabilities and $n$ is some integer. Show that:
$\displaystyle \sum_{n_0=1}^n \sum_{m=0}^{min(n_0-1,n-n_0-1)} \binom{n_0-1}{m}\binom{n-n_0-1}{m}x^m(1-x)^{n_0-m-1}y^m(1-y)^{n-n_0-m-1} ...
3
votes
2answers
76 views
identities and binomial coefficients
I'm having some problems proving this identity. I tried using some formulas I found on the internet so I can turn that $2$ base number into something else but i'm not really sure how to do that. I ...
1
vote
2answers
36 views
Proof of Identity to Zero of the Sum of a Product of Binomial Coefficients & Pochhammer Numbers
It's well-know that the sum across an entire row of binomial coefficients (of degree, say, $n$) with alternating signs attached is 0; and it can easily be proven by demonstrating that it is the ...
-2
votes
2answers
36 views
A proving question based on binomial theorem [closed]
$$C_0-C1(a-1)(b-1)(c-1)_+C_2(a-2)(b-2)(c-2)+.... (-1)^nC_n(a-n)(b-n)(c-n) $$=0 I tried to solve this problem by using multinomial theorem but was not able to proceed further please help me out.
0
votes
5answers
79 views
Prove that if $\binom{n}{k}$ = $\binom{n}{k+1}$, then $n$ must be odd [closed]
Prove that if $\displaystyle\binom{n}{k}$ = $\displaystyle\binom{n}{k+1}$, then $n$ must be odd.
I am having problems with manipulating factorials and just can't seem to get the grasp on how to ...
-1
votes
0answers
14 views
A proving question based on binomial theorem and complex numbers [closed]
Prove that:
$$C_1+C_4+C_7+...=\frac{1}{3}(2^n-\cos\frac{n\pi}{3}+\sin\frac{n\pi}{3})$$ I try to solve this problem by taking a general equation $(1+x)^n$ and putting the value of $x$ as $w$ and using ...
-2
votes
0answers
26 views
Is $\sum_{r=1}^n (-1)^{n-r}\binom{n}{r}r^n$ equivalent to the factorial function, for whole numbers? [duplicate]
$$\sum_{r=1}^n (-1)^{n-r}\binom{n}{r}r^n$$
Can someone help prove or disprove whether the above series sum is equivalent to the factorial function, for whole numbers?
original formula image
-1
votes
1answer
47 views
Question based on binomial theorem and complex numbers. [closed]
Prove that $$C_1+C_5+ C_9+... =\frac{1}{2}\bigg(2^{n-1}+2^{n/2}\sin\frac{n\pi}{4}\bigg)$$
Here $C_i$ denotes the binomial coefficient $\binom ni$.
I tried to solve this problem by using de Moivre's ...
2
votes
3answers
68 views
Derive $\sum_{s=r}^{\infty} \binom{m}{s} \binom{s}{r}(-1)^s=0 $ using an identity $(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$
To prove:
$$\sum_{s=r}^{\infty}\binom{m}{s} \binom{s}{r}(-1)^s=0 $$
Use the identity: $$(1 + x)^
m (1 + x)^{
-(r+1)} = (1 + x)^{
m-r-1}$$
I have trouble understanding the hint, could somebody ...
0
votes
1answer
19 views
Proof number-partitions $P_n = \sum_{k=1}^{n} P_{n,k}$ in positive summands
Let $n \in \mathbb{N}$. Let $P_n$ be the number of number-partitions of $n$ in positive summands, i.e. $$P_n = \sum_{k=1}^{n} P_{n,k}$$
How can one prove the following?
The amount of number-...
0
votes
2answers
54 views
One term of (2π+5)^n = 288000π^8, what's n?
Without using calculator what's the value of n?
Using binomial expansion I get:
nCp * 2n-p * πn-p * 5p = 288000π8
Easily I know that n-p=8, by the π's power
Then the power of 2 is also 8, so I can ...
0
votes
2answers
43 views
Counting paths through a checkers board (only moving diagonally)
a) Imagine that a checker is placed in the bottom right corner of a 6 by 6 checker board. The piece mmay be moved one square at a time diagonally left or right to the next row up. Calculate the number ...
1
vote
2answers
62 views
Weighted sum of product of binomial coefficients
I am trying to evaluate the sum
$\displaystyle \sum_{n=1}^N \sum_{k=1}^n k\binom{n}{k} \binom{N-n}{k}x^k$,
Here $x$ is some positive real
My approach so far has been to first to compute the ...
0
votes
1answer
48 views
Show there are $2^n$ forms a $n \times n$ matrix can take, preferably via Pascal's triangle
Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is ...
7
votes
2answers
102 views
Is there a closed form for the sum of the cubes of the binomial coefficients?
We know that
$$
\sum_{k=0}^n \binom{n}{k} = 2^n\;\; \text{ and }\;\;
\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}
$$
hold for all $n\in \mathbb{N}_0$.
Now I tried to find a similar expression for
$$
\...
0
votes
2answers
34 views
Is it possible to show
As part of a larger proof I need the following to be true in order to make it work,
$(a+1){b\choose a+1}x^{a+1}(1-x)^{b-a-1}=a{b\choose a}x^a(1-x)^{b-a}$
Can anyone give me a hand?
3
votes
4answers
52 views
Factorial Proof - ${n \choose r-1}+{n \choose r}={n+1 \choose r}$
${n \choose r-1}+{n \choose r}={n+1 \choose r}$
So what I tried to do was expand the first and second term.
$\frac{n!}{(r-1)!(n+1-r)!}+\frac{n!}{(r)!(n-r)!}$
Then what I did was try to get common ...
-1
votes
1answer
71 views
Given that the coefficients of the $6^{th}$ term and $16^{th}$ term in the Expansion of $(x + y) ^n$ are equal. Find the value of $n$. [closed]
The Expansion gives me: $6^{th}$ term = $\displaystyle\binom{n}{5} x^{n-5}y^5$ and
$16^{th}$ term = $\displaystyle\binom{n}{15} x^{n-15}y^{15}$. What do I do next?
2
votes
5answers
63 views
How to show that $2^n > n$ without induction
I'm solving exercises about Pascal's triangle and Binomial theorem, and this problem showed up, however I don't have any clue on how to solve it
The sum of ${n\choose p}$ from $p=0$ to $n$ is the ...
5
votes
2answers
73 views
Showing $\sum\limits_{j=0}^M \frac{M \choose j}{N+M \choose j} = \frac{N+M+1}{N+1}$
In an answer to another question, I stated $$\sum\limits_{j=0}^M \frac{M \choose j}{N+M \choose j} = \frac{N+M+1}{N+1}.$$
It is clearly true when $N=0$ since you add up $M+1$ copies of $1$, and when $...
1
vote
2answers
76 views
Does there exist a similar identity to $\binom{n}{k} = \binom{n}{n-k}$?
I know that $$\binom{n}{k} = \binom{n}{n-k}$$
My question is does there exist a similar identity where you change the top of the choose function, o any similar to the identity above?
An example: Can ...
1
vote
1answer
58 views
General method to find sum of binomial
Specifically I want to ask the method to solve
$$\sum_{k=0}^n \binom{4n+b}{4k};\ b=[0,1,2,3]$$
And how to solve series of type
$$\sum_{k=0}^n \binom{an+b}{ak};\ a=[1,2,3,...],\ b=[0,1,2,...,a-1]$$
0
votes
2answers
42 views
Find $\sum_{n=0}^\infty \frac{\sum_{r=0}^n \frac{n!}{(n-r)!\ r!}}{n!}$.
Find the value of $$\sum_{n=0}^\infty \frac{\sum_{r=0}^n \frac{n!}{(n-r)!\ r!}}{n!}.$$
I don't understand how to apply summation to the term that's obtained after simplifying by dividing with $n$ ...
0
votes
1answer
30 views
Serge Lang - Basic Mathematics - Sum of Binomial coefficients p.387 ex. 9
I can not understand the solution.How does the second step come about? How does the expression in brackets appear?
solution image
0
votes
1answer
27 views
How does it follow from the Pascal's Triangle that binomial coefficient are integers
So I was reading this lemma which states:
Let $m,n$ be natural numbers such that $1 \leq m \leq n$. Then
\begin{equation*}
{n\choose m-1} + {n\choose m} = {n+1\choose m}.
\end{equation*}
It follows ...
0
votes
1answer
35 views
Binomial coefficient from a double sequence $\{a_{n,k}\}$ of Pascal Triangle
I really need help with the 13-th prob. Chap. 2 in the book Kuratowski "Introduction to Calculus", it says:
We consider the following table (i.e. double sequence $\{a_{n,k}\}$):
\begin{array}{cccccc}...
2
votes
6answers
74 views
${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$
In a proof, the author states that it is clear that:
Given $x\geq 1$ and $ n-x \geq 1$ and finally also $n\geq 2$
$${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$$
This is not immediately clear ...
4
votes
5answers
1k views
Binomial Theorem with Three Terms
$(x^2 + 2 + \frac{1}{x} )^7$
Find the coefficient of $x^8$
Ive tried to combine the $x$ terms and then use the general term of the binomial theorem twice but this does seem to be working.
Does ...
1
vote
3answers
38 views
Probability that Santa will give $N$ different presents to exactly $N-1$ kids
Santa is randomly giving $N$ different presents to $N$ different kids.
what is the probability that Samuel doesn't get a present?
what is the probability that every kid got a present?
what is the ...
2
votes
1answer
71 views
A mod 2 binomial identity
I would like to show the following identity: for all $n, q \geq 0$,
$$\sum_k \binom{2k}{4k-2n} \binom{n+3q}{2k+2q+1} \equiv \binom{n+3q}{2q-1} \pmod{2}.$$
This has been computer-tested for all $n, ...
0
votes
1answer
32 views
Calculating $\sum_{k=0}^{\lfloor \frac{p}{2} \rfloor} \binom{p}{k}$
I'm trying to find the value of: $$\sum_{k=0}^{\left \lfloor \frac{p}{2} \right \rfloor} \binom{p}{k}$$ For even and odd $p$, the indication I was given suggests writing it as $$\frac{1}{2}\left (\...
1
vote
3answers
49 views
Calculate $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$
Calculate $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$, I do not know hot get rid of that $k$, for me it is similar like $\binom{n}{k}=\frac{k}{n} \binom{n-1}{k-1}$, do you have some idea?
1
vote
4answers
39 views
Prove that $\binom{n}{1}^2+2\binom{n}{2}^2+\cdots +n\binom{n}{n}^2=n\binom{2n-1}{n-1}$
Prove that
$$
\binom{n}{1}^2+2\binom{n}{2}^2+\cdots + n\binom{n}{n}^2
= n \binom{2n-1}{n-1}.
$$
So
$$
\sum_{k=1}^n k \binom{n}{k}^2
= \sum_{k=1}^n k \binom{n}{k}\binom{n}{k}
= \sum_{k=1}^n n \binom{...
1
vote
1answer
20 views
Limiting sum of binomial coefficients multiplied by powers
I want to prove that:
$$\lim_{n \rightarrow \infty} \sum_{k=1}^m {m \choose k} \Big( \frac{k}{m} \Big)^n = 1.$$
My progress so far: Define the function $F(x) \equiv (1+x)^m$ and the operator $\tilde{...
1
vote
0answers
39 views
Series involving squares of binomial coefficients
Does anyone know if this sum has a closed form formula ?
$$\sum_{0 \leq k \leq n} \binom{n}{k}^2 x^k\\
n\in N$$
1
vote
1answer
35 views
Explanation for binomial sums $\sum_{n=0}^{\infty} \binom{-4}{n-1} (-1)^{n-1} x^n = \sum_{n=0}^{\infty} \binom{-4}{n} (-1) x^{n+1}$
I was looking at some negative binomial coefficient problems and I stumbled upon this explanation
$$\sum_{n=0}^{\infty} \binom{n+2}{3} x^n = \sum_{n=0}^{\infty} \binom{n+2}{n-1} x^n= \sum_{n=0}^{\...
1
vote
1answer
34 views
Sum involving squares of binomial coefficients
Find the sum of $\sum_{r=1}^{n}r(^nC_r)^2$.
I am attempting it as follows
$(1+x)^n=C_0+xC_1+x^2C_2+x^3C_3+⋯+x^nC_n$.
On differentiating we get following relation
$n(1+x)^{n−1}=\sum_{r=1}^n rx^{r−1}...
3
votes
1answer
101 views
How to expand product of $n$ factors.
I have a product say
\begin{equation}
F(a,n,x) = \prod _{j=0}^{n}(1-{a}^{n-2\,j}x)
\end{equation}
I want to expand and hope to have general terms of the coefficients. I did for $n= 2,3,4,5,6,7,8...$ ...
0
votes
2answers
35 views
Solving for $n$
$$\binom{n}{0}+\binom{n}{1}+\binom{n}{2} = 22$$
I'm trying to solve this equation for $n$.
If
$$\binom{n}{0} = 1$$
Then we have that
$$1+\binom{n}{1}+\binom{n}{2} = 22 \implies \binom{n}{1}+\...
