Algebraic identity prove

Mar 2015
34
1
USA
Hi,

I need to prove the following identity:



I tried to go straight forward with the definition of (n choose k), but I got stuck. Do you know how can I prove this?
 
May 2016
1,310
551
USA
Is there any information about k and r?

Did you try mathematical induction?
 
Mar 2015
34
1
USA
Induction on r? on k?
I don't see how this leads me to the solution.

By the way, here is my attempt:

 
May 2016
1,310
551
USA
Because you did not give a full set of constraints on k, n, and r, I am guessing that the real problem is

$\displaystyle Prove:\ \sum_{m=0}^n \left ( \dfrac{m - k}{n - r} * \dfrac{\dbinom{m}{k} * \dbinom{n - m}{r - k}}{\dbinom{n+1}{r+1}} \right ) = \dfrac{k + 1}{r + 2}\ given$

$k,\ n,\ r \in \mathbb Z,\ n \ge 2,\ and\ 1 \le k \le r \le n - 1.$

$\displaystyle Let\ x(k,\ r,\ n) = \sum_{m=0}^n \left ( \dfrac{m - k}{n - r} * \dfrac{\dbinom{m}{k} * \dbinom{n - m}{r - k}}{\dbinom{n+1}{r+1}} \right ) = \dfrac{1}{(n - r) * \dbinom{n + 1}{r + 1}} * \sum_{m=0}^n \left \{(m - k) * \dbinom{m}{k} * \dbinom{n - m}{r - k} \right \}.$

$ASSUME\ n = 2 \implies 1 = k = r.$

$\displaystyle \therefore x(1,\ 1,\ 2) = \dfrac{1}{(2 - 1) * \dbinom{2 + 1}{1 + 1}} * \sum_{m=0}^2 \left \{(m - 1) * \dbinom{m}{1} * \dbinom{2 - m}{1 - 1} \right \} \implies $

$\displaystyle x(1,\ 1,\ 2) = \dfrac{1}{1 * \dbinom{3}{2}} * \sum_{m=0}^2 \left \{(m - 1) * \dbinom{m}{1} * \dbinom{2 - m}{0} \right \} \implies$

$\displaystyle x(1,\ 1,\ 2) = \dfrac{1}{3} * \sum_{m=0}^2 \left \{(m - 1) * \dbinom{m}{1} \right \} \implies$

$x(1,\ 1,\ 2) = \dfrac{1}{3} * \left ( \{(0 - 1) * 0 \} + \{ (1 - 1) * 1 \} + \{(2 - 1) * 2 \} \right ) \implies$

$x(1,\ 1,\ 2) = \dfrac{1}{3} * (0 + 0 + 2) = \dfrac{2}{3} = \dfrac{k + 1}{r + 2}.$

So this gives you a base case for an induction. Moving forward may become a bit tricky because when you go from j to j + 1, you have to prove the two cases where r = j separately. (It may be straight forward: I did not try to do it. If you have a problem, please show your work, and we shall try to help you move forward.)

EDIT: There may be a cleaner method. I admit that this seems to be pure brute force.
 
Last edited:
Mar 2015
34
1
USA
Do you mean to perform the induction on k,r and n simultaneously?
I deduce that because you took the smallest possible values for k,r and n in your base case (by the way, you were right about the constraints about k,r and n).

As far as I know, we can use induction only on one variable. I.E., we can perform the induction on k, and take general n and r. Isn't it so?
 
May 2016
1,310
551
USA
My academic training was in European languages and history so my comments on formal mathematical proofs should be viewed with caution.

I know (but see prior paragraph) of no reason that you cannot do a series of inductive arguments. If you took that path, I think you would need to start with n because that is the primary constraining variable and then follow with r because that is the secondary constraining variable and end with k.

I do not, however, think that series of inductive proofs is necessary.

What was shown in the base case was that there exists a non-empty set S, every element of which has the following properties:

$s \in S \implies s \in \mathbb Z,\ s \ge 2,\ and\ x(k,\ s,\ r) = \dfrac{k + 1}{r + 2}\ if\ 1 \le k \le r \le s - 1.$

Now let j be an arbitrary member of S.

As I tried to imply in my previous post, I SUSPECT that you can use

$x(k,\ j,\ r) = \dfrac{k + 1}{r + 1}\ if\ 1 \le k \le r \le j - 1$ to show that

$x(k,\ j + 1,\ r) = \dfrac{k + 1}{r + 2}\ if\ 1 \le k \le r \le j - 1$ because

I suspect all the terms in j + 1 will cancel out.

Then you would have to show that

$x(k,\ j + 1,\ j) = \dfrac{k + 1}{j + 2}\ if\ 1 \le k \le j.$

And finally you would have to show that

$x(j,\ j + 1,\ j) = \dfrac{j + 1}{j + 2}.$

At that point you would have shown that

$x(k,\ j + 1,\ r) = \dfrac{k + 1}{r + 2}\ if\ 1 \le k \le r \le (j + 1) - 1.$

You would have a proof by induction.

As I said in my previous post, I have not actually done such a proof, and there may be a more elegant way to proceed. I'd give it a shot, however, because it appears that terms cancel all over the place. If you give it a try and get stuck, someone will give you more help if you show us where you got stuck.
 
May 2016
1,310
551
USA
It is not so easy as I had hoped. But the initial work can be done without induction.

$Given:\ k,\ n,\ r \in \mathbb Z\ and\ 1 \le k \le r \le n - 1.$

$Define\ \displaystyle x(k,\ n,\ r) = \sum_{m=k+1}^n \left \{ \dfrac{m - k}{n - r} * \dbinom{m}{k} * \dbinom{n - m}{r - k} \div \dbinom{n + 1}{r + 1} \right \}.$

$Prove:\ x(k,\ n,\ r) = \dfrac{k + 1}{r + 1}.$

We need a lemma, which is step 1.

$Step\ 1:\ \alpha \in \mathbb Z\ and\ \alpha \ge 2 \implies$

$\displaystyle \left ( \sum_{i= 2}^{\alpha}(i^2 - i) \right ) = \left (\sum_{i= 2}^{\alpha}i^2 \right ) - \left ( \sum_{i= 2}^{\alpha}i \right ) =\left (-\ 1^2 + \sum_{i= 1}^{\alpha}i^2 \right ) - \left (-\ 1 + \sum_{i= 1}^{\alpha}i \right ) =$

$\dfrac{\alpha (\alpha + 1) (2 \alpha + 1)}{6} - \dfrac{\alpha ( \alpha + 1)}{2} + 1 - 1 = \dfrac{(\alpha + 1) * \alpha * (\alpha - 1)}{3} = \dfrac{( \alpha + 1)!}{3 * ( \alpha - 2)!}.$

Step 2: Show that x(1, n, 1) = (k + 1) / (r + 2).

$\displaystyle x(1,\ n,\ 1) = \sum_{m=2}^n \left \{ \dfrac{m - 1}{n - 1} * \dbinom{m}{1} * \dbinom{n - m}{1 - 1} \div \dbinom{n + 1}{1 + 1} \right \}\implies$

$\displaystyle x(1,\ n,\ 1) = \dfrac{1}{n - 1} * \sum_{m=2}^n \left \{ (m - 1) * m * \dbinom{n - m}{0} \div \dbinom{n + 1}{2} \right \} \implies$

$\displaystyle x(1,\ n,\ 1) = \dfrac{1}{n - 1} * \sum_{m=2}^n \left \{ (m^2 - m) * 1 * \dfrac{2! * \{(n + 1) - 2\}!}{(n + 1)!} \right \} \implies$

$\displaystyle x(1,\ n,\ 1) = \dfrac{1}{n - 1} * \sum_{m=2}^n \left \{ (m^2 - m) * \dfrac{2! * (n - 1)!}{(n + 1) * n * (n - 1)!} \right \} \implies$

$\displaystyle x(1,\ n,\ 1) = \dfrac{1}{n - 1} * \dfrac{2}{(n + 1) * n} * \sum_{m=2}^n (m^2 - m) \implies$

$\displaystyle x(1,\ n,\ 1) = \dfrac{2 * (n - 2)!}{(n + 1)!} * \sum_{m=2}^n (m^2 - m) \implies$

$x(1,\ n,\ 1) = \dfrac{2 * \cancel {(n - 2)!}}{\cancel {(n + 1)!}} * \dfrac{\cancel {(n + 1)!}}{3 * \cancel {(n - 2)!}} = \dfrac{2}{3} \implies$

$x(1,\ n,\ 1) = \dfrac{k + 1}{r + 1}.$

Now if we need induction, the next step would be to show that

$x(1,\ n,\ r) = \dfrac{k + 1}{r + 1}\ for\ 1 \le r \le (n - 1).$

We certainly have our base case for r = 1. But induction may not be the way to go.
 
Similar Math Discussions Math Forum Date
Algebra
Algebra
Calculus
Elementary Math