问:
Stirling's formula: proof?
Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$

Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = \sqrt{2 \pi}$.

What is a good way of doing this? Could we use L'Hopital's Rule? Or maybe take the log of both sides (e.g., compute the limit of the log of the quantity)? So for example do the following $$\lim_{n \to \infty} \log \left[\frac{n!}{n^{n+(1/2)}e^{-n}} \right] =  \log C$$

答:
Using the Leibniz rule $\frac{d}{dt}\Bigg[\int_{a(t)}^{b(t)}f(x,t)dx\Bigg]=\int_{a(t)}^{b(t)}\frac{\partial}{\partial t}f(x,t)dx+\bigg[f(b(t),t)\frac{d}{dt}b(t)-f(a(t),t)\frac{d}{dt}a(t)\bigg]$

$$
\int_0^\infty e^{-x}dx=1\\
\text{Let }x=tu\implies dx=t.du,t>0\\
\int_0^\infty te^{-tu}du=1\implies \int_0^\infty e^{-tu}du=\frac{1}{t}\\
\frac{d}{dt}\int_0^\infty e^{-tu}du=\int_0^\infty \frac{\partial}{\partial t}e^{-tu}du=\frac{-1}{t^2}\\
\int_0^\infty ue^{-tu}du=\frac{1}{t^2}\\
\int_0^\infty u^2e^{-tu}du=\frac{2}{t^3}\\
\int_0^\infty u^3e^{-tu}du=\frac{6}{t^4}\\
\int_0^\infty u^4e^{-tu}du=\frac{24}{t^5}\\
\int_0^\infty u^ne^{-tu}du=\frac{n!}{t^{n+1}}\\
\implies \int_0^\infty \bigg[\frac{x}{t}\bigg]^ne^{-x}\frac{dx}{t}=\frac{n!}{t^{n+1}}\\
\implies \boxed{\int_0^\infty x^ne^{-x}dx=n!=\Gamma(n+1)}
$$
Dividing by $\bigg[\frac{n}{e}\bigg]^n$
$$
\bigg[\frac{e}{n}\bigg]^n\Gamma(n+1)=\int_0^\infty \left[\frac{x}{n}\right]^ne^{-(x-n)}dx\\
\text{Let } s=x-n,\\
\bigg[\frac{e}{n}\bigg]^n\Gamma(n+1)=\int_{-n}^\infty \bigg[1+\frac{s}{n}\bigg]^ne^{-s}ds=\int_{-n}^\infty f(s)ds
$$
where $f(s)=\bigg[1+\frac{s}{n}\bigg]^ne^{-s}$
$$
\ln(f(s))=n\ln\bigg[1+\frac{s}{n}\bigg]-s=n\bigg[\frac{s}{n}-\frac{1}{2}\bigg(\frac{s}{n}\bigg)^2+\frac{1}{3}\bigg(\frac{s}{n}\bigg)^3-\cdots\bigg]-s\\
=\frac{-s^2}{2n}+\frac{s^3}{3n^2}-\cdots
$$
For large $n$,
$$
\ln(f(s))\approx\frac{-s^2}{2n}
$$
$$
\bigg(\frac{e}{n}\bigg)^n\Gamma(n+1)\approx\int_{-\infty}^\infty e^{-s^2/2n}ds=\sqrt{2\pi n}, \text{ since }\int_{-\infty}^\infty e^{-at^2}dt=\sqrt{\frac{\pi}{a}}\\
\Gamma(n+1)\approx\bigg(\frac{n}{e}\bigg)^n\sqrt{2\pi n}\\
\implies \boxed{n!=\Gamma(n+1)\approx \bigg(\frac{n}{e}\bigg)^n\sqrt{2\pi n}}
$$

Title: Stirling's formula: proof?


问:
A basic question about the definition of $\Sigma_n$ completeness
Suppose I want to show that $A$ is $\Sigma_8$-complete. By definition, this requires to prove, in particular, that $A$ is itself a $\Sigma_8$ set. But I don't really understand if I need to prove as well that $\Sigma_8$ is the "best" one could get? (I.e., that $A$ is not $\Sigma_i$ or $\Pi_i$ for $i=1,2,3,4,5,6,7$.) Some $\Sigma_8$ sets may be as well $\Sigma_1$, but they still qualify for being $\Sigma_8$...

答:
There are three different notions here:

Being $\Sigma_8$.

Being properly $\Sigma_8$, which is to say being $\Sigma_8$ but not $\Sigma_n$ for any $n<8$ (or $\Pi_k$ either for that matter for any $k\le 8$).

Being $\Sigma_8$-complete.

If we want to show that something is $\Sigma_8$-complete, it is - as you say - not enough to simply show that it is $\Sigma_8$. But it is also not enough to show that it is properly $\Sigma_8$! $\Sigma_8$-completeness is a very strong property: we have to show that any other $\Sigma_8$ set is many-one reducible to the given set, and that doesn't follow from proper-$\Sigma_8$-ness alone. In order to prove that a set $A$ is $\Sigma_8$ complete, we have to prove two things:

$A$ is $\Sigma_8$.

Every $\Sigma_8$ set $B$ can be many-one reduced to $A$.

That's it - we never need to refer to proper-$\Sigma_8$-ness, and we don't get any benefit from doing so either.

(That said, as a matter of practice basically every naturally-occurring properly-$\Sigma_n$ set is $\Sigma_n$-complete. So you can always take a proof of proper-$\Sigma_n$-ness as really good evidence for $\Sigma_n$-completeness. But this isn't a theorem or anything, it's just a fact about the sorts of sets we run into in mathematical practice ... at least, so far.)

Note, incidentally, that it is not immediately obvious that $\Sigma_8$-completeness implies properly-$\Sigma_8$-ness! To get that you need to use the fact that the arithmetical hierarchy doesn't collapse, which takes a proof. Of course that's not hard, but it is worth noting - and it's worth keeping in mind that there are hierarchies out there which do, or may as far as we know, collapse.

ContentLicense: CC BY-SA 4.0


问:
Let $a,b,c$ be positive integers such that $a^3+b^3=2^c.$ Show that $a=b$.

Let $a,b,c$ be positive integers such that $$a^3+b^3=2^c.$$ Show that $a=b$.

I have that $$a^3+b^3=(a+b)(a^2-ab+b^2)=2^c =2^x\cdot2^y$$ now it can only be that $a$ and $b$ are both odd or even since they sum to an even number. Thus if $a$ and $b$ are both odd I have that $a^2$ is odd, $ab$ is odd and $b^2$ is odd. This would imply that $a^2-ab+b^2 = 2^y =1$ which in turn implies that $a^3+b^3 = a+b \implies a=b.$ The problem I have is that if I would have considered that both $a$ and $b$ are even I would have gotten that $a=2t, b=2k$ from where $$8t^3+8k^3=2^c \implies t^3+k^3=2^{c-3}$$ but I couldn't deduce anything from here why cannot $a$ and $b$ be even?

答:
It's easy to see if $a= 2^km; m$ odd and $b = 2^jn;n $odd that $k=j$ (we can factor out $2^{\min(3j,3k)}$ from $a^3 + b^3$) so wolog we can assume $a,b$ are both odd.

If $a \ne b$ and wolog $a < b$ we have $a= 2^x -d;b =2^x + d$ where $d$ is odd and so

$(a^2 -ab+b^2) = (2^x-d)(2^x-d) - (2^x+d)(x^2 - d) +(2^x+d)(2^x+d)=$

$4\cdot 2^{2x} +3d^2$ is .... odd.


问:
Find $\lim_{n\to\infty}2^nx_n$

Find $\lim_{n\to\infty}2^nx_n$ where
$$x_{n+1}=\frac{x_n}{1+\sqrt{x_n^2+1}},\forall n\in \mathbb{N}$$
given $x_1=\sqrt{3}$

I tried finding the first few terms which go as follows:

$$\sqrt3,\frac{1}{\sqrt3},\frac{1}{2+\sqrt3},\cdots$$

This doesnt seem to follow a definite pattern, and Im not sure how to proceed. Any hint is appreciated!

答: Let $x_n = \tan\theta_n, \theta_n \in \left(0,\frac{\pi}{2}\right),\forall n \ge 1\implies \tan(\theta_{n+1})=\dfrac{\tan(\theta_n)}{1+\sec\theta_n}=\dfrac{\sin(\theta_n)}{1+\cos(\theta_n)}=\tan(\frac{\theta_n}{2})\implies \theta_{n+1} = \dfrac{\theta_n}{2}, \theta_1=\dfrac{\pi}{3}. $ Can you take it from here?

Title: Find $\lim_{n\to\infty}2^nx_n$


问:
If $I=\langle q\rangle$ then $\{q\}$ is a Gröbner basis for I.
I've been reading Cox "Ideals, Varieties and Algorithms" and I've got stuck on this problem.

It looks easy but I don't know what to do.

I tried finding a contradiction on remainder being not equal to $0$ but I'm having doubts.

答:
Hint

The condition that each member of $\ I\ $  has remainder $\ 0\ $ with respect to $\ \{g\}\ $ looks like it might be one of the easiest to verify.

For polynomials in two or more indeterminates, the proof that every element of $\ \langle g\rangle\ $ leaves a remainder of $\ 0\ $ with respect to $\ \{g\}\ $ is closely analogous to that for the case of univariate polynomials.


问:
How to simplify $\frac{\frac{\cos x}{2\sqrt{x}} + \sqrt{x}\sin x}{\cos^2x}$, step by step?
I want to simplify this expression

$$\frac{\frac{\cos(x)}{2\sqrt{x}} + \sqrt{x}\sin(x)}{\cos^2(x)}$$

and I know this is the answer

$$\frac{\cos(x)+2x \sin(x)}{2\sqrt{x}\cos^2(x)}$$

How can I get there step by step? Thanks in advance!

Body:
Well, we have:

$$\frac{\frac{\cos(x)}{2\sqrt{x}}+\sqrt{x}\sin(x)}{\cos^{2}(x)} =\frac{\frac{\cos(x)}{2\sqrt{x}}+\frac{2\sqrt{x}}{2\sqrt{x}}\sqrt{x}\sin(x)}{\cos^{2}(x)}=\frac{\frac{\cos(x)+2x\sin(x)}{2\sqrt{x}}}{\cos^{2}(x)}=\boxed{\frac{\cos(x)+2x\sin(x)}{2\sqrt{x}\cos^{2}(x)}}$$


问:
Tensor product of direct sums = direct sum of tensor products?
I have an example in my mind for which this statement holds, but I'm wondering if this is true in general:

Let $M_1$ and $M_2$ be right $R$-modules, and let $N$ be a left $R$-module. Is it true that $(M_1 \oplus M_2) \otimes_R N$ is isomorphic to $(M_1 \otimes_R N) \oplus (M_2 \otimes_R N)$?

In particular I'm not seeing how the map $\phi: (m_1, m_2) \otimes_R n \mapsto (m_1 \otimes_R n, m_2 \otimes_R n)$ is injective. In another word, if $(m_1 \otimes_R n, m_2 \otimes_R n) =(0,0)$ then why is $(m_1, m_2)\otimes_R n = 0$?

Edit: This is true for vector spaces because $m \otimes_F n = 0$ if and only if either $m=0$ or $n=0$. This needs not be true if $F$ is not a field.

Edit: I feel like this is true if $M_1, M_2$, and $N$ are free abelian groups since then they'll have bases.

答:
This is true in general. In case you know some category theory, a short proof would be to use that since $\otimes_R M$ is left adjoint to $\hom(M,-)$, it preserves colimits.

Usually explicit constructions of a tensor product are ugly, it's better to use its universal property whenever possible. From this universal property is that you've constructed the map $(M_1 \oplus M_2) \otimes_R N \to (M_1 \otimes_R N) \oplus (M_2\otimes_R N)$.

Note that tensoring the inclusions $\iota_i \colon M_i \hookrightarrow M_1 \oplus M_2$ with $N$ give maps $\iota_i \otimes 1 \colon M_i \otimes_R N \to (M_1 \oplus M_2) \otimes_R N$, which in turn induce a map

$$
(\iota_1 \otimes 1, \iota_2\otimes 1) \colon (M_1 \otimes_R N) \oplus (M_2\otimes_R N) \to (M_1 \oplus M_2) \otimes_R N.
$$

Explicitly, a pair of elementary tensors $(m\otimes n, m'\otimes n')$ has image $(m,0)\otimes n+(0,m') \otimes n'$.

Check that this is the inverse of your map by computing both compositions.


问:
Help finding Eigenvectors
The matrix is \begin{equation*}
A =
\begin{pmatrix}
1 & 0 & 0 \\
2 & 1 & -2 \\
3 & 2 & 1
\end{pmatrix}
\end{equation*}

I got the eigenvalues $\lambda_1 = 1, \lambda_2 = 1 + 2i$, and $\lambda_3 = 1-2i$. I am only concerned with the complex valued eigenvectors. For $\lambda_2$, I got the eigenvector
\begin{equation*} v_2=
\begin{pmatrix}
0 \\
i \\
1
\end{pmatrix}\end{equation*} and for $\lambda_3$, I got the eigenvector

\begin{equation*}v_3=
\begin{pmatrix}
0 \\
-i \\
1
\end{pmatrix}\end{equation*}

In the back of the book, it is saying the eigenvectors for $\lambda_2$ and $\lambda_3$ are \begin{equation*} v_2=
\begin{pmatrix}
0 \\
1 \\
-i
\end{pmatrix}\end{equation*}
and \begin{equation*}v_3=
\begin{pmatrix}
0 \\
1 \\
i
\end{pmatrix}\end{equation*}

When I checked on Wolfram Alpha, it is saying that my answers are correct. Did I do something wrong or is the back of my book wrong?

答:
You're correct. The eigenvalues are $\lambda_1=1,\lambda_2=1-2i,\lambda_3=1+2i$

$$v_1=\left[\begin{array}{rrr|r}
0 & 0 & 0 & 0 \\
2 & 0 & -2 & 0 \\
3 & 2 & 0 & 0 \\
\end{array}\right]\sim\left[\begin{array}{rrr|r}
1 & 0 & -1 & 0 \\
0 & 1 & \frac{3}{2} & 0 \\
0 & 0 & 0 & 0 \\
\end{array}\right]\longrightarrow\left[\begin{array}{rrr|r}
x_3 \\
-\frac{3}{2}\cdot x_3 \\
x_3 \\
\end{array}\right]=\left[\begin{array}{rrr|r}
1 \\
-\frac{3}{2} \\
1 \\
\end{array}\right]$$

$$v_2=\left[\begin{array}{rrr|r}
2i & 0 & 0 & 0 \\
2 & 2i & -2 & 0 \\
3 & 2 & 2i & 0 \\
\end{array}\right]\sim\left[\begin{array}{rrr|r}
1 & 0 & 0 & 0 \\
0 & 1 & i & 0 \\
0 & 0 & 0 & 0 \\
\end{array}\right]\longrightarrow\left[\begin{array}{rrr|r}
0 \\
-i\cdot x_3 \\
x_3 \\
\end{array}\right]=\left[\begin{array}{rrr|r}
0 \\
-i \\
1 \\
\end{array}\right]$$

$$v_3=\left[\begin{array}{rrr|r}
-2i & 0 & 0 & 0 \\
2 & -2i & -2 & 0 \\
3 & 2 & -2i & 0 \\
\end{array}\right]\sim\left[\begin{array}{rrr|r}
1 & 0 & 0 & 0 \\
0 & 1 & -i & 0 \\
0 & 0 & 0 & 0 \\
\end{array}\right]\longrightarrow\left[\begin{array}{rrr|r}
0 \\
i\cdot x_3 \\
x_3 \\
\end{array}\right]=\left[\begin{array}{rrr|r}
0 \\
i \\
1 \\
\end{array}\right]$$

Title: Help finding Eigenvectors


问:
Prove if $n^2$ is even, then $n$ is even.
I am just learning maths, and would like someone to verify my proof.

Suppose $n$ is an integer, and that $n^2$ is even.  If we add $n$ to $n^2$, we have $n^2 + n = n(n+1)$, and it follows that $n(n+1)$ is even.  Since $n^2$ is even, $n$ is even.

Is this valid?

答: Yes; $ $ simpler: $\,n\  {\rm odd}\,\Rightarrow\, 1\!+\!n\,\ {\rm even}\,\Rightarrow\, n = (1\!+\!n)n-n^2 =\rm even-even = even\,\Rightarrow\Leftarrow$</p>

ContentLicense: CC BY-SA 3.0


问:
Closed form of infinte product proof: $\prod_{i=1}^{n}(1 + x^{2^{i-1}}) = \frac{1-x^{2^n}}{1-x}$
I was working through problems in "An Introduction to Mathematical Reasoning" and am stumped on an induction proof in Problems I: Question 18, which is:

$$\prod_{i=1}^{n}(1 + x^{2^{i-1}}) = \frac{1-x^{2^n}}{1-x}$$

I checked the base case using n=1, and got:

$$1-x^2=1-x^2$$

So I assumed this was true:

$$\prod_{i=1}^{k}(1 + x^{2^{i-1}}) = \frac{1-x^{2^k}}{1-x}$$

and tried this:

$$\prod_{i=1}^{k+1}(1 + x^{2^{i-1}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$\prod_{i=1}^{k}(1 + x^{2^{i-1}})\times(1+x^{2^{k+1-1}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$\frac{1-x^{2^k}}{1-x}\times(1+x^{2^{k}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$1-x^{2^k}\times(1+x^{2^{k}}) = 1-x^{2^{k+1}}$$

$$1-x^{2^{k+k}} \not= 1-x^{2^{k+1}}$$

I've been over this so many times and I still don't see where I'm going wrong, what I've missed, or an alternative approach. Any guidance would be appreciated!

答:
We will proceed by induction.

Note that the base case $n=1$ is true because $\displaystyle 1 + x = \frac{1-x^{2}}{1-x}$. Now, let us assume that the case $n=k$ is true. Then, we have:

$$\prod_{i=1}^{k}(1+x^{2^{i-1}}) =\frac{1-x^{2^{k}}}{1-x}$$

$$(1+x^{2^{k}})\prod_{i=1}^{k}(1+x^{2^{i-1}})=(1+x^{2^{k}})\frac{1-x^{2^{k}}}{1-x}$$

$$\prod_{i=1}^{k+1}(1+x^{2^{i-1}})=\frac{1-(x^{2^{k}})^{2}}{1-x}=\frac{1-x^{2\cdot 2^{k}}}{1-x}=\frac{1-x^{2^{k+1}}}{1-x}$$

Thus, if case $n=k$ is true, then case $n=k+1$ is true as well. Then, because case $n=1$ is true, the statement is true for all $n\in\mathbb{N}$. $\blacksquare$

Your error was in assuming $(1-x^{2^{k}})(1+x^{2^{k}}) = 1 - x^{2^{2k}}$.


答:
You made a calculation error in the very last line.

$$\begin{align}
\left(1-x^{2^k}\right)\left(1+x^{2^k}\right)&=1-\left(x^{2^k}\right)^2\\
&=1-x^{2\cdot2^k}\\
&=1-x^{2^{k+1}}
\end{align}$$

In the last line, on the left-hand side, you have an exponent of $2^{k+k}$, but the correct exponent is $2^k+2^k$.

Title: Closed form of infinte product proof: $\prod_{i=1}^{n}(1 + x^{2^{i-1}}) = \frac{1-x^{2^n}}{1-x}$

Body:
I was working through problems in "An Introduction to Mathematical Reasoning" and am stumped on an induction proof in Problems I: Question 18, which is:

$$\prod_{i=1}^{n}(1 + x^{2^{i-1}}) = \frac{1-x^{2^n}}{1-x}$$

I checked the base case using n=1, and got:

$$1-x^2=1-x^2$$

So I assumed this was true:

$$\prod_{i=1}^{k}(1 + x^{2^{i-1}}) = \frac{1-x^{2^k}}{1-x}$$

and tried this:

$$\prod_{i=1}^{k+1}(1 + x^{2^{i-1}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$\prod_{i=1}^{k}(1 + x^{2^{i-1}})\times(1+x^{2^{k+1-1}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$\frac{1-x^{2^k}}{1-x}\times(1+x^{2^{k}}) = \frac{1-x^{2^{k+1}}}{1-x}$$

$$1-x^{2^k}\times(1+x^{2^{k}}) = 1-x^{2^{k+1}}$$

$$1-x^{2^{k+k}} \not= 1-x^{2^{k+1}}$$

I've been over this so many times and I still don't see where I'm going wrong, what I've missed, or an alternative approach. Any guidance would be appreciated!


问:
Group of characters $q$ modulus $\sum_{\chi\pmod q}\chi(n)$
I was solving the following question (in fig), with the hint that if $n \neq 1 \pmod q$ then there exist a character $\phi$ mod q such that $\phi(n) \neq 1$.

Show that
$$
\sum_{\chi\pmod q}\chi(n)
= \begin{cases}
\varphi(q) &\text{if } n \equiv 1 \pmod q \\
0 &\text{otherwise}.
\end{cases}
$$

I am not sure how the hint is true. But my logic for the hint is following -:
$(\mathbb{Z}/q\mathbb{Z})^*$ is isomorphic to direct product
$\mathbb{Z}/2\mathbb{Z} \times
\mathbb{Z}/2^{\alpha_2-2}\mathbb{Z} \times \mathbb{Z}/p_{2}^{\alpha_2}\mathbb{Z}^* \cdots \times \mathbb{Z}/p_{k}^{\alpha_k}\mathbb{Z}^*$.

Where $q = 2^{\alpha_1}p_1^{\alpha_2} \cdots p_k^{\alpha_k}$. So each of the RHS is a direct product of cyclic groups hence every character of our original group is determined by these characters of these $k+1$ groups of RHS.

So if $n \neq 1 \pmod q$ the, if we see its image on RHS at least one component of RHS will be not identity and we can map that to an element not equal to $1$.

Is my reasoning correct?

答:
Yes. I think the most elementary way is to show that for any finite abelian group $G=\langle H,a\rangle$ then any character on $H$ extends to some character on $G$.

Proof: let the least $k\ge 1$ such that $a^k\in H$, and take $\psi_G(a)$ such that $\psi_G(a)^k = \psi_H(a^k)$.

Starting with $H$ the cyclic subgroup of $\Bbb{Z/(q)}^\times$ generated by $n$ and some obvious non-trivial character we can extend it to a character on $\Bbb{Z/(q)}^\times$ such that $\psi(n)\ne 1$, from which $(\psi(n)-1)\sum_{\chi\bmod q}\chi(n)=0\implies \sum_{\chi\bmod q}\chi(n)=0$.


问:
Difference between the maximum and minimum values of $a+b$ that satisfy $a+b+\frac{1}{a}+\frac{9}{b}=10, (a,b\in\mathbb{R}^+)$

Find the difference between the maximum and minimum values of $a+b$
that satisfy
$$a+b+\frac{1}{a}+\frac{9}{b}=10,\quad(a,b\in\mathbb{R}^+)$$

I'm trying to use  Cauchy–Schwarz inequality, but I can't get a sense of how to transform and solve the given equation. Can anyone help me?

答:
Let $s=a+b$.

Replacing $b$ by $s-a$ in the given equation, we get
$$
s+\frac{1}{a}+\frac{9}{s-a}=10\;\;\;(*)
$$
Regarding $s$ as an implicit finction of $a$, and differentiating the above equation with respect to $a$, we get
$$
s'-\frac{1}{a^2}-\frac{9(s'-1)}{(s-a)^2}=0
$$
Setting $s'=0$, we get $(s-a)^2=9a^2$, which gives $s=4a$.

Replacing $a$ by ${\Large{\frac{s}{4}}}$ in $(*)$, we get
$$
s+\frac{16}{s}=10
$$
which has solutions $s=2$ and $s=8$.

Thus, subject to constraint $(*)$, the difference between the maximum and minimum values of $s$ is $8-2=6$.


问:
Suppose $f$ is entire and one-to-one. Show that $f(z)=az+b$.
My instinct is that it may be proved by Liouville's extended theorem. But how to do so? Or are there any other methods?

Thanks!

答:
Hint: Consider $f(\frac{1}{z})$ and examine the behavior of the singularity at $0$. It can't be an essential singularity (see this using the Weierstrass-Casorati theorem on the behavior near an essential singularity along with the open mapping theorem). So it is either removable or a pole. Then $f(\frac{1}{z})$ has a finite number of negative powers of $z^{-1}$ in its Laurent expansion, so $f(z)$ is a finite power series and must be a polynomial. If the polynomial has degree greater than $1$, then it has $2$ or more roots, contradicting the one-to-one hypothesis.

Note that this gives you the automorphism group of $\mathbb C$.


问:
Induced group homormophism $f_{*} : \pi_1( S^1,p) \rightarrow \pi_1( S^1,f(p))$ due to $z \mapsto z^2$.
Let $f: S^1 \rightarrow S^1$ s.t. $z \mapsto z^2$. This map induces a group homormophism $f_{*} : \pi_1( S^1,p) \rightarrow \pi_1( S^1,f(p))$ . How can we explicitly write this map? I know that the mapping is that a loop gets mapped to 2 loops. But I am not sure how to write it?

答:
Let's consider $\mathbb{S}^1 = \{ z \in \mathbb{C} \mid \lvert z \rvert = 1 \}$. If you'd rather think of the circle living in $\mathbb{R}^2$, just use the standard map $z \mapsto (\Re(z), \Im(z))$, under which $re^{i\theta} \mapsto (r \cos \theta, r \sin \theta)$.

Fix the isomorphism: $\pi_1(\mathbb{S}^1, 1) \to \mathbb{Z}$ with $[\alpha] \mapsto 1$, where $\alpha: \bigl( [0, 1], \{0, 1\} \bigr) \to (\mathbb{S}^1, 1)$ is given by the parametrization $t \mapsto e^{2\pi i t}$. Notice that the endpoints of the interval map to the basepoint $1 \in \mathbb{S}^1 \subset \mathbb{C}$, as required.

Now, the map $f: (\mathbb{S}^1, 1) \to (\mathbb{S}^1, 1)$, $z \mapsto z^2$ produces the parametrization $f \circ \alpha: \bigl( [0, 1], \{0, 1\} \bigr) \to (\mathbb{S}^1, 1)$ given by the formula $t \mapsto \smash[t]{\bigl( e^{2\pi i t} \bigr)^2} = e^{4\pi i t}$. This is a trajectory that moves around the circle at double speed, completing two complete loops as $t$ varies over $[0, 1]$.

What's interesting to observe is that this double-speed loop is precisely the same loop as the one produced by adding $1 + 1 = 2$ in the fundamental group. All that's needed is that they represent the same homotopy class, but in this case they already match as parametrized loops.

Note: generally the fundamental group of a pointed space is non-abelian, so we use multiplicative notation. But in this case, it is abelian, and it's more standard to use the additive notation of the integers. If you insist on multiplicative notation, you could consider a generator $g$ of the group $G$ under the isomorphism $1 \mapsto g^1$, where $m + n \mapsto g^m g^n$ more generally.

Back to the double-speed loop. The way that two classes are combined ("added" in this abelian fundamental group) is by running double speed over the parametrizing intervals for each of the loops, then concatenating the two loops. Recall, if $\beta, \gamma: \bigl( [0, 1], \{0, 1\} \bigr) \to (\mathbb{S}^1, 1)$ are any two loops representing classes in the fundamental group, then $\beta + \gamma: \bigl( [0, 1], \{0, 1\} \bigr) \to (\mathbb{S}^1, 1)$ is defined piecewise by
$$
(\beta + \gamma)(t) = \begin{cases}
\beta(2t), & 0 \leq t \leq \tfrac{1}{2} \\
\gamma(2t-1), & \tfrac{1}{2} \leq t \leq 1
\end{cases}
$$
and we define $[\beta] + [\gamma] = [\beta + \gamma] \in \pi_1(\mathbb{S}^1, 1)$.

But with $\beta = \gamma = \alpha$ as defined above, the parametrization $\alpha + \alpha$ is given by
$$
\alpha(2t) = e^{2 \pi (2t)} = e^{4 \pi t}
\qquad \bigl( 0 \leq t \leq \tfrac{1}{2} \bigr)
$$
and
$$
\alpha(2t-1) = e^{2 \pi (2t-1)} = e^{4 \pi t - 2\pi} = e^{4 \pi t}
\qquad \bigl( 0 \leq t \leq \tfrac{1}{2} \bigr).
$$
Since these are the same formula, you can glue them together without breaking the domain into two pieces. This is the parametrization of the loop representing $2 \in \mathbb{Z}$.

Therefore, $[f \circ \alpha] = [\alpha] + [\alpha] = 2[\alpha] \mapsto 2 \in \mathbb{Z}$.

Addendum: this generalizes to show that for $d \in \mathbb{Z}$, $f_d(z) = z^d$ induces the map $n \mapsto dn \in \mathbb{Z}$ on the fundamental group of $\mathbb{S}^1$.


问:
Expected value 2 distributions
There are 2 continuous normal distributions  $(1,^2)$ and $(-1,^2)$. There is a variable $x$, with probability $p_1$ it is sampled from the first distribution and probability $p_{-1}$ from the second. I have a signal that tells me that $x$ is higher (or lower) than some constant $y$.

I want to calculate the expected value of $x$. How can I do this?

答:
Let $S_{-1},S_1$ be the events that you sampled from
$N(-1,\sigma^2),N(1,\sigma^2)$. Suppose your signal indicates that $X\geq y$. You need to calculate $\mathbb{E}(X|X\geq y)$. We get from the total law of expectation that $$\mathbb{E}(X|X\geq y)=\mathbb{E}(X|X\geq y,S_{-1})P(S_{-1}|X\geq y)+\mathbb{E}(X|X\geq y,S_{1})P(S_{1}|X\geq y)$$ First observe how $$\mathbb{E}(X|X\geq y,S_{-1})=\frac{\int_y^{\infty}\frac{x}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x+1}{\sigma}\big)^2}dx}{\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x+1}{\sigma}\big)^2}dx}$$ $$\mathbb{E}(X|X\geq y,S_{1})=\frac{\int_y^{\infty}\frac{x}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x-1}{\sigma}\big)^2}dx}{\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x-1}{\sigma}\big)^2}dx}$$ It is not reasonable to assume that $S_{-1}$ and $\{X\geq y\}$ are independent; knowing, for example, that $X\geq 2$ would make it more likely that we sampled from $N(1,\sigma^2)$ than from $N(-1,\sigma^2)$. We can calculate our "updated" probability $P(S_{-1}|X\geq y)$ via Baye's Theorem: $$P(S_{-1}|X\geq y)=\frac{P(X \geq y|S_{-1})p_{-1}}{P(X \geq y|S_{-1})p_{-1}+P(X \geq y|S_{1})p_{1}}$$ This becomes $$P(S_{-1}|X\geq y)=\frac{p_{-1}\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x+1}{\sigma}\big)^2}dx}{p_{-1}\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x+1}{\sigma}\big)^2}dx+p_{1}\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x-1}{\sigma}\big)^2}dx}$$ Similarly, $$P(S_{1}|X\geq y)=\frac{p_{1}\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x-1}{\sigma}\big)^2}dx}{p_{-1}\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x+1}{\sigma}\big)^2}dx+p_{1}\int_y^{\infty}\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{1}{2}\big(\frac{x-1}{\sigma}\big)^2}dx}$$ Combining all four components will give you an expression for $\mathbb{E}(X|X\geq y)$. On the other hand, if your signal indicates that $X<y$, you should be able to replace every $\int_y^{\infty}$ with $\int_{-\infty}^y$ and get an expression for $\mathbb{E}(X|X<y)$.

I hope this helps.

Title: Expected value 2 distributions


问:
Specific poof by induction of the pigeonhole principle
I have real trouble understanding this formal proof of the pigeonhole principle. I must also state that I struggle with understanding proofs by induction in general. I still haven't gotten the hang of them.

I have added my questions in brackets.

Theorem: Let $m > n \geqslant 1$ be natural numbers. Then there is no injective function from $\{1, \dots, m\} \to \{1, \dots, n\}$.

Proof: We first prove by induction on $n$ that there can be no injective function $\{1, \dots, n+1\} \to \{1,\dots,n\}$.

Base case: For $n=1$ we only have the constant function $f: \{1,2\} \to \{2\}$, given by $f(1) = 1$ and $f(2) = 1$, which is not injective.

Inductive step: We assume that there is no injective function $\{1, \dots, n+1\} \to \{1,\dots,n\}$. Let $f: \{1, \dots, n+2\} \to \{1,\dots,n+1\}$ be any function and let $k=f(n+2)$. If there is a $j \in \{1,\dots,n+1\}$ with $f(j)=k=f(n+2)$, then (f) is not injective. We assume that there is no such (j).

If $k=n+1$, we consider the restricted function $g:\{1,\dots,n+1\} \to \{1,\dots,n\}, \ j \mapsto f(j)$. Based on the assumption that there is no $j \in \{1,\dots,n+1\}$ with $f(j)=k=n+1$, the function is well-defined [How is the function now well-defined? And how could $k=n+1$ anyway? Isn't the function only mapping to $\{1,\dots,n\}$?]. Because of the inductive step, we know that $g$ cannot be injective. Therefore, there exists $i \neq j \in \{1, \dots, n+1\}$, where $f(i)=f(j)=g(i)=g(j)$ [I understand that because $g$ is injective, there must exist $g(i)=g(j)$. But why does that also apply to $f(i)=f(j)$?].

If $k < n+1$, we define

$\sigma: \{1,\dots,n+1\} \to \{1,\dots,n+1\}, j \mapsto \begin{cases}
    n+1 \text{ if } j = k \\
    k \text{ if } j = n+1 \\
    j \text{ if } j \neq k \text{ and } j \neq n+1
 \end{cases}$

and get a new function $F= \sigma f$, which satisfies $F(n+2)= \sigma(k) = n+1$ [What happened here? What is this function and why do we compose it like that? And how and why does it satisfy $F(n+2)= \sigma(k) = n+1$?]. We know that $F$ is not injective [why?]. But because $\sigma$ is bijective [why?] and $f= \sigma \circ F$, $f$ is also not injective [again, why?].

This concludes the proof. We have now proven that for a natural number $n \geqslant 1$, there is no Injection from $\{1, \dots, n+1\}$ to $1, \dots, n$. For $m > n \geqslant 1$ we can conclude that there is no Injection from $\{1, \dots, m\}$ to $\{1, \dots, n\}$ [Is it because we can repeat the above steps?].

答:
I was going to write a step-by-step explanation of the proof, answering your questions, but then I decided that the real issue here is that the proof is poorly presented. It does not explain what it is doing well, so the reader is left to work it out from context. And for those without much experience, this is very difficult to do.

So instead, I am going to rewrite the inductive step of the proof in what I think is a more clear description. The proof itself is still the same. I'm just trying to be more clear as to what it is doing, and why.

To make the notation a little easier, let me define for integers $i \le j$,
$$\langle i, j\rangle := \{i, i + 1, \dots, j\}$$

Inductive step: We assume that there is no injective function $\langle 1, n+1\rangle \to \langle 1, n\rangle$.

Let $f : \langle 1, n+2\rangle \to \langle 1, n+1\rangle$ be any function. Divide the proof into four cases:

There is a $j < n+2$ with $f(j) = f(n+2)$.

There exist $j \ne i$ with $f(j) = n+1$ and $f(i) = n+1$

For all $j < n+2, f(j) < n+1$.

All functions not satisfying the other three cases.

These four cases cover all possible $f$.

Case 1 is trivial. Since $j \ne n+2$ but $f(j) = f(n+2)$, $f$ is not injective.

Case 2 is also trivial. $f(j) = f(i)$ with $j \ne i$, so $f$ is not injective.

Case 3: Because for all $j \in \langle 1,n+1\rangle, f(j) < n+1$, we can restrict both the domain and codomain of $f$ to define a new function:
$$g : \langle 1, n+1\rangle \to \langle 1, n\rangle : j \mapsto f(j)$$

(Note that instead of just defining $g$, then showing why $g$ is "well-defined", I chose to justify the definition before giving it. $f$ can take on $n+1$ as a value, $g$ cannot, so we have to know that $f(j) \ne n+1$ for any $j$ in the domain of $g$.)

By the induction hypothesis, $g$ cannot be injective. So there is some $i,j \in \langle 1, n+1\rangle$ with $i \ne j$ and $g(i) = g(j)$. But $g$ is just the restriction of $f$, so $f(i) = g(i), f(j) = g(j)$ and therefore $f(i) = f(j)$. $f$ is not injective.

Case 4:

Because case $3$ is false, there is some $j < n+2$ with $f(j) = n+1$. Because case 2 is false, there is no other $i$ with $f(i) = n+1$. In particular $f(n+2) < n+1$.

Define the mapping $$\sigma : \langle 1, n+1\rangle \to \langle 1, n+1\rangle : i \mapsto \begin{cases}
i, & i \ne n+1 \text{ and } i \ne f(n+2)\\
n+1, & i = f(n+2)\\
f(n+2), & i = n+1
\end{cases}$$
$\sigma$ flips $f(n+2)$ and $n+1$ while leaving the other numbers unchanged. $\sigma$ is a bijection. (You asked about this, but quite frankly, you should try harder to see it yourself. The definition of $\sigma$ is right there, and it is simple to show.) So it has an inverse $\sigma^{-1}$.

Define a function $F = \sigma f$. Then

For all $i < n+2$, if $i \ne j$ then $f(i) \ne n+1$, and because case 1 is false, $f(i) \ne f(n+2)$. So $F(i) = \sigma(f(i)) = f(i)$. In particular $F(i) < n+1$.

$F(j) = \sigma(f(j)) = \sigma(n+1) = f(n+2) < n+1$.

So $F : \langle 1, n+2\rangle \to \langle 1, n+1\rangle$ is a function such that for all $i < n+2, F(i) < n+1$. Thus by Case 3 with $F$ playing the role of $f$, $F$ cannot be injective.

So there is some $i, k \in \langle 1, n+2\rangle$ with $i \ne k$, but $F(i) = F(k)$. But then $f(i) = \sigma^{-1}(F(i)) =  \sigma^{-1}(F(k)) = f(k)$, and therefore $f$ is not injective either.

In all cases, $f$ cannot be injective.


问:
Let $p\left(x\right)=x^{2}+bx+c=0$ and equation $p\left(p\left(p\left(x\right)\right)\right)=0$ have a common root then:

prove that equations $p(p(p(x)))=0$ and $p(p(p(p(p(x)))))=0$ have at least two common roots.

prove that $p(p(p(p(p(p(x))))))=0$ has $0$ as a root.

How do i go about solving these problems, what's the concept behind it? Please help!

答: Suppose $a$ is the common root for the first two polynomials. It follows that $0=p(p(p(a)))=p(p(0))=p^2(0)$ where, for brevity, we denote by $p^n(x)$ the $n$th step composition of $p$. Thus, for any even $n$, $p^n(0)=p^{n-2}(p^2(0))=p^{n-2}(0)$. Induction shows that $0$ is now a root of $p^n(x)$ for all $n\in 2\Bbb N$. Now apply this trick with $a$ instead of $0$ for odd $n$.


问:
Proving combinatorial identity with the product of Stirling numbers of the first and second kinds
$$ \sum_{k} \left[\begin{array}{c} n\\k \end{array}\right] \left\{\begin{array}{c} k\\m \end{array}\right\} = {n \choose m} \frac{\left( n-1\right)!}{\left(m-1 \right)!}, \quad \text{for } n,m > 0 $$

$ \left[\begin{array}{c} n\\k \end{array}\right]  $ is Stirling number of the first kind

$ \left\{\begin{array}{c} k\\m \end{array}\right\} $ Stirling number of the second kind

I don't know how to aproach this. I tried think of combinatorial interpretation and mathematical induction, but I got stuck a the beginning.

答:
Here is a combinatorial proof. Count tuples $(\sigma_1,\ldots,\sigma_m)$ of permutations such that the domain of each $\sigma_i$ is a subset $A_i$ of $[n](=\{1,\ldots,n\})$ with $(A_1,\ldots,A_m)$ an ordered partition of $[n]$ in two different ways.

Each such tuple induces a unique permutation $\sigma$ on $[n]$, namely the permutation $\sigma$ for which the restriction of $\sigma$ to $A_i$ is precisely $\sigma_i(1\leq i\leq m).$ The number of tuples that induce a permutation with $k$ cycles is equal to the number of ordered partitions of a $k$-element set into $m$ subsets, i.e., ${k \brace m}m!$. Therefore, the total number of tuples must be
$$
\sum_k {n \brack k}{k \brace m}m!.
$$

We may also count such tuples $(\sigma_1,\ldots,\sigma_m)$ by viewing them as words. Arrange the elements of $[n]$ into a word in $n!$ ways and select $m-1$ of the $n-1$ gaps between letters to split the word into $m$ permutations. The number of ways to do this is
$$
n!{n-1 \choose m-1}.
$$
Therefore, we must have
$$
\sum_k {n \brack k}{k \brace m}m!=n!{n-1 \choose m-1},
$$
which is equivalent to your identity.


问:
Creating nearest neighbors Laplacian matrix
I want to create a general formula for an $N \times N$ nearest neighbors Laplacian matrix such that I can write an mfile in MATLAB to compute the matrix for given $N$.

The nearest neighbors Laplacian matrix is of the below form

\begin{equation}
L=\left[
\begin{array}{ccc}
-2 & 1 & 0 & \cdots & 0 & 1\\
1 & -2 & 1 & 0 & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
0 & \cdots & 0 & 1 & -2 & 1\\
1 & 0 & \cdots & 0 & 1 & -2\\
\end{array}
\right].
\end{equation}

where the main diagonal elements are all $-2$ and we have two elements of $1$ before and after each element in the main diagonal.

Would appreciate any help...

答:
For small matrices (e.g. $n=10$), try

```<code>L = eye(10)
L = circshift(L,[1 0]) + circshift(L,[0 1]) - 2*L
</code>```

For larger dimensions (e.g. $n=1000$), you'll probably want a sparse matrix

```<code>L = speye(1000)
L = circshift(L,[1 0]) + circshift(L,[0 1]) - 2*L
</code>```

Body:
For small matrices (e.g. $n=10$), try

L = eye(10)
L = circshift(L,[1 0]) + circshift(L,[0 1]) - 2*L

For larger dimensions (e.g. $n=1000$), you'll probably want a sparse matrix

L = speye(1000)
L = circshift(L,[1 0]) + circshift(L,[0 1]) - 2*L


问:
For a non-surjective function, $f : \Bbb{R} \to \Bbb{R}^+$ is better than $f : \Bbb{R} \to \Bbb{R}$?
Example:

From this we can tell no negative real number can be the image of any element of the domain. Thus not surjective because the range is not equal to the codomain, which means the function associates a any real number to a positive real number only. Is it better to write it this way $f : \Bbb{R} \to \Bbb{R}^+$ then?

答:
It depends on how you define what a function is (i.e., whether you take the set of ordered-pairs alone a la Bourbaki, or use something like the source-target predicate).

If you use the Bourbaki definition (i.e., $f\colon A\to B$ is $\{(a,f(a))\mid a\in A\}\subseteq A\times B$ and the Kuratowski ordered pair $(a,b)=\{\{a\},\{a,b\}\}$), then the codomain $B$ cannot be recovered from $f$.

On the other hand, if you build the codomain into the function as in source-target predicate, then you get the absolute value $\mathbb{R}\to\mathbb{R}$ and $\mathbb{R}\to\mathbb{R}^+$ are two different functions (which are related by the inclusion $\mathbb{R}^+\to\mathbb{R}$), which may or may not be what you want.


问:
Prove maximum of function
I have a function

$$f(x,k) = \frac{x^{p-k} \prod_{j=0}^k K_j}{\sum_{i=0}^p (x^{p-i} \prod_{j=0}^i K_j)}$$

for $k=0,...,p$, where $K_0:=1$ and $x$ is real positive. How can one prove that the value of $x$ which maximises $f(x,k)$ for a given $k$ is the root of

$$\frac{\sum_{i=0}^p ((p-i)x^{p-i} \prod_{j=0}^i K_j)}{\sum_{i=0}^p (x^{p-i} \prod_{j=0}^i K_j)} = p-k$$

for $k=1,...,p-1$, which numerically seems to work as the answer?

Title: Prove maximum of function

Body:
Let $\Pi_{j=0}^i K_j=a_i$ for $i=1\dots p$, then

$$f'(x,k)=x^{p-k-1}a_k\frac{(p-k)\sum_{i=1}^p x^{p-i}a_i-x\sum_{i=1}^p (p-i)x^{p-i-1}a_i}{\left(\sum_{i=1}^p x^{p-i}a_i\right)^2}
$$

Now, $$f'(x,k)=0\implies(p-k)\sum_{i=1}^p x^{p-i}a_i-x\sum_{i=1}^p (p-i)x^{p-i-1}a_i=0,$$

and, therefore

$$
\begin{aligned}(p-k)\sum_{i=1}^p x^{p-i}a_i&=x\sum_{i=1}^p (p-i)x^{p-i-1}a_i,\\
&=\sum_{i=1}^p (p-i)x^{p-i}a_i.
\end{aligned}$$

This results in
$$
\begin{aligned}(p-k)&=
\frac{\sum_{i=1}^p (p-i)x^{p-i}a_i}{\sum_{i=1}^p x^{p-i}a_i}\\
&=\frac{\sum_{i=1}^p (p-i)x^{p-i}\Pi_{j=0}^i K_j}{\sum_{i=1}^p x^{p-i}\Pi_{j=0}^i K_j}.
\end{aligned}$$


问:
Combinatorics Through Guided Discovery Question 77
I need help with a homework question. Thank you in advance!

```<code> Suppose that f is a function on the nonnegative integers such that f(0) = 0 and f(n) = n+f(n−1).

 (A) Prove that f(n) = n(n+1)/2. Notice that this gives a third proof that 1 + 2 + · · · + n =
 n(n+1)/2, because this sum satisfies the two conditions for f. (The sum has no terms and is thus 0
 when n = 0.)

 (B) Also find a formula if f(0)=3.
</code>```

(A): I believe the induction portion for part A goes as follows:

```<code>We prove the formula for f by induction on n. If n = 0, then n(n+1)/2=0.

Assume that f(k-1) = ((k-1)k)/2

Then,
f(k) = k + f(k-1)
f(k) = k + ((k-1)k)/2
f(k) = k(k+1)/2

Therefore, the truth of the formula for n=k-1 implies its truth for n=k and thus by the principle of
induction, the formula for f holds true for all nonnegative integers n.
</code>```

(B): I'm not too sure how to find the formula, but I know it has to be recursive. Once a closed formula is found, then it has to be proved with induction. Any tips for finding a formula for f(0)=3 would be appreciated for this part!

答:
Your part (A) is basically correct. My only point is that when you state your assumption that $f(k-1) = \frac{(k-1)k}{2}$, you should also state it's for some $k \ge 1$.

As for part (B), note $f(1) = 1 + f(0) = 1 + 3$, $f(2) = 2 + f(1) = 2 + 1 + 3 = (2 + 1) + 3$, $f(3) = 3 + f(2) = 3 + (2 + 1) + 3 = (3 + 2 + 1) + 3$, etc. I assume you see a pattern here, which I'll leave to you to finish. However, dodoturkoz's question comment already states the result for you.


问:
Solving summation $2n+2^2(n-1)+2^3(n-2)+....+2^n$
Can anyone help me with this summation? I tried to use the geometric series on this, but I can't use that.
$$2n+2^2(n-1)+2^3(n-2)+....+2^n$$
I am trying to do this for studying algorithms. Can we get a closed form for this ?</p>

答:
All you have to find out is how to sum out $$\sum_{k=1}^n 2^k(n-k+1)$$

This unwinds as

$$(n+1) \sum_{k=1}^n2^k-\sum_{k=1}^nk2^k$$

The first term is a geometric series. Can you find out what the second term is?

One way is to note that $$\sum_{k=1}^n x^k=x\frac{1-x^n}{1-x}$$

Now, differentiate and multiply by $x$ to get that

$$\sum_{k=1}^n kx^k=x\cdot\frac{d}{dx}\left(x\frac{1-x^n}{1-x}\right)$$

After finding out what the right hand side is, plug $x=2$.


答:
It depends on the context, but you're right that writing $f : \Bbb{R} \to \Bbb{R}^+$ contains superior information about the rule $x \mapsto |x|$. There are a few reasons why you might choose to write a more general codomain than what is called for, for example:

Sometimes a definition will tie you to a codomain. For example, the definition of function composition takes a function $f : A \to B$ and $g : B \to C$ and produces a function $g \circ f : A \to C$, defined by $(g \circ f)(x) := g(f(x))$. Now, if we take, for example, $g : \Bbb{R} \to \Bbb{R} : x \mapsto x^3 - x$, then we can only really compose with $f$ it is has codomain $\Bbb{R}$, to match the domain of $g$. Of course, it's a simple thing to do to extend a codomain (or even limit the domain of $g$ to $\Bbb{R}^+$), but one or the other should be done in order to make the composition kosher.

Sometimes the codomain is easy, but the range is unknown. As per Hagen von Eitzen's suggestion, we can take any object conjectured to exist (but whose existence is unknown) and turn it into a function to $\{0, 1\}$ with unknown range. For example:
$$f : \Bbb{N} \to \{0, 1\} : n \mapsto \begin{cases} 1 & \text{if $n$ is an odd perfect number} \\ 0 & \text{otherwise.} \end{cases}$$
Nobody knows the range of this function, but we do know the codomain is $\{0, 1\}$.

Sometimes, when you're writing mathematics, you choose a more general codomain, because writing the range as the codomain becomes an unproven assertion that demands proof, and writing a proof will interrupt the flow of the writing.

And sometimes there are pedagogical reasons. You might want to show your students that not every function needs to be surjective, to give the term "surjective" some meaning!

Title: For a non-surjective function, $f : \Bbb{R} \to \Bbb{R}^+$ is better than $f : \Bbb{R} \to \Bbb{R}$?

Body:
Example:

From this we can tell no negative real number can be the image of any element of the domain. Thus not surjective because the range is not equal to the codomain, which means the function associates a any real number to a positive real number only. Is it better to write it this way $f : \Bbb{R} \to \Bbb{R}^+$ then?


问:
Story behind the proof of hard theorems
I would like to know the story of how the proofs of some "hard" theorems were reached. More specifically, how did the author get to the "right" ideas (especially when the proof is long and complicated)? Though I'm not particularly interested in the ideas per se.

I am mainly interested in the field of analysis but any contribution is welcome.

Let me start with the example of Carleson's theorem on the pointwise almost everywhere convergence of Fourier series of $L^2$ functions, which is an example of a theorem that "everybody" thought it wouldn't be true.

I tried for some years and then I forgot about
it before it again came back to me. Then, in the
beginning of the 1960s, I suddenly realized that I
knew exactly why there had to be a counterexample
and how one should construct one. Somehow, the
trigonometric system is the type of system where it
is easiest to provide counterexamples. Then I could
prove that my approach was impossible. I found
out that this idea would never work; I mean that it
couldn’t work. If there were a counterexample for
the trigonometric system, it would be an exception
to the rule.
Then I decided that maybe no one had really
tried to prove the converse. From then on it only
took two years or so. But it is an interesting example of “to prove something hard, it is extremely
important to be convinced of what is right and
what is wrong”. You could never do it by alternating between the one and the other because the
conviction somehow has to be there.

This is an excerpt from an interview of Carleson by Raussen and Skau.

答: You might enjoy Cédric Villani's Birth of a Theorem, a first hand account of his journey to fomulate, and prove, the theorem that ultimately won him the Fields Medal. There is also this lecture with the same title (and a Q&A) on Youtube.

Title: Story behind the proof of hard theorems


问:
Help understanding matrix math in whitening transformation proofs
I'm looking at a couple small articles about whitening transformations:

Background

https://theclevermachine.wordpress.com/2013/03/30/the-statistical-whitening-transform/
and
https://andrewcharlesjones.github.io/posts/2020/05/whitening/

In both articles, there comes a step where given a centered data matrix $X$

we compute its covariance

$$\Sigma = XX^T$$

and come up with a matrix $W$ that satisfies

$$WW^T = \Sigma^{-1}$$

The idea now is that if we transform our data $X$ into $Y = WX$ we can show that

$$cov(Y) = WX (WX)^T$$
$$= WXX^TW^T$$
$$= W\Sigma W^T$$

Issue

All of this seems reasonable so far, but both authors in the referenced articles make the following leap:
They claim you can reduce the above to $I$. In this article,

https://theclevermachine.wordpress.com/2013/03/30/the-statistical-whitening-transform/,

some of the work is sort of shown:

It is stated that $W\Sigma W^T$ = $WW^T\Sigma$ which would then obviously reduce to $I$.

Why is it OK to swap the order of $W^T$ and $\Sigma$ in the above expression?

Note: some of the matrix math in the article by andrew jones has a few matrix dimension mistakes. He is going to fix those. I believe though that what I have summarized here makes sense except for the last line in the proof. I am curious if that line is justified in some way that I don't see... And I have a suspicion that it's gone to be something that I'm just overlooking.

答:
Short answer

If $\Sigma=XX^T$ then Sigma is nxn and X is nxp. Ok. Then if Y=WX then W is pxn and Y is pxp. Then cov(Y) is pxp. $W\Sigma W^T=WW^T\Sigma$ makes no sense because first is pxn nxn nxp and the second is pxn nxp nxn.

Longer answer

I will address the introduction of the Andy Jones article.

First, the original data matrix $X$ has to be centered. The column mean has to be subtracted from each element of the column.

Next, the article states that $cov(X)=X^TX$. If $X$ is centered, its covariance is $cov(X)=\frac{X^TX}{n-1}$.

The dimensions of $X^T\Sigma^{-1} X$ in the introduction make no sense. $X^T$ has dimensions p x n, $\Sigma^{-1}$ has dimensions p x p, and $X$ has dimensions n x p.

The author claims $W^TW=\Sigma^{-1}$. For this to be true, $W$ has dimensions m x p for some m. Now $Y=WX$ by definition. But $W$ has dimensions m x p and $X$ is a n x p matrix.

It does not make sense no matter how hard you try to play around with the dimensions. It is possible I have gotten it completely wrong. In which case, do let me know. But as I have tried to work it out, it doesn't work.

Conclusion

This article was not written to make mathematical sense. The Berkeley article is just as bad. I recommend not reading too much into the math in these two articles and try doing it on your own.


问:
Solving integral involving Dirac delta function i.e$\int_{-\infty}^\infty e ^{\delta(x)} dx$
I know some properties of Dirac-delta function specially those which are useful for integration involving these functions such as
$$\int\limits_{-\infty}^{\infty}\delta(x)\,\mathrm{d}x$$

But I am stuck in this (below) integral and don't know how to proceed further or which property should we use?

$$\int\limits_{-\infty}^\infty e ^{\delta(x)}\,\mathrm{d}x$$

How to solve this problem?

Any hint would be appreciated!

答:
The expression is not defined. However, we can certainly say that the integral does not converge if we define $\delta$ through approximations.

We will use a Lorentz-curve
$$\delta_\varepsilon(x) = \frac{1}{\pi}{\frac{\varepsilon}{x^2+\varepsilon^2}}.$$
This function has a narrow maximum at $x=0$, the width is
$\sqrt {\epsilon }\to 0$ and the hight
$\frac{1}{\sqrt {\epsilon }}\to \infty$. For all $\varepsilon$ the area below the function is $1$.
As we choose $\varepsilon\to0$, $\delta_\varepsilon(x)$ tends to $\delta(x)$. Now we can evaluate
$$\int\limits_{-\infty}^{\infty}e^{\frac{1}{\pi}\lim\limits_{\varepsilon\to0}{\frac{\varepsilon}{x^2+\varepsilon^2}}}\,\mathrm{d}x > \operatorname{PV} \int\limits_{-\infty}^{\infty}e^{\frac{1}{\pi}\lim\limits_{\varepsilon\to0}{\frac{\varepsilon}{x^2+\varepsilon^2}}}\,\mathrm{d}x,$$
which is not the exact same thing as your integral but it now at least makes  a little bit more sense. As you can see I put another integral as an inequality there. The $\operatorname{PV} $ is the Cauchy principal value. So our $x$ does not take values anymore at the "critical point" zero. This integral becomes
$$\operatorname{PV} \int\limits_{-\infty}^{\infty}e^{\frac{1}{\pi}\cdot0}\,\mathrm{d}x = \operatorname{PV} \int\limits_{-\infty}^{\infty}1\,\mathrm{d}x\to\infty.$$
This integral is smaller than our original integral and tends to $\infty$, which means that our first integral diverges too.


Title: Solving summation $2n+2^2(n-1)+2^3(n-2)+....+2^n$

Body:
Can anyone help me with this summation? I tried to use the geometric series on this, but I can't use that.
$$2n+2^2(n-1)+2^3(n-2)+....+2^n$$
I am trying to do this for studying algorithms. Can we get a closed form for this ?</p>

Body:
Notice that
$$S_n=2n+2^2(n-1)+2^3(n-2)+\cdots+2^{n-1}(2)+2^n(1)$$
$$S_{n-1}=2(n-1)+2^2(n-2)+2^3(n-3)+\cdots+2^{n-1}(1)+2^n(0)$$
differ by
$$S_n-S_{n-1}=2+2^2+2^3+\cdots+2^n=2(2^n-1)$$

Therefore, $$S_n=2(2^n-1) + S_{n-1} =2(2^n-1) + 2(2^{n-1}-1) + S_{n-2}$$and so on until
$$S_n=2(2^n-1 +2^{n-1}-1+2^{n-2}-1+\cdots+2^{1}-1)=2([2^1+2^2+\cdots+2^n]-n)$$

You should be able to figure out the answer.


问:
Counting one-to-one functions with some restriction
Let $A= \{1,2,3,4,5\}$ and $B=\{0,1,2,3,4,5\}$. What is the number of one-to-one functions $f:A\to B$ such that that $f(i) \neq i$ for all $i\geq 2$ and $f(1)\neq 0,1$?

I tried using derrangements to solve this problem, but I am getting stuck. I have tried using two approaches.

Approach 1: let us say $A$ had one more number (say $0$), so we should derange $6$ of these which will give the answer as $265$. Now, we need to subtract the number of one-to-one functions with $f(0)=0$ as 0 is an additional number that we have added. So I did $265- 5P4= 145$ but that is incorrect (the answer is $256$)

Approach 2: I modified the ranges taking 2 cases. Case 1: one out of $0$ or $1$ is not in range (so the number of possibilities is the number of derrangements of $5$). Case 2: one out of $2,3,4,5$ is not in the range.

I am unable to correctly solve case 2. Any help/suggestion/new method will be very helpful. I would be happy to learn!

答:
We'll consider these cases based on what element is missing from the range.

Case 1: If $0$ is missing from the range, then we just have a derangement of $A$, of which there are $44$.

Case 2: Let $b>0$ be the element missing from the range, and let $a$ be the element with $f(a)=0$. Note that $a$ cannot be $1$.

Case 2a: If $a\neq b$, the consider the function $g:A\to A$ defined by $g(a)=b$, and $g(i)=f(i)$ for all $i\neq a$. Then $g$ is also a derangement of $A$. You can obtain any function $f$ that falls under this case by taking a derangement $g$ of $A$, and then picking one of $2, 3, 4$, or $5$, and sending that element to $0$. There are $44$ ways to choose $g$, and then $4$ ways of picking what gets sent to $0$, so this case has $44*4$ possibilities total.

Case 2b: If $a=b$, then $f$ deranges the elements of $A\setminus a$ and sends $a$ to $0$. There are $4$ choices of which element gets sent to $0$, and then $9$ ways to choose a derangement of the remaining $4$ elements, so this case has $4*9$ possibilities total.

Hence, the answer is $44+44*4+36=256$ possibilities.


问:
First Order Differential Equation Problem - Calorie intake
UPDATE:  Thanks to Matthew for pointing out what to do next, this problem has been solved.

Thanks everyone for your time and effort.

I've been stuck on this DE problem for a few days now and was wondering if someone can point me in the right direction.  I know the solution is $101$ days.

The daily calorie intake is taken to be a fixed quantity $C$ and is modelled by the DE.

$$\frac{dt}{dm} = \frac{1}{a(C-bm)}$$

where $a$ and $b$ are both constants.

A man is $90$kg.  If he were to take no calories for $14$ days, his mass would reduce by $20$%.  How long will it take him to reduce his mas by the same amount if he took $3/4$ of the calories required to keep his mass constant at $90$kg?

I'm missing something simple, but just can't figure it out.

Thanks in advanced.

So far I have the general solution to the DE as:

$$\int dt = \int\frac{1}{a(C-bm)} dm$$

$$t + K = - \frac{1}{ab} ln|C-bm| $$

$$-tab - Kab = ln|C-bm| $$

$$|C-bm| = e^{-tab} e^{-Kab}$$

$$C-bm = Ae^{-tab}$$ where $$A=\pm e^{-Kab}$$ and $K$ is an arbitrary constant.

Now, when $t=0$ $m=90$kg, so $A=C-90b$, therefore we now have

$$C-bm = (C-90b)e^{-tab}$$

Transposing

$$ bm= \frac{C-(C-90b)e^{-tab}}{b}$$

$$ m(t) = \frac{C+(90b-C)e^{-tab}}{b}$$

Next, $t=14$ , $m=72$ ($20$% reduction of $90$), $C=0$

$$72b = 90be^{-14ab}$$

$$\frac{72}{90} = e^{-14ab}$$

$$e^{14ab} = \frac{90}{72}$$

Thus

$$ab=\frac{\ln\frac{90}{72}}{14}$$

$$ab=\frac{1}{14}\ln\Big(\frac{5}{4}\Big)$$

$$ab=0.0159$$

So substituting $ab$ back into the equation

$$ m(t) = \frac{C+(90b-C)e^{-t0.0159}}{b}$$

So I have 3 unknows $C$ , $b$ and $t$. I can seem to extract the required information to solve for $t$.

The next part is where I get stuck.  I don't know how to implement the $3/4$ of the calories required in my formula.

答:
@Stephen you're right. I made an elementary integration error. Here is the correct solution.

The solution to the DE $\frac{dm}{dt}=a(C-bm)$ subject to the initial condition $m(0)=90$ is $$m(t)=\frac{C+(90b-C)e^{-abt}}{b}$$ If $C=0$ then $m(14)=72$ implies $ab=\frac{1}{14}\ln\Big(\frac{5}{4}\Big)$ which reduces our solution to $$m(t)=\frac{C+(90b-C)(0.8)^{t/14}}{b}$$The daily calorie intake which renders the mass of the individual constant is $C^{*}=bm_0$ where $m_0$ is the initial mass. In our scenario our person initially weighs $m_0=90 \text{kg}$ making $C^*=90b$. Replacing $C$ with $\frac{3}{4}C^*=\frac{135b}{2}$ in our solution gives $$m(t)=\frac{135}{2}+\frac{45}{2}(0.8)^{t/14}$$ Solving $m(t)=72$ for $t$ yields $t\approx 101$.


问:
Number Theory - Find all $n$ such that $x^2 ≡ x$ (mod $n$) for $x$ ≡ 0,1 (mod $n$) only
When $n = p^k$, where p is prime and k is a positive integer

if $x^2  ≡ x$ (mod $p^k$), then $p^k$ divides $x^2-x = x(x-1)$, since $x$ and $x-1$ are coprime, $p^k$ divides either $x$ or $x-1$, so $x ≡ 0$ (mod $p^k$) or $x ≡ 1$ (mod $p^k$).

When n is not in the form of $p^k$,

on checking of counterexamples, $4^2  ≡ 4$ (mod $6$), where $4$ is not congruent to $0,1$ modulo $6$ and $6$ is a product of distinct primes.
Please suggest the general approach to prove that there exists solution other than $x ≡ 0,1$ (mod $n$) for this case.

答: If the modulus is of the form $pq$ for $p, q$ coprime, use the Chinese Remainder theorem to solve $x \equiv 0 \pmod p, x \equiv 1 \pmod q$ or the other way around.  Note that also $3^2 \equiv 3 \pmod 6$ which is the other way around from $4$.


问:
Determinant Expression
How I will be able to found any expression for the determinant of the matrix $R^{N\times N}$ wiht entries belong $\mathbb{R} $, if $R_{ij}=\dfrac{2}{N}-\delta_{ij}$?</p>

答:
A matrix such as your $R$ has a lot of structure that is worth understanding. Note this. Define the following, normalized vector

$$ |\xi\rangle = \frac{1}{\sqrt{N}} \sum_{j=1}^{N} |j\rangle$$

In other words $ |\xi\rangle$ is the unit vector with all components one in the standard basis ($|j\rangle$ is the vector with component $1$ at position $j$). Now note your matrix is simply

$$R = 2 |\xi\rangle \langle \xi| -I $$

were $I$ is the identity matrix. It should be clear that $|\xi\rangle \langle \xi|$ is the orthogonal projector projecting onto direction $|\xi\rangle$. Its eigenvalues hence are 1, with multiplicity 1, with eigenvector $|\xi\rangle$ and zero, with multiplicity $N-1$ corresponding to all vectors orthogonal to $|\xi\rangle$. The determinant is the product of the eigenvalues hence

$$\det(R) = (2\cdot 1 -1) (2\cdot 0 -1)^{N-1} = (-1)^{N-1} $$

Title: Determinant Expression


问:
A well defined homomorphism from $\mathbb{Z}/48\mathbb{Z}$ into $\mathbb{Z}/{36}$
I read book of Dummit and Foot Abstract algebra. I need some help with the following question.

Let $\mathbb{Z}/{36} = <x>.$ For which integers $a$  does the map $\psi_{a}$ defined by $\psi_{a}: \bar{1} \mapsto x^a$ extend
  to a well defined homomorphism from $\mathbb{Z}/48\mathbb{Z}$ into $\mathbb{Z}/36\mathbb{Z}$ Can $\psi_{a}$ ever be a surjective
  homomorphism?

Here are some attempts.

Let $n+m<48.$ We have $$\psi_a (\bar{n}+\bar{m})=x^{a(n+m) \mod 36}.$$ On the other hand
$$\psi_a (\bar{n})\psi_a (\bar{m})=x^{an\mod 36}x^{am\mod 36}=x^{an\mod 36+am\mod 36}.$$
Suppose that $\psi_{a}$ is  a surjective. Then for all $x^i, i=0\ldots 35$ there is $\bar(j), j=0\ldots48.$ such that $\psi_a (\bar{j})=x^i.$ For which values a???

This is my attempt so far.-

答:
I am using the additive groups $\mathbb{Z}/m \mathbb{Z}$ for both the domain and range.

First suppose $\psi_a$ is a well defined homomorphism.
We have $\psi_a([1]_{48}]) = [a]_{36}$ and if $\psi_a$ is a homomorphism then
$\psi_a([n]_{48}]) = [an]_{36}$ and so
$\psi_a([48]_{48}]) = [0]_{36} = [48a]_{36}$ from which we get $36 \mid 48a$. This
gives $3 \mid 4a$ and hence $3 \mid a$.

Now suppose $3 \mid a$, then we first need to check that $\psi_a$ is well defined in the sense that if $[x]_{48}=[y]_{48}$ then $\psi_a([x]_{48})=[ax]_{36} = \psi_a([y]_{48})=[ay]_{36}$,
or equivalently, $[a(x-y)]_{36}=[0]_{36}$. Since $x-y = 48 k$ for some $k$ we see that $48 ak = 12 \cdot 4 \cdot a k = 4 \cdot 12 \cdot 3 \cdot {a \over 3} k = 36 \cdot 4 \cdot {a \over 3} k$ and so $[a(x-y)]_{36}=[0]_{36}$.

Then since
$\psi_a([n+m]_{48}]) = [a(n+m)]_{36} = [an]_{36} + [am]_{36} = \psi_a([n]_{48}]) + \psi_a([m]_{48}])$, we see that $\psi_a$ is a homomorphism.

Note that $\operatorname{im} \phi_a = < [a]_{36}>$, and Proposition 5 (2) in Dummit & Foote shows that
$|\operatorname{im} \phi_a| = {36 \over \gcd(a, 36)} $. Since $3 \mid a$, we see
that $\gcd(a, 36) \ge 3$ and so $|\operatorname{im} \phi_a| \le 12$ and so $\psi_a$
cannot be surjective.


问:
In the figure, OB is the perpendicular bisector of line segment DE
In figure, $OB$ is perpendicular bisector of line segment $DE$, $FA$ perpendicular to $OB$ and $FE$ intersects $OB$ at the point $C$, then find the sum $\displaystyle \frac{OC}{OA}+\frac{OC}{OB}$

I have proved the similarity of the triangles FAC~EBC and DBO~FAO
please help after that.

答:
From $\triangle FAC \sim \triangle EBC$:

$$\frac {BE}{AF} = \frac {BC}{AC}$$

From $\triangle DBO \sim \triangle FAO$:

$$\frac {DB}{FA} = \frac {OB}{OA}$$

Since $OB$ is the perpendicular bisector of $DE$, we have $BD = BE$. Therefore:

$$\frac {BO - CO}{CO-AO} = \frac{BC}{AC} = \frac {BE}{AF} = \frac {DB}{FA} = \frac {OB}{OA}$$

$$OA\times OB - OA \times OC = OB \times OC - OA \times OB$$

$$2 \times OA \times OB = OA \times OC + OB \times OC$$

Thus

$$\frac {OC}{OA} + \frac {OC}{OB} = \frac {OB \times OC + OA \times OC}{OA \times OB} = 2$$


问:
How to relate $|\delta x|$ and $|\tilde\delta x|$ in an inequality $A\le |\tilde\delta x|\le B$ where $A$ and $B$ contain $|\delta x|$?
$|\delta x| = |(\tilde x - x)/x|$  (this is the absolute value of relative error)

$|\tilde\delta x| = |(\tilde x - x)/\tilde x|$ (bound for some distinct quantity)

I need to find an inequality which relates these in this way:

$A\le |\tilde\delta x|\le B$ where $A$ and $B$ contain $|\delta x|$.

I know $\tilde x = x(1 + \delta x)$ or $\delta x = \delta(x)/x = (\tilde x - x)/x$

No idea how to proceed with finding that inequality though. Thank you very much if you can show me how this is done.

答:
Note that
$$|\tilde\delta x| = |\delta x| \frac{|x|}{|\tilde x|}.$$
From the first equation in the question,
$\left| \frac{
\tilde x}{ x}-1\right| = |\delta x| $,
so by triangle inequality, we obtain $$\frac{|\tilde x|}{|x|}  \le 1 + \left| \frac{\tilde x}{ x}-1\right| = 1+|\delta x|,$$
and
$$ \frac{|\tilde x|}{| x|} \ge 1 - \left| \frac{\tilde x}{ x}-1\right| = 1-|\delta x|.$$
Thus
$$ \frac{|\delta x|}{1+|\delta x|}\le |\tilde \delta x | \le \frac{|\delta x|}{1-|\delta x|}.$$


答: The integral does not converge. $\delta(x)=0$ everywhere, except at zero. $e^0=1$. This means, the function under the integral is equal to $1$ nearly everywhere. Regardless of what happens at $0$, the integral diverges.

Title: Solving integral involving Dirac delta function i.e$\int_{-\infty}^\infty e ^{\delta(x)} dx$

Body:
I know some properties of Dirac-delta function specially those which are useful for integration involving these functions such as
$$\int\limits_{-\infty}^{\infty}\delta(x)\,\mathrm{d}x$$

But I am stuck in this (below) integral and don't know how to proceed further or which property should we use?

$$\int\limits_{-\infty}^\infty e ^{\delta(x)}\,\mathrm{d}x$$

How to solve this problem?

Any hint would be appreciated!


问:
Set of units in localization of $R$
Let $R$ be a ring, and let $P$ be a prime ideal of $R$. Let $S = R \setminus P$, and set $R_p = S^{-1} R$.

What are the units in $R_p$? I'm trying to prove that $\frac{a}{b}$ is an unit if and only if $a \in S$, but I'm having trouble.

One direction is easy as if $a \in S$, $\frac{b}{a} \in R_p$, which is the desired inverse.

The other direction is giving me some trouble.

So we let $\frac{a}{b}$ be an unit, and we find its inverse $\frac{a'}{b'}$. Then $\frac{aa'}{bb'} = \frac{1}{1}$ This means there exists $t \in S$ such that $taa' = tbb'$, but I have no idea how to proceed from here.

Thanks for your help!

答:
Hint: Look at both sides of the equation $taa'=tbb'$.  Each element of $R$ is either in $P$ or in $S$.  With that in mind, what can you say about the different parts of this equation?

More details are hidden below.

 Since $t,b,$ and $b'$ are all in $S$, so is $tbb'$.  This means that $a\in S$, since otherwise $a$ would be in $P$ and so $taa'$ would be in $P$ as well.

Title: Set of units in localization of $R$


问:
Doubt in $\varepsilon$-$\delta$ proof of continuity of $x^2$
I have one elementary doubt on the proof that $f(x)=x^2$ is continuous for every $a \in \Bbb R$. The initial steps usually presented are: to deduce which $\delta$ will work we write:

$$|x^2-a^2|=|x-a||x+a|$$

Now, we must find some bound for $|x+a|$, so we require that $|x-a|<1$ or some other positive real number. Here comes my first doubt, this trick appears very often, what's the intuition on making $|x-a|<1$?

After that we have that this implies $x < 1 + a$ and this implies that $|x+a| < 1 + 2|a|$. Now it's obvious that if we set $|x-a|< \varepsilon/(1+2|a|)$ and this obviously will make $|f(x)-f(a)|<\varepsilon$. However this was deduced under the hypothesis that $|x-a|<1$, so what if it were not true that $|x-a|<1$? Also the end of the proof is normally saying that we must take

$$\delta = \min\{1, \varepsilon/(1+2|a|)\}$$

However it happens that if the minimum is $1$, it seems to not work, because when we use this $\delta$ the $\varepsilon$ doesn't even appear. I think my problem is that I didn't really get the trick of making $|x-a|<1$.

Thanks very much in advance!

答:
The thing is that we really care about $|x-a|$ being very small, even close zero, so we may as well assume that it is smaller than $1$. Because given an $\varepsilon$ we need to tell what sort of $\delta$ suits it, we can choose it to our liking.

And since we are free to choose our $\delta$, we can always choose $\delta$ to be smaller than $1$, e.g. $\min\left\{\frac12,\frac\varepsilon{1+2|a|}\right\}$.


问:
Is that true that $ H \trianglelefteq G $, then $ G/H \trianglelefteq G$?
$ G/H = \{xH \mid x \in G\} $ , so if $ y \in G $, then
$$
y(G/H)y^{-1} = \{yxHy^{-1} \mid x \in G \}  = \{ yxy^{-1}H \mid x \in G \}
$$
(Because $H$ is normal, so $ y^{-1}H = H y^{-1} $)

so $ y(G/H)y^{-1} \subseteq G/H $ for all $ y \in G $

so $ G/H \trianglelefteq G $

Is there something mistake?

答: This doesn't really make sense. If $H\subseteq G$ is a subgroup, then $G/H$ is not by definition a subset of $G$. If $H$ is normal, then $G/H$ is a group, but there may not even exist a nontrivial group homomorphism $G/H\to G$. Indeed, take $G=\Bbb{Z}$ and $H=n\Bbb{Z}$. Then $\Bbb{Z}/n\Bbb{Z}$ has no nontrivial map to $\Bbb{Z}$. Indeed, if $[k]\mapsto a$, the $n\cdot a=0$, and hence $a=0$.


问:
Proving a set is open iff its complement is closed from scratch
We have that a set $F$ is closed if every limit point of $F$ is a point of $F$ and we say that $p$ is a limit point of a set $E$ is every neighborhood $N$ of $p$ contains a point $q \neq p$. In other words, if $N \cap E \neq \varnothing$.

${\bf TASK:}$ Prove that $U$ is open iff $U^c$ is closed.

TRY: Let $U$ be a open set. Let $x$ be a limit point of $U^c$. We need to show that $x \in U^c$. If $x \in U$, then there is a neighboorhood $N$ of $U$ such that $N \cap U = \varnothing$ so that $x$ is not limit point. Therefore, $x$ better be in $U^c$, as desired.

On the other hand, say $U^c$ is closed. Let $x \in U$. We must find a neighborhood of $x$ that is contained in $U$.

If we can show that $x$ is not  limit point of $U^c$, then we will be able to have a neightborhood $N$ that is completely outside $U^c$ (that is, inside of $U$). So if $x$ is a limit point of $U^c$, then $x \in U^c$ by assumption and this contradiction proves that $x$ is not a limit point of $U^c$.

Is this a correct proof?

Thanks

答:
What you want to say is that $p$ is a limit point of $E$ when for every neighborhood $N$ of $p$, we have $N\cap E\setminus\{p\}\ne\emptyset$.

Everything works out, as this is usually taken as the definition.


答:
Observe that, $$\frac {AC}{BC}=\frac {AF}{EB}=\frac {AF}{BD}=\frac {OA}{OB}$$ and thereafter $$\frac {AC}{OA}=\frac {BC}{OB}$$.

Therefore, $$\frac {OC}{OA} + \frac {OC}{OB}=\frac {OA+AC}{OA}+\frac {OB-BC}{OB}=2+\frac {AC}{OA}-\frac {BC}{OB}=\boxed {2}$$

Title: In the figure, OB is the perpendicular bisector of line segment DE

Body:
In figure, $OB$ is perpendicular bisector of line segment $DE$, $FA$ perpendicular to $OB$ and $FE$ intersects $OB$ at the point $C$, then find the sum $\displaystyle \frac{OC}{OA}+\frac{OC}{OB}$

I have proved the similarity of the triangles FAC~EBC and DBO~FAO
please help after that.


问:
$\lim_{n\to\infty} \frac{a^{2n}+1}{a^n+2}.$
I would like to ask why is the sequence convergent to $\dfrac{1}{2}$ when the parameter $|a|<1$ ?
At the same time, I would like to ask if there is a limit for $a<-1$, because the sequence would alternate with signs.

$$\lim_{n\to\infty} \frac{a^{2n}+1}{a^n+2}$$

答:
I have tried to make the answer as simple as possible, so forgive me if it sounds a bit silly to the many experts among you....  :~)

First we simplify $\frac{a^{2n}+1}{2+a^n}=\frac{a^{2n}}{2+a^n}+\frac{1}{2+a^n}$

we know that if |a|<1, then, $\lim _{x\rightarrow \infty }a^n=0$ (as when numbers smaller than one are raised to higher powers, they get smaller, eg. (0.01)^2=0.001,etc ...)

Hence,   $\lim _{n\rightarrow \infty }\ \ \frac{a^{2n}+1}{2+a^n}=\frac{a^{2n}}{2+a^n}+\frac{1}{2+a^n}=\frac{0}{2+0}+\frac{1}{2+0}=\frac{1}{2}$

1 raised to any positive power is 1, hence at a=1,  we have $\lim _{n\rightarrow \infty }\ \ \frac{a^{2n}+1}{2+a^n}=\frac{\left(1^{\infty }+1\right)}{2+1^{\infty }}=\frac{2}{3}$

But if |a|>1, then $\lim _{x\rightarrow \infty }a^n=\infty$ (as when numbers bigger than  one are raised to higher powers, they get bigger, eg. 10^2=100,etc ...)

Hence,  $\lim _{n\rightarrow \infty }\ \ \frac{a^{2n}+1}{2+a^n}=\frac{a^{2n}}{2+a^n}+\frac{1}{2+a^n}=\frac{\left(a^n\cdot a^n\right)}{2+a^n}+\frac{1}{2+a^n}=\frac{\left(a^n\right)}{\frac{2}{a^n}+1}+\frac{1}{2+a^n}=\frac{\infty }{\frac{2}{\infty }+1}+\frac{1}{2+\infty }=\infty $


问:
Fitting Data to Model Equation
I am attempting to fit an equation which models how fast a chemical reaction progresses. Given the following equation:

$$\ln(k)= \ln\biggl(\frac{d\,k_0\,M}{1+P_r}\biggl)+\ln\biggl(\frac{a\exp(-b/T)+\exp(-T/c)}{1+s\ln^2(P_r)}\biggl)+e\,\ln T$$

where
$$k_0=f\,T^g \exp\biggl(\frac{-h}{R\,T}\biggl)$$
and
$$P_r=M\,\frac{f}{i}\,T^{g-j}\exp\biggl(\frac{k-h}{R\,T}\biggl)$$

The variables I would like to fit are $a-k$. $M$ is a function determined outside of this regression; $s$ is a non-fit constant. I already have the derivatives and can perform a standard curve fit/least squares fit; however, I don't have a method of finding a good initial guess. Since this will be in an optimization scheme, the values of $\ln(k)$ will vary and the prior guess will not always be sufficient. I've found similar posts with answers by @JJacquelin, but I'm uncertain how to implement this method with my equation. An English translation to the scribd papers that JJacquelin refers to can be found here.

Sample data is given as
\begin{array}{|c|c|c|}
\hline
T& M & \ln(k) \\ \hline
1513.8 & 7.95\times10^{-9} & -1.0378 \\ \hline
1889.7 & 6.36\times10^{-9} & 5.3839 \\ \hline
2513.8 & 4.78\times10^{-9} & 9.4501 \\ \hline
1513.8 & 7.95\times10^{2} & -0.6490 \\ \hline
1889.7 & 6.36\times10^{2} & 6.7692 \\ \hline
2513.8 & 4.78\times10^{2} & 13.6235 \\ \hline
1513.8 & 5.30\times10^{-3} & -0.7416 \\ \hline
1763.8 & 4.55\times10^{-3} & 4.2598 \\ \hline
2013.8 & 3.98\times10^{-3} & 7.5729 \\ \hline
2263.8 & 3.54\times10^{-3} & 9.8066 \\ \hline
2513.8 & 3.19\times10^{-3} & 11.3176 \\ \hline
\end{array}

and $s=0.1886$

Edit: A few additional notes.

Fitting $a-k$ may have been too ambitious and unnecessary. What if instead I only fit $a-e$?

The number of data points being kept small is intentional. I use the minimum number of $\ln k$ to define the constants; however, I think I can have as many as 11 values define 5 variables if I instead only fit $a-e$.

The data that I am working with is numerical. It has machine precision and does not have uncertainty.

答:
For this sort of regression problem, one of the standard algorithms for non-linear least squares is the Levenberg-Marquardt algorithm. As far as the initial guess, you could just use the regressed parameters of a similar reaction system or the last set of parameters.

In your case, with models that are somewhat parsimonious you can add regularization to the parameters to tame some of the problems with it, I think nonlinear ridge regression would help in this case. However, with such a nonlinear model with datapoints = the number of regressed variables you will have many cases of regressed models just being nonsense.

As a side note from someone who has regressed reaction parameters from data, you can't really trust them more than $\approx \pm 10\%$. Unless you are running this as a simulation, an appropriate error bar on this data set would be in the neighborhood of $1\%$ relative error for every reading (for reasonable well-maintained gauges and sensors).

Title: Fitting Data to Model Equation


问:
Calculation of an integral based on a normal distribution CDF and PDF
Let $X$ be a normally-distributed random variable with mean $0$ and some positive variance.

Denote $f$ as its probability density function, and $F$ as its cumulative distribution function.

I am interested in calculating
$$\int_{-\infty}^{0}F(kx)f(x)\text{ d}x$$
where $k \neq 0$ is a known constant that does not depend on $x$.

How exactly would I calculate this?

When I saw this integral, I made the mistake of thinking it was $\mathbb{E}[F(kX)]$, but soon realized it wasn't, as the integral does not cover all of $\mathbb{R}$, but only $(-\infty, 0)$.

No complete solutions are necessary; hints are appreciated.

答:
Hint: Write it as
$$
\int_{-\infty}^0 F(kx)f(x)\,\mathrm{d}x
=\iint_{\mathbb{R}^2}f(x)f(y)\mathbf{1}_{x<0}\mathbf{1}_{y<kx}\,\mathrm{d}\mathcal{L}^2(x,y)
$$
and $\{x<0, y<kx\}$ can be easily described in polars.


问:
Is there a dot product with which the following linear operator becomes Hermitian
Given the linear operator

$A \in L(M_2(\mathbb{C}))$

$A \begin{bmatrix}a & b \\ c & d \end{bmatrix}=\begin{bmatrix}a-b & -a+b \\ d & -c \end{bmatrix}$

Is there a dot product where the operator becomes Hermitian? ($A^*=A$)

I don't know how to prove that there exists one, but I don't know how to construct a dot product either. Any help is appreciated.

答:
Hint: If a bounded linear operator on a Hilbert space is self-adjoint w.r.t. some inner product, its eigenvalues must be real (see the proof on ProofWiki). Now the matrix representation of the linear operator $A$ w.r.t. the standard basis of $M_2(\mathbb{C})$ is
$$
\pmatrix{1&0&-1&0\\
0&0&0&1\\
-1&0&1&0\\
0&-1&0&0}.
$$
What are the eigenvalues of $A$?


问:
Central limit theorem for dependent Bernoulli random variables on the edges of a sequence of growing hypercubes?
Imagine a growing sequence of hypercube graphs. For each integer n, you have the $n$-hypercube with $2^n$ vertices.
Now, assign $\text{Bernoulli}(1/2)$ i.i.d. random variables to all the vertices.
On each edge, you define a r.v. taking values in $\{0,1\}$ such that it is $1$ if the Bernoulli r.v.s of the two vertices it touches are equal, and it is $0$ otherwise.
So for each given n, you have Bernoulli r.v.s that are correlated on the edges and the correlation decreases with the distance (of the shortest path on the $n$-hypercube).
Note that going from one vertex to another on the hypercube requires that EXACTLY one binary component of the position changes by 1.
For example, with n=3, you can go from (1,1,0) to (1,1,1) because exactly one component (the third one) changes by 1.
This generalizes to all dimensions.
Now, the question is, if you take the sum of the (dependent) Bernoulli r.v.s on the EDGES (not vertices) and normalize it correctly (i.e. you translate by the expectation and divide by the standard deviation), does this normalized sequence converges to a $\text{Normal}(0,1)$ distribution ?

I know there are versions of the CLT for strong mixing sequences, but I didn't find a version that would suit the problem here.

答:
We will work with edge variables taking values $\pm 1$ instead of $0,1$, since applying an affine transformation $x \mapsto 2x-1$ will not affect the result. Thus if $x_u$ are i.i.d. mean zero $\pm 1$ valued variables on the nodes, $x_{uw}=x_u x_w$ are the edge variables. Denote the  sum over all hypercube edges by $Q_n=\sum_{\{uw\}} x_{uw}$. Then  $Q_n=\sum_{i=1}^n S_i(n)$ where $S_i =S_i(n)$ is the sum of the   variables $x_{uw}$ corresponding to edges $\{uw\}$ parallel to the $i$'th axis. With this notation, each $S_i(n) $ has mean $0$ and variance $2^{n-1}$;   the variables $S_i $ are uncorrelated, so $Q_n$ has variance $\sigma_n^2=n2^{n-1}$. Also, observe that
$$E[Q_n^4]=O(n^2 2^{2n}) \quad (*) $$
since there are only $2^{n-2}$ simple cycles of length $4$ in the hypercube, so the main contribution to the fourth moment comes from selecting a pair of edges and taking each of them twice.

Let $k=k(n)$ grow sublinearly e.g., $k  =\lfloor \sqrt n \rfloor$, and define
$R_n=\sum_{i=1}^{n-k} S_i(n)$.
Observe that the ratio Var$(R_n)/\sigma_n^2$ tends to $1$ as $n \to \infty$.

We can write
$$R_n=\sum_{v \in \{0,1\}^k} Q_{n-k}^v$$
where $Q_{n-k}^v$ is the sum along all edges parallel to one of the first $n-k$ directions where the last $k$ coordinates form the vector $v$.
Now by (*),
$$\sum_{v \in \{0,1\}^k} E[(Q_{n-k}^v)^4 ]=2^k O(n^2 2^{2(n-k)})$$
so
$$\sum_{v \in \{0,1\}^k} E[(Q_{n-k}^v/\sigma_n)^4] =O(2^{-k})$$
By the Lyapunov CLT [1] with $\delta=2$, the ratio
$R_n/\sigma_n$ tends in law to $N(0,1)$.

Finally, $Q_n-R_n$ has variance $k2^{n-1}=o(\sigma_n^2)$ so the CLT for $R_n$ implies the CLT  for $Q_n$ with the same normalization.

[1] https://en.wikipedia.org/wiki/Central_limit_theorem#Lyapunov_CLT


问:
Proper-$\Sigma_n$-ness of $\Sigma_n$-complete sets
This is a follow-up to this answer.

How does the fact that the arithmetic hierarchy doesn't collapse imply that if $A$ is $\Sigma_n$ complete, then $A$ is properly-$\Sigma_n$?

Some thoughts (but nothing serious). Assume that $A$ is not properly-$\Sigma_n$. Then it's either $\Sigma_i$ for $0\leq i\leq n-1$ or $\Pi_i$ for $0\leq i\leq n$. Suppose the former first. We know that any $\Sigma_n$ set is $m$-reducible to $A$. Should I consider a proper-$\Sigma_n$ set and show somehow that it's not possible to $m$-reduce it to $A$ (if this is even true)? I don't really see how the properness or inclusions in the hierarchy would be used.

Update: here are the definitions.

A set $B$ is $\Sigma_0$ ($\Pi_0$, $\Delta_0$) if $B$ is computable.

For $n\ge 1$, a set $B$ is  $\Sigma_n$ if there is a computable relation  $R(x,y_1,\dots,y_n)$ such that $$x\in B\iff (\exists y_1)(\forall y_2)\dots (Q y_n) R(x,y_1,\dots, y_n)$$ where $Q$ is $\exists$ for $n$ odd and $\forall$ for $n$ even.

The definition of $\Pi_n$ sets for $n\ge 1$ is similar (just switch the quantifiers).

A set $B$ is $\Delta_n$ if it's both $\Sigma_n$ and $\Pi_n$

A set $B$ is $\Sigma_n$-complete if $B$ is $\Sigma_n$ and for any $\Sigma_n$ set $A$, one has $A\leq_m B$.

答:
The key fact here is that if a set $A$ qualifies for some level of the hierarchy, then so does any set m-reducible to $A.$ Thus if $A$ is $\Sigma_n$ complete, and also qualifies for some lower level, then any $\Sigma_n$ set also qualifies for that lower level and the hierarchy collapses.

To prove the key fact based on your definition for the levels of the hierarchy, just observe that if $f$ is a total computable function and $R(n,y_1,\ldots, y_n)$ is a computable relation, then the relation $R'$ defined  by $$R'(n,y_1,\ldots,y_n)\iff R(f(n),y_1,\ldots,y_n) $$ is computable. Thus if $B$ is m-reducible to $A,$ then there is a total computable $f$ such that $n\in B$ iff $f(n)\in A,$ and we can see from the definition this means that $B$ qualifies for any level that $A$ qualifies for.


问:
finding a unit vector of maximum distance from a subspace in a banach space
Let $W$ be a strict subspace of a Banach space $X$ and let the distance between a vector $v$ and the subspace $W$ be defined as $d(v,W)=\inf_{w\in W}|w-v|$.

If $X$ is a Hilbert space, then we can always find a unit vector $v$ st. $d(W,v)=1$. Does this also hold for Banach spaces? If not, what is a counter example?

答:
The replacement for the Hilbert space result is given by Riesz Lemma:
https://en.wikipedia.org/wiki/Riesz%27s_lemma</p>


问:
Bogus prove of the irrationality of $\sqrt{\frac{1}{2}}$.
I need help figuring out my mistake.
Proof. Proving by contradiction that $\sqrt{\frac{1}{2}}$ is irrational.
Suppose $\sqrt{\frac{1}{2}}$ is rational so:
$\sqrt{\frac{1}{2}}=\frac{m}{n}$. Where $m/n$ are in lowest terms.

Squaring both sides and solving for $n$ we have  $n^{2}=2m^{2}$.

So $n^2$ is even therefore $n$ is also even therefore $n=2k$ and $n^{2}=4k^{2}$.

Now, replacing $n^2$ in $n^{2}=2m^{2}$, we have  $4k^{2}=2m^{2}$. Which means $m$ is also even.

So we are left with an even numerator and an even denominator which contradicts the initial assumption that m/n are in lowest terms. Therefore $\sqrt{\frac{1}{2}}$ is irrational. (which we know is wrong)

答: Your proof is actually correct. We know$\sqrt{\frac12} = \frac{1}{\sqrt{2}}$. So, if we prove $\frac{1}{\sqrt{2}}$ is irrational, then so is $\sqrt{\frac12}$ since they are equal. Let $\sqrt{2} = \frac{m}{n}$. So that means $\frac{1}{\sqrt{2}} = \frac{n}{m}$. However, we know that $\sqrt{2}$ is irrational thus there is no $m,n$ such that $\sqrt{2} = \frac{m}{n}$. Since there is no such $m,n$, that means there are no solutions to $\frac{1}{\sqrt{2}} = \frac{n}{m}$, either. Thus, $\frac{1}{\sqrt{2}}$ is irrational, so your proof is actually fine, since there was no error in your logic and conclusion was correct.


答: The number $1$ is arbitrary; it was chosen for its simplicity. You are right that $|x-a| < 1$ is not satisfied for every $x$, but it does not matter.  We are only interested in what happens when $x$ is very close to $a$; more precisely, when $x$ satisfies $|x-a| < \delta$. But by our choice of $\delta$, $|x-a| < 1$ is always satisfied whenever $x$ is $\delta$-close to $a$.</p>

Title: Doubt in $\varepsilon$-$\delta$ proof of continuity of $x^2$

Body:
I have one elementary doubt on the proof that $f(x)=x^2$ is continuous for every $a \in \Bbb R$. The initial steps usually presented are: to deduce which $\delta$ will work we write:

$$|x^2-a^2|=|x-a||x+a|$$

Now, we must find some bound for $|x+a|$, so we require that $|x-a|<1$ or some other positive real number. Here comes my first doubt, this trick appears very often, what's the intuition on making $|x-a|<1$?

After that we have that this implies $x < 1 + a$ and this implies that $|x+a| < 1 + 2|a|$. Now it's obvious that if we set $|x-a|< \varepsilon/(1+2|a|)$ and this obviously will make $|f(x)-f(a)|<\varepsilon$. However this was deduced under the hypothesis that $|x-a|<1$, so what if it were not true that $|x-a|<1$? Also the end of the proof is normally saying that we must take

$$\delta = \min\{1, \varepsilon/(1+2|a|)\}$$

However it happens that if the minimum is $1$, it seems to not work, because when we use this $\delta$ the $\varepsilon$ doesn't even appear. I think my problem is that I didn't really get the trick of making $|x-a|<1$.

Thanks very much in advance!


问:
Continuity of a function over a closed interval
The definition I have of continuity of a function $f:D \rightarrow \mathbb{R}$ at a point $c\in D$ is that $f$ is continuous at $c$ if for all sequeunces $(x_n)$ in $D$ s.t. $x_n \rightarrow c$, we have $f(x_n) \rightarrow f(c)$.

So my question is, if we say $f:D \rightarrow \mathbb{R}$ is continuous on an interval $[a,b]$, are we saying that:

for any $c \in [a,b]$, we have that for all sequeunces $(x_n)$ in $D$ s.t. $x_n \rightarrow c$, we have $f(x_n) \rightarrow f(c)$

or are we saying that:

for any $c \in [a,b]$, we have that for all sequeunces $(x_n)$ in $[a,b]$ s.t. $x_n \rightarrow c$, we have $f(x_n) \rightarrow f(c)$?

答: It means the former. To say a function is continuous on a subset $C$ of domain $D$, it means to be continuous at every point $c \in C$. To be (sequentially) continuous at a point $c \in C$ means that, for all sequences $(x_n)$ in $D$ such that $x_n \to c$, we have $f(x_n) \to f(c)$.


问:
Solving a Recurrence with a Summation of Exponents as a Term
This is totally a homework problem, but it's due in 27 minutes so I know I won't get anything in time for that. I don't want the answer, I just want to learn the technique. I've started a MS program but it's been over 30 years since my calculus classes.

I'm trying to solve the following recurrence:

$$
T(n) = 3T({n \over 2}) + 8n, \ T(1) = 1\ and \ n=2^k
$$

I have gotten to this point, and cannot get any further despite my most frenetic Googling:

$$
T(n) = 3^k + 8 \sum_{j=0}^{k-1} 3^j {n \over 2^j}
$$

The lectures for the class and all the other videos or pages I've found have either eliminated the initial exponential term completely and/or only have a simple exponential in the summation term (which is then solvable as a geometric summation).

It's now 16 minutes until deadline, but I still want to understand this so any pointers appreciated.

Randy

Body:
$$T(2^k) = 3T(2^{k-1}) + 8 \cdot2^k \tag{1}$$
$$T(2^{k-1}) = 3T(2^{k-2}) + 8 \cdot2^{k-1}\tag{2}$$
$$T(2^{k-2}) = 3T(2^{k-3}) + 8 \cdot2^{k-2}\tag{3}$$

$(3)$ in $(2) \implies$
$$T(2^{k-1}) = 3^2T(2^{k-3}) + 3 \cdot8 \cdot2^{k-2} + 8 \cdot2^{k-1} \tag{4}$$

$(4)$ in $(1) \implies$
$$T(2^k) = 3(3^2T(2^{k-3}) + 3 \cdot8 \cdot2^{k-2} + 8 \cdot2^{k-1}) + 8 \cdot2^k$$

Or, $$T(2^k) = 3^3T(2^{k-3}) + 3^2 \cdot8 \cdot2^{k-2} + 3 \cdot 8 \cdot2^{k-1} + 8 \cdot2^k$$

If you repeatedly substitute, ultimately you'll have

$$T(2^k) = 3^kT(2^{k-k}) + 8(3^{k-1}\cdot2^1 + 3^{k-2} \cdot 2^2 + \ldots + 3^{k-k} \cdot2^k) = 3^k + 8 \sum_{j=0}^{k-1}3^j 2^{k-j}$$

Or, $$T(2^k) = 3^k +  8 \sum_{j=0}^{k-1} 3^j \frac{n}{2^j}$$


问:
convert a matrix to change to system of linear equations and show non-trivial solution
To show $$\begin{pmatrix}
2 & 2 & 3 \\
2 & 3 & 2 \\
3 & 2 & 2 \\
\end{pmatrix}$$, a matrix named G. Then I have a vector $x$, which is unknown, how do I write $Gx=mx$, $m \in \mathbb{R}$ as a system of linear equations? I wish to convert to to linear, and not matrix. I only know there's 3 linear equations to finish it. I also can have to show if $m=7$, then there is a non-trivial solution to the system.

答:
Since that you have $$G=\begin{pmatrix} 2 & 2 & 3 \\ 2 & 3  & 2 \\ 3 & 2 & 2 \end{pmatrix}$$
so you can find the eigenvalues of $G$. It's easy using the equation $$\det(G-\lambda I)=0$$
where the $\lambda$'s be eigenvalues of the matrix $G$.

Note that, $$\det(G-\lambda I )=\left| \begin{pmatrix} 2 & 2 & 3 \\ 2 & 3  & 2 \\ 3 & 2 & 2 \end{pmatrix}-\lambda \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}  \right|=(\lambda+1)(\lambda-1)(\lambda-7)=0.$$
So, we have that $$\lambda_{1}=-1, \quad \lambda_{2}=1, \quad \text{and} \quad \lambda_{3}=7$$

So, you can write $$[1] \quad \begin{pmatrix} 2 & 2 & 3 \\ 2 & 3  & 2 \\ 3 & 2 & 2 \end{pmatrix} \begin{pmatrix} x\\ y \\ z \end{pmatrix}=-1 \begin{pmatrix} x \\ y \\ z\end{pmatrix}$$

$$[2] \quad \begin{pmatrix} 2 & 2 & 3 \\ 2 & 3  & 2 \\ 3 & 2 & 2 \end{pmatrix} \begin{pmatrix} x\\ y \\ z \end{pmatrix}=1 \begin{pmatrix} x \\ y \\ z\end{pmatrix}$$

$$[3] \quad \begin{pmatrix} 2 & 2 & 3 \\ 2 & 3  & 2 \\ 3 & 2 & 2 \end{pmatrix} \begin{pmatrix} x\\ y \\ z \end{pmatrix}=7 \begin{pmatrix} x \\ y \\ z\end{pmatrix}$$
where $(x,y,z)\not=\vec{0}_{3\times 1}$ and $(x,y,z) \in \mathbb{R}^{3}$.

This is part of the diagonalization theory, you can read about it here: https://en.wikipedia.org/wiki/Diagonalizable_matrix.


问:
Proof that a certain fraction is always an integer
Prove that $$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}$$ is or is not an integer for $0\leq k \leq n$, where $k$ and $n$ are integer values.

This looks like $\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$. The above statement is true for k=1 and k=2 as seen by observing modular residues. Not sure how to proceed.

答:
I’m going to give the answer more or less as I worked through the problem, since these numbers turn out to be rather interesting; if you just want a quick and easy computational proof, skip to the end.

I rewrote it as

$$\frac{n!}{k!(n-k)!}\cdot\frac{(n+1)!}{(k+1)!(n-k+1)!}=\frac1{k+1}\binom{n}k\binom{n+1}k\,,\tag{1}$$

and calculated some values:

$$\begin{array}{c|cc}
n\backslash k&0&1&2&3&4&5\\\hline
0&1\\
1&1&1\\
2&1&3&1\\
3&1&6&6&1\\
4&1&10&20&10&1\\
5&1&15&50&50&15&1
\end{array}$$

The row sums are familiar: $1,2,5,14,42,132$ are the Catalan numbers $C_{n+1}$. This does suggest that these numbers may be counting something. And if we look up the triangle in OEIS by searching on the sequence

$$1,1,1,1,3,1,1,6,6,1,1,10,20,10,1\,,$$

the very first return is A001263, the sequence of Narayana numbers, whose first FORMULA entry is an offset version of the righthand side of $(1)$. If the entry in row $n$, column $k$ of my table is $t(n,k)$, then $t(n,k)$ is the Narayana number $N(n+1,k+1)$ and is the number of Dyck paths of length $2(n+1)$ having exactly $k+1$ peaks. Thus, it must be an integer.

That $N(n,k)$ is the number of Dyck paths having exactly $k$ humps is not obvious; one proof can be found in this PDF. However, the FORMULA section of the OEIS entry also notes that

$$N(n,k)=\binom{n-1}{k-1}\binom{n+1}k-\binom{n}{k-1}\binom{n}k\,,$$

which suggests the following purely computational proof that the original expression is an integer:

$$\begin{align*}
&\binom{n}k\binom{n+2}{k+1}-\binom{n+1}k\binom{n+1}{k+1}\\\\
&\qquad=\frac{n!(n+2)!}{k!(k+1)!(n-k)!(n-k+1)!}-\frac{(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\
&\qquad=\frac{n!(n+2)!-(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\
&\qquad=\frac{(n+1)!^2\left(\frac{n+2}{n+1}-1\right)}{{k!(k+1)!(n-k+1)!(n-k)!}}\\\\
&\qquad=\frac{n!(n+1)!}{{k!(k+1)!(n-k+1)!(n-k)!}}\,.
\end{align*}$$

Here the first expression is clearly an integer, and the last is easily seen to be equivalent to the original fraction.


问:
Solving summation $2n+2^2(n-1)+2^3(n-2)+....+2^n$
Can anyone help me with this summation? I tried to use the geometric series on this, but I can't use that.
$$2n+2^2(n-1)+2^3(n-2)+....+2^n$$
I am trying to do this for studying algorithms. Can we get a closed form for this ?</p>

答:
It actually is possible to use the formula for the sum of a geometric series, though it’s certainly not the quickest approach. Expand the series into a triangular array like this:

$$\begin{array}{cc}
2&+&2&+&2&+&\ldots&+&2&+&2&=&2n\\
&&2^2&+&2^2&+&\ldots&+&2^2&+&2^2&=&2^2(n-1)\\
&&&&2^3&+&\ldots&+&2^3&+&2^3&=&2^3(n-2)\\
&&&&&&\ddots&&\vdots&\vdots&\vdots\\
&&&&&&&&2^{n-1}&+&2^{n-1}&=&2^{n-1}\big(n-(n-2)\big)\\
&&&&&&&&&&2^n&=&2^n\big(n-(n-1)\big)
\end{array}$$

Now sum the columns to the left of the equals sign; each is a geometric series, so this isn’t hard. For $k=1,\dots,n$ the $k$-th column sum is

$$\sum_{i=1}^k2^i=2\sum_{i=0}^{k-1}2^i=2(2^k-1)=2^{k+1}-2\;,$$

so the original series is

$$\begin{align*}
\sum_{k=1}^n\left(2^{k+1}-2\right)&=2^2\sum_{k=0}^{n-1}2^k-2n\\\\
&=2^2(2^n-1)-2n\\\\
&=2^{n+2}-2(n+2)\;.
\end{align*}$$

You can also use a little calculus. Consider the function

$$f(x)=\sum_{k=1}^nx^k(n-k)\;;$$

you’re looking for $f(2)$. Now

$$\begin{align*}
f(x)&=n\sum_{k=1}^nx^k-\sum_{k=1}^nkx^k\\\\
&=nx\sum_{k=0}^{n-1}x^k-x\sum_{k=0}^{n-1}(k+1)x^k\\\\
&=\frac{n(x^n-1)}{x-1}-x\frac{d}{dx}\sum_{k=0}^nx^k\\\\
&=\frac{n(x^n-1)}{x-1}-x\frac{d}{dx}\left(\frac{x^{n+1}-1}{x-1}\right)\;,
\end{align*}$$

and a little straightforward calculus and algebra will finish off the general calculation.


问:
$1+i$ is a prime element of ring of Gaussian integers.
I want to prove that $1+i$ is a prime element of ring of Gaussian integers $Z[i]$. I started off with saying that if $1+i$ is prime then $1+i|(a+bi)(c+di)$ implies $1+i|a+bi$ or $1+i|c+di$ for $a+bi,c+di$ in $Z[i]$.
Taking conjugate, we get

$1-i|(a-bi)(c-di)$

Next we get,

$2|(a^2+b^2)(c^2+d^2)$

Since $2$ is a prime in $Z$ hence $2|(a^2+b^2)$ or $2|(c^2+d^2)$. After this I am stuck. I do not know how to get $1+i|a+bi$ or $1+i|c+di$ from here. Please suggest.

答:
Firstly, your way of phrasing your solution is not entirely correct. If you are trying to show that $z$ is prime, you should not start with "If $z$ is prime". However, your working is actually salvageable.

You showed that if $(1 + i) \mid (a + bi)(c + di)$, then that alone implies $2 \mid (a^2 + b^2)(c^2 + d^2)$.

(Without any assumption of $1 + i$ being prime. This is what I meant with "salvageable".)

WLOG, we have $2 \mid (a^2 + b^2)$. (We wish to show that $(1 + i) \mid (a + bi)$.)

Thus, either $a$ and $b$ are both even or both odd.

Case 1. $a$ and $b$ are even.

In this case, $2 \mid a$ and $2 \mid b$ and hence, $2 \mid (a + bi)$. Since $1 + i \mid 2$, you are done.

Case 2. $a$ and $b$ are odd.

Write $a = 2a' + 1$ and $b = 2b' + 1$ for integers $a', b'$.

Then, $$a + bi = 2(a' + b'i) + (1 + i).$$
Again, since $(1 + i) \mid 2$, it follows that $(1 + i) \mid a + bi$.


问:
Player input prediction pseudoCode

I am making a simple game where a player has to select either heads or tails.

So let heads be 0 and tails be 1. now suppose they choose a sequence like this:

0,1,0,1,0,1...   or

0,0,1,0,0,1...

So is there any way i can find the pattern mathematically and guess the next prediction.

Eventhough i am coding in python, a pseudocode will be more than enough

If computer guesses right,it will get a point and the other way around

答:
Try to use the longest previous match(es) as predictors:

Given previous inputs $x_1,\ldots, x_n$.

If $n=0$, output a random guess; perhaps you also prefer to output a random guess if $n=1$; otherwise continue

Build a list $L\leftarrow\{1,2,\ldots,n\}$

Let $d\leftarrow 1$

Let $L'\leftarrow\{\,i\in L\mid i>d\land x_{i-d}=x_{n+1-d}\,\}$

If $L'$ is non-empty, set $L\leftarrow L'$, $d\leftarrow d+1$, and go back to step 4.

Pick a unformly random element $r\in L$ and output $x_r$

Title: Player input prediction pseudoCode


问:
Riemann stieltjes integral concern
Suppose $f(x)=x^2=z$ and $g(x)=x^6$.Now $\int g(x) df(x)$ is an stieltjes integral which is evaluated as $\int z^3 dz$,then we apply the antiderivative concept like we did with an independent variable $x$.But the concept that differentiation is the reverse process of integration is only proved considering $x$ as an independent variable while here $z$ is not,why can then we treat $z$ in the same way as $x$?

答:
I don't understand what does "...which is evaluated as..." mean. By the basic properties of the RS integral, and since $\;f\;$ is continuosuly idfferentiable everywhere, we get that

$$\int g(x)\,d(f(x)) =\int\,g(x)\,f'(x)\,dx=2\int x^7\,dx=\frac14x^8+C$$

...though the RS integral is usually used with limits in the integral. In fact, I've never used RS integral without limits, so the above must be understood as integral $\;\int\limits_a^b g\,d(f)\;$ , with $\;a,b\in\Bbb R\;$ .

Title: Riemann stieltjes integral concern


问:
Entrance exam probability problem
Suppose that a fair coin is tossed until a head appears. Given that the coin is tossed four times and no head is obtained in these four tosses, what is the probability that the coin must be tossed at least two more times to obtain the first head?

I am getting 1/2 as my answer and I want to cross check my answer. Thank you in advance for helping me.

答:
Yes, correct.

The possible results in the next 2 tosses are

TT

TH

HT

HH

Thus the only 2 favourable events are the first two, with a total probability 0.5

Title: Entrance exam probability problem


问:
Real numbers satisfing a trigonometric property
One of my students sent me the problem below and I am looking for solution. I tried simply to expand using complex numbers ($Re(\sum e^{i(A-B)}$) but to no avail. Does any body have idea how to proceeed?

If $$\cos (A-B)+\cos (B-C)+\cos (C-A)=-\frac32$$ find the value of $$\cos A+\cos B+\cos C$$

答:
Consider the expression
$$
(\cos A + \cos B + \cos C)^2+(\sin A + \sin B + \sin C)^2\ .
$$
Using the relations $\sin^2 x + \cos^2 y=1$ and $\cos(x-y) = \cos x \cos y + \sin x \sin y$, this expression simplifies to
$$
3 + 2 (\cos(A-B) + \cos(B-C)+\cos(C-A))\ .
$$
Plugging in the provided value $-\frac{3}{2}$ for the part in parentheses, we find that the initial sum of squares is equal to zero. This means that $\cos A + \cos B + \cos C = \sin A + \sin B + \sin C = 0$.

Alternatively, using the language of complex numbers, we can consider $e^{i A} + e^{i B} + e^{i C}$. The norm is
$$
\begin{align}
& \quad (e^{i A} + e^{i B} + e^{i C})(e^{-i A} + e^{-i B} + e^{-i C})\\
& = 3 + e^{i(A-B)} + e^{i(B-A)} + e^{i(B-C)} + e^{i(C-B)} + e^{i(C-A)} + e^{i(A-C)} \\
& = 3 + 2 (\cos(A-B) + \cos(B-C)+\cos(C-A))\ .
\end{align}
$$
As before this is zero, so $e^{i A} + e^{i B} + e^{i C}$ must be zero. This means that its real part is also zero.


答:
This does have a nice closed form.

We can write your original sum, $2n+2^2(n-1)+2^3(n-2)+....+2^n$, as
$(2+2^2+2^3+...2^n)+(2+2^2+2^3+...2^{n-1})+2+2^2+2^3+...2^{n-2})+...+2$, because this sum will have $n$ $2$'s, $n-1$ $2^2$'s, and so on. By the geometric series formula, this sum simplifies to $(2^{n+1}-2) + (2^n-2) + (2^{n-1}-2)+...+(2^2-2)$, which itself simplifies (again by the geometric series formula) to $2^{n+2}-4-2n$.


问:
A problem about ring isomorphism?

problem:let $R$ and $R'$ be commutative rings,and let $I⊆R$ and $I'⊆R'$ be ideals.
if $f:R→R'$ is homomorphism with $f(I)⊆I'$,prove that :
(i)$f_*:r+I→f(r)+I'$ is well-defined  homomorphism $f_*:R/I→R'/I'$
(ii)If $f$ is isomorphism,then $f_*$ is also.

My attempt:
For(i) I use condition $f(I)⊆I'$ to prove $f*$ is well-defined, and the homomorphism of $f_*$can derived by homomorphism $f$.
For(ii) i don't know how to do it.Because i think (ii)  is wrong. We know $ker f_*=\{r:f_*(r)=0 \}=\{r:f(r)+I'=I' \}=\{r:f(r)∈I' \}=f^{-1}(I')$.

If $ f_*$ is isomorphism,then $ker f_*=f^{-1}(I')=\{0\}$,but $f$ is also isomorphism,then $I'=0$.

答:
Indeed, $$\ker f_* = \{r+I : r \in R,\, f(r)+I' = I'\} = \{r+I : r \in f^{-1}(I')\} = f^{-1}(I')/I$$ and note that $f_*$ is surjective if and only if for each $r' \in R'$ there exists $r \in R$ such that $r'+I' = f(r)+I'$, that is, if for each $r' \in R'$ there exists $r \in R$ such that $r'-f(r) \in I'$.

Thus, we see that

$f_*$ is injective iff $I = f^{-1}(I')$; and

$f_*$ is surjective iff $R' = \operatorname{im} f + I'$.

Title: A problem about ring isomorphism?


答:
Yes. You need at least two more tosses to get a head means that the fifth toss is again a tail, so
$$P(\text{at least two tosses for a head}\mid \text{four tails})=P(\text{the fifth is tail}\mid \text{four tails})=P(\text{the fifth is tail})=0.5,$$

since the fifth toss is independent of the first four.

Title: Entrance exam probability problem

Body:
Suppose that a fair coin is tossed until a head appears. Given that the coin is tossed four times and no head is obtained in these four tosses, what is the probability that the coin must be tossed at least two more times to obtain the first head?

I am getting 1/2 as my answer and I want to cross check my answer. Thank you in advance for helping me.