5
$\begingroup$

Here's a homework problem I have for my class about Discrete Mathematics:

Suppose that we want to prove that

$\frac12\cdot\frac34\cdot\ldots\cdot\frac{2n-1}{2n} < \frac1{\sqrt{3n}}$

for all positive integers $n$.

a) Show that if we try to prove this inequality using mathematical induction, the basis step works but the inductive step fails.

b) Show that mathematical induction can be used to prove the stronger inequality

$\frac12\cdot\frac34\cdot\ldots\cdot\frac{2n-1}{2n} < \frac1{\sqrt{3n + 1}}$

for all integers greater than $1$, which, together with a verification for the case where $n = 1$, establishes the weaker inequality we originally tried to prove using mathematical induction.

I'm not sure how to proceed in the inductive step. I have

$\begin{align*}P(k)&: \frac12\cdot\frac34\cdot\ldots\cdot\frac{2k-1}{2k} < \frac1{\sqrt{3k}}\\ P(k+1)&:\frac12\cdot\frac34\cdot\ldots\cdot\frac{2(k+1)-1}{2(k+1)} < \frac1{\sqrt{3(k+1)}} \end{align*}$

then from that point (which is the very beginning) I'm stumped. This answer exists on Yahoo! Answers, but there's no explanation to the technique. Neither my friends nor my professor have given me a clear step by step answer to the problem. If someone could, it'd be very much appreciated!

  • 0
    What the not well-worded (a) presumably means is that given an (unknown) $f(k)$ such that f(k)<\frac{1}{\sqrt{3k}}, we cannot deduce that f(k)\frac{2k+1}{2k+2}<\frac{1}{\sqrt{3k+1}}. It is an interesting fact that sometimes to prove a result by induction, the natural approach is to prove a stronger result. A simpler example would be proving that \sum_1^n \frac{1}{i(i+1)}<1. Using **only** \sum_1^k \frac{1}{i(i+1)}<1, nothing else, we cannot show that \sum_1^{k+1} \frac{1}{i(i+1)}<1.2012-04-07

1 Answers 1

5

For (a), the first thing to do is show that the basis step works, i.e., that $P(1)$ is true. $P(1)$ says that $\frac12<\frac1{\sqrt3}$; since $2>\sqrt3$, this is true. The second part of (a) is to show that you can’t make the induction step work; that is, you can’t assume $P(k)$ and deduce $P(k+1)$. The natural way to try to start the induction step is this:

$\begin{align*} \frac12\cdot\frac34\cdot\ldots\cdot\frac{2(k+1)-1}{2(k+1)}&=\left(\frac12\cdot\frac34\cdot\ldots\cdot\frac{2k-1}{2k}\right)\cdot\frac{2(k+1)-1}{2(k+1)}\\ &<\frac1{\sqrt{3k}}\cdot\frac{2(k+1)-1}{2(k+1)}\;, \end{align*}$

because the induction hypothesis $P(k)$ says that the product in the large parentheses is less than $\frac1{\sqrt{3k}}$.

Then you’d want to show that $\frac1{\sqrt{3k}}\cdot\frac{2(k+1)-1}{2(k+1)}\le\frac1{\sqrt{3(k+1)}}\;,\tag{1}$ from which $P(k+1)$ would follow immediately. $(1)$ can be simplified to $\frac{2k+1}{2(k+1)\sqrt{3k}}\le\frac1{\sqrt{3k+3}}\;.\tag{2}$ Unfortunately, when we substitute $k=1$ into this, we get $\frac3{4\sqrt3}\le\frac1{\sqrt6}\;,$ which is equivalent to $3\sqrt6\le4\sqrt3$, which implies (by squaring) that $9\cdot 6\le 16\cdot 3$, or $54\le 48$. Since this is obviously false, the natural approach to the induction step simply cannot work.

In fact the same idea can be applied to $(2)$ without substituting a value for $k$: it’s equivalent to $(2k+1)\sqrt{3k+k}\le2(k+1)\sqrt{3k}$, which implies that $3(2k+1)^2(k+1)\le12k(k+1)^2$ and hence that $(2k+1)^2\le4k(k+1)$, i.e., that $4k^2+4k+1\le4k^2+4k$, which is clearly false.

I’ll leave you to try (b) on your own for now. For the induction step try to follow the pattern that didn’t work above.

  • 0
    That makes total sense. Thanks a ton.2012-04-08