God, I hate Number Theory Proofs

1. Oct 2, 2005

Shinjo

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

$$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$$

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.

Last edited: Oct 2, 2005
2. Oct 2, 2005

ramsey2879

I suggest that you start a tree with the pair (!,2)(2,1) at the top then increase the value of n+m with each subsequent row using the formula T(n,m) = T(n,m-1) + T(n-1,m). Look for a pattern that suggests a proof.

3. Oct 2, 2005

neurocomp2003

have you tried mathematical induction?
(..) is that the choose function or the jacobian/legendre symbol?
if its the choose(combination) function trhen it should be rather straight forward

4. Oct 2, 2005

ComputerGeek

Number Theory Proofs are not different than any other proof.

5. Oct 2, 2005

ramsey2879

Actually, you should start at T(2,2) = 2 as the zero row. The first row then consists of T(2,3) =3 and T(3,2) = 3. The ith row is framed by the terms T(2,2+i) = 2+i and T(2+i,2) = 2+i instead of 1's. This forms a triangular table just as the Pascal triangle except the vertical left side (1st column) is the series 2,3,4,5,6....m where m is the value:
$$\ T(2,m) = \left(\begin{array}{cc}m\\1\end{array}\right)\$$
and the diagonal right side is the series 2,3,4...m where m is the value
$$\ T(m,2) = \left(\begin{array}{cc}m\\m-1\end{array}\right)\$$
The intermediate terms are given as the sum of the number just above and to the immediate left in the previous row, just as in Pascal's triangle. Thus, the terms in second column is the series 3,6,10 .... T(3,m) where
$$\ T(3,m) = \left(\begin{array}{cc}m+1\\2\end{array}\right)\$$

This should get you started on your proof.

6. Oct 4, 2005

_quicksilver

what are we using exactly for the inductive step then? im not too sure where the pascal triangle thing would be written

7. Oct 5, 2005

ramsey2879

1) Show that T(2,1), T(1,2) corresponds to the binominal coeficients for (a+b)^(n+m-2) corresponding to row 1 of the Pascal's triangle.
2) Let $$T(n,m) \forall n,m \in N, n + m \geq 2$$ be assigned to row n+m-2, column m.
3) Prove that if row s of the above created table corresponds to row s of Pascal's triangle then row s + 1 corresponds to row s+1 of Pascal's triangle.
4) Then
$$T(n,m) = \left(\begin{array}{cc}n+m-2\\n-1\end{array}\right) \forall n,m \in N, n + m \geq 2$$

Last edited: Oct 5, 2005