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)

3
votes
1answer
27 views

Show by committee selection argument

First post in Stack Exchange and feel bad to be in need of help. But, I'm having a hard time understanding this one or rather showing the argument. $\binom{n}{k} = \binom{n-2}{k-2} + ...
0
votes
2answers
52 views

What is the combinatorial interpretation of the product of binomial coefficients?

Full disclosure: This question is relating to a homework question. It's not a homework question itself, but rather a clarifying question to help myself get a handle on the actual question. Suppose I ...
5
votes
5answers
132 views

Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $

I need any hint with calculating of the sum $$ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}. $$ Maple give the strange unsimplified result $$ I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( ...
0
votes
1answer
37 views

Sum of products of binomial coefficients is equal to another binomial coefficient [duplicate]

Need help in proving (by induction or by combinatorics) the following statement Is it possible to do it by induction? there are 3 veriables and I think I cannot easily do it by induction. Correct? ...
3
votes
1answer
103 views

Combinatorial Analysis: Fermat's Combinatorial Identity

I was looking through practice questions and need some guidance/assistance in Fermat's combinatorial identity. I read through this on the stack exchange, but the question was modified in the latest ...
1
vote
2answers
56 views

Sum of Binomial Coefficient products

I am trying to prove that $$\sum\limits_{y=0}^d \frac{{2x \choose y} {2d-2x \choose d-y} }{2d \choose d} = x $$ So far, I have tried using induction on $d$ but I am having trouble using the ...
3
votes
1answer
52 views

Prove combination identity

$ \sum_{k=0}^n {2k \choose k} {2n-2k \choose n-k} = 4^n $ I tried with mathematical induction only to fail. Is this formula related to some special function like Beta, Gamma, etc?
0
votes
2answers
41 views

Probability for a 'pair' to occur when rolling 5 dice

5 fair dice are rolled. A pair is defined to be any number that shows up twice, while the rest of the dice show different numbers (to the number on the pair and to each other). I am looking for the ...
1
vote
2answers
48 views

Gosper's Identity $\sum_{k=0}^n{n+k\choose k}[x^{n+1}(1-x)^k+(1-x)^{n+1}x^k]=1 $

The page on Binomial Sums in Wolfram Mathworld http://mathworld.wolfram.com/BinomialSums.html (Equation 69) gives this neat-looking identity due to Gosper (1972): $$\sum_{k=0}^n{n+k\choose ...
0
votes
1answer
32 views

binominal inequality - checking

I have to show that $\displaystyle \binom{n}{k}<\binom{n}{l}$ for $\displaystyle 0 \le k <l \le\frac{n}{2}$ where $n,k,l$ are an integers. I think I solved it but I'm not sure if my approach is ...
9
votes
4answers
168 views

Inequality $\binom{2n}{n}\leq 4^n$

I would like to prove the following inequality, for $n=0,1,2,...$, $$ \binom{2n}{n}\leq 4^n.$$ I already proved it by induction, and I'm looking for another proof.
5
votes
1answer
68 views

Proving that $\sum_{i = 0}^{m}{\binom{k+i}{i} \binom{n-i}{m-i}} = \binom{n+k+1}{m}$

Goal: prove that $\displaystyle\sum_{i = 0}^{m}{\binom{k+i}{i} \binom{n-i}{m-i}} = \binom{n+k+1}{m}$ How to give a combinatorial argument, i.e. counting in two ways, for this problem? I tried by ...
0
votes
0answers
22 views

Transformation of a sum

I want to prove the following or a similar result: For $1\le k \le n$ \begin{align}&1-\sum\limits_{j=k+1}^n\binom nj(1-x)^jx^{n-j}~~~~~~(1)\\ ...
1
vote
1answer
28 views

Function related to Harmonic numbers, the Pascal triangle, Logarithmic integral and the Polylogarithm.

What function satisfies the following: Let the matrix: $$\displaystyle T = \left(\begin{matrix} 1&0&0&0&0&0&0&\cdots \\ 1&1&0&0&0&0&0 \\ ...
4
votes
4answers
102 views

Solve for $n$, where $n$ is a positive integer

I have $$ {n \choose 2} = 21 $$ and as the title mentions I have to solve for $n$, but so far all I have managed to get to is $$n^2 -n =42 $$ and from there I'm completely lost. Any hints would ...
3
votes
3answers
69 views

Show that $ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $?

I can't resolve this exercise and I need a tip. $$ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $$ where $ n \geq s $.
1
vote
1answer
46 views

Finding the coefficient of $x^{46}$ in an expression

In this problem, I found that the answer is the coefficient of $x^{46}$ in $\left(\displaystyle\sum_{r=0}^{3} x^r \right)^6\left(\displaystyle\sum_{r=0}^{8} x^r \right)^4$ Is there possibly a way to ...
1
vote
3answers
58 views

Find $a_1$ given that $(1+x)^{100} = \sum_{i=0}^{100} a_ix^i$

If $(1+x)^{100} = \sum_{i=0}^{100} a_ix^i$, then $a_1$ is .. The options are $1$, $2$, $99$ or $100$. I'm sure the problem is trivial, but I just don't understand what is meant.
5
votes
2answers
92 views

Challenge: How to prove this identity between bi- and trinomial coefficients?

This question is the continuation of its predecessor. Using the convention that trinomial coefficients $$ \binom{n}{k_1,k_2,k_3}=\frac{n!}{k_1! k_2! k_3!} $$ are zero if $k_i<0$ or $\sum_i k_i\neq ...
2
votes
0answers
33 views

Evaluate $ \sum\limits_{j \in \mathbb{Z}_{\geq 0}} {n \choose r+kj}$ where $n,k$ are fixed

Is there a general way/technique to evaluate $ \sum\limits_{j \in \mathbb{Z}_{\geq 0}} {n \choose r+kj}$ in terms of $r$, where we consider $n$ and $k$ fixed natural numbers and $n > k$? (here, ...
2
votes
2answers
56 views

Proof of Pascal' identity

The identity $$\binom{x+1}{k}-\binom{x}{k}=\binom{x}{k-1}$$ is claimed to hold (using the binomial polynomials, considered as lying in $\mathbf{Q}[x]$) for $k$ at least $1$. Proof: by the usual ...
9
votes
1answer
98 views

Consecutive terms in Pascal's Triangle

is it known whether or not there are infinitely many pairs of consecutive terms in this sequence: http://oeis.org/A006987 ? The sequence is the list of numbers expressible in the form ...
1
vote
1answer
49 views

$\sum_{k+M = 0}^n {n \choose k} {n-k \choose m} = 3^n$ help with combinatorial reasoning

$\sum_{k+M = 0}^n {n \choose k} {n-k \choose m} = 3^n $ I have worked the cases for $n=2$, $n=3$, and $n=4$ by hand and it appears to be true. $n=2$: $${2\choose 0}{2\choose 0} + {2\choose ...
1
vote
0answers
25 views

Algorithm for determining whether certain numbers appear in Pascal's triangle

Is there any easy characterisation for the numbers which appear in Pascal's triangle that ARE NOT $\dbinom{n}{1}$, $\dbinom{n}{n-1}$? Is there a fast way to determine if some number (given its prime ...
1
vote
4answers
43 views

Why is $\sum\limits_{b=1}^{t-1} {t \choose b} 2^{t-b} = (3^t - 2^t - 1)$

Why is $$\sum\limits_{b=1}^{t-1} {t \choose b} 2^{t-b} = (3^t - 2^t - 1)$$ Thanks.
1
vote
3answers
221 views

Using Binomial Theorem to prove the following [duplicate]

$$\large\sum_{j=0}^n (-1)^j {n\choose j}={n\choose 0}-{n\choose 1}+.....+\pm{n\choose n}=0 $$ I'm confused by the last part of the equation $\pm$. it seems imply that the sum would be equal to 0 no ...
2
votes
2answers
63 views

Factorial as a sum. Insight appreciated

I recently posted an answer to a question about ways to express the factorial function as a sum. I posted the following formula, which I discovered several years ago and I haven't seen anywhere else: ...
2
votes
1answer
39 views

Find coefficient of $x^3$ in (2+x) ^(3/2)/(1-x)

I can expand $\dfrac{(2+x)^{3/2}}{1-x}=(1+x+x^2+\ldots)\left({3/2\choose0}+{3/2\choose1}(x+1)+{3/2\choose2}(x+1)^2+\ldots\right)$, but that doesn't seem to lead anywhere.
7
votes
3answers
129 views

How to prove the following limit: $\lim_{n \to +\infty} 4^n\left[\sum_{k=0}^n (-1)^k{n\choose k}\ln (n+k)\right]=0$?

How to prove the following limit: $$\lim_{n \to +\infty} 4^n\left[\sum_{k=0}^n (-1)^k{n\choose k}\ln (n+k)\right]=0?$$
3
votes
0answers
90 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
1
vote
1answer
35 views

Meaning of coefficients when multiplying together $(1+x^a)(1+x^b)(1+x^c)\cdots$?

I know that when you multiply out $(1+x)^n$, the coefficient of $x^a$ tells you how many ways you can pick a of the brackets to use the x from to make $x^a$. I was wondering whether there is a meaning ...
3
votes
3answers
126 views

Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$ \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
-2
votes
1answer
52 views

Number after binomial coefficient

What does the number 2 mean in this picture? link Thanks. Sorry I'm not a math expert. I need this to make a program in C to generate a trinomial triangle for a guy who asked it on StackOverflow ...
6
votes
2answers
496 views

How to solve 0.5 choose 4?

I was solving this problem for homework. It says, in the problem, that if n is positive you use the generalized definition of binomial coefficients. In my case, n is positive so I just plugged n= 0.5 ...
2
votes
1answer
54 views

How prove this sum $\sum\limits_{n=k}^{\infty}\dbinom{n}{k}\left(\dfrac{-z}{1-z}\right)^n$

prove or disprove $$\sum_{n=k}^{\infty}\binom{n}{k}\left(\dfrac{-z}{1-z}\right)^n= (1-z)(-z)^k$$ my try: since ...
1
vote
1answer
56 views

How to evaluate the finite sum $\sum_{k=0}^n{\alpha \choose k}^2\lambda^k$

Is there a close form expression for the series \begin{equation} \sum_{k=0}^n{\alpha \choose k}^2\lambda^k,\quad \alpha ~ \text{is non-integer} \end{equation} As far as I know, there is an identity ...
1
vote
1answer
56 views

Binomial Congruence (mod 5) Identity

I've got a (hard?) Putnam-style problem that I've been given to look at . . . I've never worked any problem even vaguely like this, but my director thinks I should be able to do it. I doubt it (100% ...
6
votes
3answers
141 views

Evaluation of $\sum_{k=0}^n{n\choose k}^2u^k$

I am trying to evaluate the finite sum \begin{equation} f(u)=\sum_{k=0}^n{n\choose k}^2u^k,\quad 0<u\le1 \end{equation} In an first attempt, I think of the generating function \begin{equation} ...
1
vote
2answers
107 views

Proof that $\dfrac{1}{e^x}=e^{-x}$ without converting it to $e^{x}e^{-x}=1$.

I want to show that $\dfrac{1}{e^x} = e^{-x}$ from the Taylor expansion of $e^x$. To express $\dfrac{1}{e^x}$ as a power series, I let: $$ \left(\dfrac{1}{0!}x^0 + \dfrac{1}{1!}x^1 + ...
0
votes
1answer
47 views

How to evaluate $\sum_{k=0}^{n} \alpha^k \binom{n}{k}$?

I am trying to show that the function that satisfies $f^\prime(x)=f(x)$ with $f(0)=1$ behaves in an exponential way (in other words, I want to justify writing it as $e^x$). I need to show that: $$ ...
2
votes
2answers
28 views

Appromixation of binomial coefficient for large numbers

In the context of writing a program for sortition, I would like to know if the entropy of my input random variable in large enough to potentially produce all outcome of my sortition problem. Let say ...
2
votes
1answer
32 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
2
votes
2answers
134 views

Alternating sum of binomial coefficients is equal to zero [duplicate]

Prove without using induction that the following formula:$$\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ is valid for every $n\ge1$. Progress For each odd $n$ we can use the ...
2
votes
2answers
89 views

How to prove $n! > n^a$ for all $a\in \mathbb{R}$ (for sufficiently large $n$)?

I've encountered a proof which claims $n! > n^2$ for sufficiently large $n$. I tried using induction to prove it for an arbitrary $a$: $n! > n^a$. Lets assume the claim is true for $n$: $n! ...
1
vote
1answer
40 views

Verification of binomial coefficient congruence $\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$

Let $j\ge 1$ be an integer and $p$ prime. Is it true that $$\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$$ My work No, take $j>p$, then the RHS is zero, while the LHS need not be $\equiv 0$. For ...
7
votes
4answers
158 views

How prove this inequality $(1+\frac{1}{16})^{16}<\frac{8}{3}$

show that $$(1+\dfrac{1}{16})^{16}<\dfrac{8}{3}$$ it's well know that $$(1+\dfrac{1}{n})^n<e$$ so $$(1+\dfrac{1}{16})^{16}<e$$ But I found this $e=2.718>\dfrac{8}{3}=2.6666\cdots$ ...
0
votes
0answers
25 views

is binomial congruence given in article true or false?

I'm just reading a paper which, on its page 3, Application 8, claims the following: $$\binom{k+sp}{j}\equiv\binom{k}{j}\pmod{p}$$ where $p\ge 1$, $s\ge 1$, $k\ge 1$ and $p\not\mid j$ (actually, it ...
1
vote
3answers
73 views

Showing that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$

I'm trying to prove that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$. I figured induction was the way to go, so I tried. This is what I've accomplished so far: Proved ...
-1
votes
2answers
59 views

Squared binomial paradox?

When you square this $$(5-2)^2$$ you will get 49 $$ 5^2 - 2 * 5 * (-2) + (-2)^2$$ $$25 + 20 + 4 = 49$$ but if you do it like this (5-2) * (5-2) you will get 9 $$ 5(5-2) - 2(5-2)$$ $$25-10-10+4$$ ...
1
vote
3answers
28 views

refactoring binomial with negative power

I am reading Calculus Made Easy where in Chapter IV: $$(x+dx)^{-2}$$ Is refactored as: $$x^{-2}\left(1+\frac{dx}x\right)^{-2}$$ Could someone give me an insight into this refactoring? I can see from ...