calculus - Evaluating $limlimits_{ntoinfty} e^{-n} sumlimits_{k=0}^{n} frac{n^k}{k!}$

I'm supposed to calculate:

$$\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$$

By using W|A, i may guess that the limit is $\frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.

Answer

Edited. I justified the application of the dominated convergence theorem.

By a simple calculation,

$$ \begin{align*}
e^{-n}\sum_{k=0}^{n} \frac{n^k}{k!}
&= \frac{e^{-n}}{n!} \sum_{k=0}^{n}\binom{n}{k} n^k (n-k)! \\

(1) \cdots \quad &= \frac{e^{-n}}{n!} \sum_{k=0}^{n}\binom{n}{k} n^k \int_{0}^{\infty} t^{n-k}e^{-t} \, dt\\
&= \frac{e^{-n}}{n!} \int_{0}^{\infty} (n+t)^{n}e^{-t} \, dt \\
(2) \cdots \quad &= \frac{1}{n!} \int_{n}^{\infty} t^{n}e^{-t} \, dt \\
&= 1 - \frac{1}{n!} \int_{0}^{n} t^{n}e^{-t} \, dt \\
(3) \cdots \quad &= 1 - \frac{\sqrt{n} (n/e)^n}{n!} \int_{0}^{\sqrt{n}} \left(1 - \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \, du.
\end{align*}$$

We remark that

1. In $\text{(1)}$, we utilized the famous formula $ n! = \int_{0}^{\infty} t^n e^{-t} \, dt$.


2. In $\text{(2)}$, the substitution $t + n \mapsto t$ is used.


3. In $\text{(3)}$, the substitution $t = n - \sqrt{n}u$ is used.

Then in view of the Stirling's formula, it suffices to show that

$$\int_{0}^{\sqrt{n}} \left(1 - \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \, du \xrightarrow{n\to\infty} \sqrt{\frac{\pi}{2}}.$$

The idea is to introduce the function

$$ g_n (u) = \left(1 - \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \mathbf{1}_{(0, \sqrt{n})}(u) $$

and apply pointwise limit to the integrand as $n \to \infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < \sqrt{n}$, then

$$ \log g_n (u)
= n \log \left(1 - \frac{u}{\sqrt{n}} \right) + \sqrt{n} u
= -\frac{u^2}{2} - \frac{u^3}{3\sqrt{n}} - \frac{u^4}{4n} - \cdots \leq -\frac{u^2}{2}. $$

From this we have $g_n (u) \leq e^{-u^2 /2}$ for all $n$ and $g_n (u) \to e^{-u^2 / 2}$ as $n \to \infty$. Therefore by dominated convergence theorem and Gaussian integral,

$$ \int_{0}^{\sqrt{n}} \left(1 - \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \, du = \int_{0}^{\infty} g_n (u) \, du \xrightarrow{n\to\infty} \int_{0}^{\infty} e^{-u^2/2} \, du = \sqrt{\frac{\pi}{2}}. $$

algebra precalculus - Rewriting a sum

I'm stuck proving this result...

Let $a$ be a positive even integer and $m$ a positive integer.

Show that $$a^m\sum_{k=0}^{m}\frac{(-1)^k {2k \choose k}a^{-k}}{2^{2k}} $$ can be rewritten as $$\frac{2K+1}{2^b}$$ where $K\in \mathbb Z$ and $b$ satisifies $$b=m+e_b$$ where $e_b$ is the exponent of $2$ in $m!$

I really don't know how to begin... Thanks for your help.

Answer

We have
$$a^m\sum^m_{k=0}\frac{(-1)^k\binom{2k}{k}a^{-k}}{4^k}=\frac{x}{2^{m+e}}$$

where $x$ is odd
$$\sum^m_{k=0}\binom{2k}{k}(-4)^{-k}a^{m-k}=\frac{x}{2^{m+e}}=\frac{x2^{m-e}}{4^m}$$
If $m$ is even, then the parity of $-k$ is the same as $m-k$ and we can safely manipulate
$$\sum^m_{k=0}\binom{2k}{k}(-4a)^{m-k}=x2^{m-e}\tag{1}$$
If not, the sign of the whole sum gets inverted, but this does not change the parity of it.By the same token as robjohn's answer, we have that
$$\text{number of factors 2 in n!}=\nu_2(n) =\sum_{i=0}^kn_i\left(1+2+2^2+\dots+2^{i-1}\right)$$
Where $n_i$ are the i th coefficients of the binary representation of $n$.
Since the binary representation of $2n$ is just the one of $n$ shifted one number to the left, we then have that
$$
\begin{align}

\nu_2(2n)
&=\sum_{i=0}^kn_i\left(1+2+2^2+\dots+2^{i-1}+2^i\right)\\
&=\nu_2(n)+\sum_{i=0}^kn_i2^i=\nu_2(n)+n
\end{align}$$
Then, the number of factors $2$ in the last term of $(1)$ is
$$\nu_2(m)+m-2\nu_2(m)=m-v_2(m)=m-e$$

So now we just have to show that the other terms are an even multiple of $2^{m-e}$.

We then have that the exponent of two of the penultimate term is

$$[m-1-\nu_2(m-1)]+2=m+1-\nu_2(m-1)$$
Since $\nu_2(m-1)\le\nu_2(m)$, we have
$$m-\nu_2(m)\le m-\nu_2(m-1)Therefore the exponent of two in the last term is strictly smaller than the previous one,i.e. all the other terms are an even multiple of it. Finally, we know that $2^{m-e}$ is the highest power of $2$ that divides our expression.

definite integrals - Alternative (contour preferred) method to evaluate $int_{0}^{infty}frac{dz}{cosh z + cos theta}$

We know the indefinite integral with $d$ being the differential operator (e.g., by substitution $t=e^z$ and partial fraction)

$$\frac{dz}{\cosh z+\cos\theta}=-\frac i{\sin\theta}d\ln\frac{e^z+e^{i\theta}}{e^z+e^{-i\theta}}.$$
Can we find a nice contour in the complex plane and using the Cauchy residue theorem to directly show its definite form?
$$\int_0^\infty\frac{dz}{\cosh z+\cos\theta}=\frac{\theta}{\sin\theta}$$
Other methods are welcome too.

The upper (neither the lower) hemispherical contour does not work because the segment integral close to the imaginary axis at infinity does not vanish.

Answer

A more direct approach than the one I mentioned in the comments is to integrate $$f(z) = \frac{z}{\cosh z + \cos \theta} \, , \quad 0 < \theta < \pi, $$ around a rectangle in the upper half-plane of height $ 2 \pi i$.

Doing so, we get $$ \begin{align} \int_{-\infty}^{\infty} \frac{x}{\cosh x + \cos \theta} \, dx - \int_{-\infty}^{\infty} \frac{x+ 2 \pi i }{\cosh x + \cos \theta} \, dx &= 2 \pi i \Big( \text{Res}\left[f(z), i(\pi - \theta)\right] + \text{Res}\left[f(z), i(\pi + \theta \right)]\Big) \\ &= 2 \pi i \left(\frac{i(\pi - \theta)}{\sinh(i(\pi -\theta)) }+ \frac{i(\pi + \theta)}{\sinh(i(\pi + \theta))}\right) \\ &=2 \pi i \left(\frac{\pi - \theta}{ \sin \theta }- \frac{\pi + \theta}{ \sin \theta}\right)\\ &= - 4 \pi i \, \frac{\theta}{\sin \theta}. \end{align}$$

(The integrals along the sides of the rectangle vanish in the limit since $|\cosh z|$ grows exponentially as $\text{Re}(z) \to \pm \infty$.)

Therefore, $$ 2 \pi i \int_{-\infty}^{\infty} \frac{1}{\cosh x + \cos \theta} \, dx = 4 \pi i \, \frac{\theta}{\sin \theta} \, , $$ and the result follows since the integrand is even.

number theory - Residue distributions are not uniform

With $n_1$ and $n_2$ two positive integers, the formula

$$L = \sum_{k=0}^{498}\, \left(n_1+n_2\, k \right) {(10^{6})}^{k}$$

can construct very large numbers $L$.

Once we have $L$ we can let $n$ vary from $1$ to $1,000,000$ and construct residues

$$n \mapsto [L \pmod n] \pmod {53}$$

The residues will all belong to $\{0,1,2,\dots,52\}$. Since we are taking $1,000,000$ residues, you might guess that each residue will occur around $\frac{10^6}{53} \approx 18,868$ times, but this is not the case.

I wrote a Python program (see next section) and found the following distributions:

Please input big number seed 1: 1
Please input big number seed 2: 2
seeds = 1 2
[(16, 37359), (25, 19262), (4, 19164), (13, 19153), (26, 18985), (1, 18972), (41, 18885), (15, 18855), (12, 18814), (7, 18766), (46, 18766), (29, 18755), (50, 18746), (20, 18735), (10, 18716), (39, 18701), (9, 18638), (33, 18638), (45, 18626), (48, 18575), (18, 18573), (43, 18569), (31, 18527), (22, 18511), (5, 18509), (2, 18459), (8, 18454), (38, 18449), (21, 18443), (0, 18440), (34, 18430), (49, 18422), (23, 18416), (47, 18413), (35, 18409), (17, 18405), (42, 18401), (27, 18400), (36, 18399), (28, 18321), (32, 18320), (14, 18302), (3, 18294), (24, 18278), (44, 18167), (30, 18162), (19, 18153), (40, 18152), (52, 18123), (37, 18083), (11, 18068), (51, 17996), (6, 17841)]


Please input big number seed 1: 123
Please input big number seed 2: 321
seeds = 123 321
[(48, 36932), (13, 19246), (2, 19144), (18, 19060), (29, 19047), (42, 18992), (49, 18840), (21, 18830), (47, 18801), (22, 18797), (39, 18768), (20, 18767), (3, 18734), (1, 18698), (52, 18693), (15, 18679), (25, 18675), (5, 18661), (0, 18655), (28, 18629), (7, 18628), (17, 18623), (32, 18613), (8, 18608), (46, 18604), (19, 18593), (33, 18562), (4, 18531), (51, 18497), (9, 18496), (14, 18477), (38, 18476), (36, 18443), (30, 18439), (44, 18408), (23, 18382), (24, 18372), (41, 18371), (43, 18327), (45, 18314), (34, 18269), (11, 18208), (26, 18207), (31, 18164), (35, 18148), (37, 18145), (10, 18133), (50, 18117), (27, 18112), (12, 18063), (40, 18035), (6, 18012), (16, 17975)]

Please input big number seed 1: 88
Please input big number seed 2: 78
seeds = 88 78
[(16, 37746), (7, 19142), (40, 19121), (23, 19050), (38, 18929), (51, 18921), (42, 18904), (1, 18845), (20, 18826), (15, 18761), (39, 18758), (41, 18748), (4, 18746), (6, 18697), (0, 18663), (31, 18652), (11, 18646), (48, 18617), (17, 18580), (22, 18569), (9, 18563), (12, 18559), (24, 18541), (26, 18516), (8, 18509), (45, 18491), (36, 18489), (28, 18474), (32, 18447), (25, 18446), (37, 18438), (50, 18433), (52, 18430), (46, 18394), (49, 18383), (18, 18356), (29, 18356), (14, 18337), (3, 18328), (43, 18318), (33, 18314), (10, 18286), (13, 18261), (19, 18260), (44, 18221), (2, 18219), (47, 18201), (5, 18178), (34, 18175), (21, 18144), (35, 18088), (30, 17964), (27, 17960)]

Notice how the first most common residues stand out:

$(16, 37359)$
$(48, 36932)$
$(16, 37746)$

in each of the three programs runs.

I started out using $\text{mod } 50$ and that pattern was really weird so I tried using the prime number $53$. It works better but still not looking uniform.

Any explanation for this distribution pattern?

My work and motivation

I'm interested in cryptography and was thinking that if two parties shared a secret large number $L$ they could transmit $n$ to represent one of, say, $53$ characters.

So with seeds $= 1,\, 2$ and $(25, 19262)$ counter output, you have $19,262$ different choices for $n$ to transmit the $25^{th}$ character of your 'alphabet'. Of course you can find more $n$ by going past the (artificially} selected one million mark.

Any answers/comments on the strengths and weaknesses of this idea would be appreciated.

---

Python program (not optimized)

M = 1000000


def bP(i):
    p = 1
    for j in range(0, i):
        p = (p * M)
    return p

def getTerm(i):
    return ((n1 + n2 * i) * bP(i)) 

import collections


while True:
    print()
    n1 = int(input('Please input big number seed 1: '))
    n2 = int(input('Please input big number seed 2: '))
    print('seeds =',n1,n2)
    L = 0
    for i in range(0, 499):
        L = (L + getTerm(i)) 
    cnt = collections.Counter()

    for n in range(1, 1000001):
        c = (L % n) % 53
        cnt[c] += 1
    print(cnt.most_common())

integration - Asymptotic expansion of $int_0^1 frac{operatorname{K}(r x)}{sqrt{(1-r^2 x^2)(1-x^2)}} , mathrm{d} x $

Notation: For $\varphi \in [0,\frac{\pi}{2}]$ and $k \in [0,1)$ the definitions
$$ \operatorname{F}(\varphi,k) = \int \limits_0^\varphi \frac{\mathrm{d} \theta}{\sqrt{1-k^2 \sin^2(\theta)}} = \int \limits_0^{\sin(\varphi)} \frac{\mathrm{d} x}{\sqrt{(1 - k^2 x^2)(1-x^2)}} $$
and $\operatorname{K}(k) = \operatorname{F}(\frac{\pi}{2},k)$ will be used for the elliptic integrals of the first kind.

When answering this question, I came across the function
$$ \psi \colon [0,1) \to (0,\infty) \, , \, \psi(k) = \int \limits_0^1 \frac{\operatorname{K}(k x)}{\sqrt{(1-k^2 x^2)(1-x^2)}} \, \mathrm{d}x = \int \limits_0^{\pi/2} \frac{\operatorname{K}(k \sin(\theta))}{\sqrt{1-k^2 \sin^2 (\theta)}} \, \mathrm{d} \theta \, .$$

While $\psi(k) = \frac{\pi^2}{4} [1+ \frac{3}{8} k^2 + \mathcal{O}(k^4)]$ near $k=0$ is readily found using Maclaurin series, the expansion at $k=1$ is more elusive.

The naive attempt of replacing $\operatorname{K}(kx)$ by $\operatorname{K}(k)$ (since the largest contribution to the integral comes from the region near $x=1$) yields $\psi(k) \simeq \operatorname{K}^2 (k)$, which according to plots is not too far off but also not quite right. Integration by parts reproduces this term, but the remaining integral does not look very nice:
\begin{align}
\psi(k) &= \operatorname{K}^2 (k) - k \int \limits_0^1 \operatorname{K}'(k x) \operatorname{F}(\arcsin(x),k) \, \mathrm{d} x \\
&= \operatorname{K}^2 (k) - \int \limits_0^1 \left[\frac{\operatorname{E}(k x)}{1-k^2 x^2} - \operatorname{K}(kx)\right] \frac{\operatorname{F}(\arcsin(x),k)}{x} \, \mathrm{d} x \, .
\end{align}
The expansion $\operatorname{K}(k) = -\frac{1}{2} \log(\frac{1-k}{8}) + \mathcal{o}(1)$ is useful for the final steps, but I do not know how to extract all the leading terms, so:

How can we find the asymptotic expansion (ideally up to and including the constant terms) of $\psi(k)$ as $k \nearrow 1$ ?

Answer

Some heuristics:
From DMLF we get the asymptotic Expansion of $K(z)$ up toll all orders around $z=1_-$
$$
K(z)\sim-\frac12\log(1-z^2)+2\log(2)+O((1-z^2) \log(1-z^2))
$$

disregarding the terms which vanish at $z=1_{-}$ we obtain (Unluckily i don't see a way of making a precise estimate of the $O$-term, but it should definitly be $o(1)$)

$$
\psi(k)\sim -\int_0^1\frac{1}{2}\frac{\log(1-k^2x^2)}{\sqrt{1-x^2}{\sqrt{1-(kx)^2}}}dx-2 \log(2)\int_0^1\frac{1}{\sqrt{1-x^2}{\sqrt{1-(kx)^2}}}
$$

or (a proof for the first integral can be found here in section 7., the second is just the very defintion of $K(k)$)

$$
\psi(k)\sim -\frac12K(k)\log(1-k^2)-2\log(2)K(k)
$$

which fits Pretty well (the relative error for $k=0.999999999$ is about $2.1$% and for $k=0.9999999$ is about $2.5$%, so we are most likely off by a constant)

Using the asympototic Expansion from the beginning of the post again we could further simplifiy the above, but i leave it like that...

gcd and lcm - GCD Proof to find all integers that satisfy $am + bn = gcd(a, b)$

I have this question that I'm not entirely sure how to answer.

Suppose that $a, b$ are non-zero integers. Find all integers $m, n$
such that $am + bn = \gcd(a, b)$

I know that it suffices to show that if $m, n$ and $m', n'$ are 2 possible solutions that showing that $\frac{b}{\gcd(a, b)}\mid m-m'$ and $\frac{a}{\gcd(a, b)}\mid n-n'$. However, I'm not entirely sure how to get there. Thanks.

Answer

Let $c = \text{gcd}(a,b)$.

• Hint 1: Start with $am + bn = c$ and $am' + bn' = c$. What happens if you combine these equations?


• Hint 2: What is the value of $\text{gcd}(a/c, b/c)$?


• Hint 3: If $x \mid yz$ and $\text{gcd}(x,y) = 1$, what is the relationship between $x$ and $z$?

arithmetic - What does the raised $^2$ stand for?

What does the raised $2$ stand for? My first guess was: $4^2$ is $2\times 4=8$?

^{Note: Am not really good at math}

Answer

It is called 'exponent' or 'power'.

Here $4^2$ means $4$ multiplied twice or in other words product of two $4's$. So:

$$4^2 = 4*4 = 16$$
Similarly $7^3$ means $7$ multiplied thrice or in other words product of three $7's$. So:
$$7^3 = 7*7*7 = 343$$
Since you are a starter, you can get more information about it here.