# Mathematical Induction help

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.

-
Not linear algebra, so I removed the tag. – Andres Caicedo Apr 30 '11 at 16:48
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

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?

-

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

-

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.

-