Factorials

Printable View

September 2nd 2008, 03:21 AM
Number Cruncher 20

Factorials

Hi,

Does anyone know whether it is possible to simplify a factorial as follows:

${n\choose i}{n-m\choose i-m}$

= (n-m)! / ((i-m)!(n-m-i-m)!)
=(n-m)!/((i-m)!(n-i)!)
=(n-m)!/(i-m+n-i)!
=(n-m)!/(n-m)!
=1
September 2nd 2008, 03:57 AM
flyingsquirrel

Hello,

Quote:

Originally Posted by Number Cruncher 20

Does anyone know whether it is possible to simplify a factorial as follows:

${n\choose i}{n-m\choose i-m}$

= (n-m)! / ((i-m)!(n-m-i-m)!)

No... your forgot $\tbinom{n}{i}=\tfrac{n!}{i!(n-i)!}$ . We have

$\begin{aligned} {n\choose i}{n-m\choose i-m}&=\frac{n!}{i!(n-i)!}\cdot \frac{(n-m)!}{(i-m)![n-m-(i-m)]!}\\&=\frac{n!}{i!(n-i)!}\cdot \frac{(n-m)!}{(i-m)!(n-i)!}\\&= \frac{(n-m)!n!}{i!(i-m)!(n-i)!^2}\end{aligned}$

and it seems this can't be further simplified. If you were asked to simplify $\tbinom{n}{m}\tbinom{n-m}{i-m}$ then we could derive the equality $\tbinom{n}{m}\tbinom{n-m}{i-m}=\tbinom{n}{i}\tbinom{i}{m}$ but that's not what you're asked to do, is it?
September 2nd 2008, 04:16 AM
Number Cruncher 20

no, what ive been asked is to derive a closed formed expression for

(a) s = http://www.mathhelpforum.com/math-he...488598ba-1.gif for n= 0,1,2,....

(b) t = http://www.mathhelpforum.com/math-he...27c930f6-1.gif for n=0,1,2, .. and m = 0,1,2,...n

ive done the first part and showed that its equal to 1 when n = 0 and 0 when n not equal to 0. for the second part ive been given a hint that

http://www.mathhelpforum.com/math-he...fb3cf705-1.gif for http://www.mathhelpforum.com/math-he...195e4ccc-1.gif.

and to use this and part a to find a closed form expression for (b). i get the part a and the hint but i just dont see how to go from there to solving part b.
September 2nd 2008, 04:57 AM
flyingsquirrel

Quote:

Originally Posted by Number Cruncher 20

and to use this and part a to find a closed form expression for (b). i get the part a and the hint but i just dont see how to go from there to solving part b.

We have

$t=\sum_{i=m}^n(-1)^i\binom{n}{i}\binom{i}{m}=\sum_{i=m}^n(-1)^i\binom{n}{m}\binom{n-m}{i-m} $

since we are told that $\tbinom{n}{i}\tbinom{i}{m}=\tbinom{n}{m}\tbinom{n-m}{i-m}$ . As $\tbinom{n}{m}$ doesn't depend on $i$ we can factor this term to get

$t=\binom{n}{m}\sum_{i=m}^n(-1)^i\binom{n-m}{i-m}$ .

Using the result of question (a), can you find a closed formed expression for $\sum_{i=m}^n(-1)^i\binom{n-m}{i-m}$ and thus for $t$ ?

Hint (highlight to read) : * change the index of summation to j = i-m *
September 2nd 2008, 05:43 AM
Number Cruncher 20

I havent done summations for a while. Have i changed the variables properly so that we get:

$ \binom{n}{m}\sum_{j=o}^n(-1)^(j+m)\binom{n-m}{j} $
September 2nd 2008, 05:55 AM
flyingsquirrel

Quote:

Originally Posted by Number Cruncher 20

I havent done summations for a while. Have i changed the variables properly so that we get:

$ \binom{n}{m}\sum_{j=o}^n(-1)^(j+m)\binom{n-m}{j} $

That's almost it, there is only a little mistake : for $i=n,\,j=n-m$ so

$t=\binom{n}{m}\sum_{j=0}^{{\color{blue}n-m}}(-1)^{j+m}\binom{n-m}{j} $ .

Factoring $(-1)^m$ we get

$t=(-1)^m\binom{n}{m}\sum_{j=0}^{n-m}(-1)^j\binom{n-m}{j} $

and now you can use the answer to the first question to conclude.
September 2nd 2008, 06:06 AM
Number Cruncher 20

Thank you for your help its really appreciated.
September 2nd 2008, 06:29 AM
Number Cruncher 20

One last thing, but should the sum read:

(-1)^(j+2m) or is it right as (-1)^(j+m)
September 2nd 2008, 06:39 AM
flyingsquirrel

Quote:

Originally Posted by Number Cruncher 20

One last thing, but should the sum read:

(-1)^(j+2m) or is it right as (-1)^(j+m)

If you're talking about the following sum

Quote:

Originally Posted by flyingsquirrel

$t=\binom{n}{m}\sum_{j=0}^{{\color{blue}n-m}}(-1)^{j+m}\binom{n-m}{j} $

then it is right as $(-1)^{j+m}$ since this term comes from $(-1)^{i}$ where we've substituted $i=j+m$ . Why do you think it should be $(-1)^{j+2m}$ ?
September 2nd 2008, 06:47 AM
Number Cruncher 20

sorry my bad i forgot the restrictions on the range of n and m so i thought it had to be $(-1)^{2m}$ for it to be 1.

Thanks again
September 2nd 2008, 06:52 AM
Number Cruncher 20

what i meant is that you get
$ (-1)^{m} \binom{n}{m} (0)^{n-m} $

and when n=m

if m and n are odd then t = -1 and when m and n are even then t is 1

is that the right answer.