Help Needed: Proving T(n,m) ≤ (n+m-1 choose n-1) with Induction

[Shinjo]

I've done 3 of my 5 problems, which took me 2 days and over 30-50 pieces of scrap paper. I'm serious, I didn't even eat dinner today because I spent straight hours just staring at questions, thinking I was coming close to solutions, then only to find out I've gotten no where. So in the end, I decided to come here and find out if anyone can lend me a hand.

Let T(n,m) = T(n,m-1) + T(n-1,m) and T(s,2) = T(2,s) = s for all natural numbers s. Use induction to prove that

[tex]T(n,m) \leq \left(\begin{array}{cc}n+m-1\\n-1\end{array}\right) \forall n,m \in N, n + m \geq 2[/tex]

Here's what I got so far
Basically if I expand the recurrence relation out a bit in a sort of "binary tree" form, so my top node will be T(n,m), then the next row is T(n,m-1) and T(n-1,m), then the next row will be T(n,m-2), T(n-1,m-1), T(n-1,m-1), and T(n-2,m), I started to notice something similar to Binomial Coefficients pascal's triangle thingy, which I also know that the left side of the inequality has a combination function.

I also noticed that as I go down each row on the tree, each sub node loses only an integer of one. For instance, the first root node is n+m, the next one is n+m-1, and the next is n+m-2, and so forth.

Someone told me to try and fix one variable then proving the other, which I think is how I'm supposed to tackle this problem. Unfortunately, for these kinds of proofs, there has to be some idea behind it, like a loop invariant, or a fixed form of the predicate. Without those, I can't even start the proving part.

If someone can help me, it would be much appreciated. Thank You.

 

[StatusX]

A proof by induction is done by assuming the statement is true for n-1 (or in your case, (n,m-1) and (n-1,m) ), and showing that this implies it is also true for n. Then if you can show it is true at the beginning, you know it is true for all higher numbers, because the first ones imply the next ones, which imply the next ones, and so on. So, can you show that if the relation is true for T(n,m-1) and T(n-1,m), it is also true for T(n,m)? Then what else do you need to show to finish the proof?

 

[mitjak]

CSC236? :)

Why if you look at the sum of m+n? See how it changes for T(n-1,m) and T(n,m-1)