Can Newton's Binomial be Used to Prove the Equation ΣC(2+k,4) = (n+3,4)?

[Lilia]

Homework Statement

Using the Newton's binomial, prove that
ΣC(2+k,4) = (n+3,4), k=0,n

Homework 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

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

 

[fresh_42]

Homework Statement

Using the Newton's binomial, prove that
ΣC(2+k,4) = (n+3,4), k=0,n

Homework 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

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

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} ##

 

[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...

 

[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?

 

[fresh_42]

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?

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.

 

[Lilia]

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

 

[fresh_42]

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

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.

 

[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?

 

[haruspex]

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?

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?

 

[Ray Vickson]

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?

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}##.

 

[Lilia]

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?

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

 

[haruspex]

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

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.

 

[Lilia]

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

 

[haruspex]

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

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