2

Hello I am trying to solve that the following expression is true for all positive integers n:

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

I know that this question needs to be proven by inductions. Please give me hint.

Cameron Williams
  • 29,432
user92821
  • 133
  • 7
  • Since you've identified induction as the proof method, you need a base case and an inductive step to do that. For the positive integers, what is the base case? Can you formulate how the inductive step should look? Inductive steps always assume that the relationship is true for $n$ and then seek to show that it is then also true for $n+1$. – Kevin Driscoll Sep 29 '13 at 23:53
  • The base case is $n=1$, but in that case the equation becomes $1\cdot 2=2^1\cdot 1$; there is no $3$ or $5$ in it. – Brian M. Scott Sep 30 '13 at 00:01
  • And how should I get the 3 and the 5? Using more terms of n+1, n+2, n+3?, because then a 4 would appear. – user92821 Sep 30 '13 at 00:04
  • @user92821 Once you've shown that the statement is true for $n=1$ then you need to do the inductive step, as manthanomen suggests. The 3,5,etc. will appear naturally there. – Kevin Driscoll Sep 30 '13 at 00:06
  • So would we get the base case from 2n-2=0 for both LHS and RHS? – user92821 Sep 30 '13 at 00:23

2 Answers2

1

To prove a statement using induction, you need to do two things. First, prove the statement for the smallest applicable value of $n$ (called the base case). In your case, this is $n = 1$ since the statement involves only positive integers. Next, prove that if the statement is true for an arbitrary value of $n$, then it's true for $n + 1$.

manthanomen
  • 3,186
1

HINT for the induction step:

$$\frac{(n+2)(n+3)\ldots(2n+2)}{(n+1)(n+2)\ldots(2n)}=\frac{(2n+1)(2n+2)}{n+1}=2(2n+1)\;;$$

what is

$$\frac{2^{n+1}\cdot1\cdot3\cdot\ldots\cdot(2n+1)}{2^n\cdot1\cdot3\cdot\ldots\cdot(2n-1)}\;?$$

Brian M. Scott
  • 616,228