2
$\begingroup$

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.

  • 0
    @Andres: +1 for working with small examples.2011-04-30

3 Answers 3

4

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?

2

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)$

2

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.

  • 0
    Could you elaborate on how to approach this using multiplicative telescopy?2016-07-27