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)

0
votes
1answer
23 views

$X_n = \sqrt[k]{n^{p}+an^{q}+1}-\sqrt[k]{n^{p}+bn^{q}+1} $

For what given p and q below sequence is bounded? $X_n = \sqrt[k]{n^{p}+an^{q}+1}-\sqrt[k]{n^{p}+bn^{q}+1} $ where $0\leq q<p$ and $a\ne b$ My try ...
2
votes
4answers
37 views

Find the value of $ \sum _{r=0} ^{2n} r ( ^{2n}C _r) ( \frac 1{r+2} ) $

Find the value of $$ \sum _{r=0} ^{2n} r ( ^{2n}C _r ) ( \frac 1{r+2} )$$ In order to solve this I am trying to make the term(s) of the series independent of $r$. However I'm unable to solve ...
3
votes
3answers
75 views

A combinatorial identity: $\sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $

I proved this combinatorial identity while doing some linear algebra. For any positive integer $k$, $$ \sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $$ I was wondering what ...
3
votes
0answers
123 views

Sum problem involving Factorials

got the following problem to prove for $n \in \mathbb{N}$ and $1 \leq i \leq n$: \begin{equation} \sum_{k=1}^{n-i} \frac{(2n-1-i-2k)! 2^{2k}}{(n-i-k)! (n-k)! 2}=\sum_{k=1}^{n-i} \frac{(2n-1-i-k)! ...
1
vote
1answer
126 views

Need help finding a closed form for complicated sum

I'm trying to find a closed form expression for the following sequence: $$a_n=\sum_{i=1}^{n}\frac{(n-1-i+d)!}{(n-2i)!(i)!}=\sum_{i=1}^{\frac{n}{2}}\frac{(n-1-i+d)!}{(n-2i)!(i)!}$$ Where $n$ and $d$ ...
2
votes
2answers
91 views

Binomial coefficients identity: $\sum i \binom{n-i}{k-1}=\binom{n+1}{k+1}$

I am trying to prove $ \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}=\binom{n+1}{k+1} $ Whichever numbers for $k,n$ I try, the terms equal, but when I try to use induction by n, I fail to prove the ...
3
votes
0answers
26 views

An inequality concerning non-negative integer matrices with constant row and column sums

I'd appreciate any suggestions for how to prove (or disprove) the inequality described below. Some notation first: for positive integers $k$ and $M$, let ${\mathcal D}_{k,M}$ denote the set of all $k ...
1
vote
0answers
138 views

Sum concerning Catalan triangle and binomials

I am trying to prove the following relation. For $k \in \mathbb{N},k \geq 2$ and $i=1,\ldots,k-1$ \begin{equation} {2k-2-i \choose k-1-i}=\sum \limits_{l=0}^{k-1-i} 2^{2l} T(k-2-l,k-1-i-l)-2 \sum ...
3
votes
4answers
110 views

Closed form for a formula with a summation over $i\binom{n-i}{k-1}$, and combinatorial proof?

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end. $$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i ...
1
vote
2answers
58 views

Using Binomial coefficient to solve a problem with unfair coins

I have 5 fair coins and 10 unfair coins in a bag. For the unfair coins, there is 80% chance of getting a head and 20% for tails. What's the probability of flipping 4 heads out of 6 flips? Each flip is ...
5
votes
1answer
80 views

Inequality with sum of Binomial coefficients.

Prove that for every positive integer $n \ge 2$$$\sum^n_{k=1}k \sqrt{\begin{pmatrix}n\\ k\end{pmatrix}}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
2
votes
1answer
99 views

Evaluate $\sum_{k=1}^{n} (2k-1){n \choose k}$ using calculus

Evaluate $\sum_{k=1}^{n} (2k-1) {n \choose k} $ using calculus I found out the value by the following method: $$T_r= (2r-1) {n\choose r}$$ $$S_r= \sum^n _{r=1} \left(2r {n\choose r} - {n\choose ...
1
vote
1answer
34 views

Inequality involving binomial coefficients

I recently stumbled upon an inequality involving binomial coefficients. There is reason to suspect that it holds for all $l\in\mathbb{N}$. It states that $$ (2l+1)^{2l+1} < \sum_{m = 0}^{l} ...
1
vote
0answers
30 views

Maximizing expected value when distribution is binomial

Consider the following problem: $$\max_{n\in\mathbb N}\;f(n)= \frac12 \left[v_0 \sum_{i=\lceil k_n \rceil}^n \binom{n}{i}p^i (1-p)^{n-i} + v_1\sum_{i=1}^{\lfloor k_n ...
10
votes
1answer
424 views

New Year Combinatorics

In the spirit of the festive period and in appreciation of the encouraging response to my X'mas Combinatorics problem posted recently, here's one for the New Year! Express the following as a ...
5
votes
1answer
51 views

Sum of squares of Binom(n,p) values

Let $x_{n,p}(j)$ be the probability that a random variable distributed according to a binomial distribution with parameters $n \in \mathbf{N}_+$ and $p \in (0,1)$ takes the value $j \in ...
0
votes
0answers
33 views

Closed form equation with binomial coefficients

I need a closed form for the sum $\sum\limits_{i=0}^{\infty}{n-iT-1 \choose i}x^i$ $n$, $T$ are constants and positive but may not be integers. However, they can take nearest integer values, if not ...
3
votes
1answer
60 views

Do these ratios of the Eulerian number triangle converge to the logarithm of x?

Consider the matrix $A_3$ with the definition if $n=k$ then $A_3(n,k)=\binom{n-1}{k-1}=1$, else if $n\ge k$ then $A_3(n,k)=\frac{\binom{n-1}{k-1}}{1-x}$ else $A_3(n,k)=0$. $\binom{n-1}{k-1}$ means the ...
8
votes
2answers
117 views

Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem. I have $n$ items that I can place on $m$ positions. $m$ ...
1
vote
1answer
54 views

The limit of an infinite product involving the squares of $\binom{n}{j}x^j(1-x)^{n-j}/k$

Some months ago, me and a friend tried to solve the following $"~natural~"$ question: Given weights $p_{1},\ldots,p_{m}$ and distinct points in $S_{0} := \left\{\, x_{1},\ldots,x_{n}\,\right\}$ of ...
2
votes
0answers
54 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
12
votes
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
0
votes
2answers
44 views

How $(r-k){r \choose r-k}$ becomes $r{r-1 \choose r-k-1}$?

I'm reading Knuth/Graham/Patashnik's Concrete Mathematics: I don't understand how he goes from $(r-k){r \choose r-k}$ to $r{r-1 \choose r-k-1}$ using $(5.6)$. The mentioned property has a $k$ ...
7
votes
1answer
98 views

Is $(n+\ell)^{-1}\binom{kn}{n}$ an integer for only $(\ell,k)=(1,2)$?

Find all pairs $(\ell,k)$ of natural numbers, such that the number $\dfrac1{n+\ell}\dbinom{kn}{n}$ is an integer for all natural $n$. Is $(\ell,k)=(1,2)$ the only solution?
2
votes
1answer
52 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that ${-1\choose 0}=1$?

I'm trying to use the binomial coefficient: $$\binom{x}k=\begin{cases} \frac{x^{\underline k}}{k!},&\text{if }k\ge 0\\\\ 0,&\text{if }k<0\;, \end{cases}$$ To check that ${-1\choose 0}=1$. ...
1
vote
1answer
35 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that $ {-n \choose -n}=0$?

I am trying to use this definition of the binomial coefficient: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-[k-1])}{k(k-1)(k-2)\cdots 1}$$ To ...
1
vote
1answer
70 views

Why $ {-1\choose 3}=-1$?

Having the following definition: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}\tag{1}$$ Why $\bbox[1px,border:1px ...
0
votes
2answers
59 views

Sum of binomial coefficients $\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$

$$\sum _{ x=r-2 }^{ n-2 } \binom{x}{r-2}$$ I can't find the sum of the following series. I would appreciate if anyone can show me this problem's solution.
6
votes
2answers
72 views

Is there a “counting groups/committees” proof for the identity $\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$?

This is exercise number $57$ in Hugh Gordon's Discrete Probability. For $n \in \mathbb{N}$, show that $$\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$$ My algebraic solution: ...
4
votes
4answers
157 views

Combinatoric proof for $\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$ ($n\geqslant5$)

I'm trying to proove the following: $For\space every\space n \ge 5$: $$\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$$ I've tried cancelling one $(n-k)$, and got this: ...
27
votes
1answer
984 views

X'mas Combinatorics

Inspired the various** algebraic X'mas greetings sent to me over the festive period, I thought I would try to devise one of my own. $$\Large ...
5
votes
6answers
135 views

How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

When trying to answer this question I arrived at $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ After using Wolfram Alpha to ...
1
vote
3answers
52 views

If a word appears with probability $0.05$, how many words are needed so that it appears with probability $0.99$?

Probability of a specific word appearing in a language is $0.05$. How many words must there be in a text, so that the word appears at least once with a probability of $0.99$? My understanding is ...
1
vote
3answers
155 views

What is the value of $\sum_{n=0}^{\infty}(-\frac{1}{8})^n\binom{2n}{n}$

What is the value of $$\sum_{n=0}^{\infty}\left(-\frac{1}{8}\right)^n\binom{2n}{n}\;?$$ EDIT I bumped into this series when inserting $\overrightarrow{r_1}=\left(\begin{array} ...
3
votes
1answer
66 views

Good approximation for $\binom{N}{\frac{N}{2}}$

$$\log_2\binom{N}{\frac{N}{2}}\approx N\log_2N - 2(N-\frac{N}{2})\log_2(N-\frac{N}{2})=N\log_2N - 2\frac{N}{2}\log_2(\frac{N}{2})$$ $$=N\log_2N - {N}{}\log_2({N}) + {N}{}=N$$ ...
6
votes
1answer
56 views

An identity involving partial fractions decompositions

In Vladimir A. Smirnov's book Analytic Tools for Feynman Integrals (page 38), the following identity is suggested to perform partial fractions decompositions $$ \begin{split} ...
3
votes
0answers
62 views

Asymptotics of integer compositions

A (weak) composition of a positive integer $n$ into $k$ parts is an ordered sequence of nonnegative integers $(a_1, a_2, \ldots, a_k)$ such that $ \sum_{i=1}^k a_i = n $. I am interested in the case ...
0
votes
1answer
23 views

expressing canonical base of univariate polynomials in binomial base

Two bases are fairly standard for ${\mathbb Q}[X]$ : the canonical base $(X^j)_{j\geq 0}$ and the binomial base $(b_j(X))_{j\geq 0}$ where $b_j(X)=\binom{X}{j}=\frac{X(X-1)\ldots (X-(j-1))}{j!}$ (thus ...
2
votes
2answers
103 views

Binomial theorem.

I first saw this thing (admittedly much to late in life) in a third year class entitled non-linear dynamics and chaos theory. There if i am remembering correctly we used to look for non-zero terms to ...
0
votes
4answers
118 views

How to prove that the sum of squared binomials equals $\binom{2n}{n}$ [duplicate]

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem ...
0
votes
2answers
30 views

Congruence with binomial

I tried to prove this by induction on $k$. But I did not manage Let $p$ be a prime. For every $k\in\{0,\cdots,p-1\}$, one has $$\binom{p-1}k\equiv(-1)^k\pmod p.$$ By Wilson theorem, it suffices to ...
-2
votes
0answers
93 views

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this : [duplicate]

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
-3
votes
3answers
150 views

Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of [closed]

If $k, m, n$, are natural numbers and $k \leq n$ What is: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
2
votes
2answers
44 views

If given $\sum_{r=1}^{m-1}\binom r3$, how does the summation evaluate when $n<r$ in $\binom nr$?

Correct me if I'm running the summation correctly - $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\sum_{r=2}^{m-1}\binom r3$$ $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\binom 23+\sum_{r=3}^{m-1}\binom r3$$ ...
11
votes
1answer
123 views

How find all postive integer number such $(n+k)\nmid \binom{2n}{n}$

Question: Find the all integer $k$,such there are exist infinitely many $n$ such $$(n+k)\nmid \binom{2n}{n}$$ This is china 2014 (CMO problem 4),it's have been end exam three hours ago. I ...
6
votes
1answer
157 views

How to transform the product to sum?

I just wonder that how to prove that $$ \prod_{m=1}^{n}\Big(x-2\cos\frac{m\pi}{n+1}\Big)=\sum_{k=0}^{[n/2]}(-1)^{k}\binom{n-k}{k}x^{n-2k}. $$ Similarly, how to transform the product $$ ...
0
votes
1answer
56 views

Can this binomial summation be simplified?

I got something like $\displaystyle\sum_{i=0}^K{ \binom{n+i}{i} \cdot \alpha^i} $ where $n,\ K,\ \alpha$ are definite values, $\binom{n+i}{i}$ is the Combinatorial number that choose $i$ from ...
3
votes
3answers
244 views

Is there a closed-form formula for sum of “odd combinations”? [closed]

So, I was trying to come with a formula for the sum of below series: ${2^n \choose 1}+{2^n \choose 3}+...+{2^n \choose 2^n - 1}$ Thank you.
1
vote
1answer
23 views

What can you conclude about the first moment of a variable given the 3rd moment exists and is finite

Suppose you are given a random variable $X$ and told that $E[X^3]$ exists and finite. Can you conclude that $E[X]$ exists and is finite? What about $E[X^2]$? How would you argue rigorously whether ...
6
votes
4answers
1k views

Probability that given a 1000 page book with 1000 misprints, a page will have 3 misprints.

Setting A book of 1000 pages contains 1000 misprints. Estimate the chances that a given page contains at least three misprints. Solution My solution is ...