Question

Prove that \(\sqrt{n+1}-\sqrt{n}=O(\sqrt{n}\).
No idea how to start. Hints please?

Answer 1

Multiply by a creative use of "1." Hint, think of the conjugate of \[\sqrt{n+1} - \sqrt{n}\]

Answer 2

Also, write out the definition of Big O of a function again. Write it here so everyone can see and be on the same page, sometimes books use slightly different definitions

Answer 3

@blockcolder What is the "O" on the right hand side of the equation?

Answer 4

f(x) is O(g(x)) if \(|f(x)| \leq C|g(x)|\) for sufficiently large x.

Answer 5

Going by @domu 's advice, I got \(\large \sqrt{n+1}-\sqrt{n}=\frac{1}{\sqrt{n+1}-\sqrt{n}}\)
I suppose the next step is to bound that last one above?

Answer 6

Said otherwise

\[\lim_{x \rightarrow \infty} \frac{ f(x) }{ g(x) } =C\]

Answer 7

Yup yup, your on the right path. Though that " - " sign in the denominator should be a " + " Everything else is looking good so far!

Answer 8

Does this look ok?
\[\frac{1}{\sqrt{n+1}+\sqrt{n}}<\frac{1}{2\sqrt{n}}<\frac{1}{\sqrt{n}}<\sqrt{n}\]
since we're considering large n.

Answer 9

Looks good to me! Another way would be to note that the left hand side tends to 0 as n gets large. Your answer is much more concrete though and I like it : ) Nice work

Answer 10

Thanks for the help.