# Prove Pascals formula

1. May 30, 2007

### Elruso

Prove "Pascals formula"

1. The problem statement, all variables and given/known data
Show that (k)+(k+1)+......+(n) = (n+1) it's supposed to be combinations
(k) (k ) (k) (k+1)

That's the question in my math book. I guess you need to use Pascals triangle and Pascals formula but unfortionately I dont know how to implement them here.

2. May 30, 2007

### lalbatros

please define what are these notations
what is the meaning of (k) ???

3. May 30, 2007

### AKG

lalbatros, he means show that:

$${{k}\choose{k}} + {{k+1}\choose{k}} + \dots + {{n}\choose{k}} = {{n+1}\choose{k+1}}$$

The second line of (k)'s and the (k+1) is supposed to line up underneath the stuff on the previous line. I'm about to hit the space bar 10 times. I just hit it 10 times, I see a big gap between "times." and "I just" but when I post this message, you'll only see one space.

Elruso, use Pascal's triangle on the right side of your equation together with induction.

4. May 30, 2007

### Elruso

Well, n=1,2,3,4.......... and k=1,2,3,4...............

5. May 30, 2007

### AKG

I don't know what your point is. Do induction on n. The base case is the trivial fact that ${{k}\choose{k}} = {{k+1}\choose{k+1}}$.

6. May 30, 2007

### VietDao29

Are you sure the problem is copied correctly? I think I should have read:
$$\left( \begin{array}{c} k \\ k \end{array} \right) + \left( \begin{array}{c} k + 1 \\ k \end{array} \right) + \left( \begin{array}{c} k + 2 \\ k \end{array} \right) + ... + \left( \begin{array}{c} k + n \\ k \end{array} \right) = \left( \begin{array}{c} k + n + 1 \\ k + 1 \end{array} \right)$$

As AKG's pointed out, you need a Proof By Induction. Proof By Induction requires 3 steps, i.e:
Step 1: Start with n = 0, or 1, or 2, or whatever according to what the problem asks you to do (in this case, you should choose n = 0), to see if it's correct.
Step 2: Assume the statement is true for k = n.
Step 3: prove that if it holds true for k = n, then it would also hold true for k = n + 1.

Can you go from her? :)