real analysis - How to prove $ {a_n} = frac{n!}{2^n}$ diverges to $+ infty$?

I would like to prove that the sequence $ {a_n} = \frac{n!}{2^n}$ diverges to $+ \infty$. As I understand it, this means that for all numbers $M$, I must find a number $N$ such that for all $n \ge N$, I get $a_n \ge M$. However, I'm not sure how to pick $N$.
Thanks.

Answer

You can use a lower bound on $n!$ instead of $n!$ itself. For example, when $n \ge 3$, $a_n = \frac{n!}{2^n} = \frac{2}{2^n}(3\cdot \ldots \cdot n) \ge \frac{2}{2^n}(3^{n-2}) = \frac{1}{2}\left(\frac{3}{2}\right)^{n-2}$. Since the sequence $\left(\frac{3}{2}\right)^n$ goes to $+\infty$ as $n$ goes to $+\infty$, $a_n$ must also go to $+\infty$.

If you wish to go all the way back to the definition, you only need to elaborate the last sentence. This can be done as follows.

Note that now we know that $a_n \ge \frac 12\left(\frac 32\right)^{n-2}
$ for $n \ge 3$. For any given $M > 0$, pick $N$ such that $\frac 12\left(\frac 32\right)^{N-2} = M$. (More specifically, $N = \frac{\log(2M)}{\log(3/2)}+2$.) If $N < 3$, we pick $N = 3$ instead. Then, for all $n > N$, we know $a_n \ge \frac 12\left(\frac 32\right)^n > M$.

limits - Sum of all the positive integers problem

The staff of Numberphile has shown that the sum of all the integers from $0$ to $\infty$ is $-\frac1{12}$. Recently I was looking for the sum of all the (positive) integers from $0$ to $n$ and I found that: $$\sum_{i=0}^n i=\frac{n(n+1)}{2}$$ So I decided to take the limit: $$\lim_{n\to \infty}\frac{n(n+1)}{2}$$ but that tends towards $\infty$ when I expected that to be $-\frac1{12}$!
Where did I got wrong? (the result is also confirmed by Wolfram Alpha)

Negative Algebra Formula

Quite simple for you Math Genius but I'm struggling to understand the following equation. (I've only just started an introductory course in Mathematics and I'm keen to learn) :)

I'm getting 2 answers

On my scientific Calculator $= 5.4$

On this website $= -5985$

My formula below. First I would like to know which one is correct or an explanation as to why they can both be correct. if someone could then break it down for me so I can understand where I have gone wrong.

$$10+6\cdot-\frac{8}{2(-25)}\cdot(-10)+5=$$

Answer

To be honest the mistake seems to lie somewhere within the interpretation of your given parenthesis hence it is not clear at all. The website you are refering to interprets your input as

$$10+6\cdot-\frac{8}{2}(-25)\cdot(-10)+5=-5985$$

where on the other hand you are asking for the evaluation of

$$10+6\cdot-\frac{8}{2(-25)}\cdot(-10)+5=5.4$$

The simple mistake is that the calculator you used online did not know that the $(-25)$ belongs to the denominator. Therefore use more parenthesis to make sure what you want to be computed.

Modular arithmetic in Montgomery form

I am trying to apply an algorithm that requires significant modular arithmetic, but in such a way as to avoid as many costly mod or division operations as possible.

I found the Montgomery multiplication method and its form of integer residues (via wikipedia and thus the original paper), but I am having difficulty understanding how to apply it practically.

Using the example in the wikipedia writeup, with $n = 17$ and an $R^{-1} = 8$, I can do very simple arithmetic with an implementation of redc that matches the expected value $mod\ n$:

$ (7 * 15) `mod` n
3
$ redc (3 * 4 * r')
3
$ (7 + 15) `mod` n
5
$ redc (3 + 4)
5

However, while the original paper and the wikipedia page say explicitly that most arithmetic operations can be applied over residues as "normally used", I'm not seeing that borne out:

$ (7 * 15 * 15) `mod` n
11
$ redc (3 * 4 * 4 * r')
12

(I know this might be on the edge of this being a stackoverflow question, but I suspect I'm suffering from a formal misunderstanding here, rather than a simple programming error.)

calculus - Limits and substitution

As in @RobertZ's answer to this question, we often perform substitutions when evaluating limits. For instance, if you're asked to show that
$$
L = \lim_{t \to 0} \frac{\sin t^3}{t^3} = 1,
$$
it's pretty common to say "Let $x = t^3$; then as $t \to 0$, we have $x \to 0$, so
$$
L = \lim_{x \to 0} \frac{\sin x}{x}
$$

which we know is $1$, and we're done."

What's going on here in general is an application of the following "Theorem"

Theorem 1: If the function $g$ satisfies [fill in missing properties] and $$\lim_{t \to a} g(t) = b,$$ then
$$
\lim_{t \to a} f(g(t)) = \lim_{x \to b} f(x),
$$
i.e., one limit exists if and only if the other does, and if they both exist, they're equal.

---

In the example above, $f(x) = \frac{\sin x}{x}$ and $g(t) = t^3$ and $a = b = 0$.

---

There's an alternative form, in which we're asked to show that
$$
L = \lim_{t \to 0} \frac{\sin \sqrt[3]{t}}{\sqrt[3]{t}} = 1,
$$

it's pretty common to say "Let $t = x^3$; then as $t \to 0$, we have $x \to 0$, so
$$
L = \lim_{x \to 0} \frac{\sin x}{x}
$$
which we know is $1$, and we're done."

In this case, the implicit theorem is very similar to the other, but with the role of $g$ reversed (i.e., we're substituting $ t = x^3$ instead of $x = t^3$, so the natural form of the theorem puts $g$ on the other side):

Theorem 2: If the function $g$ satisfies [fill in missing properties] and $$\lim_{x \to b} g(x) = a,$$ then
$$

\lim_{t \to a} f(t) = \lim_{x \to b} f(g(x)).
$$

---

In the second example above, we have $a = b = 0$, $f(t) = \frac{\sin \sqrt[3]{t}}{\sqrt[3]{t}}$, and $g(x) = x^3$.

The two theorems are obviously the same: if you swap $a$ and $b$, $x$ and $t$, and reverse the equality in the last line, they're identical. But each represents a different approach to working with limits, so I've stated both.

In the second form, it's clearly important that $g$ be surjective near $a$ (i.e., for every small enough interval $I = (b-\epsilon, b + \epsilon)$, there's an interval $I' = (a-\delta, a + \delta)$ such that $I- \{b\} \subset g(I' - \{a\})$. (Hat-tip to MathematicsStudent1122 for the observation that I need to delete $a$ and $b$ from those intervals). Otherwise you could use things substitutions like $s = t^2$, which would turn a two-sided limit into a one-sided one (or vice versa), in which case one limit might exists and the other might not.

Addendum to clarify why this might matter, for @MathematicsStudent1122:

Consider $$f(x) = \begin{cases}
1 & x \ge 0 \\
0 & x < 0
\end{cases}.$$

and look at $L = \lim_{x \to 0} f(x^2)$. It's clear that $L$ exists and is $1$. But if we substitute $t = x^2$, then we get $L = \lim_{t \to 0} f(t)$, which does not exist; hence this "substitution" is not valid: I've turned what amounts to a 1-sided limit (which exists) into a two-sided limit (which does not exist). The domains of $f$ and $g$ are both all of $\Bbb R$.

(End of addendum)

My question is this:

What is a reasonable set of missing properties for each of these theorems? (I can work out the exact properties easily enough by running through the definitions, but they don't seem to be very helpful/checkable.)

One answer might be "$g$ is locally a bijection", but that rules out things like $y = x + x\sin \frac{1}{x}$ near $x = 0$, so it seems too limited. (It also rules out things like $x \mapsto x + \sin x$ for limits as $x \to \infty$, which is a pity.)

I recognize that this is not a strictly mathematical question. But my goal is to come up with a "calculus student's theorem", one that says "if you're trying to work out a limit, which may or may not exist, then it's OK to do substitutions of this sort along the way," and which will cover the vast majority of the problems that they might encounter in a standard calculus book, or even in Spivak's book.

This question gives two theorems, but both have assumptions about the existence of limits. This one comes a little closer, but still isn't entirely satisfactory.

I'd love any nice-enough condition to be broadly useful. In particular, I think it's completely reasonable to require, for instance, that the "substitution function" $g$ be continuous, and perhaps even differentiable (although I doubt that's of much use).

abstract algebra - Proving the order of a finite field without using the characteristic

I'm trying to prove the order of a particular quotient field of $\mathbb{Z}[i]$ without using the characteristic of the field. My hesitation in using the characteristic comes from the fact that I'm working my way through Dummit and Foote's Abstract Algebra and encountered this question before the section on field theory. This question arose in the section on UFD's. There must by some way to prove my claim without using the field theoretic notion of a characteristic.

Claim: Let $q \in \mathbb{Z}$ be a prime such that $q \equiv 3$ (mod $4$). Then, $\mathbb{Z}[i]/(q)$ is a field of order $q^2$.

A few things about this claim are immediately clear. First, q is clearly an irreducible in $\mathbb{Z}[i]$ because it would only be reducible if $q=2$ or $q \equiv 1$ (mod $4$). Since $\mathbb{Z}[i]$ is a UFD, it follows that $(q)$ is prime. Moreover, it's pretty simple to show that $\mathbb{Z} \cap (q) = q\mathbb{Z}$. By the second isomorphism theorem for rings, you then recover that $\mathbb{Z} + (q)/(q) \cong \mathbb{Z}/q\mathbb{Z}$. But that seems like a dead end because I can't figure out a way to break down the rest of $\mathbb{Z}[i]$ and show that it's disjoint with $\mathbb{Z} + (q)$ and isomorphic to $\mathbb{Z}/q\mathbb{Z}$ also.

Answer

It is easy to see that $a+bi\in\mathbb{Z}[i]$ is divisible by $q$ iff both $a$ and $b$ are divisible by $q$ as integers. It follows that $a+bi\equiv c+di$ mod $q$ iff $a\equiv c$ and $b\equiv d$ mod $q$. So this gives a bijection (in fact, an additive group-isomorphism) $\mathbb{Z}[i]/(q)\to \mathbb{Z}/(q)\times\mathbb{Z}/(q)$.

asymptotics - Growth of $Gamma(n,n)$

How can you get the asymptotics for the growth of $\Gamma(n,n)$?

$$

\Gamma(n,n) = \int_n^\infty x^{n-1} \exp(-x) \mathrm{d}x
$$

Answer

You can get it by a simple rescaling of the integral. Let $x=n t$; then

$$\begin{align}\Gamma(n,n) &= n^n \int_1^{\infty} dt \: t^{n-1} e^{-n t}\\ &= n^n \int_1^{\infty} \frac{dt}{t} e^{n (\log{t}-t)} \\ &= n^n e^{-n} \int_0^{\infty} \frac{du}{1+u} e^{n [\log{(1+u)}-u]} \end{align}$$

The contribution to this integral is dominated by that near $u=0$ as $n \rightarrow \infty$. We may then Taylor expand the term in the exponential and see that the leading asymptotic behavior of the integral is

$$\Gamma(n,n) \sim n^n e^{-n} \int_0^{\infty} du \: e^{-n u^2/2} = n^n e^{-n} \sqrt{\frac{\pi}{2 n}}$$

We may find further terms in the asymptotic behavior by Taylor expanding the higher-order terms in the exponential and the term outside the exponential. The next higher order term is

$$\left ( 1 + \frac{n u^3}{3} \right ) (1-u) \sim 1-u +\frac{n u^3}{3} $$

Evaluating the integrals that result from this expansion, we find the next higher term in the expansion:

$$\Gamma(n,n) = n^n e^{-n} \left [ \sqrt{\frac{\pi}{2 n}} - \frac{1}{3 n} + O\left ( n^{-3/2} \right ) \right ]$$