0

For this question, I know how to do the base case and the inductive hypothesis but I'm having trouble with the inductive step. Here is what I have so far. Can anyone please help me out?

Prove by induction that for all integers $n\ge2$

$\sqrt n < \sum_{i=1}^n \frac{1}{\sqrt n }$

Base Case:

n = 2

$\sqrt 2 < 1 + \frac{1}{\sqrt 2}$

Inductive Hypothesis:

Let k be an arbitrary integer such that $k\ge2$

$\sqrt k < \sum_{i=1}^k \frac{1}{\sqrt n }$

Inductive Step:

Show true for k+1

$\sqrt{k+1} < \sum_{i=1}^{k+1} \frac{1}{\sqrt n }$

user325
  • 11
  • 3

1 Answers1

0

Your inequality is backwards. After fixing this, establishing the inductive step amounts to proving the following inequality: $$ \sqrt n + \frac{1}{\sqrt{n+1}}>\sqrt{n+1}. $$ You can prove it by moving the fraction to the right side, to obtain the equivalent inequality $$ \sqrt n >\sqrt{n+1}-\frac{1}{\sqrt{n+1}}. $$ You can combine the fractions on the right side using a common denominator as follows: $$ \sqrt{n+1}-\frac{1}{\sqrt{n+1}}=\frac{n+1}{\sqrt{n+1}}-\frac{1}{\sqrt{n+1}}=\frac{n}{\sqrt{n+1}}. $$ Thus the inequality that remains to be proven is $$ \sqrt n>\frac{n}{\sqrt{n+1}}, $$ which is equivalent to $$ \sqrt{n+1}>\sqrt{n} $$ after multiply both sides by $\sqrt{n+1}$ and then dividing by $\sqrt{n}$.

pre-kidney
  • 30,223
  • Oh so this is essentially a proof by contrapositive then? – user325 Jan 25 '20 at 23:49
  • No, I am saying that you messed up the inequality sign of what you wanted to prove. So I changed your question to use the other sign. Then I used a usual proof by induction. No contrapositive involved. – pre-kidney Jan 25 '20 at 23:50
  • Also shouldn't we use another variable like k, since that is the inductive hypothesis? – user325 Jan 25 '20 at 23:57
  • Oh I see what you're saying now. For the actual proof you flip the inequality sign – user325 Jan 25 '20 at 23:58
  • How did we get root n plus 1 over root n plus 1 in your first line on the left side of the inequality? – user325 Jan 26 '20 at 00:28
  • If you write out what the inductive step is saying explicitly, you will see that you can substitute the inductive hypothesis to cover all but one of the terms in the sum. The remaining term is where the $1/\sqrt{n+1}$ comes from. The $\sqrt{n}$ is from the inductive hypothesis. – pre-kidney Jan 26 '20 at 00:33
  • Ah yes I see now. Do we need to use n or can we use another variable like k? Because in the inductive hypothesis we're supposed to use another arbitrary integer to show that the claim is true – user325 Jan 26 '20 at 00:47