Limit of a sequence (i.e. discrete limit)
===

In all this discussion, variables $n$ and $k$ will be positive integers.

A sequence $S \equiv S(n)$ (denoted as $S_n$) where $n \in \mathbb{Z}^+$ is said to have a _finite_ limit $a$ iff

$$
\forall d \in \mathbb{R}_{\gt 0}, (\exists k \in \mathbb{Z}, (\forall n \gt k, (|a - S_n| \lt d)))
$$

From an adversary game point of view, no matter how small you choose $d$ (without making it 0), you will find that the distance between $a$ and $S_n$ stays less than $d$ after a certain point.

There is no notion of continuity for sequences. Sequences are discrete functions after all.

## $\lim S = \infty$ vs. non existence

$(\lim S = \infty)$ $\implies$ Not convergent

Limit equals infinity is special. It's a bit of abuse of terminology, imo. This is also called "improper limit".

Therefore,

**Non convergent seq** $\Longleftrightarrow$ $(\lim_{n->\infty} S_n = \infty)$ $\vee$ **No limit**

~~Any sinusoidal function sampled at less than half the period - thus giving a discrete function, is an example of a sequence that _does not have a limit_ and hence it's divergent. It's limit is obviously not $\infty$ either.~~

Then what is limit equals infinity?

In plain english, a sequence tends to infinity when the value of the sequence is unbounded _and_ in a way "blows up" - not the formal "monotic function" definition by the way so don't confuse with it. That sense is difficult to explain in english so a stricter mathematical definition will have to suffice.

The definition of $\lim_{n \rightarrow \infty^+} S_n = \infty^+$

$$
\forall d \in \mathbb{R}^+, (\exists k \in \mathbb{Z}, (\forall n > k, (S_n > d)))
$$

From an adversary game point of view, no matter how large you choose d, you will find that $S_n$ never goes below i.e. stays above $d$ after a certain point.

A sequence with limit equal to infinity is also a divergent sequence as it doesn't have a limit as per the definition.

Coming back to sinusoids, the sequence $S_n = \sin(n\pi/4)$ does not have a finite limit, nor is it's limit $\infty$. It's non convergent. English - the function keeps cycling up and down, but of course that's not enough for non convergence.

The function $sin(x)/x$, and it's discretized version (i.e. a sequence of samples) is an example of a non-monotonic function, that has a limit = $0$. It also "cycles up and down" but is convergent.

A pseudorandom number generator (PRNG) with uniform distribution in $[0 \ldots 1)$ is also a non convergent sequence.

The absolute value of the sequence $S_n = (-1)^n$ has limit of infinity (again, it's an improper limit, i.e. divergent nonetheless), but the sequence itself does not have limit equals infinity. The sequence is divergent. BTW, this sequence is same as $S_n = \sin(\pi/2 + n\pi)$.

Function function $n^2$ does not have a finite limit, and is divergent and has "improper limit" of $\infty$. It's monotonic.

The function $x \cdot sin(x)$ does not have a finite limit, and is divergent and has "improper limit" of $\infty$. It's not monotonic, but "blows up".

## Big-O

Most often in asymptotic analysis of algorithms, the functions assumed are continuous although in practial use the argument to the function is discrete since it denotes number of inputs ($= n$), a positive integer.

A function $f \equiv f(n)$ is in $O(g)$ where $g \equiv g(n)$, i.e. $f \in O(g)$ iff

$$
\exists k \geq 1, (\exists n', \forall n > n', (f(n) \leq k \cdot g(n)))
$$

The definition looks similar to the definition of the limit of a sequence. Can we rephrase in terms of limit of sequence (discrete limit), especially since these functions are only applied to positive integers? Assume that $g$ converges, i.e. has a limit.

$$
\exists k \geq 1, (\lim_{n \rightarrow \infty} \frac{f(n)}{k \cdot g(n)} \in [0 \ldots 1])
$$

Here the sequence of which the limit is computed is $S(n) = \frac{f(n)}{k \cdot g(n)}$

Write a somewhat formal proof?

## Zeno's paradox

http://homes.sice.indiana.edu/donbyrd/Teach/Math/Zeno+Footraces+InfiniteSeries.pdf

The proof says that the total time taken by Achilles to reach the tortoise **is not greater than 11.1111... seconds**. How do you deduce from that Achilles **reaches** the tortoise at 11.1111... seconds? Does this _prove_ spacetime is discrete? Something something Planck length? Don't know.

## What line is an odd function mirrored on

Working without any reference to particular dimension. A line in 2D (or plane in 3D or hyperplane in any _n_ D) can be represented using it's normal $\hat{n}$ and the signed distance $d$ of the origin. If origin is "behind" the normal, $d$ is negative otherwise it's positive. The signed distance of a point $\tilde{x}$ from the line is given as

$$
D(\tilde{x}) = \hat{n} \cdot \tilde{x} + d
$$

Clearly any point lying on the line will satsify $D(\tilde{x}) = 0$. That can be seen as an implicit equation for specifying the line.

Suppose we want to "mirror" a point $\tilde{x}$ about a line in 2D (or plane in 3D). The closest point to $\tilde{x}$ on this line is going to be $\tilde{u} = \tilde{x} - D(\tilde{x})\hat{n}$.

Think of it this way. You first walk from origin towards $\tilde{x}$ and then walk towards the plane in the reverse $\hat{n}$ direction (which is why the $-$ sign) for a distance of $D(\hat{x})$.

But to get the mirror point you have to walk another $D(\tilde{x})$ along the reverse of the $\hat{n}$. So the mirror point is given as

$$
\tilde{p'} = \tilde{x} - 2D(\tilde{x})\hat{n}
$$

$$
\tilde{p'} = \tilde{x} - 2(\hat{n} \cdot \tilde{x} - 2d)\hat{n}
$$

Now, to be concrete, take the line with the following implicit equation

$$
y = -x
$$

The normal vector of this line is $\hat{n} = \langle 1/\sqrt{2}, 1/\sqrt{2} \rangle$ (the vector is parallel to line $y = x$, really), and signed distance of origin is $0$

Given a point $\langle x, f(x) \rangle$. The corresponding mirrored point about the $y = -x$ line is given by

$$
\tilde{p'} = \tilde{x} - 2(\hat{n} \cdot \tilde{x} - 2d) \hat{n}
$$

Putting values for $\hat{n} = \ldots$ and $d = 0$

$$
= \langle x, f(x) \rangle - 2(\langle 1/\sqrt{2}, 1/\sqrt{2} \rangle \cdot \langle x, f(x) \rangle)\langle 1/\sqrt{2}, 1/\sqrt{2} \rangle
$$

Don't bother with the calculation. We get

$$
\tilde{p'} = \langle -f(x), -x \rangle
$$

**Which shows that no, in general odd functions are not mirrored about the $y = -x$ line.** Rather they have rotational symmetry about the origin. Proof is much simpler will share later.

### Correct proof

Rotating a 2D vector $\langle x, y \rangle$ by 180 degree (counter clockwise along the "$z$" axis) is same as multiplying by the matrix

$$
\begin{bmatrix}
-1 && 0 \\
0 && -1
\end{bmatrix}
$$

So we get $\langle -x, -y \rangle$. Letting $y = f(x)$, we see that if we rotate $\langle x, f(x) \rangle$ by $180\deg$, we get the point $\langle -x, -f(x) \rangle$. If $f$ is odd, then this point is equal to $\langle -x, f(-x) \rangle$ and this point belongs to the graph of $f$.

---

Extra tidbit - When you rotate $\langle x, y \rangle$ by $90\deg$, you get the point $\langle -y, x \rangle$, i.e. swap the values of the components and negate the $x$ component. So to get the vector when you rotate $\langle x, y \rangle$ by $180 \deg$ you do this thing twice and yo