Proof by Induction involving Binomial Coefficients

In summary, To prove by induction that for any positive integers a, b, and n, (a choose 0)(b choose n) + (a choose 1)(b choose n-1) + ... + (a choose n)(b choose 0) = (a+b choose n), start by using the given equations to solve the basis (n=1) and obtain a+b=a+b. Then, for the inductive step, reduce the right side to (a+b choose n)*(a+b-n)/(n+1) and try to find a way to make the series on the left side match the right side. Alternatively, you can do induction on 'a' or 'b' or 'a+b'
  • #1
Tollschnee
3
0

Homework Statement


Prove by induction that for any positive integers a, b, and n,
(a choose 0)(b choose n) + (a choose 1)(b choose n-1) + ... + (a choose n)(b choose 0) = (a+b choose n)


Homework Equations


(x choose y) = (x!)/((x-y)!y!)


The Attempt at a Solution


I am able to do the first step of induction, the basis. That is quite simple because all I had to do was set n equal to 1 and solve both sides. I ended up with a+b=a+b. My problem is with proving the inductive step (assuming that n works and using that to prove that n+1 works). I understand the equation conceptually and how it works, however the problem requires I do a proof by induction and I cannot figure out how to prove the inductive step.
 
Last edited:
Physics news on Phys.org
  • #2
The usual approach is to start with your left side of the equation (for k+1), use the assumption (assume it works for k...) to reduce the math, and finally conclude after some simplification/rearranging the right hand side (for k+1).

You can of course work from the right side to conclude the left, but in inductive proofs it is generally easier to work with the more "complicated" side in order to conclude the "easier" side.
 
  • #3
So I have reduced the right side (a+b choose n+1) to (a+b choose n)*(a+b-n)/(n+1)
I obtained this from applying the formula I was given and applying it to both (a+b choose n) and (a+b choose n+1) and simplifying the latter to contain the former along with whatever else... in this case: (a+b-n)/(n+1)

I guess the real trouble I am having at this point is dealing with the series on the left side of the equation and simplifying it out to match the right side. I've been trying to find some way to make the n+1 series match the n series along with some multiplier, but I can't find the trick.
 
Last edited:
  • #4
Tollschnee said:
So I have reduced the right side (a+b choose n+1) to (a+b choose n)*(a+b-n)/(n+1)
I obtained this from applying the formula I was given and applying it to both (a+b choose n) and (a+b choose n+1) and simplifying the latter to contain the former along with whatever else... in this case: (a+b-n)/(n+1)

I guess the real trouble I am having at this point is dealing with the series on the left side of the equation and simplifying it out to match the right side. I've been trying to find some way to make the n+1 series match the n series along with some multiplier, but I can't find the trick.

You don't necessarily need to do induction on 'n'; you could, instead, do induction on 'a' or 'b' or 'a+b'.
 

Related to Proof by Induction involving Binomial Coefficients

1. What is proof by induction?

Proof by induction is a method of mathematical reasoning used to prove statements about natural numbers or other recursively defined objects. It involves breaking down the statement into simpler cases and proving that it holds for a base case, and then showing that if it holds for one case, it also holds for the next case. This process is repeated until the statement is proven for all cases.

2. What are binomial coefficients?

Binomial coefficients, also known as binomial coefficients, are the numerical coefficients that appear in the expansion of a binomial expression. They are used to represent the number of ways to choose a certain number of objects from a larger set. They are written as n choose k, and are denoted as n C k.

3. How are binomial coefficients used in proof by induction?

Binomial coefficients are often used in proof by induction when dealing with summations or other mathematical expressions involving natural numbers. They can be used to simplify the expressions and make them easier to work with, ultimately leading to a more concise and elegant proof.

4. Can proof by induction involving binomial coefficients be used for other types of numbers?

While proof by induction is often used with natural numbers, it can also be applied to other types of numbers, such as integers or real numbers. However, when dealing with binomial coefficients, it is important to note that they are only defined for non-negative integers, so the proof may need to be modified accordingly.

5. Are there any common mistakes to avoid when using proof by induction involving binomial coefficients?

One common mistake to avoid when using proof by induction involving binomial coefficients is forgetting to include the base case in the proof. It is also important to carefully consider the inductive step and make sure it is valid for all cases. Additionally, when dealing with binomial coefficients, it is crucial to keep track of the indices and make sure they are used correctly throughout the proof.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
577
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
401
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
677
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
378
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
567
Back
Top