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
75 views

Summation of binomial coefficients [duplicate]

Is there a closed formula for: $\sum_{i=1}^{N}{\binom{i+k}{i}}$ ( k is a constant whole number )
1
vote
1answer
26 views

$\sum^n_{r=0} (-1)^r C_r(1/2^{r}+3^r/2^{2r}+7^r/2^{3r}+\cdots\infty)$

$$\sum^n_{r=0} (-1)^r C_r(1/2^{r}+3^r/2^{2r}+7^r/2^{3r}+\cdots\infty)$$ is equal to? How to approach this problem?Hints please!!! BTW $C(r)$ stands for $(n)C(r)$
0
votes
2answers
66 views

Bonferroni Inequalities

Let $k$ and $m$ be positive integers with $k>m$. Then the partial sums of $$ 1-\binom{k}{1} + \binom{k}{2} - \cdots (-1)^m\binom{k}{m} $$ has alternating signs. (The partial sums of the ...
4
votes
1answer
121 views

Complex Analysis proof of multinomial expression

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$ A nice complex analysis proof (by Felix Marin, here) follows as: ...
5
votes
2answers
108 views

Which term of the binomial expansion of $\left(1+\sqrt{2}\right)^{50}$ is the greatest?

Which term of the binomial expansion of $\left(1+\sqrt{2}\right)^{50}$ is the greatest? How can I find it, without comparing all 51 values? Is there a quicker way to do it? (The solution says ...
2
votes
2answers
46 views

Prove that $\frac{1}{(1-x)^k}$ is a generating function for $\binom{n-k-1}{k-1}$

On my discrete math lecture there was a fact that: $\frac{1}{(1-x)^k}$ is a generating function for $a_n=\binom{n-k-1}{k-1}$ I'm interested in combinatorial proof of this fact. Is there any simple ...
1
vote
1answer
39 views

binomial identity with negatives

Prove that $$\sum_{k=0}^n(-1)^k\binom{n+1}{k+1}(k+1)^n=0\;.$$ I tried finding a combinatorial interpretation but to no avail. Here is a combinatorial statement, however crappy. Suppose we have $n$ ...
9
votes
1answer
163 views

Interpretation of a combinatorial identity

I am trying to find an combinatorial interpretation for the following combinatorial identity involving iterated binomial coefficients, which appeared in the November 1980 edition of The American Math ...
0
votes
3answers
39 views

Does $^nC_{n+1}$ exist? [duplicate]

is there any value assigned to $^nC_{n+1}$? My teacher wrote it equal to $0$, but what will negative factorial mean? $$^nC_{n+1} = \frac{n!}{(n+1)!\cdot(n-n-1)!} = \frac{n!}{(n+1)!\cdot(-1)!}$$ ...
2
votes
0answers
51 views

Birthday problem, I'm confused by this formula

I've given the following statement (n is given, and equals 100) : Now, I'm quite confused by the second binomial coefficient: how can that represent the days for the birthdays of the remaining 98 ...
2
votes
4answers
66 views

Evaluate $\int_{0}^{1}(1-x)^ndx$ by expanding the bracket.

I'd like to get a hint on this exercise. I believe I'm somewhat close to the answer. I used the binomial theorem to get: $\displaystyle\int_{0}^{1}(1-x)^ndx = \int_{0}^{1}\sum_{k=0}^{n}{n\choose ...
1
vote
1answer
29 views

Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$

Show that for $n \ge 2$, $\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n$ where $r_k = \frac{k^k}{(k-1)^{k-1}}$. This is a generalization of How to prove through induction which asks for a proof ...
3
votes
3answers
38 views

Application of the Binomial Theorem-remainder

I am having a confusion in this question- What is the remainder when $7^{103}$ is divided by 24? I attempted it as follows - It can be written as $(7^2)^{51} \cdot 7$ Which can be written as ...
0
votes
0answers
30 views

How to compute linear recurrence of a sum of binomial-multiplied linear recurrences [duplicate]

I have $$g(n) = \sum_{k=1}^{n} \binom{n}{k}f(k)$$ where $f(k)$ is a large linear recurrence. $g(n)$ is also a linear recurrence as well. Normally, when computing the value of a linear recurrence, I ...
4
votes
1answer
55 views

Simplying linear recurrence sum with binomials

Is there a way to simplify $$\sum_{k=1}^{n} \binom{n}{k}f(k)$$ Where $f(k)$ is a large linear recurrence?
0
votes
0answers
22 views

Coefficients for the falling factorial

Hello fellow mathematicians, I am trying to find a generating function, or at least find some useful property from the coefficients of the falling factorial. Let $(x)_n$ denote a falling factorial, ...
8
votes
4answers
293 views

Orthogonality for Binomial Coefficients

Could somebody explain to me where these two formulas come from as applications of the binomial theorem? $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$ for non-negative integers $r\lt n$. And ...
1
vote
0answers
37 views

Weighted sum of binomial coefficients by powers of lower value.

I am trying to calculate $\sum_{i=0}^n i^K {n \choose i}$ for $K \in \mathbb{N}$. Clearly, the case $K=0$ is trivially $2^n$ by the binomial theorem. For higher $K$ I am stumped. I know I can use: ...
0
votes
0answers
24 views

Binominial Theorem proving

As I was trying to understand the proof of Binomial Theorem by induction, I got stuck at this line. What formulas should be used to get from left to right part? Any explanations and answers ...
0
votes
1answer
20 views

Cofficient of x in a product

How can I efficiently find the coefficient of $x^m$ in the following product - $\prod\limits_{i=1}^{n-1}(1 - p_i + p_ix)$
3
votes
4answers
120 views

Show that $\binom{2n}{n}$ is an even number, for positive integers $n$.

I would appreciate if somebody could help me with the following problem Show by a combinatorial proof that $$\dbinom{2n}{n}$$ is an even number, where $n$ is a positive integer. I ...
1
vote
1answer
50 views

Sum of Some Binomial Terms Equals Zero

Let $q$ and $\ell$ be positive integers. Then the sum $$ \sum_{k=q}^\ell (-1)^{k+q}\binom{k}{q}\binom{\ell}{k} = \left\{\begin{array}{ccc} 1 \mbox{ if } \ell =q\\ 0 \mbox{ if }\ell ...
1
vote
1answer
37 views

Bound on the Beta function

For positive integers x and y, we have that $$ B(x,y) = \frac{\Gamma(x) \Gamma(y)}{\Gamma(x+y)} = \frac{1}{x} \left( \begin{array}{c} x+y-1 \\ x \end{array} \right)^{-1} . $$ However, $$ \left( ...
2
votes
2answers
60 views

Summation over a product of binomial coefficients

Question: I can't figure out why the following equality is true $\sum_\limits{k=a-b-c}^{d} (-1)^k \binom{d}{k}\binom{k+b+c}{a} = (-1)^d \binom{b+c}{a-d} $ How can this be shown? (In the book it just ...
0
votes
0answers
18 views

Stirling or better binomial approximation

Is there a method to find a approximation to $\log_2 \dbinom{n}{n^a}$ with $a\in(0,1)$? Similar to Approximating the logarithm of the binomial coefficient however here argument scales as radical of ...
1
vote
1answer
35 views

Show that $\binom{n}{k}=\frac{1}{2i\pi}\int_{C}\frac{(1+z)^{n}}{z^{k+1}}dz.$

I would like to prove that $$\binom{n}{k}=\frac{1}{2i\pi}\int_{C}\frac{(1+z)^{n}}{z^{k+1}}dz.$$ C is the circle at $0$ with radius $r>0$. I cannot get that expression, if I write the integral as ...
2
votes
2answers
107 views

Why General Leibniz rule and Newton's Binomial are so similar?

The binomial expansion: $$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$ The General Leibniz rule (used as a generalization of the product rule for derivatives): $$(fg)^{(n)} = ...
1
vote
3answers
73 views

Combinatorial proof of $ \sum \limits_{i = 0} ^{m} 2^{n-i} {n \choose i}{m \choose i} = \sum\limits_{i=0}^m {n + m - i \choose m} {n \choose i} $

I've been wondering for a while how to solve (prove) a combinatorial identity, using just combinatorial interpretation: $$ \sum \limits_{i = 0} ^{m} 2^{n-i} {n \choose i}{m \choose i} = ...
1
vote
1answer
42 views

How can find this two sequence recursive relations?

Let $$D_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j-1},E_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j}$$ I want find $D_{n}$ and $E_{n}$ recursive relations, I ...
0
votes
2answers
25 views

Is there limitation when applying binomial theorem?

Problem as title showed. $(a+b)^{-n}$. If $n$ is a positive integer. Can $a$ or $b$ be a complex number? Many thanks in advance.
4
votes
3answers
55 views

Evaluating $\sum_{0\leq k,l \leq n}\binom{n}{k}\binom{k}{l}l(k-l)(n-k)$ algebraically

I'm having problems with the following sum: $$\sum_{0\leq k,l \leq n}\binom{n}{k}\binom{k}{l}l(k-l)(n-k)$$ It's quite easy to think about it combinatorically: We have $n$ balls, we're coloring $k$ ...
1
vote
2answers
32 views

A sum expressed by a Kampe de Feriet function.

Let $a_1$,$a_2$, $a_3$ and $b_1$,$b_2$, $b_3$ be real numbers subject to $1+b_1+b_2 - b_3 > 0 $. By generalizing the result from A sum involving a ratio of two binomial factors. we have shown that ...
0
votes
0answers
45 views

Second question about a limit.

Is the following sequence converge? $$ \lim_{n\rightarrow\infty}\frac{1}{(1+M)^{2n}}\sum_{i=0}^{n}\left( \begin{array}{c} 2n ...
4
votes
2answers
48 views

What is wrong with ${13 \choose 1}{4 \choose 2} \cdot {12 \choose 1}{4 \choose 2}$ as combinations for two pair in poker?

Let's consider two pairs in a 52 cards deck of poker where every person gets five cards. My idea to approach this problem is to take following steps: First pair There are ${4 \choose 2}$ ...
6
votes
2answers
66 views

Binomal theorem show that $\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\dots=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\dots=2^{n-1}$

I'm having some trouble with this question Show that $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\dots=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\dots=2^{n-1}$$ Attempt: Expanding $(1+1)^n=2^n$ ...
1
vote
0answers
28 views

Truncated Binomial Series

Can the truncated binomial series be expressed as a closed form \begin{align} \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{k} x^{k} \end{align}
0
votes
1answer
55 views

Use induction on n for the Binomial Coefficient

Use induction on n to show that the divide and conquer algorithm for the Binomial Coefficient problem computes 2*C(n,k) -1 terms to determine C(n,k). The C(n,k) means "n choose k" I started through ...
0
votes
3answers
29 views

What is the alternating sum of coefficients and what does it have to do with the zeroes of the function?

So, my teacher told us today, while we were solving this integral: $$\int\frac{dx}{x(2x^3+x^2+1)}$$ that the alternating sum of coefficients of $2x^3+x^2+1$ is 0 (2-1+0-1=0) and hence, one zero of the ...
3
votes
1answer
83 views

What is the sum of this infinite series

So the question is - $\displaystyle S = \sum_{n=1}^\infty{\frac{1}{10^n}\left(\begin{matrix}2n\\ n\end{matrix}\right)}$. Find $S$. I tried converting the $n^{th}$ term as a difference of two terms ...
3
votes
4answers
68 views

Equality of sums

How does one show that $$\sum_{j=k}^n\binom{j-1}{k-1}q^{j-k}=\sum_{j=k}^n\binom{n}{j}p^{j-k}q^{n-j},$$ where $p+q=1$? I suppose one needs to substitute $p=1-q$ on the right side and then use the ...
-1
votes
1answer
59 views

Coefficient calculation problem with $x^{50}$

I get a calculation problem, when surprisingly come to this question: $f(x)= \frac {1}{(1+x)(1+x^2)(1+x^4)} $ and try to find the coefficient of $x^{50}$ in $(f(x))^3$ sentence? how this will ...
4
votes
4answers
118 views

What is the story behind ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$? [duplicate]

By exploring the inductive proof from this question I came to the point where I did not understand this step: $${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$ There is a wikipedia article but ...
2
votes
1answer
44 views

Discrete Math Identity Proof Binomial Coefficients

The question is to prove this identity: ! where k, m, n ∈ Z+. Using pascal's identity on the left, so far I have: ! If m is even then they cancel each other and should equal 0. If m is odd then ...
1
vote
1answer
20 views

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime.

Find $v_p\left(\binom{ap}{bp}-\binom{a}{b}\right)$, where $p>a>b>1$ and $p$ odd prime. Here $v_p(k)$ denotes the largest $\alpha\in\mathbb Z_{\ge 0}$ s.t. $p^\alpha\mid k$. We have ...
2
votes
2answers
90 views

Why does $\binom{n}{2} = \frac{n^2 - n }{2}$?

In a proof in Introduction to Algorithms, the book says $\binom{n}{2} \cdot \frac{1}{n^{2}} = \frac{n^2 - n }{2}\cdot \frac{1}{n^{2}}$, which implies $\binom{n}{2} = \frac{n^2 - n }{2}$. Why are ...
0
votes
1answer
65 views

How to simplify $\sum_{i=0}^{2n - d - 1} {n \choose i}$?

Is it possible and how could I simplify this sum into a formula who's quantity of operations is independent of n? $$ \sum_{i=0}^{2n - d - 1} {n \choose i} $$ ...
2
votes
1answer
38 views

Comparing Coefficients in Summations

Suppose I have the following equality: $$\sum_{k=0}^{n-a}\sum_{j=0}^{k}\binom{n}{k}\binom{k}{j}\frac{f(a,k)\cdot g(b,n-k)}{n!}=\sum_{k=0}^{n-a}\binom{n}{k}\binom{n-k}{a}\frac{z^k \cdot ...
1
vote
1answer
47 views

Binomial Coefficients

I want to get ahead in my classes and learn Binomial Theorem ahead of time. What I know so far is that the formula below is the Binomial Coefficient: $\binom n k = \frac {n!} {(n-k)!k!}$ and ...
0
votes
1answer
51 views

Calculate the sum $\sum_{k=0}^{n-1}x^k \binom{n-1}{k} \dfrac{1}{(n-k)!}$.

I want to calculate this sum: $\sum_{k=0}^{n-1}x^k \binom{n-1}{k} \dfrac{1}{(n-k)!}$. I tried to use some differentation techniques, but they didn't work. Could you help me with this?
2
votes
2answers
71 views

Proving if it is prime

I'm quite lost on how to prove things, with the $n \choose k$ and proving. So the question is: Prove that $n \choose k$ is divisible by $n$ if $n$ is a prime number and $1 \le k\le n-1$ Like, how ...