4
votes
5answers
206 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
6
votes
3answers
129 views

Help with a Binomial Identity: $\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = 2^{n+1}$

The following is a problem from the 5th edition of Niven's An Introduction to the Theory of Numbers: Problem 23 of Section 1.4 asks us to prove that $$\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = ...
3
votes
6answers
599 views

How do I begin proving this binomial coefficient identity: ${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
7
votes
2answers
235 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
2
votes
4answers
99 views

Finding an algebraic proof for $r{n \choose r} = n{n-1 \choose r-1}$ [closed]

I can't seem figure this proof out. How are both sides equal. $$r{n \choose r} = n{n-1 \choose r-1}$$
1
vote
2answers
66 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
1
vote
2answers
63 views

How to prove $\sum_{k\leq n}^{n} \binom{n}{k}= 2^n$ by induction [duplicate]

$\sum_{k\leq n}^{n} \binom{n}{k}= 2^n , n, k \in \mathbb{N}$ Im trying with mathematical induction but im stuck. My inductive step: $H) \sum_{k=0}^{h} \binom{h}{k}= 2^h$ $T) \sum_{k=0}^{h+1} ...
1
vote
2answers
45 views

prove that for $n \ge 4, {{2n}\choose{n}} \ge n\cdot2^n$

Prove that for $n \ge 4$ $${{2n}\choose{n}} \ge n\times2^n$$ I tried like that: $T_4$: ${{8}\choose{4}} = 70 \ge 4\times2^4$ = 64 so it's ok $T_{n+1}$: $$\frac{(2n+2)!}{(n+1)!)(n+1)!} \ge ...
5
votes
4answers
629 views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
2
votes
2answers
58 views

If $n = mp^e$ where $e$ is maximal, then $\binom{n}{p^e}$ is not divisible by $p$.

Let $n \geq 2$ be an integer, $p$ a prime with $p^e$ the highest power of $p$ dividing $n$. Then $\binom{n}{p^e}$ is not divisible by $p$. I think you can do it using this formula for ...
-1
votes
1answer
83 views

Revisited: Binomial Theorem: An Inductive Proof

I'm asked to use the fact that $\begin{pmatrix}n\\r\end{pmatrix}+\begin{pmatrix}n\\r-1\end{pmatrix}=\begin{pmatrix}n+1\\r\end{pmatrix}$ to show, by induction, that ...
3
votes
0answers
207 views

Proving identity involving sum

I'm stuck trying to prove the following identity: $$\displaystyle\sum_{i=j}^k\frac{(-1)^{i+j}{k+1 \choose i}{i \choose j}(4S-i-k-3)!(4S-2i-1)}{(4S-i-j-1)!} $$ $$=\frac{(-1)^{j+k}(4S-2k-3)!{k+1 ...
5
votes
4answers
221 views

Combinatorial Proof

I have trouble coming up with combinatorial proofs. How would you justify this equality? $$ n\binom {n-1}{k-1} = k \binom nk $$
3
votes
1answer
50 views

Binomial coefficient help?

I'm studying for my exams and would appreciate any help with binomial coefficients. I think I got the idea but having trouble with a specific one: Q) If a there are 11 dogs and 9 cats: a) How many 7 ...
4
votes
2answers
619 views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
1
vote
1answer
160 views

Prove: If $n=2^k-1$, then $\binom{n}{i}$ is odd for $0\leq i\leq n$

Kinda stuck on this one. Help is appreciated. I'm going for either a direct or contrapositive proof. Prove: If $n=2^k-1$, for $k\in\mathbb{N}$, then every entry in Row $n$ of Pascal's Triangle is ...
12
votes
5answers
1k views

Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially

I have to give a combinatorial proof of $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$ I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have ...
4
votes
3answers
385 views

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity: \begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation} Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
4
votes
1answer
116 views

Combinatorial reasoning for linear binomial identity

I have the following equation: \begin{equation} m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1} \end{equation} I iteratively took $m=1$ to $m=4$ to solve for the coefficients. I got ...
7
votes
2answers
221 views

Combinatorial argument for the identity $k\binom{n}{k} = n\binom{n-1}{k-1}$

I am looking for the combinatorial argument for the identity: \begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1} \end{equation} This is easy to show algebraically as: \begin{equation} \binom{n}{k} ...
7
votes
7answers
636 views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
9
votes
3answers
352 views

Problem of limit with binomial coefficients

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to ...
1
vote
2answers
1k views

Combinatorial proof of an identity [duplicate]

Possible Duplicate: Combinatorially prove something I have to give a combinatorial proof of the identity: $$\sum_{i=0}^{n}{\binom{n}{i}}{2^i}=3^n$$ I can use prove it using the binomial ...
4
votes
3answers
2k views

Using Binomial Theorem to prove identity

I need to prove the following using the binomial theorem $${n \choose k} = {n-2 \choose k} + 2{n-2 \choose k-1} + {n-2 \choose k-2}$$ The binomial theorem states $$(1+x)^n = \sum_{k=0}^n {n \choose ...
8
votes
3answers
229 views

Putting ${n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ in a closed form

As the title says, I'm trying to transform $\displaystyle{n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ into a closed form. My work: $\displaystyle\left(1 + ...
0
votes
1answer
122 views

Algebra on $\binom{k+1}{i} = \binom{k+1}{0} + \binom{k+1}{1} + \cdots + \binom{k+1}{k} + \binom{k+1}{k+1}$ [duplicate]

Possible Duplicate: Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$ I am trying to prove $\sum \limits_{i=0}^n \binom{n}{i} = 2^n$ by induction. I've been all over the net ...
2
votes
2answers
436 views

Divisibility using binomial coefficients

I have to prove that $6 \mid n^3 + 5n$ in a number of ways. One that I've been finding impossible is binomial coefficients. This is the problem statment: Use an expression in terms of binomial ...
5
votes
1answer
150 views

Showing two definitions of a binomial coefficient are the same

I have a homework question where we have to prove the following definitions of a binomial coefficient are equal, algebraically. This is what I got so far, and it's getting pretty complicated. And I ...