# Proof by Induction(Verification)

inductionproof-writingsolution-verification

Can someone verifies this proof and maybe tell me if my induction layout and terms are correct. Thanks in advance.

Proof that $$\displaystyle \sum_{n=1}^{m} \frac{1}{\sqrt{n}} \leq 2\sqrt{m}-1 \tag{1}$$

Proof:
Base step: $$m = 1$$
$$\frac{1}{\sqrt{1}} = 2\sqrt{1} – 1 \tag{2}$$
Induction Hypothesis: Suppose that (1) is true for $$m = k$$

Induction Step:
$$\sum_{n=1}^{k} \frac{1}{\sqrt{n}} + \sum_{n=k+1}^{k+1} \frac{1}{\sqrt{n}} \leq 2\sqrt{k+1}-1 \tag{3}$$
Use induction hypothesis and rewrite:
$$2\sqrt{k}-1 + \frac{1}{\sqrt{k+1}} \leq 2\sqrt{k+1}-1 \tag{4}$$
Bring down to a common denominator:
$$\frac{(2\sqrt{k}-1)(\sqrt{k+1})}{\sqrt{k+1}} + \frac{1}{\sqrt{k+1}} \leq 2\sqrt{k+1}-1 \tag{5}$$
$$\frac{2\sqrt{k}\sqrt{k+1}-\sqrt{k+1} + 1}{\sqrt{k+1}} \leq 2\sqrt{k+1}-1 \tag{6}$$
Multiply by $$\sqrt{k+1}$$ and simplify:
$$2\sqrt{k}\sqrt{k+1}-\sqrt{k+1} + 1 \leq 2k+2-\sqrt{k+1} \tag{7}$$
$$2\sqrt{k}\sqrt{k+1} \leq 2k+1 \tag{8}$$
Square and simplify:
$$4k(k+1) \leq 4k^{2}+4k+1 \tag{9}$$
$$4k^{2}+4k \leq 4k^{2}+4k+1 \tag{10}$$
$$0 \leq 1 \tag{11}$$

$$\blacksquare$$

Edit:
If I understand the answers correctly, the proof should go like this:
We are currently at equation (6).
We will use the following inequality to see why (6) is true:
$$4k^{2}+4k \leq 4k^{2}+4k+1$$
Rewrite and take the squareroot.
$$4k(k+1) \leq (2k+1)^{2}$$
$$2\sqrt{k}\sqrt{k+1} \leq 2k+1$$
Subtract $$\sqrt{k+1}$$ from both sides and add 1 to both sides.
$$2\sqrt{k}\sqrt{k+1} -\sqrt{k+1} + 1\leq 2k+2 -\sqrt{k+1}$$
Rewrite:
$$2\sqrt{k}\sqrt{k+1} -\sqrt{k+1} + 1\leq 2(k+1) -\sqrt{k+1}$$
$$2\sqrt{k}\sqrt{k+1} -\sqrt{k+1} + 1\leq 2\sqrt{k+1}\sqrt{k+1} -\sqrt{k+1}$$
Divide by $$\sqrt{k+1}$$ and observe that it is equation (6).
$$\blacksquare$$

@GerryMyerson's comment is a really important one! I have seen many students get into trouble going about writing inductive proofs the way you do it, so I'd like to elaborate on its danger.

So yes, I have seen many proofs that end with something to the effect of $$0=0$$ ... followed by a triumphant QED! or Check!

But the problem is that of course $$0=0$$ ... showing that $$0=0$$ therefore does not mean anything at all.

Likewise, your proof establishes that $$0\leq 1$$ ... so what?!?

As Gerry says, with your method you start with $$LHS\leq RHS$$, and end with $$0\leq 1$$, while what you really need to end with is $$LHS\leq RHS$$

For example, suppose that in some other inductive proof I need to show that $$LHS = RHS$$.

Now, with the method of starting with $$LHS=RHS$$, I could proceed as follows:

$$1. LHS = RHS$$

$$2. LHS*0 = RHS*0$$ (from 1)

$$3. 0=0$$ (from 2)

Check!

OK, I think you see the problem: the steps are not reversible (in particular, 1 does not follow from 2). If between all steps you could put a 'if and only if', you'd be good. While I didn't look at all at the details of your proof, I assume that is in fact the case for your proof, and many people would therefore find it acceptable.

Still, by starting with what you need to end up with, you have reversed the natural flow we want to think about the proof, and it is therefore easy to make a mistake that is far more subtle ... but basically follows the above pattern. So, my very strong recommendation is to write the proof so that you end with what you need to prove.

Of course, how do you find such a proof? Well, for that, you'd indeed probably go the other way around. That is, for the discovery process, you'd probably work backwards the way you did .... but for the proof, you really should go forwards (which then also forms a check for yourself that what you did is in fact correct).