So, How can we use algebraic manipulation to prove the limit of a sequence?

[Bennigan88]

I am trying to prove that $$\lim\left[\sqrt{n^2+n}-n\right]=\frac{1}{2}$$
Where $n \in \mathbb{N}$ and $\lim$ is the limit of a sequence as $n\to\infty$.

From the definition of a limit, I know that I need to show that $$\exists{N}:n>N\Rightarrow\left|\sqrt{n^2+n}-n-\frac{1}{2}\right| < \epsilon$$

Through algebraic manipulation I was able to arrive at
$$\left| \sqrt{n^2+n} - n - \frac{1}{2} \right| = \left| \frac{n-\sqrt{n^2+n}}{n+ \sqrt{n^2+n}} \right|$$

Which now means that I must show that
$$\exists N : n>N \Rightarrow \left| \frac{n-\sqrt{n^2+n}}{n+ \sqrt{n^2+n}} \right| < 2\epsilon$$

The problem here is I'm not sure how this makes the proof any easier. It seems like now I must start with the assumption that this part is less than $2\cdot\epsilon$ but I don't see how to isolate n in this inequality. Any nudge in the right direction (no spoilers, please!) would be greatly appreciated.

 

[Mandelbroth]

I am trying to prove that $$\lim\left[\sqrt{n^2+n}-n\right]=\frac{1}{2}$$

...Limit of what? You need to define what your limit is doing.

 

[Bennigan88]

Fixed.

 

[LCKurtz]

Which now means that I must show that
$$\exists{N} : n>N \Rightarrow \left| \frac{\sqrt{n^2+n}}{\sqrt{n^2+n}+n} \right|< 2 \cdot \epsilon$$

The problem here is I'm not sure how this makes the proof any easier. It seems like now I must start with the assumption that this part is less than $2\cdot\epsilon$ but I don't see how to isolate n in this inequality. I am also having a difficult time seeing how I can find a lower bound of the LHS of the last inequality in order to simplify the problem. Any nudge in the right direction (no spoilers, please!) would be greatly appreciated.

I would try dividing numerator and denominator of the left side by $\sqrt{n^2+n}$ and see if that helps. Maybe you can get all the $n$'s under the square root.

[Edit] Apparently you solved it while I was typing.

 

[Bennigan88]

Nope, still haven't solved this one. Came very close, filled up my hand-held whiteboard with stuff, but it fell apart at the last minute because of one little error at the beginning. I'm still working on it now.

 

[Bennigan88]

I think I have $\left| \sqrt{n^2+n} - n - \frac{1}{2} \right| < 2\epsilon \Rightarrow \left( \sqrt{n+1} - \sqrt{n} \right)^2 < 2\epsilon$ but now I'm not sure where to go from here, or if this is even a useful place to be at. I get a nagging feeling that I am missing something very simple and elegant at the beginning of this problem. I have spent HOURS on this today...starting to get pretty demoralized. Not sure how hard this is "supposed" to be.

 

[Dick]

Nope, still haven't solved this one. Came very close, filled up my hand-held whiteboard with stuff, but it fell apart at the last minute because of one little error at the beginning. I'm still working on it now.

I would divide numerator and denominator by n. The denominator will be greater than 1, so don't worry about it. Just try and make the numerator small.

 

[Bennigan88]

I would divide numerator and denominator by n. The denominator will be greater than 1, so don't worry about it. Just try and make the numerator small.

Okay, I think what you're saying is this: $\left| \frac{n - \sqrt{n^2+n}}{\sqrt{n^2+n}+n} \right| = \left| \frac{1- \sqrt{1+\frac{1}{n}}}{\sqrt{1+\frac{1}{n}}+1} \right|$. The problem for me here is that I don't see how to get an inequality of the form $n > f(\epsilon)$. Keep in mind I am not using the limit theorems in this problem, this is an epsilon proof, also each algebraic step must be logically reversible, i.e. each implication must be bidirectional.

 

[Dick]

Okay, I think what you're saying is this: $\left| \frac{n - \sqrt{n^2+n}}{\sqrt{n^2+n}+n} \right| = \left| \frac{1- \sqrt{1+\frac{1}{n}}}{\sqrt{1+\frac{1}{n}}+1} \right|$. The problem for me here is that I don't see how to get an inequality of the form $n > f(\epsilon)$. Keep in mind I am not using the limit theorems in this problem, this is an epsilon proof, also each algebraic step must be logically reversible, i.e. each implication must be bidirectional.

Just concentrate on the numerator. How large does n have to be to make $\sqrt{1+\frac{1}{n}}-1 \lt \epsilon$?

 

[Bennigan88]

Alright I have
$$\sqrt{1+\frac{1}{n}} - 1 < \epsilon$$
$$\Rightarrow \sqrt{1+\frac{1}{n}} < \epsilon + 1$$
$$\Rightarrow 1 + \frac{1}{n} < \left( \epsilon + 1 \right) ^2$$
$$\Rightarrow \frac{1}{n} < \left(\epsilon + 1 \right)^2 - 1$$
$$\Rightarrow n > \frac{1}{\left(\epsilon + 1 \right)^2 - 1}$$

I don't understand why I can forget about the denominator.

Edit: Oh! If something is less than epsilon, then something smaller than that is also less than epsilon! Is that the idea?

 

[Dick]

Alright I have
$$\sqrt{1+\frac{1}{n}} - 1 < \epsilon$$
$$\Rightarrow \sqrt{1+\frac{1}{n}} < \epsilon + 1$$
$$\Rightarrow 1 + \frac{1}{n} < \left( \epsilon + 1 \right) ^2$$
$$\Rightarrow \frac{1}{n} < \left(\epsilon + 1 \right)^2 - 1$$
$$\Rightarrow n > \frac{1}{\left(\epsilon + 1 \right)^2 - 1}$$

I don't understand why I can forget about the denominator. For the proof I have to be able to reverse my steps, and $a < \epsilon \nRightarrow \frac{a}{b} < \epsilon$

The denominator is greater than 2. If the numerator is less than ε, so is the fraction. $a < \epsilon \Rightarrow \frac{a}{b} < \epsilon$ if b>2.

 

[Dick]

Edit: Oh! If something is less than epsilon, then something smaller than that is also less than epsilon! Is that the idea?

Of course!

 

[Bennigan88]

The denominator is greater than 2. If the numerator is less than ε, so is the fraction. $a < \epsilon \Rightarrow \frac{a}{b} < \epsilon$ if b>2.

Ok I think I'm with you. I was getting mixed up over the reversibility thing, but what your saying makes perfect sense to me now. Thank you! I will try to knock out the actual proof now.

 

[Bennigan88]

It's solid! Thank you so much!

 

[deluks917]

An alternate idea. Let a_n = $\sqrt{n^2 + n}$ and b_n = $\frac{1}{2} +n$ Then b_n² - a_n² = (b_n - a_n)(b_n + a_n) = 1/4.

As lim_n->∞(b_n + a_n) = ∞ as we must have lim_n->∞(b_n - a_n) = 0.