Showing that (m n) + (m n-1) = (m+1 n).

[Matthewkind]

Homework Statement

Show that if n is a positive integer at most equal to m, then
(m n) + (m n-1) = (m+1 n).

Homework Equations

The Attempt at a Solution

I understand that (m n) = m!/n!(m-n)!. I'm not entirely sure how to figure out (m n-1) because the book I'm studying from never explains this. It merely explains factorials and then shows that (m n) = m!/n!(m-n)!; however, I can at least figure out by reasoning it out that (m n-1) = m!/(m-n+1)!(n-1)!. However, I cannot understand how the next step goes.

If we're adding m!/n!(m-n)! and m!/(m-n+1)!(n-1)! then I'm at a loss. The book says that the common denominator is n!(m-n+1)!, but I don't understand that. And the numerator comes out to be m!(m-n+1)+m!n?! This I just cannot understand! I've turned this problem over in my head for over and hour and still nothing! Please help!

 

[Matthewkind]

This problem is from Serge Lang's 'Basic Mathematics' book. Chapter 1 - Numbers >> Rational Numbers >> Problem 7, part d.

 

[rock.freak667]

Since you have the two terms on the left expanded try expanding the individual terms.

Your book should say that n!= n(n-1)(n-2)(n-3)...x3x2x1 right?

Well this can be written in a simpler manner, n!=n(n-1)!

See if you can simplify and bring both terms to a common denominator.

 

[Matthewkind]

The book doesn't say anything about how n! = n(n-1)!. But that confuses me. I'm new to factorials and the binomial coefficient, so I'm a little confounded at the moment. How is n! = n(n-1)! a simplification of n! = n(n-1)(n-2)(n-3)...x3x2x1? :O

 

[Matthewkind]

What I mean to say is how can you drop all of those other terms?

 

[Matthewkind]

Also, if I write n! as n(n-1), then I get: m!/n(n-1)(m-n)! + m!/(m-n+1)!(n-1)!. I still can't quite make both denominators fit... I'm sorry for bothering you so much over a simple problem like this... I promise I'm trying. I think I'm just cracking under pressure.

 

[Matthewkind]

Hmm... Even if I can get both denominators to become the same, how does the numerator end up as: m!(m-n+1)+m!n?! If they have a common denominator, shouldn't I be able to just add m! and m! together?

 

[Dick]

The book doesn't say anything about how n! = n(n-1)!. But that confuses me. I'm new to factorials and the binomial coefficient, so I'm a little confounded at the moment. How is n! = n(n-1)! a simplification of n! = n(n-1)(n-2)(n-3)...x3x2x1? :O

If you don't understand why n!=n*(n-1)! then you are cracking under pressure. That's the most basic thing about factorials. 3*2*1=3*(2*1). So 3!=3*2!.

 

[Matthewkind]

Oooooh. I see! Sorry. XD I get how n! = n(n-1)!. Goshhhh. How silly.

 

[Matthewkind]

So then m! = m(m-1) as well. So I can also set m! = m(m-1) as both numerators. But there are still some steps I seem to be missing. Blargh, what am I missing?! ;___; And why is this only introduced as a problem with no explanation?

 

[Matthewkind]

I've been working through a bunch of different proofs and maybe I just need a break. I'm a bit discouraged that I don't understand what I'm doing when it comes to this part, but maybe it's alright. I just really want to be a theoretical physicist and it certainly is silly that such problems are slowing me down!

 

[Dick]

Oooooh. I see! Sorry. XD I get how n! = n(n-1)!. Goshhhh. How silly.

Ok then the rest of it goes the same. Express (m, n-1) and (m+1, n) as some factor times (m,n). Then show you have an identity.

 

[Matthewkind]

I'm already nineteen and I'm still struggling with this stuff! Is it even possible for me to grasp differential geometry and tensor analysis in my lifetime at this rate?!

 

[Matthewkind]

Ok then the rest of it goes the same. Express (m, n-1) and (m+1, n) as some factor times (m,n). Then show you have an identity.

I don't understand what you mean. Where are you getting (m, n-1) and (m+1, n)? ;__;

 

[Dick]

I've been working through a bunch of different proofs and maybe I just need a break. I'm a bit discouraged that I don't understand what I'm doing when it comes to this part, but maybe it's alright. I just really want to be a theoretical physicist and it certainly is silly that such problems are slowing me down!

Becoming a theoretical physicist involves a number of challenges and this isn't the greatest of them by a long shot. It's not alright if you can't do this. Do it.

 

[Matthewkind]

Oh, sorry. I meant it's alright if I take a break to cool my head. XD No, I won't leave any stones upright in this area!

 

[Dick]

I don't understand what you mean. Where are you getting (m, n-1) and (m+1, n)? ;__;

I'm getting them from your problem statement. Don't you remember?

 

[Matthewkind]

Oh, the commas confused me. The way it's written there were no commas. I see. Let me try re-starting the problem.

 

[Matthewkind]

(m, n) + (m, n-1) = (m+1, n). That's what I'm supposed to prove. So (m, n) = m!/n!(m-n!) and (m, n-1) = m!/(m-n+1)!(n-1)!. If I expand it, then I get: m(m-1)/n(n-1)(m-n)! + m(m-1)/(m-n+1)!(n-1)!. However, then I get stuck.

 

[Matthewkind]

I know that (m+1, n) = (m+1)!/n!((m+1)-n)!. But I can't get to this because I am still not sure what to do after I hit what was mentioned above...

 

[Dick]

Can you show, for example, that (m,n-1)=(m,n)*n/(m-n+1)? It's a pretty simple extension of n!=n*(n-1)!.

 

[Matthewkind]

How do you do that? (m,n-1) = m!/(n-1)!(m-n+1)!. (m,n) = m!/n!(m-n)!.

m!/n!(m-n)! multiplied by n/(m-n+1)? Where does that part come in? I mean, if (m,n) + (m,n-1) = (m+1, n), then wouldn't (m+1, n) - (m,n) = (m,n-1)? I'm so completely confused!

 

[Matthewkind]

I can't take it anymore. I'm losing my mind. I need to stop and come back to this later. I don't even have any more hair to pull.

 

[Matthewkind]

Thanks for trying to help me. I learned a bit about the nature of the problem (which was never even touched upon in the book for some reason...).

 

[Dick]

Thanks for trying to help me. I learned a bit about the nature of the problem (which was never even touched upon in the book for some reason...).

You can easily express factorials in terms of the factorial of a quantity that differs by 1. E.g. (n-1)!=n!/n. (m-n+1)!=(m-n)!*(m-n+1). It will probably look a lot easier when you come back to this.

 

[Matthewkind]

Yes! Thank you so much! I believe I have solved the problem!

I first expanded the problem so that (m, n-1) + (m, n) = (m+1, n) is m!/n!(m-n)! + m!/(n-1)!(m-n+1)! = (m+1)!/n!(m-n+1)!.

Next I took the four terms of all denominators: n! (m-n)! (n-1)! and (m-n+1)! and multiplied them by each term to cancel out the fractional forms. I'm left with:

m!(n-1)!(m-n+1)! + m!n!(m-n)! = (m+1)!(m-n)!(n-1)!. So I have to get both of these sides equal, right?

Next, I expanded what I thought was necessary in order to factor out the correct terms.

m!(n-1)!(m-n+1)(m-n)! + m!n(n-1)!(m-n)! = (m+1)!(m-n)!(n-1)!. Then I factored.

m!(n-1)!(m-n)![m-n+1+n] = (m+1)!(m-n)!(n-1)!.

Then I added the two n terms together.

m!(m-n)!(n-1)![m+1] = (m+1)!(m-n)!(n-1)!. Finally I multiplied m! and [m+1] to get:

(m+1)!(m-n)!(n-1)! = (m+1)!(m-n)!(n-1)!

I know that I'm pretty silly for not being able to do this, but I am just now embarking on my mathematical quest. I finished this earlier and it looked to me like beauty. I wonder: do you all feel this way or am I being unnecessarily sentimental? I felt like crying with joy.

 

[Matthewkind]

But you're right. I was being so close-minded at the time. I wonder why getting so worked up inhibits my ability to solve a problem logically. :/