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.

  • 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