1
$\begingroup$

Prove by induction that

(a) $n! > n^3$ for every $n \ge 6$.

(b) prove $\frac{(2n)!}{n!2^n}$ is an integer for every $n\geq 1$

I'm quite terrible with induction so any help would be appreciated.

$\endgroup$
4
  • $\begingroup$ So far I've done the base case which is easy: 6! > 6^3 or 720 > 216. Setting up the induction step is a bit more tricky. Letting n = k I get k! > k^3 for k >= 6 (P(k)) and then I believe we let n = k + 1 and that's really where I get confused, I don't know how to show P(k+1) holds. $\endgroup$ Oct 9, 2013 at 14:53
  • $\begingroup$ As it stands, part (b) isn't a statement, but an expression. Please check to make sure you've typed it correctly. $\endgroup$ Oct 9, 2013 at 15:04
  • $\begingroup$ Alright, thanks for the heads up, I edited it. $\endgroup$ Oct 9, 2013 at 15:07
  • $\begingroup$ Not proposing to close, just linking to the node of this network of duplicates. This post here is older, but it is less focused. $\endgroup$ Feb 6, 2020 at 20:11

2 Answers 2

2
$\begingroup$

In part b, you have an interesting expression. What we will prove there is that $$\frac{(2n)!}{n!2^n}=1\times 3\times 5\times\cdots \times 2n-1,$$ the product of the first $n$ odd numbers.

Base case: $\frac{(2\times1)!}{1!2^1}=1$.

This tells us that when we plug $n=1$ into the above equation, we get the result of multiplying the first odd number, $1$.

Inductive step:

We first state the inductive hypothesis. This is that $$\frac{(2n-2)!}{(n-1)!2^{n-1}}=1\times 3\times 5\times\cdots\times 2n-3.$$ Now we compute $$\frac{(2n)!}{n!2^n}=\frac{2n(2n-1)}{2n}\frac{(2n-2)!}{(n-1)!2^{n-1}}=(2n-1)\frac{(2n-2)!}{(n-1)!2^{n-1}}=\\ 1\times 3\times 5\times\cdots\times 2n-3\times 2n-1,$$ which is he product of the first $n$ odd numbers, which is in fact an integer.

Note that we have proved a bit more than you wanted. Note that this is essentially the same proof that Martin gave, except we are keeping track of a little bit more. Note only did we prove the expression to be an integer, we describe what the integer is in a nice way. This should tell us that when we prove something by induction, it behooves us to look at it closely to see if we can squeeze more information out of the proof. A nice exercise is to find an expression for the first $n$ even numbers.

$\endgroup$
2
$\begingroup$

(a) $n! > n^3$ for every $n \geq 6$

For the induction base, we simple have to show that $6! \geq 6^3$. Hence, $6 * 5 * 4 * (3 * 2) * 1 \geq 6*6*6$. Hence $6 * 6 * (5 * 4) \geq 6^3$. This is evidently true, as $5*4 = 20 > 6$.

For the induction step, we have to show that $(n+1)! \geq (n+1)^3$ for $n\geq 6$. Now suppose $n! > n^3$ is true for all $n \geq 6$. Then $(n+1)! = (n+1)n! \geq (n+1)n^3$.

Hence, we are done if $(n+1)n^3 \geq (n+1)^3$ for $n\geq 6$. Thus, we need to show that $n^4 + n^3 \geq n^3 + 3n^2 + 3n + 1$ for $n\geq 6$.

Rearranging yields $n^4 - 3n^2 - 3n - 1 \geq 0$ for $n\geq 6$. The second derivative of this is $12n^2 - 6$, which is strictly convex for $n\geq 6$. Hence, we are through if both $f(n) := n^4 - 3n^2 - 3n - 1 \geq 0$ and $f'(n) = 4n^3 -6n - 3 \geq 0$ for $n=6$. This is trivial to check.

(b) $\frac{(2n)!}{n! 2^n}$ is an integer for every $n\geq 1$.

The induction base is trivial: simply insert $n=1$.

For the induction step, we need to show that $\frac{(2(n+1))!}{(n+1)^2 2^{n+1}} = \frac{(2n+2)!}{(n+1)n! * 2 * 2^n} = \frac{(2n+2)(2n+1)}{2(n+1)} * \frac{(2n)!}{n! 2^n}$ is an integer for all $n\geq 1$.

Now, by the induction hypothesis, the right multiplicand must be an integer. Hence, it suffices to show that the left multiplicand must be an integer as well. Since $(2n+2) = 2(n+1)$, this is obviously the case.

$\endgroup$
1
  • $\begingroup$ Thanks so much, I appreciate it! $\endgroup$ Oct 9, 2013 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .