# [SOLVED] factorial manipulation

• Dec 17th 2008, 03:48 PM
spidey64
[SOLVED] factorial manipulation
hi,
I'm trying to do a proof by induction showing that (2x+1)!/(2^x (x)!) = ((2x+1)(2x-1)!)/(2^(x-1) (x-1)!) , but i don't quite remember factorial manipulation. I can recall that (x+1)! = (x+1)x! , but i can't remember if there's anything like this for (x-1)! or in this case, (2x-1)! as well.

any help is appreciated!
• Dec 17th 2008, 03:57 PM
o_O
They aren't equal. Take $x = 5$.

\begin{aligned} \text{LHS} & = \frac{(2x+1)!}{2^x \cdot x!} \\ & = \frac{(2(5)+1)!}{2^5 \cdot 5!} \\ & = \frac{11!}{32 \cdot 5!} \\ & = 10395 \end{aligned}.......... \begin{aligned} \text{RHS} & = \frac{(2x+1)!(2x-1)!}{2^{x-1} \cdot (x-1)!} \\ & = \frac{(2(5)+1)!(2(5)-1)!}{2^{5-1} \cdot (5-1)!} \\ & = \frac{11! \cdot 9!}{16 \cdot 4!} \\ & = 3.7721375 \times 10^{10} \end{aligned}
• Dec 17th 2008, 04:10 PM
spidey64
crap....

the proposition is:

1*3*5*...*(2x-1) = (2x-1)!/(2^(x-1) (x-1)!)

so i took the inductive step to (where x->x+1) :

1*3*5*...*(2x-1)*(2x+1) = (2x-1)!/(2^(x-1) (x-1)!) * (2x+1)

so i'm trying to get (2x-1)!/(2^(x-1) (x-1)!) * (2x+1) to equal

(2(x+1)-1)!/(2^((x+1)-1) ((x+1)-1)!) which equals (2x+1)!/(2^x (x)!), right?

or am i way off here?
• Dec 17th 2008, 04:20 PM
spidey64
Quote:

Originally Posted by o_O
They aren't equal. Take $x = 5$.

\begin{aligned} \text{LHS} & = \frac{(2x+1)!}{2^x \cdot x!} \\ & = \frac{(2(5)+1)!}{2^5 \cdot 5!} \\ & = \frac{11!}{32 \cdot 5!} \\ & = 10395 \end{aligned}.......... \begin{aligned} \text{RHS} & = \frac{(2x+1)!(2x-1)!}{2^{x-1} \cdot (x-1)!} \\ & = \frac{(2(5)+1)!(2(5)-1)!}{2^{5-1} \cdot (5-1)!} \\ & = \frac{11! \cdot 9!}{16 \cdot 4!} \\ & = 3.7721375 \times 10^{10} \end{aligned}

AH, my mistake, in the original post, i placed an extra factorial in the numerator, my second post reflects the REAL problem. sorry.
• Dec 17th 2008, 04:38 PM
o_O
Quote:

Originally Posted by spidey64
the proposition is:

$1 \cdot 3 \cdot 5 \cdots (2x-1) = \frac{(2x-1)!}{2^{x-1}(x-1)!}$
1*3*5*...*(2x-1) = (2x-1)!/(2^(x-1) (x-1)!)

Assume it is true for $n = k$, i.e. $1 \cdot 3 \cdot 5 \cdots (2k-1) = \frac{(2k-1)!}{2^{k-1}(k-1)!}$

It remains to show that it is also true for $n=k+1$, i.e. $1 \cdot 3 \cdot 5 \cdots (2k-1)(2k+1) = \frac{(2k+1)!}{2^{k} \cdot k!}$

Looking at the LHS:
\begin{aligned} \underbrace{1 \cdot 3 \cdot 5 \cdots (2k-1)}_{\text{Our assumption}}(2k+1) & = \frac{(2k-1)!}{2^{k-1}(k-1)!} \cdot (2k+1) \\ & = \frac{(2k+1)(2k-1)!}{2^{k-1}(k-1)!} \cdot {\color{red} \frac{2k}{2k}} \\ & = \frac{(2k+1){\color{red}2k}(2k-1)!}{{\color{red}2}\cdot 2^{k-1} \cdot {\color{red}k}(k-1)!}\end{aligned}

Can you change the numerator into a single factorial? Simplify the denominator as well. Then you should be good.
• Dec 17th 2008, 04:45 PM
spidey64
Quote:

Originally Posted by o_O
Assume it is true for $n = k$, i.e. $1 \cdot 3 \cdot 5 \cdots (2k-1) = \frac{(2k-1)!}{2^{k-1}(k-1)!}$

It remains to show that it is also true for $n=k+1$, i.e. $1 \cdot 3 \cdot 5 \cdots (2k-1)(2k+1) = \frac{(2k+1)!}{2^{k} \cdot k!}$

Looking at the LHS:
\begin{aligned} \underbrace{1 \cdot 3 \cdot 5 \cdots (2k-1)}_{\text{Our assumption}}(2k+1) & = \frac{(2k-1)!}{2^{k-1}(k-1)!} \cdot (2k+1) \\ & = \frac{(2k+1)(2k-1)!}{2^{k-1}(k-1)!} \cdot {\color{red} \frac{2k}{2k}} \\ & = \frac{(2k+1){\color{red}2k}(2k-1)!}{{\color{red}2}\cdot 2^{k-1} \cdot {\color{red}k}(k-1)!}\end{aligned}

Can you change the numerator into a single factorial? Simplify the denominator as well. Then you should be good.

Aha! yes! then the numerator merges into one (2k+1)! and the denom multiplies a 2^1 * 2^k-1 making it 2^k and merges the factorial to k! !!!
thanks a ton!