# (Inductive Proofs) Show why one inductive hypothesis works, and the other does not.

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!

-
Related (and possibly dupe): math.stackexchange.com/questions/119773/… –  Aryabhata Apr 6 '12 at 22:56
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$. –  André Nicolas Apr 7 '12 at 1:19

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.

-
I don't understand how the inductive step in a) may fail. For such thing to happen, the hypothesis would have to be false, but we know (e.g. by second part) it is true (or maybe we speak about different hypotheses?). Wrong proof is not a proof of impossibility. –  dtldarek Apr 6 '12 at 23:24
@dtldarek: Agreed. I think that the problem is very badly worded and have simply answered the question that was clearly intended. –  Brian M. Scott Apr 6 '12 at 23:33
Thanks for the help! Yeah, the topic was called "Strengthening the Inductive Hypothesis," not to be confused with Strong Induction. Is it important in eq. (1) that the sign is <= rather than simply <? In part b) I completed all steps an found P(k+1) to be true but I don't really know why I used <= in the proof. –  Maharlikans Apr 8 '12 at 4:24
@Maharlikans: I want to show that $\frac12\cdot\frac34\cdot\ldots\cdot\frac{2(k+1)-1}{2(k+1)}<\frac1{\sqrt{3k+1}}$‌​. I’ve already shown that it’s $<\frac1{\sqrt{3k}}\cdot\frac{2(k+1)-1}{2(k+1)}$, so showing that $\frac1{\sqrt{3k}}\cdot\frac{2(k+1)-1}{2(k+1)}<\frac1{\sqrt{3k+1}}$ would be overkill; it’s enough to show $\le$, as I wrote at $(1)$. Getting rid of the clutter: if I want $a<c$, and I’ve shown that $a<b$, it’s good enough to show that $b\le c$; I don’t need to show that $b<c$. –  Brian M. Scott Apr 8 '12 at 5:42
That makes total sense. Thanks a ton. –  Maharlikans Apr 8 '12 at 6:51