Answer to Question #217656 in Discrete Mathematics for Ali Haider

Question

(b) For any natural number n, prove the validity of given series by mathematical induction:

Answer 1

For any natural number n, prove the validity of given series by mathematical induction:

$$2(\sqrt{n+1}-1)<1+(\dfrac{1}{\sqrt{2}})+...+(\dfrac{1}{\sqrt{n}})<2\sqrt{n}$$

Let $P(n)$ be the proposition that for the first $n$ positive integers

$$2(\sqrt{n+1}-1)<1+(\dfrac{1}{\sqrt{2}})+...+(\dfrac{1}{\sqrt{n}})<2\sqrt{n}$$

BASIS STEP: $P(1)$ is true, because

$$2(\sqrt{1+1}-1)<1<2\sqrt{1}$$

$$2(\sqrt{2}-1)<1<2$$

INDUCTIVE STEP: For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary positive integer $k.$ That is, we assume that

$$2(\sqrt{k+1}-1)<1+(\dfrac{1}{\sqrt{2}})+...+(\dfrac{1}{\sqrt{k}})<2\sqrt{k}$$

Under this assumption, it must be shown that $P(k+1)$ is true, namely, that

$$2(\sqrt{(k+1)+1}-1)<1+(\dfrac{1}{\sqrt{2}})+...+(\dfrac{1}{\sqrt{k}})$$

$$+(\dfrac{1}{\sqrt{k+1}})<2\sqrt{k+1}$$

We have that

$$2(\sqrt{k+1}-1)+(\dfrac{1}{\sqrt{k+1}})<1+(\dfrac{1}{\sqrt{2}})+...+(\dfrac{1}{\sqrt{k}})+(\dfrac{1}{\sqrt{k+1}})$$

$$<2\sqrt{k}+(\dfrac{1}{\sqrt{k+1}})$$

Show that

$$2(\sqrt{k+2}-1)<2(\sqrt{k+1}-1)+(\dfrac{1}{\sqrt{k+1}})$$

$$2(\sqrt{k+2}-\sqrt{k+1})<\dfrac{1}{\sqrt{k+1}}$$

$$\dfrac{2(k+2-k-1)}{\sqrt{k+1}+\sqrt{k+2}}<\dfrac{1}{\sqrt{k+1}}$$

$$\dfrac{2}{\sqrt{k+1}+\sqrt{k+2}}<\dfrac{1}{\sqrt{k+1}}$$

$$\dfrac{2}{\sqrt{k+1}+\sqrt{k+2}}<\dfrac{2}{\sqrt{k+1}+\sqrt{k+1}}=\dfrac{1}{\sqrt{k+1}},$$

True for $k\geq1.$

Show that

$$2\sqrt{k}+(\dfrac{1}{\sqrt{k+1}})<2\sqrt{k+1}$$

$$\dfrac{2(k+1-k)}{\sqrt{k}+\sqrt{k+1}}>\dfrac{1}{\sqrt{k+1}}$$

$$\dfrac{2}{\sqrt{k}+\sqrt{k+1}}>\dfrac{1}{\sqrt{k+1}}$$

$$\dfrac{2}{\sqrt{k}+\sqrt{k+1}}>\dfrac{2}{\sqrt{k+1}+\sqrt{k+1}}=\dfrac{1}{\sqrt{k+1}}$$

True for $k\geq1.$

We show that $P(k+1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all positive integers $n.$

That is, we have proven that for any natural number $n,$

$$2(\sqrt{n+1}-1)<1+(\dfrac{1}{\sqrt{2}})+...+(\dfrac{1}{\sqrt{n}})<2\sqrt{n}$$