1
$\begingroup$

I am attempting to use Induction to prove this, but I am not sure if it is the right method to take. Here is what I have tried:

Induction Hypothesis: Assume $P(k)$ is true for some fixed $ k \geq 1$ or $ 2^k | \frac {2k!}{2k-k!} $

Induction Step: Prove that $P(k+1)$ is true.

$$ P(k+1)=P(2(k+1),k)= \frac{2(k+1)!}{(2(k+1)-k)!} $$

$$ = \frac {2(k+1)k!}{2k+2-k)!} $$ $$ = \frac {2(k+1)k!}{(k+2)!} $$

and this is where I am stuck, I know I can't distribute the factorials through. I am not even sure that this is the right approach. Any hints or tips would be greatly appreciated.

  • 0
    Don't conflate an expression with a proposition. Define $P$.2011-11-10
  • 0
    do you mean something along the lines of $P(k)=P(2k,k)=\frac{2k!}{(2k-k)!}$?2011-11-10
  • 1
    Either that or as a proposition; in either case you'll have to adapt the question accordingly, because you've used it both as a proposition and as a number in the question. Also your use of parentheses is rather haphazard; there seem to be quite a number of them missing.2011-11-10

2 Answers 2

1

The following is an induction argument, but the way it is written out, it doesn't look like it. We are looking at $$\frac{(1)(2)(3)(4)\cdots(2n)}{n!}$$ Separate out the odd terms on top. We get $$\frac{[(1)(3)(5)\cdots(2n-1)][(2)(4)(6)\cdots (2n)]}{n!}.$$
But $(2)(4)(6)\cdots(2n)=2^n n!$. So our quotient is $$2^n(1)(3)(5)\cdots(2n-1).$$ We conclude that $2^n$ divides our original expression. Not only that, it is the highest power of $2$ that does.

The idea can be turned into a textbook style induction. We prove that the highest power of $2$ that divides $P(2n,n)$ is $2^n$. The result is clearly true at $n=1$. Suppose it is true at $n=k$. We show that it is true at $n=k+1$. Note that $$P(2k,k)=(2k)(2k-1)\cdots (k+2)(k+1),$$ and $$P(2k+2,k+1)=(2k+2)(2k+1)(2k)\cdots (k+2).$$ Divide, noting that most of the terms cancel. We get $$\frac{P(2k+2, k+1)}{P(2k,k)}=\frac{(2k+2)(2k+1)}{k+1}=2(2k+1),$$ and therefore $$P(2k+2,k+1)=2(2k+1)P(2k,k).$$ Thus if $2^k$ is the highest power of $2$ that divides $P(2k,k)$, then $2^{k+1}$ is the highest power of $2$ that divides $P(2k+2,k+1)$.

Comment: Induction is exceedingly common, and usually not noticed. Roughly speaking, when we manipulate an expression that involves $\dots$, there is induction going on,

  • 0
    $P(2k,k)=2^k(2k-1)!!$ where $(2k-1)!!$ is the [double factorial](http://en.wikipedia.org/wiki/Factorial#Double_factorial), which is odd.2011-11-10
1

I assume the problem is to show that $2^k|P(2k,k)$ for all $k\in\mathbb{Z}$, where $P(a,b)=a!/(a-b)!$, using induction. There are two major issues with what you've written: first, you refer to $P$ as if it were a proposition or hypothesis, when in reality it is an expression. Now $P =\mathrm{blah}$ is a statement, and that is the form of the theorem and the hypothesis. Second, when putting $n+1$ into the expression you made an error: you only replaced one of the $n$'s in $P(2n,n)$, when you need to replace all copies.

The correct argument might begin like:

Induction Hypothesis: $2^n|P(2n,n)$ for the particular number $n$.

Induction Step: Observe

$$P(2(n+1),(n+1))=\frac{(2n+2)!}{(n+1)!}.$$

Recall that $P(2n,n)=(2n)!/n!$; show that the above is $2$ times a multiple of $P(2n,n)$, hence $2^{n+1}$ divides the new expression $P(2(n+1),(n+1))$. Can you do this and fill in the rest?

  • 0
    Yes absolutely... They key was I looked over that the equation is $ P(2(n+1),(n+1))$ not $P(2(n+1),n)$. Thank you so much for catching my oversight.2011-11-10