Binomial Coefficient Identity Proven by Induction

[PeterBradshaw]

Hello, everyone.

I am currently trying to solve a problem, but I can't seem to get anywhere. This is the problem:

Verify the following identity by math induction:

C(n, 0) + C(n+1, 1) + C(n+2, 2) + ... + C(n+r, r) = C(n+r+1, r)

I know that I can derive this identity by setting C(n+r+1, r) equal to c(n+r, r) + C(n+r, r-1), but I'm having trouble making the math induction work.

Here's what I've done so far.

Assume n = a, thus Sum(k=0 to r) [C(a+k,k)] = C(a+r+1, r)
Let n = a+1
Sum(k=0 to r) C(a+k+1, k) = C(a+r+2, r)

RHS:
C(a+r+2, r) = C[(a-1)+r+1, r]
= Sum(k=0 to r) C(a+k-1, k)

And then I realize that the left-hand-side is Sum(k=0 to r) C(a+k+1, k), which as far as I know doesn't equal what I've written for the right-hand-side.

I also tried manipulating the left-hand-side, trying to subtract Sum(k=0 to r) C(a+k, k) from the same equation when n = a+1, but the numbers don't subtract neatly.

I really wish that I could just write my explanation by hand, because it's very difficult to explain math by typing.

If anyone knows how to go about solving this, I would greatly appreciate it. I'm preparing for an extremely important test, so I need to be an expert on binomial identities.

Thank you.

 

[JeffM]

Hello, everyone.

I am currently trying to solve a problem, but I can't seem to get anywhere. This is the problem:

Verify the following identity by math induction:

C(n, 0) + C(n+1, 1) + C(n+2, 2) + ... + C(n+r, r) = C(n+r+1, r)

I know that I can derive this identity by setting C(n+r+1, r) equal to c(n+r, r) + C(n+r, r-1), but I'm having trouble making the math induction work.

Here's what I've done so far.

Assume n = a, thus Sum(k=0 to r) [C(a+k,k)] = C(a+r+1, r)
Let n = a+1
Sum(k=0 to r) C(a+k+1, k) = C(a+r+2, r)

RHS:
C(a+r+2, r) = C[(a-1)+r+1, r] How do you get this \(\displaystyle \dbinom{a + r + 2}{r} = \dbinom{(a - 1) + r + 1}{r} = \dbinom{a + r}{r}?\)

= Sum(k=0 to r) C(a+k-1, k)

And then I realize that the left-hand-side is Sum(k=0 to r) C(a+k+1, k), which as far as I know doesn't equal what I've written for the right-hand-side.

I also tried manipulating the left-hand-side, trying to subtract Sum(k=0 to r) C(a+k, k) from the same equation when n = a+1, but the numbers don't subtract neatly.

I really wish that I could just write my explanation by hand, because it's very difficult to explain math by typing.

If anyone knows how to go about solving this, I would greatly appreciate it. I'm preparing for an extremely important test, so I need to be an expert on binomial identities.

Thank you.

I have not worked this out, but it may PERHAPS be a double induction. But let's figure out where you are first because I am confused (which is sort of my natural state).

 

[pka]

This is the problem:
Verify the following identity by math induction:
C(n, 0) + C(n+1, 1) + C(n+2, 2) + ... + C(n+r, r) = C(n+r+1, r)

I know that I can derive this identity by setting C(n+r+1, r) equal to c(n+r, r) + C(n+r, r-1), but I'm having trouble making the math induction work.

Basically you need to show that the RHS is
\(\displaystyle \binom{n+r+1}{r} +\binom{n+r+1}{r+1}=\binom{n+r+2}{r+1}\)

 

[PeterBradshaw]

I'm sorry for that mistake in the post. I was a little bit mentally compromised when I was transcribing what I wrote. Anyway, I figured it out this morning, and it ended up working exactly like pka described. Thanks everyone for their input.