0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – user187373 Oct 27 '14 at 4:51
  • $\begingroup$ Well, there's nothing really wrong. It's just that the professor asked me to do so $\endgroup$ – Adrian Oct 27 '14 at 4:55
  • $\begingroup$ He asked you to do what? $\endgroup$ – user187373 Oct 27 '14 at 4:55
  • $\begingroup$ To go from $n - 1$ to $n$ $\endgroup$ – Adrian Oct 27 '14 at 4:56
  • $\begingroup$ 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$. $\endgroup$ – user187373 Oct 27 '14 at 4:58
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}^+$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.