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.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: God I hate recursive proofs so much

**Physics Forums | Science Articles, Homework Help, Discussion**