Show that ${n\choose r}={{n-1}\choose{r-1}}+{{n-1}\choose {r}}$.   My try:  $$\dfrac{n!}{(n-r)!\;r!}=\dfrac{(n-1)!}{(n-r)!(r-1)!}+\dfrac{(n-1)!}{(n-1-r)!\;r!}$$ Multiplying all terms by $r!(n-r)!$ $$n!=r(n-1)!+(n-1)!(n-r)$$ Dividing everything by $(n-1)!$ $$n=r+(n-r)$$ $$n=n$$  Is this correct?
18019
I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$.  I suppose I could use the counting rules in probability, perhaps combination= ${{n} \choose {r}}=\frac{n!}{r!(n-r!)}$.  I want to see an actual proof behind this equation.  Does anyone have any ideas?
103593
Assume that a,b,n are all natural numbers.  I was going to set it up as:  na = q(1)*n(b) + r(1)     where a>b  and go down the chain:  nb = q2 * r(1) + (r2)  but something seems off. Someone told me that in the first part, it should be n*r(1), but I don't understand why. May I please have some direction?
33898
I encountered this particular combinatorial identity :$$\begin{align}&amp;1\dbinom{n-1}{r-1}+2\dbinom{n-2}{r-1}+\cdots+(n+1-r)\dbinom{r-1}{r-1}\\=&amp;\dbinom{n}{r}+\dbinom{n-1}{r}+\cdots+\dbinom{r}{r}\\=&amp; \dbinom{n+1}{r+1}\end{align}$$How does one figure it out?
116415
For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity:   \begin{align} \binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r} . \end{align}   The problem is that I can't come up with a good counting argument of what exactly the two sides are doing. The left hand side is quite mysterious, and the right hand side is apparently choosing $r$ items and then choosing $k-r$ items from the remaining, which should be equivalent to $\binom{n}{k}$ but somehow isn't. How should I approach this problem?
33804
$$\sum_{r=1}^nr(r+1)=\frac{n(n+1)(n+2)}{3}$$  could you help me with how exactly I work this out?
3339
If $F_n$ is the $n$-th fibonacci number, then prove that, $$F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$$  I tried the idea of using Pascal's triangle, but it seems to need some adjustment, so I am stuck, please help.    Any combinatorial argument would be of greater help than rigorous proof.  Thank you.
8115
Prove the combinatorial identity $${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k} .$$   I understand the left side, which is obvious, but I'm struggling to get anywhere on the RHS. I also would appreciate suggestions on how to approach these kind of problems. I was told to use committees and split them up, but even then it's not so intuitive to me.  I've tried substituting small numbers to see where I can go.  Thank you in advance for your time.
90901
Suppose we want to prove $$ k \binom{n}{k} = n \binom{n-1}{k-1}$$   In the LHS we are choosing a team of $k$ players from $n$ players. Then we are choosing a captain. In the RHS we are choosing a captain from the $n$ players. Then we are choosing the remaining $k-1$ players from the $n-1$ players.   Is this a correct interpretation?
93175
Show that if $r$ is an nth root of $1$ and $r\ne1$, then $1 + r + r^2 + ... + r^{n-1} = 0$.  I think I can represent all the roots of 1 as follows:  $r = 1^{\frac{1}{n}} ( \frac{\cos{2\pi k}}{n} +  i\frac{\sin{2\pi k}}{n} )$  From there I am not sure how to get to $1 + r + r^2 + ... + r^{n-1} = 0$.
63499
Consider the smallest number in each of the $n\choose r$ subsets (of size $r$) of $S=\{1,2,\ldots,n\}$.Show that the arithmetic mean of the numbers so obtained is ${n+1}\over{r+1}$. I have no idea, how to solve it.It would be better if the solution has bijection. Please help!
58443
From "Fundamentals of Number Theory" by William J. LeVeque:     $M_n=2^n-1$.      Show that if $n=rs$, $M_r$ divides $M_n$.   My proof is:     $(M_n=2^n-1)+(n=rs) =&gt; (M_{rs}=2^{rs}-1)=&gt;(M_{rs}=(2^r)^s-1)$      $(M_r=2^r-1)=>(M_r+1=2^r)$      $M_{rs}=(M_r+1)^s-1$      In the expansion of $(M_r+1)^s$, all components are of the form $M_rX$, except for the product of all ones. This follows from the combinatorial constraints. Therefore $M_n$ is of the form      $M_n=M_{rs}=M_r(X_1+X_2+...)+1-1$.      Thus $M_r|M_n$.     I have two questions:   1) Is this proof correct/acceptable?  2) In what other ways can this problem be solved? Specifically I am interested in what other kinds of algebraic/logical/mathematical manipulations could be used.  Thanks in advance!
54720
Mathematica tells me that  $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$  Although I have not been able to come up with a proof.  Proofs, hints, or references are all welcome.
56568
I need help proving that $$\sum_{r=0}^n\binom{n}{r}2^r=3^n$$  I'm thinking this should use the idea that $\binom{n}{r}=\binom{n}{n-r}$ but I'm not sure how to proceed with it.  Thanks in advance!
110410
Prove that for any $0\lt r\lt n$ we have $$\binom nr=\binom{n-1}{r-1}+\binom{n-1}r.$$  How do prove this and what step do i take in order for it to be true?
104057
Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$.   One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that   $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln x)^{r - 1} + O\left(x(\ln x)^{r - 2}\right)$$  The base case $r = 2$ is easy with reversing the order of summation.  The only other progress that I made was the fact that $\sum_{n\le x}\tau_{r}(n) = \sum_{d\le x}\left\lfloor\frac{x}{d}\right\rfloor\tau_{r- 1}(d)$, but I don't know how to proceed.
54109
Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.   I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then $$n=2k+1\;\text{or}\\n=3k+1\;\text{or}\\n=3k+2\;\;\;\;$$for some $n\in\mathbb{N}$. And then make induction over $k$ in each case.$$24\mid (2k+1)^2-1\;\text{or}\\24\mid (3k+1)^2-1\;\text{or}\\24\mid (3k+2)^2-1\;\;\;\;$$This question is in a text of Euclidean Division I'm reviewing, and I wonder if there is a simpler, faster, or direct this way.
59040
If $p$ is a prime number and $r = 1,2,3 \dots ,p -1$, how can I prove that the binomial coefficients $_nC_r(p,r)$ are divisible by $p$? By divisible I mean $_nC_r(p,r)/p$ leaves remainder $0$.  oivind