Algebraic identity prove

Lobinho

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?

JeffM1

Is there any information about k and r?

Did you try mathematical induction?

Lobinho

Induction on r? on k?
I don't see how this leads me to the solution.

By the way, here is my attempt:

JeffM1

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:

Lobinho

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?

JeffM1

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.

JeffM1

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