Part of an induction question

Question

I might have done or not realize something stupid, but I can't seem to prove the following...

Inductive hypothesis

Assume $\exists$k$\in$N such that P(k) is true.

P(k): $\frac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot (2k - 1)}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot (2k)}$ $\leq$ $\frac{1}{\sqrt{k + 1}}$

Inductive step

Prove P(k+1) is true.

P(k+1): $\frac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot [2(k + 1) - 1]}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot [2(k + 1)]}$ $\leq$ $\frac{1}{\sqrt{(k + 1) + 1}}$

$\frac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot [2(k + 1) - 1]}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot [2(k + 1)]}$

= $\frac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot (2k - 1) \cdot [2(k + 1) - 1]}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot (2k) \cdot [2(k + 1)]}$

$\leq$ $\frac{1}{\sqrt{k + 1}}$ $\cdot$ $\frac{2(k + 1) - 1}{2(k + 1)}$ #by IH

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

$\leq$ $\frac{2(k + 1)}{2(k + 1) \cdot \sqrt{k + 1}}$

= $\frac{1}{\sqrt{k + 1}}$

So what I seem to have done is proven that $\frac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot [2(k + 1) - 1]}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot [2(k + 1)]}$ $\leq$ $\frac{1}{\sqrt{k + 1}}$ and not $\frac{1}{\sqrt{(k + 1) + 1}}$. I seem to need a minor adjustment somewhere.

Answer 1

You have given away too much. You want to prove that $$\frac{2k+1}{2(k+1)\sqrt{k+1}}\lt \frac{1}{\sqrt{k+2}}.$$ Equivalently, you want to prove that $(2k+1)^2(k+2)\lt 4(k+1)^3$. Expand, and the result will drop out.

Answer 2

We first (directly) prove: $$\frac{1}{\sqrt{k+1}}\cdot\frac{2k+1}{2k+2} < \frac{1}{\sqrt{k+2}}$$ for $k>1$. Starting with: $$9k+2<12k+4$$ which is obviously true for $k>1$. Then, we add $4k^3+12k^2$ to both sides: $$4k^3+12k^2+9k+2<4k^3+12k^2+12k+4$$ Splitting and factoring: $$4k^3+4k^2+k+8k^2+8k+2<4k^3+8k^2+4k+4k^2+8k+4$$ $$(4k^2+4k+1)(k+2)<(4k^2+8k+4)(k+1)$$ $$(2k+1)^2(k+2)<(2k+2)^2(k+1)$$ Taking square roots: $$(2k+1)\sqrt{k+2}<(2k+2)\sqrt{k+1}$$ Dividing by $(2k+2)\sqrt{k+1}\sqrt{k+2}$ on both sides: $$\frac{1}{\sqrt{k+1}}\cdot\frac{2k+1}{2k+2} < \frac{1}{\sqrt{k+2}}$$ Now we start the induction step: $$\frac{1 \cdot 3 \cdot 5 \cdots[2k-1] [2(k + 1) - 1]}{2 \cdot 4 \cdot 6 \cdots [2k][2(k + 1)]} \leq \frac{1}{\sqrt{k + 1}}\cdot \frac{2(k+1)-1}{2(k+1)}=\frac{1}{\sqrt{k + 1}}\cdot \frac{2k+1}{2k+2}<\frac{1}{\sqrt{k + 2}}$$ There is our desired result! Q.E.D.