# Prove the equation

1. Nov 6, 2016

### Lilia

1. The problem statement, all variables and given/known data
Using the Newton's binomial, prove that
ΣC(2+k,4) = (n+3,4), k=0,n

2. Relevant equations
(1+x)^n + (1+x)^m = (1+x)^(n+m)
r≤min(m,n) => ΣC(n,k) * C(m,r-k) = C(n+m,k

3. The attempt at a solution
At first, I tried to see that this equation is correct with an example, n=3. But for the left side I get --- CC2,4)+C(3,4)+C(4,4)+C(5,4) = 6
And for the right side --- C(6,4)=C(6,2)=15
Maybe this is not a part of the process of proving but why is this happening?

And please provide me with some guidance on how to think to prove this

2. Nov 6, 2016

### Staff: Mentor

It is always a good idea to check those formulas with small values. It might not only point to errors, it also might give you an idea how to prove them.
Also, what I don't get is, why does the sum start at $k=0$ instead of $k=2$? And isn't the case $n=1$ already wrong?

So please check, if you got it right or if (at least me) has made a mistake as I took it for $\sum_{k=0}^n \binom{2+k}{4}=\binom{n+3}{4}$

3. Nov 6, 2016

### late347

Well... With some quick googling I found a proof of Newton's binomial formula using proof by induction. Proof was from university of Helsinki (so the math research paper was in Finnish language)
http://www.helsinki.fi/~koskenoj/alg1/binomikaava.pdf

I'm not very good at proving in maths myself but that proof by induction could be one style of proof to go for...

4. Nov 6, 2016

### Lilia

in the exercise k is from 0 to n, but the values 0 and 1 are useless because C(2,4) and C(3,4) are both 0. and yeah, n=1 is wrong too. so this equation is not correct?

5. Nov 6, 2016

### Staff: Mentor

At least not for all $n$, maybe for some, but I doubt it. Calculating it for a few small $n$ I assume some patterns. The LHS looks like it always has a remainder $1$ on a division by $5$ and the RHS is divisible by $5$. And the LHS is always the sum of both sides from the previous one.

6. Nov 6, 2016

### Lilia

I just noticed that, that's interestingly true. I calculated both sides for a few n but they never get equal.

7. Nov 6, 2016

### Staff: Mentor

If you like to practice, you could prove my three claims and that the term on the right is always greater than the sum on the left.

8. Nov 10, 2016

### Lilia

So, if it's

sum of C(2+m,2) = C(n+3,3), m=0,n

We have a formula:

sum of C(k+m,k) = C(k+1+n,k+1)

Is there a way to prove this?

9. Nov 10, 2016

### haruspex

Indeed.
You could get a clue by writing out a few rows of Pascal's triangle. The sum consists of adding terms parallel to the right hand side, starting with a 1 at the top. Call that A. The next term in the sum is the one below and right of it. Call that B. Note that the term below and left of A (call that C) is also a 1, so adding A and B gives the same as adding C and B.
What do you know about the sum of two adjacent terms in the same row, as B and C are?

10. Nov 10, 2016

### Ray Vickson

You can use the following facts from generating function theory:
(1) Newton's binomial theorem (not the elementary binomial theorem!) gives
$$(1-z)^{-p} = \sum_{k=0}^{\infty} {-p \choose k} (-z)^k,$$
where for integer $p > 0$ we have
$${ -p \choose k} = \frac{(-p)(p-1) \cdots (-p-k+1)}{k!} = (-1)^k {p+k-1 \choose k}$$.
Thus
$$(1-z)^{-p} = \sum_{k=0}^{\infty} {p+k-1 \choose k} z^k,$$
for integer $p > 0$.

(2) If $A(z) = \sum_{k=0}^{\infty} a_k z^k$, then
$$\frac{A(z)}{1-z} = \sum_{k=0}^{\infty} \left( \sum_{j=0}^k a_j \right) z^k .$$
Apply this to $A(z) = (1-z)^{-p}$.

11. Nov 11, 2016

### Lilia

Starting row count from 0, on the nth row the sum of two adjacent terms is C(n,k) + C(n,k+1). I see similarities to the formula but there on the left side we have a sum of choosing k elements, whereas here this formula is the sum which consists of choosing k elements then k+1 elements

12. Nov 11, 2016

### haruspex

Start with an (n,0) term and add it to the (n+1,1) term. (n,0) and (n+1,0) are both 1, so this is the same as adding (n+1,0) and (n+1,1), which of course produces (n+2,1). Now add in the (n+2,2), and so forth.

13. Nov 12, 2016

### Lilia

I did that, but I don't get to the proving part

14. Nov 12, 2016

### haruspex

Use what you discovered from that to set up an inductive hypothesis and show that it is sustained.