God, I hate Number Theory Proofs

[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.

 

[ramsey2879]

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.

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.

 

[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

 

[ComputerGeek]

Number Theory Proofs are not different than any other proof.

 

[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.

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.

 

[_quicksilver]

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

 

[ramsey2879]

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

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