Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assumption: $$(n+1)(n+2) \cdots (2n) = (2^n)\cdot 1 \cdot 3 \cdot 5 \cdots (2n-1)$$

Prove for $n+1$:

$$(n+2)(n+3) \cdots (2(n+1)) = (2^{n+1}) \cdot 1 \cdot 3 \cdot 5 \cdots (2(n+1)-1)$$

Using the assumption, I divide both sides by $(n+1)$ and substitute RHS into my $n+1$ equation, however it does not equate.

share|improve this question
1  
Not linear algebra, so I removed the tag. –  Andres Caicedo Apr 30 '11 at 16:48
7  
Do you see why the equality is true? Not by induction, but: Multiply both sides by $n!$. On the left, you get $(2n)!$. On the right you get $n!2^n 1\cdot 3\cdots(2n-1)$. Do you see why these two expressions are the same? (If you don't, play with a few examples: Take $n=3$, say, and rewrite the right hand side as $6!$. Once you understand how this works, an inductive argument should be easy. –  Andres Caicedo Apr 30 '11 at 16:50
    
@Andres: +1 for working with small examples. –  Hans Parshall Apr 30 '11 at 16:58

3 Answers 3

up vote 4 down vote accepted

My approach would be to "massage" the assumed equation to look more like the desired equation.

Hint: Try multiplying the assumed equation by 2. What's missing from the left side after this step? What's missing from the right side?

share|improve this answer

Assumption

$$C(n) := (n+1)(n+2) \cdots (2n) = (2^n)\cdot 1 \cdot 3 \cdot 5 \cdots (2n-1)$$

Proof

Basis:

$$2=2^1$$

Inductive step:

$$C(n+1):= (n+2)(n+3) \cdots (2(n+1)) = (2^{n+1}) \cdot 1 \cdot 3 \cdot 5 \cdots (2(n+1)-1)$$

$$We\ have\ to\ prove: C(n) \Rightarrow C(n+1)$$

$$\vdots$$

$$Little\ substitution:$$

$$(n+2)(n+3) \cdots (2n)(2n+1)(2n+2) = (n+1)(n+2) \cdots (2n) \cdot 2 \cdot (2n+1)$$

$$That\ leaves\ us\ with:$$

$$(2n+2) = 2 \cdot (n+1)$$

share|improve this answer

HINT $\ $ Dividing the second equation by the first yields the identity

$$\rm\frac{(2\:n+1)\ (2\:n+2)}{n+1}\ =\ \ 2\ (2\:n+1) $$

Thus the second equation is simply $\rm\ 2\ (2\:n+1)\ $ times the first equation.

Alternatively one can easily reduce the induction to a trivial induction that a product of 1's equals 1, see my prior posts on (multiplicative) telescopy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.