(adsbygoogle = window.adsbygoogle || []).push({}); I really really hate proofs!

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.

**Physics Forums - The Fusion of Science and Community**

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

# God, I hate Number Theory Proofs

Loading...

Similar Threads - hate Number Theory | Date |
---|---|

A Last Gauss Lemma Section II | Feb 4, 2018 |

B Why does every subfield of Complex number have a copy of Q? | Jun 11, 2017 |

B Why the hate on determinants? | Jun 9, 2017 |

I Similar Polygons | May 11, 2017 |

**Physics Forums - The Fusion of Science and Community**