Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

learn more… | top users | synonyms (1)

10
votes
1answer
59 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
2
votes
2answers
82 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 ...
0
votes
0answers
32 views

Binomial-like distribution

Starting with $1$, for $n$ trials multiply by either $1+p$ or $1-p$, with $0 \le p< \le 1$. Does this distribution have a name? What are its properties, such as density (PDF)? It is like a skewed ...
-1
votes
1answer
36 views

Equality involving binomial coefficient

I think the following equality is correct, but I'm not sure, so I'm asking you: $$\left(\prod_{\large\tfrac{n}{2}\,<\,p\,\le\,\tfrac{6n}{7}}p\right)\cdot\left(\prod_{\large ...
0
votes
1answer
46 views

Approximation for a binomial coefficient sequence summation

What is a good approximation to $$\dfrac{{\binom{k}{i}}{\binom{k}{i}}(i-1)!}{\binom{k(k-1)/2}{i}}$$ $$\dfrac{{\binom{k}{i}}{\binom{k}{i}}(i-1)!}{(2^{(\log ...
4
votes
0answers
65 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
0
votes
2answers
77 views

Is there a good approximation for this?

What is a good approximation for $\dfrac{k!}{\binom{k^2}{k}}$ as a function of $k$? Is there a $k_0\in\Bbb N$ such that for all $k\gt k_0$, ...
-1
votes
1answer
43 views

Is there a short expression for this?

Is there a closed form expression for $$\Bigg(\binom{n}{k-1}+\binom{n-1}{k-1}+\dots+\binom{k-1}{k-1}\Bigg)(k-1)!= \sum_{i=0}^{n-k+1}\frac{(n-i)!}{(n-k+1-i)!},$$ ...
4
votes
2answers
95 views

When does this sum of combinatorial coefficients equal zero?

$p>2$ is a prime number, $n\in \mathbb{N}$. Is the following statement true or false? Thanks. $$\sum_{i=0}^{\lfloor n/p\rfloor}(-1)^i {n\choose ip}=0$$ iff $n=(2k-1)p$ for some $k\in \mathbb{N}$.
0
votes
0answers
15 views

Dividors of binomialcoefficient

Is it true, that $ \prod_{\frac{n}{2}<p\le \frac{6n}{7}} $ divides $ \binom{3n}{n} $? Thank you in advance. I have no idea how to prove it.
0
votes
1answer
27 views

Let $f(n)$ be the base-10 logarithm of the sum of the elements of the $n$th row in Pascal's triangle. [on hold]

Let $f(n)$ be the base-$10$ logarithm of the sum of the elements of the $n$-th row in Pascal's triangle. Express $\dfrac{f(n)}{\log 2}$ in terms of $n$. Recall that Pascal's triangle begins $$ ...
1
vote
1answer
43 views

Is it possible to evaluate this binomial sum?

Would it be possible to evaluate this sum? $$\sum_{k=0}^{N/2}k\binom{N+1}{k},$$ where $N$ is even? I know that the sum $$\sum_{k=0}^{N+1}k\binom{N+1}{k}=2^N(N+1)$$ (by ...
3
votes
4answers
53 views

How do i prove that $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \binom{m+n}{k}$ [duplicate]

I have tried the following: Expanding the coefficients and i end up with something like this: $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \frac{m!}{(m-r)!r!} \frac{n!}{(n-k+r)!(k-r)!}$ and then ...
1
vote
0answers
55 views

How prove $\frac{1}{4a b}\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a}\;<\;\dbinom{a(b+1) }{a}\;<\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a} $

Let $a\in\mathbb N$, and $b\in\mathbb R, b\geq 1$ How prove $\frac{1}{4a b}\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a}\;<\;\dbinom{a(b+1) }{a}\;<\;\left[\frac{(b+1)^{b+1}}{b^{b}}\right]^{a} $
1
vote
0answers
69 views

A Summation Challenge

I am trying to understand the solution of problem from its editorial by djdolls' answer,I am not able to understand a particulare step which is as follows: $$S(n)=\sum_0^D (-1)^i \cdot ...
1
vote
0answers
22 views

How to calculate the $k$-dimension of a subspace of a polynomial ring?

Let $k$ be an infinite field and $R:=k[x_1,...,x_n]$ the polynomial ring in $n$ indeterminates. Why is the $k$-dimension of $U$ given by $\begin{pmatrix} n+m-1 \\ m\end{pmatrix}$, when $U$ is the ...
0
votes
0answers
21 views

Sum of series involving factorials [closed]

$$ \sum\limits_{j=0}^{[\frac{n}{l}]}(-1)^{slj}\left( \begin{array}{c} n \\ lj \\ \end{array} \right)^s \frac{x^{kj}}{[(a)_{bj}]^s}, $$ where $l,s,n,k,a,b$ are natural numbers and x is ...
2
votes
2answers
17 views

Generate an integer matrix such that all submatrices are non-singular

I need to generate an $\infty \times N$ integer matrix with a few properties. The top $N$ rows (and $N$ columns) should be the identity matrix. Any square submatrix (meaning the result after ...
0
votes
3answers
46 views

Lower bound for binomial coefficient

Prove that for sufficiently large $ n $ the following inequality holds: $ \binom{5n}{4n}>12^n $. Thank you in advance.
0
votes
1answer
43 views

Evaluating a cube root

How to evaluate $(8.024)^{1/3}$ from $(1+3x)^{1/3}$.I already expand it until $x^3$ but i still can't get the answer. I tried googling for the working using binomial theorem but i failed.
2
votes
3answers
94 views

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$?

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$? I can only manage to see the second inequality, could any one give a hint about the first one?
3
votes
2answers
40 views

Another binomial coefficient sum

In my work I ran across the following binomial coefficient sum: $$ S=\sum_{a=0}^{n-1-l} (-1)^a \binom{n}{l+1+a} \binom{l+a}{l} $$ where $n\geq 0$ and $0\leq l \leq n-1$. I browsed the web and found ...
0
votes
0answers
41 views

Sum involving binomial $\sum_{k=0}^{n} \binom{3n}{3k}$ [duplicate]

The main question is to evaluate: $$\sum_{k=0}^{n} \binom{3n}{3k}$$ There is a standard technique but I cannot split the sums apart and then add them together. Could you help with this step?
4
votes
3answers
225 views

Nested… binomials coefficients? [closed]

Can I have a proof that this number exists? The number: $$\binom{1}{\binom{2}{\binom{3}{\binom{4}{\vdots}}}}$$ If the number exists, then what is the closed form of that number?
0
votes
2answers
33 views

Radius of convergence of complex series

I need help for this exercise: We consider the following sequence of function $(f_n)_{n\ge0}$: $$f_n:\mathbb{C} \rightarrow \mathbb{C}$$ $$z \mapsto \frac{1}{p_n}[z(1-z)]^{4^n}$$ where $p_n$ is the ...
1
vote
3answers
31 views

Switching the order of summations of a certain function

I am looking to switch the order of the summations of the following function: $$ \lambda = -\sum_{c=1}^{n-1} \sum_{k=c}^n {k \choose c} \frac{(-1)^k}{k!} f^{k-c}U(-c,k-2c+1,-f)\phi(n,k) $$ I don't ...
2
votes
0answers
46 views

Finding a closed form for this summation

I have been trying to derive a few identities using some bell polynomials and a technique i have come up with and i came across this summation: $$ \rho(n,k) = \sum_{j=0}^k {k \choose j} {\frac{-j}{2} ...
13
votes
1answer
130 views

“Binomiable” numbers

Is there a nice criterion to determine whether a given natural $m$ can be written as a binomial number $\binom{n}{k}$ with $1 < k < n-1$? I've been thinking on this problem with a friend and ...
0
votes
1answer
18 views

Success rate of a player trying to guess a bitstring with given constriants

For work at my university I try to solve a problem. I have a bit string with given length $len$ and count of active bit $active$ An example could be: 1001 0110 ...
2
votes
0answers
22 views

Prove for $ \forall n \in \mathbb{N}, \exists x,y,z$ ( $0 \leq x < y < z$ ) such that $ n = \binom{x}{1} + \binom{y}{2} + \binom{z}{3}$ [duplicate]

I'm trying to solve a problem from the combinatorics book. Prove or disprove for $ \forall n \in \mathbb{N}, \exists x,y,z \in \mathbb{N} $ ($0 \leq x < y < z$) such that $$ n = \binom{x}{1} + ...
3
votes
1answer
64 views

Let n and k be integers such that $n > k ≥ 0$. Show that ${n\choose k }$+ ${n\choose k + 1 }$ = ${n + 1\choose k + 1 }$

I'm trying to prove it using algebra and it didn't get very far. Here is how far I got. Now I know ${n\choose k } = \frac{n!}{k!(n-k)!}$ So the entire expression would be $$\frac{n!}{k!(n-k)!} + ...
2
votes
2answers
39 views

$\sum_{i=1}^n\frac{1}{i}\binom{n}{i}p^i(1-p)^{n-i}\leq\frac{K}{n} $

How can it be proved that, if $0<p<1$, then $$\sum_{i=1}^n\frac{1}{i}\binom{n}{i}p^i(1-p)^{n-i}\leq\frac{K}{n} $$ for some constant $K$? Thanks in advance for every suggestion.
1
vote
2answers
31 views

Expression for binomial coefficient denominator

I'm trying to find an analytical expression for the denominator of $\pmatrix{-1/2\\k}$ in terms of $k$ when the fraction is fully reduced. E.g., the first several such denominators, starting with ...
0
votes
0answers
33 views

A complicated summation of binomial coefficients

I am trying to evaluate this sum. I think closed form of this sum is not possible, but there might be some bound or approximate result. So far I was unable to find any approximation. Any help will be ...
1
vote
1answer
31 views

How to get value of this binomial coefficient expression?

I am trying to work out an upper bound (big O) of an algorithm I thought of in graph theory field. Basically I have a graph $G=(V,E)$. And a subset of vertices $A=\{a_1,a_2,...,a_k\} ∈ V$ such that ...
1
vote
1answer
52 views

Better closed form for generating function $\sum \binom{n}{2k} x^k$

I have a power series $F_n(x) = \sum_k \binom{n}{2k} x^k$, which has a closed form of $F_n = \frac12 \left((1 + \sqrt{x})^n + (1 - \sqrt{x})^n\right)$. $$\begin{align} (1 + \sqrt{x})^n + (1 - ...
0
votes
0answers
24 views

Proving that binomial coefficients are integers without induction, combinatorics, or formula for exponent of prime

I know of at least three ways to prove that binomial coefficients are integers. One is combinatorial--binomial coefficients count subsets, and thus are integers. Another is inductive, for example ...
7
votes
3answers
148 views

Show that $p \in \left[\frac{4^m}{2\sqrt{m}},\frac{4^m}{\sqrt{2m+1}}\right]$

If the number of ways in which $m$ identical apples can be put in $2m$ boxes, so that no box contains more than one apple, is $p$, prove that $$p \in ...
3
votes
1answer
44 views

Proof for the upper bound and lower bound for binomial coefficients.

I have seen the bounds $\left(\frac{n}{k}\right)^k \leq {n \choose k} \leq \left( \frac{en}{k}\right)^k$ for integers $n \geq k >0$ for the binomial coefficient. I can prove the upper bound in this ...
2
votes
4answers
100 views

A combinatorial proof for $\binom mk$+$\binom m{k-1}$=$\binom {m+1}k$

I do realize that there is a elementary proof of this result which follows from applying the formula $$\binom mk=\frac{m \cdot (m-1) \cdot \ldots \cdot (m-k+1)}{k!}.$$ I do wonder if there is an ...
-2
votes
1answer
44 views

The pascal triangle [closed]

I really dont know what rules to apply to get this answer... but i know the following. I know that $$(a+b)^5$$ a decrease from $5$ to $0$ while $b$ increases .. eg \begin{array}{} ...
4
votes
2answers
37 views

Number of ways to select subsets

In how many ways can two distinct subsets of the set $\text{A}$ of $k$ $(k \geq 3)$ elements be selected so that they have exactly two common elements? I started by choosing two elements (that ...
0
votes
2answers
23 views

Mathematical expressions for binomial coefficient and Pochhammer’s Symbol with negative values

I have two questions regarding the binomial coefficient and Pochhammer’s Symbol when they contain negative value; In the following example $\sum\limits_{k=0}^{-n} \binom{-n}{k} \left(a\right)_{-n}$. ...
5
votes
2answers
120 views

Determine the number of subsets

How many distinct subsets of a set $\text{A}$ are there, containing at least $9$ elements, where the total number of elements in set $\text{A}$ is $18$ ? I've solved it by making cases of either ...
2
votes
3answers
44 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
1
vote
2answers
47 views

Kolmogorov-Zurbenko filter - Calculation of coefficients

I'm currently researching the Kolmogorov-Zurbenko filter and trying to implement it myself as a way to smooth one-dimensional signal strength values. The basic filter per se is pretty easy to ...
3
votes
3answers
196 views

matrix representations and polynomials

I just investigated the following matrix and some of its lower powers: $$M = \left[\begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&1&1&0\\ 1&1&1&1 ...
6
votes
3answers
202 views

Closed form for a binomial series

I am wondering if any knows how to compute a closed form for the following two series. $$\sum_{m=1}^{n}\frac{(-1)^m}{m^2}\binom{2n}{n+m}$$ $$\sum_{m=1}^{n}\frac{(-1)^m}{m^4}\binom{2n}{n+m}$$ ...
0
votes
1answer
42 views

Multiplication of 2 sums that equal another multiplication of 2 sums

I have been trying to prove a formula of mine and i come across something very interesting, well to me it is. If the formula is correct, it states that: $$ \left(\sum_{m=0}^{k-c} {k-c \choose m}{ms_1 ...
0
votes
3answers
87 views

Find the coefficient of $x^9$ in $(1+x)(1+x^2)(1+x^3)\cdots(1+x^{100})$ [closed]

This question had come in jee advanced 2015. Give a hint to solve it.