# Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$

Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$

I want to do the $n - 1 \rightarrow n$ induction step.

But I'm confused as to what my base case is. Usually if I want to do the $n \rightarrow n + 1$ induction, step, I start with $n = 1$ as my base case. But if I want to start with $n - 1$ would I be starting with 0?...But that doesn't really make sense since $i = 1$ already.

• What's wrong with taking $n=1$ as your base case? Whether you go from $n-1$ to $n$ or $n$ to $n+1$ doesn't really change this. If in your induction step you go from $n-1$ to $n$, you'll assume that $n-1 \geq 1$ and that you've already proved the result for $n-1$. – user187373 Oct 27 '14 at 4:51
• Well, there's nothing really wrong. It's just that the professor asked me to do so – Adrian Oct 27 '14 at 4:55
• He asked you to do what? – user187373 Oct 27 '14 at 4:55
• To go from $n - 1$ to $n$ – Adrian Oct 27 '14 at 4:56
• That's fine. There's no contradiction between that and taking $n=1$ as your base case. Think of it this way. You'll be assuming that the result is true for $n = k-1$ where $k$ is some integer $\geq 2$. Then you prove that it's true for $n = k$. Except that you phrase your proof in terms of $n-1$ and $n$ instead of $k-1$ and $k$ because it doesn't really make a difference, and it's simpler to write. You're never forced to consider the statement when $n=0$. The smallest that $n-1$ can be in the induction step is $1$. – user187373 Oct 27 '14 at 4:58

Take n = 1 as your base case. Note that for n = 0 the inequality does not hold:

0 is not less than or equal to $2\sqrt{0} - 1 = -1$

Induction still works because you are assuming the $n-1$ case to imply the $n$ case. You do not need to plug $1$ into $n-1$ or anything of the sort.

Let $$P(n)$$ be the statement that $$\sum_{i=1}^n \frac{1}{\sqrt{i}} \leq 2\sqrt{n}-1$$.

Base case: $$n=1$$ \begin{align*} \sum_{i=1}^1 \frac{1}{\sqrt{i}} &= \frac{1}{\sqrt{1}} \\ &= 1 \\ (2\sqrt{1}-1) &= 1 \quad \therefore P(1) \text{ is true} \end{align*}

Assume $$\sum_{i=1}^k \frac{1}{\sqrt{i}} \leq (2\sqrt{k}-1)$$ is true for some $$k\in\mathbb{Z}^+$$. \begin{align*} \because 4k^2+4k &\leq 4k^2 + 4k+1,\\ 4k(k+1) &\leq (2k+1)^2 \\ 2\sqrt{k}\sqrt{k+1} &\leq 2k+1\\ 1 &\leq 2(k+1) - 2\sqrt{k}\sqrt{k+1}\\ \frac{1}{\sqrt{k+1}} &\leq 2\sqrt{k+1} -2\sqrt{k} \\ \frac{1}{\sqrt{k+1}} &\leq (2\sqrt{k+1}-1) -(2\sqrt{k}-1) \end{align*}

coupling this result with the assumption, we have: \begin{align*} \sum_{i=1}^k \frac{1}{\sqrt{i}} + \frac{1}{\sqrt{k+1}} &\leq (2\sqrt{k}-1) + (2\sqrt{k+1}-1) -(2\sqrt{k}-1) \\ \sum_{i=1}^{k+1} \frac{1}{\sqrt{i}} &\leq 2\sqrt{k+1}-1 \therefore P(k) \text{ is true implies } P(k+1) \text{ is true} \end{align*}

Therefore, by mathematical induction, $$P(n)$$ is true $$\forall n\in\mathbb{Z}^+$$.