问:
$\langle A,B \rangle$ is the unique Sylow $2$-subgoup of $SL_2(F_3)$
Prove that the subgroup of $SL_2(F_3)$ generated by $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ and $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ is the unique Sylow $2$-subgoup of $SL_2(F_3)$.

Proof: Let $G=SL_2(F_3)$. $|G|=24=2^3\cdot 3$. Let

$A =\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$
and
$B =\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

By the Sylow Theorems, let $n_2$ be the number of Sylow $2$-subgroup. $n_2\equiv 1 \mod 2$ and $n_2 | 3 \Rightarrow n_2=1,3$, and Sylow $2$-subgroup(s) have order $8$. We need to check $|\langle A,B \rangle | = 8$. Note $A^4=B^4=I$. We find
$$
\langle A,B \rangle
= \left\{ \pm I, \pm A, \pm B, \pm \begin{pmatrix} -1 & 1 \\ 1 & 1 \end{pmatrix}\right\}
$$
What is left to show is $\langle A,B\rangle$ is the only one. We can do that by show $\langle A,B \rangle$ is normal.
i.e. $gng^{-1} \in \langle A,B \rangle$ $\forall g=\begin{pmatrix}
a & b \\ c & d \end{pmatrix}$ and $n\in N$.

So this is where I am stuck. I know I can do the computation for each element of $\langle A,B \rangle$ but that would suck. Is there a way to avoid that or not?

答:
Here is another way to see that the $2$-Sylow subgroup of $SL_2({\bf F}_3)$ is normal.

The group $GL_2({\bf F}_3)$ acts on the points of the projective line  via fractional linear transformations. Up to conjugacy there are three points with field of definition equal to ${\bf F}_9$. They are $\pm i$, $1\pm i$ and $-1\pm i$. Since $GL_2({\bf F}_3)$ preserves them, we get a  homomorphism $f:GL_2({\bf F}_3)\rightarrow S_3$.

It is easy to see that the matrix $\pmatrix{1&1\cr0&1\cr}$ is mapped to a $3$-cycle, while  $\pmatrix{0&1\cr1&0\cr}$ is mapped to a $2$-cycle.  Therefore $f$ is surjective.  It also shows that $f$ induces an isomorphism $GL_2({\bf F}_3)/SL_2({\bf F}_3)\rightarrow S_3/A_3$. Therefore  the subgroup $SL_2({\bf F}_3)$ is mapped onto the alternating group $A_3$. So the kernel of $f$ is a $2$-Sylow subgroup of $SL_2({\bf F}_3)$.


问:
Equivalent graph related terminologies
In my book, it's written that the following are equivalent. I don't understand why it is so.

G is bipartite;

G is 2-colourable;

G does not contain any odd length cycles.

答:
If $G$ is bipartite with parts $V$ and $W$, color the vertices in $V$ red and the vertices in $W$ blue. Conversely, if $G$ is $2$-colorable, splitting the vertices by color gives a bipartition. This shows that the first two are equivalent.

If $G$ is bipartite with parts $V$ and $W$, any path must alternate between vertices in $V$ and vertices in $W$. Suppose that you start at a vertex in $V$; then after an odd number of steps you must be in $W$, and after an even number of steps you must be back in $V$. In particular, to return to your starting point requires an even number of steps, and therefore $G$ has no odd cycles. For the converse see this question and its answer, or this answer.

ContentLicense: CC BY-SA 3.0

Title: Equivalent graph related terminologies


问:
Prove that $\angle AEF =90^\circ$ given a square $ABCD$
Let $ABCD$ be a square and $E\in CD$ such that $DE=EC$. Let $F\in BC$ such that $BC=4FC$. Prove that $\angle AEF =90^\circ$.

My attempt:

Proving that $\angle AEF =90^\circ$ is the same as proving that $\triangle AEF$ is a right triangle. In other words, we wish to prove that $AE^2 +EF^2 = AF^2$. I’ve tried a lot of methods to reach this point but none of them worked.

答:
The idea in your attempt definitely works here (although it is not the shortest proof, see the answer by Narasimham): Let $a$ be the sidelength of the square. Then we have \begin{align*}
AE^2&=AD^2+DE^2=a^2+\left(\frac{1}{2}a\right)^2\\
EF^2&=EC^2+CF^2=\left(\frac{1}{2}a\right)^2+\left(\frac{1}{4}a\right)^2\\
AF^2&=AB^2+BF^2=a^2+\left(\frac{3}{4}a\right)^2
\end{align*}
And thus: $$AE^2+EF^2=\frac{25}{16}a^2=AF^2$$

ContentLicense: CC BY-SA 4.0


问:
How to solve this $3\times3$ system of inequalities
Suppose that $x$, $y$, $z$, $\nu$, $N$, $g$ are some postitive parameters and $A$, $B$ and $C$ are variables that belong to $(0,+\infty)$. I want to identify one or all of the feasible points taht solve the following system of inequalities with respect to $A$, $B$ and $C$

\begin{equation}xA-\nu gB-Ng C>0 \\
-\nu gA+yB-Ng C>0\\
-\nu gA-\nu gB +zC>0\end{equation}

答:
Too long for a comment.

Solving the system for $A,B,C$

$$
\left\{
\begin{array}{l}
 A x-B g \nu -C g N=e_1^2 \\
 -A g \nu +B y-C g N=e_2^2 \\
 -A g \nu -B g \nu +C z=e_3^2 \\
\end{array}
\right.
$$

we get

$$
\left\{
\begin{array}{c}
A = \frac{e_1^2 \left(g^2 N \nu -y z\right)-g \left(e_3^2 N (g \nu +y)+e_2^2 \nu  (g N+z)\right)}{g^2 N \nu  (2 g \nu +x+y)+z \left(g^2 \nu ^2-x y\right)} \\
B = \frac{e_2^2 \left(g^2 N \nu -x z\right)-e_3^2 g N (g \nu +x)-e_1^2 g \nu  (g N+z)}{g^2 N \nu  (2 g \nu +x+y)+z \left(g^2 \nu ^2-x y\right)} \\
C= \frac{e_3^2 \left(g^2 \nu ^2-x y\right)-e_2^2 g \nu  (g \nu +x)-e_1^2 g \nu  (g \nu +y)}{g^2 N \nu  (2 g \nu +x+y)+z \left(g^2 \nu ^2-x y\right)} \\
\end{array}
\right.
$$

or assuming $g^2 N \nu  (2 g \nu +x+y)+z \left(g^2 \nu ^2-x y\right)>0$

$$
\left\{
\begin{array}{c}
A' = e_1^2 \left(g^2 N \nu -y z\right)-g \left(e_3^2 N (g \nu +y)+e_2^2 \nu  (g N+z)\right) \\
B' = e_2^2 \left(g^2 N \nu -x z\right)-e_3^2 g N (g \nu +x)-e_1^2 g \nu  (g N+z) \\
C'= e_3^2 \left(g^2 \nu ^2-x y\right)-e_2^2 g \nu  (g \nu +x)-e_1^2 g \nu  (g \nu +y) \\
\end{array}
\right.
$$

NOTE

The matrix associated to the linear system is

$$
M = \left(
\begin{array}{ccc}
 x & -g \nu  & -g N \\
 -g \nu  & y & -g N \\
 -g \nu  & -g \nu  & z \\
\end{array}
\right)
$$

and as long as $\det\left(M\right)=x y z-2 g^3 N \nu ^2-g^2 \nu  (N (x+y)+\nu  z)\ne 0$ we have $e_1, e_2, e_3$ as independent variations.


答:
Ignoring the similar triangles for variety...

Let the side length of the square be $s$. We have $|AF|^2 = |AB|^2 +|BF|^2 = s^2 + \left(\frac 34 s\right)^2 = \frac{25}{16}s^2$

Then $|AE|^2 = |AD|^2 +|DE|^2 = s^2 + \left(\frac 12 s\right)^2  =  \frac{5}{4}s^2 =  \frac{20}{16}s^2$

and  $|EF|^2 = |EB|^2 +|BF|^2 = \left(\frac 12 s\right)^2 + \left(\frac 14 s\right)^2  =  \frac{5}{16}s^2$

giving $|AF|^2 = |AE|^2 +|EF|^2$ as required

Title: Prove that $\angle AEF =90^\circ$ given a square $ABCD$

Body:
Let $ABCD$ be a square and $E\in CD$ such that $DE=EC$. Let $F\in BC$ such that $BC=4FC$. Prove that $\angle AEF =90^\circ$.

My attempt:

Proving that $\angle AEF =90^\circ$ is the same as proving that $\triangle AEF$ is a right triangle. In other words, we wish to prove that $AE^2 +EF^2 = AF^2$. I’ve tried a lot of methods to reach this point but none of them worked.


问:
Intuition behind why continuous random variables cannot take a particular value?
It was iterated over and over again in our probability class that continuous random variables CANNOT have a probability mass function, instead they NEED TO have a density function. I am trying to find some intuition behind this. Any help would be greatly appreciated.

Additionally the following facts were mentioned:

The probability distribution function of some continuous random variable may take a value larger than 1. Why/How?

In the case of a continuous random variable, $P(X=x) \ne p_{x}(x)$. Why?

答: I'll elaborate on the idea of "almost never" in probability - this refers to an event that occurs with probability 0, but is not impossible. Suppose we want to pick a random number from the uniform distribution on [0, 1]. There are an infinite number of choices, so the odds that we will pick exactly 0.5 (or any other numer) is zero. The fact remains, however, that 0.5 is in the range we're selecting from, so it is actually possible to pick it. A continuous random value does take on a particular value, despite the fact that the likelihood of picking any particular value is actually zero. If you throw a dart at the number line in the [0, 1] range, you have zero likelihood of hitting any particular value with infinite precision, but the dart still must land somewhere.


问:
every integers from 1 to 121 can be written as 5 powers of 3
We have a two-pan balance and have 5 integer weights with which it is possible to weight
exactly all the weights integers from 1 to 121 Kg.The weights can be placed all on a plate but you can also put some in a dish and others with the goods to be weighted.

It's asked to find the 5 weights that give us this possibility. It also asks you to prove that the group of five weights is the only one that solves the problem.

Easily i found the 5 weights: 1 , 3 , 9 , 27 , 81

but i can' demonstrate that this group of five weights is the only one that solves the problem.

Can you help me ?

Thanks in advance !

答:
The style of numbers, based on the balanced base 3, gives these exactly.

The proof that the powers of three are the only set, can be proven by the following.  Suppose the weights are  abcde, which can be either 1 (opposite the load), 0 off the scale, or M with the load.

The set E represents all weights reachable by the weights a-e.  This is required to be compact, but for every combination for +x, simply reversing the 1 and M gives -x.  So the compact range goes from -121 to +121, ie all posibilities.  We see that any weight by itself must be integer, ie 01000.

Swapping a weight from 1 to M, makes an even change, so an odd change requires the removal of a weight.  When 11111 represents 121, and removal of the lightest gives 120, then we see that e=1 is the only solution.

We now represent D as a combination of a,b,c,d, and note that the 81 combinations of D become 243 of the form D+e, D, D-e, D'+e, D', D'-e, where D and D' are adjacent combinations of a,b,c,d.  Because this implies that all D must be multiples of three.

Dividing D into some minimum d and a set C.  The arguement is as above: the value of d is 120 - 117 (the largest two members), and all of C is 9.  Repeat to show that c=9, b=27 and a=81.

Failing this, one can add the number 121 (11111 in base 3), that gives a different number, where the weight is left off the pan (1), in with the object to weigh (0), or on the side with the major weight (2).

Suppose the weight to weigh is a stone (14 lb), the number in base 3, is 112.  Adding 11111 to this, gives 12000.  This means we leave out the 81 weight (1), put the 27-weight opposite the stone, and put the 9, 3, and 1 weights with the stone.  The balanced form of 14 is 1MMM, where M is the digit for -1.

The same number system can be used to find a faulty coin (in excess or deficit), from 120 coins, with just 5 weighings.  Number the coins from 1 to 121, excluding 61, according to the balanced rule, or from 122 to 242, excluding 182, according to the usual base-3 style numbers.  The odd coins are then reversed (ie if there are an odd number of M,1, then the 1's and M's are swapped.

The five weighings, then proceed by the digits of the number.  For the $n$ weighing, put coins with an M in the $n$ column, in the left, and those marked $1$ in the right.  If the M pan descends, write $M$, if the $1$ pan descends, write $1$.  Otherwise write $0$.  Proceed in a similar manner through all five columns, until you have a five-place number.

If there is an odd number of $M$ and $1$ (together), one needs to reverse these (to $1$ and $M$).  The number at the end of this, will tell you if the coin is in defect (the first non-zero number is an M), or excess (1),  Swapping M with 1 in all the places will reveal the number of the defect coin, the number as stands is the excess.

So a weight giving results 0,M,1,1,1  tells us that it is an even coin, so no reversal is needed.  It tells us that the coin is in defect (ie the first weight is M), and that finally it's the coin we're calling 14 (1MMM = 14).

If 1MMM is too much, one can write it as 1-centric form (12000), and subtract 121 from that (135 - 121 = 14).


问:
PDF of a rectangle
If I want to find the $c$ of a $PDF$ when it's given:

$f_{X,Y}\left(x,y\right)=c\:\:\:\:\left(The\:area\:in\:blue\right),\:otherwise:\:0$

I try to do that:

$$\int _{\frac{1}{2}}^1\:\int _{-x+\frac{3}{2}}^1\:c\,dy\,dx+\int _0^1\:\int _{-x+\frac{1}{2}}^{-x+1}\:c\,dy\,dx=1$$
But I got $c=\frac{8}{5}$ and the result is $c=2$.

(I know we can calculate it with by calculating the area of the triangles but I am wondering to know why my way is not working)

答:
$$
\begin{aligned}
\iint\limits_{\text{square}}f(x, y)dxdy &= \iint\limits_{\text{white triangle}}0dxdy+
\iint\limits_{\text{blue trapezoid}}cdxdy+
\iint\limits_{\text{white trapezoid}}0dxdy+
\iint\limits_{\text{blue triangle}}cdxdy = \\
&= c\left(\iint\limits_{\text{blue trapezoid}}dxdy+
\iint\limits_{\text{blue triangle}}dxdy\right) = \\
&= \left|
\begin{aligned}
&\text{Integral over the blue trapezoid can be represented as a sum of two integrals:}\\
&\qquad\text{integral over a blue parallelogram (left to the }x = \frac{1}{2}\text{) and }\\
&\qquad\text{integral over a blue triangle (right to the }x = \frac{1}{2}\text{)}
\end{aligned}
\right| = \\
&= c\left(\int\limits_0^{\frac{1}{2}}dx\int\limits_{-x + \frac{1}{2}}^{-x + 1}dy +
\int\limits_{\frac{1}{2}}^1dx\int\limits_{0}^{-x + 1}dy +
\int\limits_{\frac{1}{2}}^1dx\int\limits_{-x + \frac{3}{2}}^1dy
\right) = \\
&= c\left(\int\limits_0^\frac{1}{2}\frac{1}{2}dx + \int\limits_\frac{1}{2}^1(-x+1)dx + \int_\frac{1}{2}^1\left(x-\frac{1}{2}\right)dx\right) = \\
&= c\left(\frac{1}{4} - \left.\frac{(-x+1)^2}{2}\right|_\frac{1}{2}^1+
\left.\frac{\left(x-\frac{1}{2}\right)^2}{2}\right|_\frac{1}{2}^1\right) = \\
&= c\left(\frac{1}{4} + \frac{1}{8} + \frac{1}{8}\right) = c\cdot\frac{1}{2} = 1 \Rightarrow c = 2
\end{aligned}
$$

Title: PDF of a rectangle


Body:
$$
\eqalign{
& AE^2 + EF^2 = \cr
& AD^2 +DE^2 + EC^2 + CF^2 = \cr
& a^2 + {a^2 \over 4} + {a^2 \over 4} + {a^2 \over 16} = {25a^2 \over 16} \cr
& \cr
& AF^2 = AB^2 + BF^2 = a^2 + {9a^2 \over 16} = {25a^2 \over 16} \cr
}
$$

since $AE^2 + EF^2 = AF^2 \rightarrow AE \perp EF$


问:
Count the numbers of integer solutions of the ecuation $x_1 + x_2 + x_3 + x_4 = 21$
How to count the number of nonnegative integer solutions to $x_1 + x_2 + x_3 + x_4 = 21$ such that $x_1$, $x_2$, $x_3$, $x_4 ≤ 7$

答: If you think about it you can see that you want the coefficient of $x^{21}$ in the expansion of $(1+x+x^2+\cdots + x^7)^4.$ I don't know an easy way to get that, but on a symbolic algebra calculator the coefficient is $120.$


答:
To follow the OP first intuition.

Consider $AB=4$. So you have $BF=3$ and $AF=5$.

Apply Pythagoras' theorem to the two smaller triangles and verify that $AEF$ is a right triangle because it follows Pythagoras' theorem.


问:
2-transitivity of the group of automorphism on unit complex disc
In M. Abate “Iteration theory of Holomorphic maps on Taut Manifolds”, Corollary 1.1.3 proves the 2-transitivity of $Aut(\Delta)$ over $\partial\Delta$, which means that for every choice of $\sigma_1,\sigma_2,\tau_1,\tau_2\in\partial\Delta$, there exists a unique $\gamma\in Aut(\Delta)$ such that $\gamma(\sigma_i)=\tau_i$ for $i=1,2$.

In the proof the author says that it is enough to prove that $\forall \tau\in\partial\Delta$ there exists a unique $\gamma\in Aut(\Delta)$ such that $\gamma(1)=1$ and $\gamma(-1)=\tau$.

My question is how to prove that this is sufficient. Here I show my attempt.

Let $R_{\sigma_1}$ and $R_{\tau_1}$ be the rotations of complex plane which map $\sigma_1$ and $\tau_1$ to $1$ respectively. Of course $R_{\sigma_1}, R_{\tau_1}\in Aut(\Delta)$. Define $\eta:=R_{\tau_1}^{-1}\circ\gamma\circ R_{\sigma_1}\in Aut(\Delta)$ for some $\gamma$ as above. Thus we have:
$$\eta(\sigma_1)= R_{\tau_1}^{-1}\circ\gamma(1)= R_{\tau_1}^{-1}(1)=\tau_1.$$
But how can we define $\gamma(-1)$ in order to have $\eta(\sigma_2)=\tau_2$?

答:
Let $u$ be an automorphism of the disk, $s=\sigma_2/\sigma_1, t=\tau_2/\tau_1$. Write $u=R_{\tau_1} \circ w \circ R_{\sigma_1}^{-1}$. Then $u(\sigma_i)=\tau_i$ for each $i$ iff $w(1)=1$ and $w(s)=t$.

Now, there are automorphisms $w^s,w^t$ of the disk mapping respectively $(1,-1) \longmapsto (1,s)$ and $(1,-1) \longmapsto (1,t)$, so take $w=w^t \circ (w^s)^{-1}$.


问:
$A\ne 0:V\to V$ be linear,real vec space $V$
$A\ne 0:V\to V$ be linear,real vec space $V$, $\dim V=n$,$V_0=A(V),\dim V_0=k<n$ and for some $\lambda\in\mathbb{R}, A^2=\lambda A$

Then

$\lambda=1$

$|\lambda|^n=1$

$\lambda$ is the only eigen value of $A$

There is a subspace $V_1\subseteq V$ such that $Ax=0\forall x\in V_1$

$4$ is true definitely as I can chose $V_1$ as kernel of $A$ which is non trivial subspace of $V$, well assuming $\lambda\ne 0$ we get charpoly for $A$ is $x(x-\lambda)=0$ so $0,\lambda$ are eigen value  with some multiplicity so $3$ is false, I have no idea about $1$ and $2$, could any one tell me?

答:
Both (1) and (2) are not true.
We'll choose:

$n=2 $

$ A=\left(\begin{array}{cc}
2 & 0\\
0 & 0
\end{array}\right) $

$ V = Sp\left\{(1,0),(0,1) \right\} $

then:

$ \dim(V)=2 $

$ \dim(AV)=1<2 $ (easy multiply)

and we get:
$ A^{2}=2A $. Therefor, those are falses.


答:
Let $AB = BC = CD = DA = 4x$.
Then: $DE = EC = 2x$, $CF = x$, and $FB = 3x$.

Now,

In triangle $ABF$, we have $AF^2 = AB^2 + FB^2 = (4x)^2 + (3x)^2 \Rightarrow AF = 5x$.

In triangle $ADE$, we have $AE^2 = DA^2 + ED^2 = (4x)^2 + (2x)^2 \Rightarrow AE = 2\sqrt{5}x$.

In triangle $ECF$, we have $EF^2 = EC^2 + CF^2 = (2x)^2 + x^2 \Rightarrow EF = \sqrt{5}x$.

Now, if you look at triangle $AEF$, we have $\underbrace{AE^2}_{(2\sqrt{5}x)^2} + \underbrace{EX^2}_{(\sqrt{5}x)^2} = \underbrace{AF^2}_{(5x)^2}$. Since Pythagoras identity holds here, we can deduce that angle $AEF = 90$.


答:
$\tan(\angle AED) = 2.$

$\tan(\angle FEC) = (1/2) = $cot$(\angle AED).$

Further, $\angle AED$ and $\angle FEC$ are both acute.

Therefore, $\angle AED + \angle FEC = 90^\circ.$


问:
Does exists any better way to solve "Simple hit problem" ? $y = \frac{a x + b}{c}$
I am looking for other solution of a problem, which I named:

$$\text{Simple hit problem}$$

Let:

$$y = \frac{a x + b}{c}$$
$$a, b, c, x \in \Bbb{Z}$$
For which $a, b, c$ there exists $x$ for such $y \in \Bbb{Z}$ ?

I noticed that the solution exists for $a, b, c$, if:

$$(ax) \ \text{mod} \ c = c - (b \ \text{mod} \ c),$$
but the approach relies on checking all unique values of result of modulo operator from left side of equation.

The question is, if there exists any better approach for this problem or anyway it come down to check, if some equation will be true for some $x \in A$, where A will be a set of finite ammount of values ?

答:
We can rewrite the equation as $ax+b=yc$, or by renaming $a$ with $-a$ to
the Diophantine equation $ax+cy=b$. This has been solved here and is a standard question:

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$


问:
Showing a infinite product is compact if each factor is homeomorphic to Sierpinski space
"Using (i) and Proposition 9.2.5, show that if $(X_i , T_i)$, for each $i \in N$, is homeomorphic to the Sierpinski Space, then $\prod_i(X_i , T_i)$ is compact."

i) There is a continuous image from $[0,1]$ to the Sierpinski space.
Proposition 9.2.5) If for each $i,$ $f_i$ is a continuous mapping from $X_i$ to $Y_i$, then $f$ defined by $f=(f_1,f_2,f_2...)$ is continuous.

We have not proven Tychonoff's theorem otherwise this would be trivial. We can use the fact that the Cantor space is compact and the Cantor Space is homeomorphic to infinite products of itself and $[0,1]$ is a continuous image of the Cantor space, so I just need to make sure I am connecting the dots correctly.

So if each factor $X_i$ is homeomorphic to the Sierpinski space, there is a continuous map from $[0,1]$ to each factor. Now from proposition 9.2.5, $f$ is continuous each $f_1$ is continuous and each $[0,1]$ is homeomorphic to the cantor space which so the product topology of $[0,1]$ is homeomorphic to the product topology of the cantor space $[0,1]$ and the cantor space is homeomorphic to any number of cartesian product of itself. The Cantor space is compact, and $f$ is a continuous mapping so compactness is preserved thus $\prod_i(X_i , T_i)$ is compact.

答: For the record I’ll note that this is a rather roundabout way to prove the result, since there’s a very simple direct proof. For $n\in\Bbb N$ let $p_n$ be the non-isolated point in $X_n$, let $$p=\langle p_n:n\in\Bbb N\rangle\in X=\prod_{n\in\Bbb N}X_n\,,$$ and suppose that $U$ is an open nbhd of $p$. By the definition of the product topology there is a $B=\prod_{n\in\Bbb N}V_n$ such that $V_n$ is open in $X_n$ for each $n\in\Bbb N$, and $p\in B\subseteq U$. The only open set in $X_n$ that contains $p_n$ is $X_n$ itself, so $B=\prod_{n\in\Bbb N}X_n=X$, and therefore $U=X$. Thus, $X$ is a member of every open cover of $X$, which is therefore compact. (Note that this argument works for the box topology as well as for the product topology.)


问:
Suppose $\dim V >\dim W$. Then no linear map from $V$ to $W$ is injective
I know this is fairly trivial but how is $\dim\operatorname{range}T > \dim W$? Basically, can someone explain the first inequality (as well as the second)?

$\mathbf{3.23}$ A map to a smaller dimensional space is not injective

Suppose $V$ and $W$ are finite-dimensional vector spaces such that $\dim V>\dim W$. Then no linear map from $V$ to $W$ is injective.

Proof$~$ Let $T\in\mathcal L(V,W)$. Then

\begin{align*}
\dim\operatorname{null} T
&= \dim V-\dim\operatorname{range} T
\\
&\ge\dim V-\dim W
\\
&>0\,,
\end{align*}

答: The second inequality is the hypothesis. Note that the first inequality stems from $\dim\,\mathrm{range}\,T \leq \dim{W}$. This inequality holds because the range of $T$ is a subspace of $W$.


答: The first inequality comes from the fact that$$\operatorname{range}T\subset W\implies\dim\operatorname{range}T\leqslant\dim W$$and the second one from the fact that we are assuming that $\dim V>\dim W$.

Title: Suppose $\dim V >\dim W$. Then no linear map from $V$ to $W$ is injective

Body:
I know this is fairly trivial but how is $\dim\operatorname{range}T > \dim W$? Basically, can someone explain the first inequality (as well as the second)?

$\mathbf{3.23}$ A map to a smaller dimensional space is not injective

Suppose $V$ and $W$ are finite-dimensional vector spaces such that $\dim V>\dim W$. Then no linear map from $V$ to $W$ is injective.

Proof$~$ Let $T\in\mathcal L(V,W)$. Then

\begin{align*}
\dim\operatorname{null} T
&= \dim V-\dim\operatorname{range} T
\\
&\ge\dim V-\dim W
\\
&>0\,,
\end{align*}


问:
Formula to determine amount before percentage deductions?
For some reason, i'm having trouble working out what should be a rather simple algebraic formula.

I have amount (X), which is the amount added to an account after tax (T) and fees (F) are deducted from the original payment (P). I know the value of X, T and F and need to determine the value of P. The part i'm getting hung up on is that T and F are percentages of P (ie: T = 20%, F = 3%).

Example:

```<code>P = 100
T = .20
F = .03
X = 77

P - (P * (T + F)) = X
100 - (100 * (.20 + .03) = 77
</code>```

How can I calculate P, if I only know T, F and X ?

答:
Adding T and P together we get that they take out $23\%$ of P
$$P-0.23P=0.77P=X\implies P=\frac{X}{0.77}\approx (1.298701299)X$$
so $$P\approx X\times 130\%$$


问:
Variational Formulation of Yamabe Problem Equivalence.
Suppose we have an n-manifold ($M$, $g_0$) with scalar curvature $S_0$. I'm aware that the Yamabe problem can be classed as the problem of minimising the following Einstein-Hilbert Functional over the conformal class of $g_0$.

$$\underset{g \in [g_0]}{\mathcal{E}({g})} =  {\frac{{\int_{\mathcal{M}}{S} {dvol_{{g}}}}}{\left({\int_{\mathcal{M}}dvol_{{g}} }\right)^{{\frac{n-2}{n}}}}}.$$

The metric which minimises this, say $\tilde{g}$, is the metric we're looking for with constant scalar curvature.

All four authors who contributed to the proof of this problem (Yamabe, Trudinger, Aubin, and Schoen) found that this is equivalent to minimising the following functional for $u$.

$$F(u) = {\frac{{\int_{\mathcal{M}}\frac{4(n-1)}{n-2}} {\lvert  \nabla u \rvert}^2 + S_0 u^2}{{\| u \|}_p^2}}.$$ and $p=\frac{2n}{n-2}$

The minimising function $\tilde{u}$ then gives our required metric $\tilde{g} = \tilde{u}^{\frac{4}{n-2}}g_0$ which has constant scalar curvature.

Moreover, the scalar curvature of an arbitrary metric $\tilde{g}$ in $g_0$'s conformal class can be given by

$$\tilde{S} = u^{\frac{-4}{n-2}}\left(S_0 - {\frac{4(n-1)}{n-2}} u^{-1} \mathop{}\!\mathbin\bigtriangleup u\right)$$
where $\mathop{}\!\mathbin\bigtriangleup$ denotes the generalised Laplacian for manifolds.

${\bf Question:}$
How are these two variational problems equivalent? I would imagine it is a simple case of plugging the formula for $\tilde{S}$ into our formula for $\mathcal{E}(\tilde{g})$. However I am unsure how the volume forms transform under this relation?

答:
It is a conformal transformation, which means that the volume form transforms as
$$
dvol_{\tilde g} = u^{\frac{2n}{n-2}}vol_{g_0},
$$
and so
$$
\int_Mdvol_{\tilde g} = \int_M u^{\frac{2n}{n-2}}vol_{g_0} = \|u\|_p^p,
$$
with $p=\frac{2n}{n-2}$. By the way I feel that the transformation formula should be $\tilde g=u^{\frac{2}{n-2}}g_0$, not $\tilde g=u^{\frac{4}{n-2}}g_0$.


问:
Can the conjunction of any two $\exists\forall$-sentences be expressed equivalently as a $\exists \forall$-sentence?
We say that a sentence is a $\exists\forall$-sentence iff it is of the form $\exists w_1\cdots\exists w_m\forall v_1\cdots\forall v_n \theta(\bar{w},\bar{v})$ where $\theta$ is quantifier-free. My question is, given any two $\psi,\varphi$ $\exists\forall$-sentences, does there exist another $\exists\forall$-sentence $\gamma$ such that $\psi\land\varphi\equiv\gamma$?

I've only managed to almost prove the case when both $\psi$ and $\varphi$ have the same amount of existential and universal quiantifiers, but I don't see how to proceed in the general case.

The main problem I have is that $(\exists x\alpha)\land(\exists x\beta)\not\equiv\exists x(\alpha\land\beta)$, however it is true that $\exists x(\alpha\land\beta)$ logically implies $(\exists x\alpha)\land(\exists x\beta)$.

Thanks for any help.

答:
The formula
$$\exists \vec{w} \forall \vec{v} \left[P(\vec{w},\vec{v})\right] \land \exists \vec{x} \forall \vec{y} \left[Q(\vec{x},\vec{y})\right]$$
is equivalent to
$$\exists \vec{w},\vec{x} \forall \vec{v},\vec{y} \left[P(\vec{w},\vec{v}) \land Q(\vec{x},\vec{y})\right].$$
This assumes that all the $\vec{w},\vec{v},\vec{x},\vec{y}$ are distinct, but you can always achieve that by renaming.


问:
a dense subspace of inner product space whose codimension is 1
Is there an example of an inner product space $V$ and a dense subspace $D$ whose codimension is $1$?

In other words, there exists $z\in V$ such that every element of $V$ can be written in the form $e+\lambda z$ for some $e\in E$ and some scalar $\lambda$.

答:
As Kavi Rama Murthy says in the comments, "Every infinte dimensional inner product space has a discontinuous linear functional f and the kernel of such a functional is dense and has codimension 1".

I would like to add a proof of the fact that every infinite dimensional normed space (in general) has an unbounded linear functional.

The kernel of a linear functional on a Banach space is either closed or dense: the kernel is closed if-f the functional is bounded. The kernel is dense if-f the functional is unbounded, see this post.

So let $X$ be a normed space with infinite dimension. Take $\{x_n\}$ a linearly independent subset of $X$ (which is possible, since $X$ has infinite dimension) and extend it to a Hamel basis of $X$, say $\{x_n\}_{n=1}^\infty\cup Z$, where $Z\subset X\setminus(\{x_n\}_{n=1}^\infty)$. We define a functional on the basis and we extend it linearly on all $X$. We simply set $f(x_n)=n\cdot\|x_n\|$ and $f(z)=0$ for all $z\in Z$. Note that $f$ cannot be bounded: if $|f(x)|\leq c\|x\|$ for all $x\in X$ for some $c>0$, then $n\|x_n\|\leq c\|x_n\|$ for all $n$, which is impossible since $\mathbb{N}$ has no upper bound.


答: The leftmost (rightmost) of the two blue regions is congruent to the rightmost (leftmost) of the two white regions, so exactly half the area is shaded, so $c=2$.

Title: PDF of a rectangle

Body:
If I want to find the $c$ of a $PDF$ when it's given:

$f_{X,Y}\left(x,y\right)=c\:\:\:\:\left(The\:area\:in\:blue\right),\:otherwise:\:0$

I try to do that:

$$\int _{\frac{1}{2}}^1\:\int _{-x+\frac{3}{2}}^1\:c\,dy\,dx+\int _0^1\:\int _{-x+\frac{1}{2}}^{-x+1}\:c\,dy\,dx=1$$
But I got $c=\frac{8}{5}$ and the result is $c=2$.

(I know we can calculate it with by calculating the area of the triangles but I am wondering to know why my way is not working)


问:
Invariant problem-Chess board

The Question

There is an integer in each square of an $8\times8$ chessboard. In one
move, you may choose any $4\times4$ or $3\times3$ square and add $1$
to each integer of the chosen square. Can you always get a table with
each entry divisible by (a) $2$, (b) $3$?

My Understanding

Here is my solution for (b), please verify:
The quantity $I$=$(W-B)^2$$\cdot$$(W+B)$
(mod3) remains invariant during the transformation as one of them is $0$ during the transformation process ($W$ is the sum of all numbers on white squares and $B$ of black squares) So, if initially we have $W=0,B=1$ we will always have $I = 1$ for (a)  $I = (W-B)^2 - (W+B) $ (mod 2)

答:
At first, note that you don't need the integers, you need only the residui modulo 2 or 3, so you operate in space (a) $\Bbb{Z}_2$ or (b) $\Bbb{Z}_3$. You can order the numbers in the chessboard to a long vector (a) $\Bbb{Z}_2^{64}$ or (b) $\Bbb{Z}_3^{64}$

Note that if you swap any two moves, it makes the same result. So you only need to keep track of how many of what kind of moves you did, regardless of their order. There are 16 4×4 squares and 25 3×3 squares, so there are 41 possible moves total. And performing the same move (a) twice (b) three times cancels out. You can orher these moves to a long vector (a) $\Bbb{Z}_2^{41}$ or (b) $\Bbb{Z}_3^{41}$.

Each move can be represented as a vector in (a) $\Bbb{Z}_2^{64}$ or (b) $\Bbb{Z}_3^{64}$. By performing the move, this vector is being added to the chessboard vector. So you can construct a matrix $M$ from these vectors, which will transform the move vectors to chessboard vectors. Its form is (a) $\Bbb{Z}_2^{64×41}$ (b) $\Bbb{Z}_3^{64×41}$.

Now let's ask: Does for any chessboard vector $c$ exist a move vector $m$ such that $Mm=c$?

This holds if and only if $M$ is surjective. It is not, because it's thin, so it's sometimes impossible to solve the puzzle. If $M$ had at least 64 colums (i.e. there were at least 64 different moves), it might be possible. You can also see that there are $2^{64}$ or $3^{64}$ states of the chessboard, but only $2^{41}$ or $3^{41}$ possible moves, so there must be many unaccessible states.

Title: Invariant problem-Chess board


问:
Find the value of parameter a, so the polynomial has root with multiplicity
everyone!

Please help me understand what do I have to do here.

I have a function:

$$f(x) = x^3 + ax^2 +3x - 1$$

I need to find possible values of parameter a, such that the root of the function has multiplicity.

I have approached this problem like that:

$$f'''(x) = 6 + 2a$$
So I have found that

$$ a = -3$$

Are there any more values of parameters a, that correspond with the requirement above?

答:
Just experimenting with
$(\pm 1, 1)$ and $(\pm2, 1/4)$ and solving for $\space a,\space $ I found

$$x^3 + ax^2 +3x - 1=(x+2)^2\left(x-\frac14\right)\quad \text{for}\quad a=\frac{15}{4}$$

so the roots are $\bigl(-2,-2,\frac14\big)$


答:
Let:

$$y = \frac{a x + b}{c}$$
$$a, b, c, x \in \Bbb{Z}$$
For which $a, b, c$ there exists $x$ for such $y \in \Bbb{Z}$ ?

Question seems ambiguous to me.  As other responses have done, a reasonable assumption is that $x$ must be an integer.

However, the other responses seemed to have interpreted the equation as that $x$ and $y$ may vary.  The alternative interpretation is that you are given some fixed integer $y$, and are asking for which values of $a,b,c$ can a solution involving an integer value of $x$ be produced.

Under this alternative interpretation of the problem, which (admittedly) the OP may not have intended, since

$cy = ax + b$,

the constraints on $a,b,c$ for the fixed value of $y$ are that

$c \neq 0$ and

$a|(cy - b)$.

Here, if $b,c$ are chosen so that $(cy - b) = 0$, then $a$ must equal $0$, and $x$ can be anything.

Alternatively, if $b,c$ are chosen so that $(cy - b) \neq 0$, then $a$ can not equal $0$.

Title: Does exists any better way to solve "Simple hit problem" ? $y = \frac{a x + b}{c}$

Body:
I am looking for other solution of a problem, which I named:

$$\text{Simple hit problem}$$

Let:

$$y = \frac{a x + b}{c}$$
$$a, b, c, x \in \Bbb{Z}$$
For which $a, b, c$ there exists $x$ for such $y \in \Bbb{Z}$ ?

I noticed that the solution exists for $a, b, c$, if:

$$(ax) \ \text{mod} \ c = c - (b \ \text{mod} \ c),$$
but the approach relies on checking all unique values of result of modulo operator from left side of equation.

The question is, if there exists any better approach for this problem or anyway it come down to check, if some equation will be true for some $x \in A$, where A will be a set of finite ammount of values ?


问:
Fewer degree-$3+$ nodes than leaf nodes in a tree
Considering this question, I was struck by the idea that:

For a graph $G$ that is a tree, the number of degree-$1$ nodes exceeds the number of nodes of degree $3$ or higher.

.. which would fairly directly solve that question.

The intuition is as follows: each degree-$3$ node adds a branch to the tree, which must also add a degree-$1$ node. Higher degree nodes add branches per extra degree. This intuition adds a numerical prediction:
$$ \sum_{k\in H}(d(k)-2) = |L|-2$$
where $H$ is the set of vertices in $G$ with degree $3$ or higher and $L$ is the set of degree-$1$ nodes, with two leaf nodes being allocated to a simple unbranched tree.

Can anyone produce or reference a more formal proof?

答:
You could prove it also with induction on the number $n\geq 2$ of vertices. Let $\ell$ be the number of leafs and $t$ the number of degree 3 or more vertices.

If $n=2$ then $\ell=2$ and $t=0$ so $\ell>t$.

Induction step: In a tree $T$ there is a leaf $m$ with neigbour $w$. If we remove it we get smaller $T'$ tree, so by induction hypothesis we have $\ell'>t'$ in $T'$. Now give $m$ back, then:

$\ell= \ell'$ if $w$ is leaf in $T'$, but then $t=t'$ so $\ell>t$;

$\ell=\ell'+1$ if $w$ is not leaf in $T'$, but then we have two subcases:

If $d(w) = 2$ then $t=t'+1$ so $\ell >t$

If $d(w) > 2$ then $t=t'$ so $\ell >t$ again.


问:
A question on the proof of an embedding theorem (point-set topology)
I'm trying to understand the proof of the following theorem:

Theorem A: For each $\alpha\in A$, let $f_\alpha\colon X\to X_\alpha$. Then the evaluation map
$e\colon X\to \prod X_\alpha$ is an embedding if, and only if, $X$ has the weak topology given by the functions $f_\alpha$ and the collection $\{f_\alpha\ \vert\ \alpha\in A\}$ separates points.

However, I'm having trouble understanding one crucial step in the $(\Rightarrow)$ of the proof. Further, I know the topology on $e(X)\subseteq\prod X_\alpha$ is the weak topology induced by the restricted projections, i.e. the weak topology induced by the family of maps $\{\pi_\alpha\vert_{e(X)}\colon e(X)\to X_\alpha\}_{\alpha}$. But, how does the assumption that $e$ is an embedding (in particular a homeomorphism onto $e(X)$) let us conclude that $X$ has the weak topology induced by the family of maps
$\{\pi_\alpha\circ e\colon X\to X_\alpha\}_{\alpha}$?

From this point, the ($\Rightarrow$) direction of Theorem A follows directly from the observation that $\pi_\alpha\circ e = f_\alpha$, hence, $X$ has the weak topology induced by the family of maps
$\{f_\alpha\colon X\to X_\alpha\}_{\alpha}$. The fact that $\{f_\alpha\ \vert\ \alpha\in A\}$ separates points is clear to.

答:
Let us begin by establishing some terminology: denote by $\tau_X$ the topology of the space $X$; $\tau_\alpha$ will be the topology of the space $X_\alpha$, and lastly $\tau$ is the weak topology induced by the family $\{f_\alpha : \alpha \in A\}$; in other words, $\tau$ is the topology in $X$ generated by the subbbasis $\mathcal{S}=\{f_\alpha^{-1}[U_\alpha] : \alpha\in A, U_\alpha\in\tau_\alpha\}$. Our goal is to suppose that $e$ is an embedding and show that $\tau_X=\tau$.

First, let's focus on verifiyng the inclusion $\tau\subseteq \tau_X$. In order to do this, it suffices to show that $\mathcal{S}\subseteq \tau_{X}$. With this in mind, fix $\alpha\in A$ and $U_\alpha\in\tau_\alpha$. Observe that $e:(X,\tau_{X}) \to \prod X_\alpha$ and $\pi_\alpha: \prod X_\alpha \to X_\alpha$ are both continuous maps. Then, the equality $\pi_\alpha \circ e = f_\alpha$ tells us that $f_\alpha^{-1}[U_\alpha]= e^{-1}[\pi_\alpha^{-1}[U_\alpha]]$ is an open subset of $(X,\tau_{X})$; equivalently, $f_\alpha^{-1}[U_\alpha]\in \tau_{X}$. This proves that $\mathcal{S}\subseteq \tau_{X}$ and so, we have $\tau\subseteq \tau_X$.

For the other inclusion, take $U\in \tau_{X}$ and $x\in U$. Since $e$ is an embedding, we know that $e[U]$ is an open subset of $e[X]$. Now take $F$, a non-empty finite subset of $A$, and for every $\alpha\in F$,  $U_\alpha\in\tau_\alpha$ in such a way that $$e(x)\in \left(\bigcap_{\alpha\in F} \pi_{\alpha}^{-1}[U_\alpha]\right) \cap e[X] \subseteq e[U] \quad ...\ (*)$$

I claim that $$x\in \bigcap_{\alpha\in F} f_{\alpha}^{-1}[U_\alpha] \subseteq U.$$ To see this, simply apply $e^{-1}$ everywhere on (*) and use the identity $\pi_\alpha \circ e = f_\alpha$. This shows that for every nonempty element of $\tau_{X}$ and every point in it, you can fit in-between a finite intersection of elements in $\mathcal{S}$; in other words, $\tau_{X}\subseteq \tau$.


问:
Hint Needed for a Decreasing Sequence of Limit Points
I'm trying to work through exercise 13E, part (4) of S. Willard's Topology through self-study.  I'm scratching my head on the question below.  I paraphrased of some notation earlier in the exericse, which is required to understand the question.

Given a set $A$, let $A'$ denote the set of accumulation points of $A$.  Let $A^1 = A', A^2 = (A^1)', A^3 = (A^2)'$ and so on . . . .

For any positive integer $n$, there is a set $A \subseteq \mathbb{R}$ such that $A,A^1,\ldots,A^{n-1}$ are non-empty and $A^n = \emptyset$.

Of course, we assume $\mathbb{R}$ has the standard topology.

I'm scratching my head trying to construct such a set $A$.  I've thought about taking the union of some collection of sets, each in a form similar to $\{ 1/n : n \in \mathbb{N} \}$, and arranging the limit points thereof so they fall off one by one as I continue to find the limit points of the limit points.  I haven't found a way to make this work, though, and I have a feeling I'm heading in the wrong direction.

Can someone please provide me a hint or some guidance?  I'd like to work this out myself, so please do no provide a solution (or if you do, please conceal it as a spoiler).  I appreciate your assistance.

Best,
Doug

Body:
Here’s a schematic of what you need to get the case $n=4$ in the plane; it generalizes easily and also adapts fairly easily to $\Bbb R$.

$$\begin{array}{rr}
\bullet&\bullet&\bullet&\bullet&\longrightarrow&\bullet\\
\uparrow&\uparrow&\uparrow&\uparrow\\
\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet\\
\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet\\
\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet\\
\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet\\
\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet&\color{red}\bullet\color{red}\bullet\color{red}\bullet\color{red}\to\bullet
\end{array}$$


问:
Flipping a function across $y = -x$
Is there a general rule of flipping a function, for example $$f(x)=\frac{2x-3}{7x-5}$$ across the line $y = -x$ on the Cartesian plane? I’ve read some articles about it but it doesn’t very help because I’m ver poor at math. When you answer can you make it as simple as possible? Thanks!

答: Simply convert $(x,y)\rightarrow (-y,-x)$. In this case, whenever you see an $x$ term, change it to $-y$. Whenever you see a $y$ term, change it to $-x$. To get some intuition on why this is true, sketch a graph! A more formal proof follows from this.

Title: Flipping a function across $y = -x$


问:
Find all $(x,y,z) \in \mathbb{N}$ such that $x^2 + y^2 =3(2023)^z +77$
The question says Do not use any modular arithmetic.

My attempt:

First of all i think that these two things would help:

If $4 \mid x^2 + y^2 \implies 2\mid x$ And $y$. I’ve proved this one

If $7 \mid x^2 + y^2 \implies 7 \mid x$ And y. I don’t know how to prove this.

And it turns out that the only possible values to $(x,y,z)=(4,8,0)$.

答:
We can write $x=7k+r$ where $r\in\{0,1,2,3,4,5,6\}$ so $$x^2 = 7(7k^2+2kr)+r^2$$ so $$x^2 = 7k'+r^2$$
Similary we have $$y^2 = 7l'+r'^2$$

Since $7\mid x^2+y^2$ we have now $$7\mid r^2+ r'^2$$

but this is possible only if $r=r'=0$ i.e. $7\mid x$ and $7\mid y$.

 We see that if right side is divisible by 7 so $7\mid x$ and $7\mid y$ so $49$ divides RHS but that mean that $49\mid 7$ if $z\geq 2$. So $z\leq 1$. Can you finish now?


问:
What is the mathematical foundation of Control Theory?
There is a question which I'm wondering again and again in recent months. I have taken courses on elementary differential equations, signals and systems, linear control systems, general theory of circuits and networks but I still do not know how can a simple linear integral transformation (Laplace transform) be so much helpful in analyzing and designing linear systems. For example, I think I somewhat know what "time domain" is, but how about the "frequency domain"?

Consider a block diagram in the frequency domain. Conceptually, what do the blocks represent? What is traveling(?) on the connections between blocks? First, I have thought that instead of taking care of the statement "when does some phenomenon happens" we consider "how many times does a phenomenon oscillate", but how can this approach be more helpful? Is it the best (optimal) way of treating such problems?

I think control systems and even systems have a more general meaning in mathematics. I even think that the very problem of "controlling a system" does have multiple "paradigms" — A.I., neural networks, state space approach, fuzzy logic, robust control, adaptive control, etc.

What I'm looking for is a book (preferred) or paper discussing the very beginning notions of system, control system, its history, and more importantly, what is the field or language in mathematics to study systems rigorously? Dynamical systems? Game theory? Differential equations? Linear algebra? A.I?

Any help is appreciated. Thanks.

P.S.: I've already studied these books:

Alan Oppenheim's Signals and Systems (I think it is the best in the field)

Ogata's Modern Control Engineering

Desore's Basic Circuits Theory

Charles A - Kuh and Ernest S's A rather brief book on the history of control systems ($H_\infty$ methods and so on, but I didn't get much; at least, this book induced some information on me that nobody actually knows what "feedback" is, why is it so helpful and why we should take samples of the output! It wasn't a precise book, I admit)

26 May 2013:

As I said, I am looking for a book or article discussing the origins of Control Theory and Systems. Seven days are passed since I started the bounty, yet I didn't find an answer. I'll get to the bottom of this issue as soon as I get some free time. Thanks.

答:
Linear Algebra Underlies Everything.

The power of the Laplace transform derives from the power of concepts like a linear operator and an eigenfunction.  The exponential is the eigenfunction of the derrivative operator, which is the main operator in control theory.  By projecting the system onto bases which are the eigenfunctions of the operators in your system, you simplify the problem by exposing the symmetries.  This is what the Laplace transform does ($\int f(x) e^{-sx}dx$ is like an inner product between co-ordinates ($f(x)$) and the new bases you want to represent your function/vector in (exponentials).  The result are new co-ordinates in the exponential space)

The complex exponential is the eigenfunction of the second derrivative operator.  So projections into this space expose a different set of symmetries, in this case, the 'frequencies'.  So the Fourier Transform is also just linear algebra.

I'd recommend a healthy dose of linear algebra, to satisfy all your inquisitive needs!


问:
Probability of Power Rangers, please correct me if I am wrong
There are five Power Rangers.  Of the five,  two are male(Red, Black) and three are female (Pink, Yellow,blue.)I randomly select two of the Power Rangers, without replacement.

(a)  What is the probability that the black Ranger is one of the two selected Power Rangers?

```<code>pretending that you only randomly select one power ranger, the
probability of picking the black would just be 1/5, so if you were
to pick another it would be 1/4 so it would be 1/5 * 1/4 = .05 so 5% chance?
it just seems low
</code>```

(b)  What is the probability at least one of the two selected Power Rangers is female?

```<code>probability that one is female is 3/5, so if you were to pick
another power ranger at random would it be 3/5*3/4
</code>```

(c)  Given that at least one of the two selected Power Rangers is male, what is the conditional probability the Pink Ranger is selected?

```<code>conditional probability, wouldnt it just be 33.3% that the pink is selected given theres only three females?
</code>```

(d)  Are the events “the Pink Ranger is one of the two selected” and “at least one of the two selected Power Rangers is female” independent?  Explain why or why not.

```<code>Yes, event A effects event B.

</code>```

答:
As the commenters have pointed out, your intuition to doubt your answer to (a) was appropriate.
$$
P(\text{selected Pink}) = P(\text{Pink selected first}) + P(\text{Not pink, then Pink}) = 1/5 + 4/5 \times 1/4 = 2/5.
$$

Then
$$
P(\text{At least } 1 \text{ female}) = 1 - P(\text{both male}) = 1 - 3/5 \times 2/4 = 1 - 3/10 = 7/10.
$$
Next, use Bayes's Theorem:
$$
P(\text{Pink}|\text{At least 1 female}) = \frac{P(\text{Pink AND at least 1 female})}{P(\text{At least 1 female})} = \frac{P(\text{Pink})}{P(\text{At least 1 female})} = \frac{2/5}{7/10} = \frac{4}{7}.
$$
(Can you see why the middle equality is true? This is useful in the final part!)

Finally, recall that two events $A,B$ are independent if $P(A \cap B) = P(A)P(B)$. Can you use this to give a clearer explanation for (d)?


问:
how to convert to a rational number with some decimal from base 10 to base 2
It is very eazy to convert an integer number to another base, say 2, using Maple. Can anyone tell me how to convert a rational numbers with several decimals from base 10 to other bases In maple? Well, I can multiply the rational number by 10th and get integer and then convert to another base, but this wont give me the true value for corresponding number in the other base. For example, I can multiply 0.25 by 10 and get 25 and after that convert 25 from base 10 to base 2 and get 10011 but this doesn't equal 0.25 in base 2.
Cam anyone tell me how to do that in Maple??
Thank you.</p>

答:
You wrote that you wanted to convert "rational numbers with several decimals", which is not clear.

Did you mean that you want to convert base-10 floating-point numbers (with several decimal digits on the right of the point) to base-2?

If that is so, then is this what you are trying to get for the 0.25 example?

```<code>convert(0.25,binary);

                     0.01000000000
</code>```

The above method can be used for any base-10 float, to convert to binary (base-2) float representation.

The question of converting other to "floating-point" representation in some other base (radix) is interesting.

```<code>restart:

G:=proc(x)
     local radix;
     if type(procname,indexed) and nops([op(procname)])>0
       and type(op(1,procname),posint)
       and op(1,procname)>1 then
        radix:=op(1,procname);
     else
        radix:=2;
     end if;
     parse(cat(op(ListTools:-Reverse(
         convert(trunc(x*radix^Digits),base,radix)))))
         *10.0^(-Digits);
    end proc:

p:=0.5555555555555555555555555555:

G(p), convert(p,binary);

                     0.1000111000, 0.1000111000

p:=98.7654321:

G(p), convert(p,binary);

                                6                6
                  1.100010110 10 , 1.100010110 10

Digits:=30:
p:=98765432.1987654321:

G[2](p), convert(p,binary);

                                   26                                    26
 1.01111000110000101001111000001 10  , 1.01111000110000101001111000001 10

G[8](p), convert(p,octal);
                                    8                                    8
  5.70605170145611124547073676376 10 , 5.70605170145611124547073676376 10

G[3](p); # how shall we test this, to see if all "digits" are accurate?

                                                  16
                2.02122112102002220121002200220 10
</code>```

Body:
You wrote that you wanted to convert "rational numbers with several decimals", which is not clear.

Did you mean that you want to convert base-10 floating-point numbers (with several decimal digits on the right of the point) to base-2?

If that is so, then is this what you are trying to get for the 0.25 example?

convert(0.25,binary);

                     0.01000000000

The above method can be used for any base-10 float, to convert to binary (base-2) float representation.

The question of converting other to "floating-point" representation in some other base (radix) is interesting.

restart:

G:=proc(x)
     local radix;
     if type(procname,indexed) and nops([op(procname)])>0
       and type(op(1,procname),posint)
       and op(1,procname)>1 then
        radix:=op(1,procname);
     else
        radix:=2;
     end if;
     parse(cat(op(ListTools:-Reverse(
         convert(trunc(x*radix^Digits),base,radix)))))
         *10.0^(-Digits);
    end proc:

p:=0.5555555555555555555555555555:

G(p), convert(p,binary);

                     0.1000111000, 0.1000111000

p:=98.7654321:

G(p), convert(p,binary);

                                6                6
                  1.100010110 10 , 1.100010110 10

Digits:=30:
p:=98765432.1987654321:

G[2](p), convert(p,binary);

                                   26                                    26
 1.01111000110000101001111000001 10  , 1.01111000110000101001111000001 10

G[8](p), convert(p,octal);
                                    8                                    8
  5.70605170145611124547073676376 10 , 5.70605170145611124547073676376 10

G[3](p); # how shall we test this, to see if all "digits" are accurate?

                                                  16
                2.02122112102002220121002200220 10


问:
Find an element that repeated $\frac{n}{5}$ times in sorted array

We are given a sorted array$A[1..n]$, we are searching to find an
element that repeated $\frac{n}{5}$ times in array.How we can do it in
$logn$?

I find an solution in $O(n)$,with checking each element $i$,and calculate it appearance in interval $A[i+\frac{n}{5}]-A[i]+1$. If $A[i]=A[i+\frac{n}{5}]$ then we find it.

But how we can decrease it to $logn$?

答: Note that the interval you're looking for is so big that it must hit one of five evenly-spaced indexes between 0 and $n$ (say $n/6,2n/6,3n/6,4n/6,5n/6$), so we have five candidate values for the repeated element. Use two binary searches for each candidate value to find its start and end indexes.


问:
Solve for natural numbers: $(2a+3)(3a+4) = 35^b$
Find $a$ and $b$ be natural numbers, such that $(2a + 3)(3a + 4) = 35^b$

One can see $a=1, b=1$ is a solution. The challenge is to prove there are no other solutions.
My intuition is that $2a + 3 = 5^b$, and $3a + 4 = 7^b$ - otherwise, $5$ would divide both terms, therefore their difference - so, $5 | a + 1, 7| a+ 1\implies 35 | a + 1,$ then LHS would not be divisible by $35$, contradiction. So, the first parenthesis is $5^b$ and second is $7^b$.

答:
hint

$$3(2a+3)-2(3a+4)=1$$

so, By Bezout's Theorem, $ 2a+3 $ and $ 3a+4 $ are relatively primes.

on the other hand

$$(2a+3)(3a+4)=5^b.7^b$$


问:
Prove that $(b_n)_{n=1}^{\infty}$ converges to $a$
Suppose $(a_n)_{n=1}^\infty$ converges to $a$, and define a new sequence $(b_n)_{n=1}^{\infty}$ by $b_n= \frac{a_n+a_{n+1}}{2}$ for all n. Prove that $(b_n)_{n=1}^{\infty}$ converges to $a$.

So from my understanding, if $(a_n)_{n=1}^\infty$ converges to $a$, and $(b_n)_{n=1}^{\infty}$ by $b_n= \frac{a_n+a_{n+1}}{2}$, I think I'm suppose to use the squeeze theorem here to prove, $(b_n)_{n=1}^{\infty}$ converges to $a$. I understand this but don't know how to put this in proof from.

答:
Because $a_n$ converge to $a$, so for each $\epsilon >0$, $\exists N$ such that $\forall n>N: |a_n-a|<\epsilon$.

Hence, $\forall n>N$, we have
$$|b_n-a| = \left|\frac{a_n+a_{n+1}}{2}-a \right|\le \frac{1}{2}(|a_n-a| + |a_{n+1}-a|) \le\epsilon \tag{1}$$

Because of (1), then for each $\epsilon >0$, $\exists N$ such that $\forall n>N: |b_n-a|<\epsilon$. By definition, $b_n$ converge to $a$.


答:
So is there a question here? If so, here is a hint, combined w what you noted in your OP:

$7^b > 2×5^b$ for all $b \ge 3$. This leaves only $b=1,2$ to check.

Title: Solve for natural numbers: $(2a+3)(3a+4) = 35^b$

Body:
Find $a$ and $b$ be natural numbers, such that $(2a + 3)(3a + 4) = 35^b$

One can see $a=1, b=1$ is a solution. The challenge is to prove there are no other solutions.
My intuition is that $2a + 3 = 5^b$, and $3a + 4 = 7^b$ - otherwise, $5$ would divide both terms, therefore their difference - so, $5 | a + 1, 7| a+ 1\implies 35 | a + 1,$ then LHS would not be divisible by $35$, contradiction. So, the first parenthesis is $5^b$ and second is $7^b$.


答:
$$b_n=\frac{a_n+a_{n+1}}{2}$$
$b_n$ is the mean between $a_n$ and $a_{n+1}$ therefore
$$\min (a_n,a_{n+1})\le b_n\le \max( a_n,a_{n+1});\forall n\in\mathbb{N}$$
as $a_n\to a$ we have  $b_n\to a$ for the squeeze theorem.

Body:
Suppose $(a_n)_{n=1}^\infty$ converges to $a$, and define a new sequence $(b_n)_{n=1}^{\infty}$ by $b_n= \frac{a_n+a_{n+1}}{2}$ for all n. Prove that $(b_n)_{n=1}^{\infty}$ converges to $a$.

So from my understanding, if $(a_n)_{n=1}^\infty$ converges to $a$, and $(b_n)_{n=1}^{\infty}$ by $b_n= \frac{a_n+a_{n+1}}{2}$, I think I'm suppose to use the squeeze theorem here to prove, $(b_n)_{n=1}^{\infty}$ converges to $a$. I understand this but don't know how to put this in proof from.


答:
Let $n_d$ be the number of nodes of degree $d$.  By the handshaking lemma and the fact that a tree on $n$ nodes has $n-1$ edges, we have
$$\sum_d d n_d = 2\left(\sum_d n_d - 1\right),$$
which implies that
$$-2 = \sum_d (d-2) n_d = -n_1 + \sum_{d \ge 3} (d-2) n_d.$$

Title: Fewer degree-$3+$ nodes than leaf nodes in a tree

Body:
Considering this question, I was struck by the idea that:

For a graph $G$ that is a tree, the number of degree-$1$ nodes exceeds the number of nodes of degree $3$ or higher.

.. which would fairly directly solve that question.

The intuition is as follows: each degree-$3$ node adds a branch to the tree, which must also add a degree-$1$ node. Higher degree nodes add branches per extra degree. This intuition adds a numerical prediction:
$$ \sum_{k\in H}(d(k)-2) = |L|-2$$
where $H$ is the set of vertices in $G$ with degree $3$ or higher and $L$ is the set of degree-$1$ nodes, with two leaf nodes being allocated to a simple unbranched tree.

Can anyone produce or reference a more formal proof?


问:
Number of sequences defined on a set
Given a set $D\subset \mathbb{R}$ and $c\in D$ how many sequences $f_r:\mathbb{N} \rightarrow D$ can be defined such that $\lim\limits_{n\rightarrow \infty} f(n)=c$

答:
HINT: If $D=\{c\}$, there is only one. If $|D|>1$, and $c$ is an isolated point of $D$, there are countably infinitely many. If $c$ is a limit point of $D$, there are $\mathfrak{c}=|\Bbb R|=|\wp(\Bbb N)|$. To prove these three results you will probably want to use the following facts.

If $c$ is isolated, any sequence in $D$ converging to $c$ must be eventually constant.

If $\sigma=\langle x_n:n\in\Bbb N\rangle$ is a sequence of distinct points converging to $c$, so is every subsequence of $\sigma$.

Title: Number of sequences defined on a set


答:
$$
\lim_{n \to \infty} b_n = \lim_{n \to \infty} \frac{a_n + a_{n+1}}2 = \frac{\lim_{n \to \infty} a_n + \lim_{n \to \infty} a_{n+1}}2 = \frac{a+a}2 = a.
$$

No need for squeeze theorem here, it's a very simple argument.

Hope that helps,

Title: Prove that $(b_n)_{n=1}^{\infty}$ converges to $a$


问:
complex analysis-roots of constant polynomial function
True or False: There exists a value for $w\in \mathbb{C}$ such that the equation $z^{100}+z +1 = w$ has no solution with $z\in\mathbb{C}$.

My answer

$False$-By fundamental theorem of algebra,Every non-constant polynomial has a root in $\mathbb{C}$.

what would be the root(s) of $z^{100}+z +1 = w$  for above answer if it is true?

答:
In general, it is known that there does not exist a closed form over radicals for the roots of arbitrary polynomials; there does exist closed forms for all polynomials of degree less than 5 and there does exist closed forms for some polynomials with higher degrees, but not all of them.

Essentially this means that the only method to find the roots of polynomials is to approximate them. Here is an interesting way to "solve" polynomials:

Start with: $$x^2-x-1=0.$$

By quadratic formula one of the roots is $$\frac{1+\sqrt{5}}{2}.$$

But what if I didn't know the quadratic formula (or in general, what if I didn't have a formula), well solve for $x$ instead:

$$x=1+\frac{1}{x}.$$

Since $x=1+\frac{1}{x}$ we must have

$$x=1+\frac{1}{1+\frac{1}{x}}.$$

Since $x=1+\frac{1}{x}$ we must also have

$$x=1+\frac{1}{1+\frac{1}{1+\frac{1}{x}}}.$$

To infinity we arrive at:

$$x=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{\ddots}}}}}$$

and the more interesting consequence is that

$$1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{\ddots}}}}}=\frac{1+\sqrt{5}}{2}. $$

They must be the same since they are both a positive root of a polynomial that only has one positive root. At the beginning we stated that not all polynomials are solvable by radicals; another way of making that statement is to say that not all "continued approximation expressions" will simplify to a nice radical expression. However, the creepy "continued approximation expressions" can always be found.

One could approach the polynomial above in the same way and find one of the roots to be:

$$z=\sqrt[100]{w-1-\sqrt[100]{w-1-\sqrt[100]{w-1-\sqrt[100]{w-1-\sqrt[100]{\cdots}}}}}$$

In this case the expression might not converge unless we pick an appropriate starting point, however when the expression above does converge it must be a root of the polynomial since it satisfies the equation.

If the above answer is upsetting, then the more upsetting consequence is that every method provided to you to find a root will reduce to some "approximation formula" like the one shown above, unless (of course) the above expression "magically" reduces over radicals and we just didn't see how it does.

Besides very tedious inefficient Galois Theory, there is no known simple method of determining when an expression will reduce over radicals. :-(


问:
P-values and statistical significance
The mean for the result of a regional test is $525$ points with a deviation of $80$.

A $90$ students class did the test and got a mean score of $535$.

Is the mean score of the class different from the regional mean score for a statistical significance of $0.05$?

I'm trying to understand the role of statistical significance and just can't wrap my head around how could these means not be different, would love to get some help understanding this problem.

答: You should specify, whether you are interested in a single sided or a two sided test. Suppose we take the latter, we know that the 95% confidence interval is approx. spanned by $\mu \pm 2 \hat \sigma_{\bar x}$, if we assume a normal distribution. In addition, we know that $\hat\sigma_{\bar x} = \hat\sigma_{x}/\sqrt{n} = 80/\sqrt{90}\approx 8.43$. Hence, the $2\sigma$ interval is $525 \pm 2\cdot 8.43 \approx [508.1, 541.8]$. Since the found value $535$ lies within this interval the result is not significant at a 5% value.

Title: P-values and statistical significance


问:
Let $H$ be a subgroup of $S_7$ consisting of permutations that send $1,2,3$ to $1,2,3$ in some order. Is $H$ isomorphic to $S_3 \times S_4$?

Let $H$ be a subgroup of $S_7$ consisting of permutations that send $1,2,3$ to $1,2,3$ in some order. (The remaining values $4,5,6,7$ are still permuted just not to the positions $1,2$ or $3$.) Is $H$ isomorphic to $S_3 \times S_4$?

This turns out to be true, but I'm not sure how to get to the answer here. Shouldn't $H$ and $S_3 \times S_4$ share a bijective mapping since we're talking about permutations here? Clearly the cardinality of $S_3 \times S_4$ is greater than the cardinality of $H$ so there isn't a bijective map between them. What might be I missing here?

答:
(I assume that $H$ is the subgroup of all the permutations of $S_7$ that send ecc.)

In general, given a set $X$ and a subset $Y\subseteq X$, the set:

$$H:=\{f\in S_X\mid f(Y)=Y\}=\{f\in S_X\mid f_{|Y}\in S_Y\}$$

is indeed a subgroup of $S_X$. In fact:

(closure) $f,g\in H\Rightarrow (fg)(Y)=f(g(Y))\stackrel{(g\in H)}{=}f(Y)\stackrel{(f\in H)}{=}Y\Rightarrow fg\in H$;

(inverse) $f\in H\Rightarrow Y=(f^{-1}f)(Y)=f^{-1}(f(Y))\stackrel{(f\in H)}{=}f^{-1}(Y)\Rightarrow f^{-1}\in H$.

Let's define $K:=\{f\in S_X\mid f(X\setminus Y)=X\setminus Y\}=\{f\in S_X\mid f_{|X\setminus Y}\in S_{X\setminus Y}\}$. Note that $K=H$.

Consider the map $\varphi\colon H\to S_Y\times S_{X\setminus Y}$ defined by $f\mapsto(f_{|Y},f_{|X\setminus Y})$. This is well defined, because $f\in H\Rightarrow f_{|Y}$ is onto $Y$ (and hence $f_{|Y}\in S_Y$), and $f\in H\Rightarrow f\in K\Rightarrow f_{|X\setminus Y}$ is onto $X\setminus Y$ (and hence $f_{|X\setminus Y}\in S_{X\setminus Y}$). Let's check for the injectivity of $\varphi$:

\begin{alignat}{1}
\varphi(f)=\varphi(g) &\Longrightarrow (f_{|Y}=g_{|Y})\wedge(f_{|X\setminus Y}=g_{|X\setminus Y}) \Longrightarrow f=g
\end{alignat}

Surjectivity of $\varphi$: $\forall (h,k)\in S_Y\times S_{X\setminus Y}$, define $f\in\operatorname{Maps}(X)$ by $f_{|Y}:=h$ and $f_{|X\setminus Y}:=k$; then $f\in H$ and $\varphi(f)=(h,k)$.

Finally, since $g\in H, y\in Y\Rightarrow g(y)=g_{|Y}(y)\in Y$, we get $\forall f,g\in H, \forall y\in Y$:

\begin{alignat}{1}
(fg)_{|Y}(y) &= (fg)(y) \\
&= f(g(y)) \\
&= f(g_{|Y}(y)) \\
&= f_{|Y}(g_{|Y}(y))= \\
&= (f_{|Y}g_{|Y})(y) \\
\end{alignat}

whence $(fg)_{|Y}=f_{|Y}g_{|Y}$. Likewise, $(fg)_{|X\setminus Y}=f_{|X\setminus Y}g_{|X\setminus Y}$. So, finally:

\begin{alignat}{1}
\varphi(fg) &= ((fg)_{|Y},(fg)_{|X\setminus Y}) \\
&= (f_{|Y}g_{|Y},f_{|X\setminus Y}g_{|X\setminus Y}) \\
&= (f_{|Y},f_{|X\setminus Y})(g_{|Y},g_{|X\setminus Y}) \\
&= \varphi(f)\varphi(g) \\
\end{alignat}

Therefore, $H(=K)\cong S_Y\times S_{X\setminus Y}$, and yours is just the particular case for $X:=\{1,2,3,4,5,6,7\}$ and $Y:=\{1,2,3\}$.


问:
Maximum Likelihood Estimator for Logarithmic Distribution
I am trying to calculate the MLE for the logarithmic distribution.
It holds

$$ P(X=k) = -\frac{p^k}{k \cdot \ln(1-p} $$

Thus, the ML function is

$$L_p(X_1,\dots, X_n) = \prod_{i=1}^{n} -\frac{p^{x_i}}{x_i \cdot \ln(1-p)} = p^{\sum_{i=1}^n x_i} \left(\frac{1}{\ln(1-p)}\right)^n \prod_{i=1}^n -\frac{1}{x_i} $$

and the log likelihood function is

\begin{align}
\log L_p(X_1,\dots,X_n)& = \sum_{i=1}^n x_i \cdot \log(p) + n \cdot \log\left(\frac{1}{\log(1-p)}\right) + \log\left(\prod_{i=1}^n -\frac{1}{x_i}\right)
\\&= \sum_{i=1}^n x_i \cdot \log(p) + n \cdot -\log(\log(1-p)) + \log\left(\prod_{i=1}^n -\frac{1}{x_i}\right)
\end{align}

So:

$$\frac{\partial L_p}{\partial p} = \frac{1}{p} \sum_{i=1}^n x_i + n \frac{1}{\log(1-p)(1-p)} \overset{!}{=} 0$$

This is equivalent to:

$$\frac{1}{n} \sum_{i=1}^n x_i = - \frac{p}{\log(1-p)(1-p)}$$

Now I don't know how to go on. How do I get the estimator for $p$?

Thanks in advance, for helping !

答:
Technically, I suspect that you have to write the log likelihood function as

$$ \sum_{i=1}^n x_i \cdot \log(p) + n \cdot \log\left(\frac{-1}{\log(1-p)}\right) + \log\left(\prod_{i=1}^n \frac{1}{x_i}\right)
$$

since $log(1-p)$ is negative, so $log(\frac{1}{log(1-p)})$ is undefined. I got the same final equation as you for the MLE, though.

I don't see a way to get a closed form solution, so I think you need to use numerical methods/root-finding algorithms to find the root(s) of
$$\frac{1}{\hat{p}} \sum_{i=1}^n x_i + n \frac{1}{\log(1-\hat{p})(1-\hat{p})} = 0$$


问:
How many Distinct Hamiltonian Maximal Planar Graphs are there (n vertices) and could this representation help?
If we make a regular polygon with n vertices (n edges) and triangulate on the inside with n-3 edges, then triangulate on the outside with (n-3) edges (or draw dotted lines inside again), a Maximal Planar Graph is formed.  Edges shouldn't be repeated and there's no loops or directions.

How many distinct graphs of this type are there?

It's connected to an earlier question where it was asked 'How many Distinct Maximal Planar Graphs are there? How many distinct Maximal Planar Graphs exist with $n$ vertices?

Will Orrick gave the OEIS numbers A000109.  It was then wondered if there was a known formula for those numbers or bounds on them.  It's conjectured that graphs of the type in this question might constitute most Maximal Planar Graphs, so a formula for the 'polygon' types might be an approximate formula or a lower bound for all types of Maximal Planar Graphs.

Dividing the polygon on the inside can be done in C(n-2) ways, where C(n) are the Catalan numbers A000108, so a connection was looked for - and A000109 seem to be close to C(n-2)*2^(n-13) at least for n=9 to 23.

So, the answer to this question would be of interest and any thoughts on connecting the A000108 and A000109 numbers.  Lots of ways have been tried so far, e.g. since the next Catalan number can be formed by adding the product of ones before, e.g. C(4) = C(3)*C(1) + C(2)*C(2) + C(1)*C(3), perhaps something similar happens for A000109, or by incorporating numbers from both sequences.  Lots of coincidences (probably) have been found including the 233 number in A000109 say X(10) is C(9-2) - the sum of the Catalan numbers before it.

Think I'm going to go crazy looking for patterns any longer!  Any suggestions please!

答:
Here is a partial answer.

In what follows the number of distinct Hamiltonian Maximal Planar Graphs with n vertices is $X(n)$. It should follow A000109 https://oeis.org/A000109/list up to $n=11$ when the first non Hamiltonian occurs.

Also used are the number of distinct ways to divide a polygon https://oeis.org/A000207 . $A(n)$ , offset by 2 from the list, will be a number from this list corresponding to the number of distinct ways to triangulate a polygon with $n$ sides There is a formula for these, not written here.

Since a Maximal Planar Hamiltonian graph can be represented by a regular polygon triangulated by 'inside' edges and also triangulated again with 'outside' edges, without repeating edges, the following is suggested.

For example the hexagon.  Let's start with the maximum number of added edges leaving a vertex, it's $3$, making a fan $F$. Let the hexagon be $ABCDEF$. If the $3$ inside (say) edges leave node $B$. The outside edges can't repeat any of these, one of the outside edges must also join $A$ to $C$, to ensure it's triangulated and not repeat edges. This leaves a pentagon to triangulate by the outside edges, but using one less edge (one was used for $AC$) - the number of distinct ways for that is $A(5)$

So we would expect $X(6)$ to be $A(5) + e(2)$ where the $e(2)$ is the number of graphs where the maximum number of edges leaving any node is 2. For the hexagon $e(2)$ is 1.
After $n=6$ the minimum maximum number of edges leaving any node is 3.

$X(7) =  A(6) + e(3)$

$X(8) =  A(7) + e(4) + e(3)$,

From $n=13$ onwards the minimum maximum number of edges leaving any node is 4

Here is a table of $A(n)$ and $X(n)$.
\begin{array}{c|cc}
n & A(n) & X(n)\\
\hline
3 & 1 & 1\\
4 & 1 & 1\\
5 & 1 & 1\\
6 & 3 & 2\\
7 & 4 & 5\\
8 & 12 & 14\\
9 & 27 & 50\\
10 & 82 & 233\\
11 & 228 & 1249\\
\end{array}

The pattern for the $e(i)$ isn't clear but some have been found using a computer program.
$$ X(6)=1+1 $$
$$ X(7)=3+2 $$
$$ X(8)=4+8+2 $$
$$ X(9)=12+23+14+1 $$
$$   X(10)=27+84+92+29+1 $$
$$   X(11)=82+281+508+333+44+0 $$

the $X(11)$ total is one short of the A000109 numbers so the program confirms that there is at most one non-Hamiltonian graph for n=11.  One graph is [was], missing for n=10 which the computer couldn’t find for Perhaps there's an undiscovered non-Hamiltonian graph with 10 nodes! [edit 14/02/2021, thanks to Will Orrick's suggestion of improving isomorphism testing, it's been found]

Now for the cases where one of the 'fan' is missing, e.g the $e(3)$ for the heptagon.  The inner edges are now 3 for the fan, from, say vertex $B$, and one somewhere else.  The outer edges cannot include the missing fan element (that would cause the maximum number leaving a vertex to be bigger than 3), so must include $AC$, leaving a shape with 6 sides to triangulate (with 3 more edges) which we would expect is again to do with $A(6)$, but this time with extra restrictions.  The remaining outer edges can't triangulate this remaining hexagon in a way that repeats the one inner edge that's inside it, or causes more than 3 edges from a vertex.

Even if many edges were missing from a fan of inner edges coming from vertex $B$, none of them can be used by the outer edges without causing too many edges to leave a vertex, so again $AC$ is needed as one of the outer edges.  If for example we were trying to find $e(16)$ for $X(30)$, then it would still seem to involve $A(29)$, but with many extras and restrictions.  Extras meaning we might have to reintroduce reflections and rotations (of distinct triangulations of the remaining 29 a-gon), restrictions due to keeping the maximum number of edges leaving a vertex to 16 (other cases would be covered by $e(17)$ etc...) and also avoiding the 11 inside edges which can be inside the 29 a-gon.

Alternative system:

Now also found are a set of $e(i)$, where the maximum must come from at least one set of triangulations, inner or outer (but not both combined). i.e. one that was previously $e(5)$ in the above, having a vertex of maximum degree 7, might count as $e(4)$ below, if its connections are 2 in the polygon, 4 inner connections and one outer connection.

For this system,

$$ X(6)=1+1 $$
$$ X(7)=3+2 $$
$$ X(8)=4+7+3 $$
$$ X(9)=12+22+15+1 $$
$$   X(10)=27+77+96+32+1 $$
$$   X(11)=82+261+498+361+46+0 $$

$X(6)$ and $X(7)$ are the same as before, $X(8)$ is the first different one. It is the graph with the lowest number of vertices that can't be drawn in polygon form, where the edges from a vertex of maximum degree can all be inside edges.  It has an interesting structure (below) with lots of symmetry.  The $X(11)$ numbers were from a run of 600,000 graphs, it's possible there could be some 'shuffling left' by one or two (for rows above n=10), but since the numbers didn't change during the second half of the run it's likely that they are exact.

The $X(8)$ first different one, can be drawn as a regular octagon (vertices 1-8) with these inside edges (1,3), (1,4), (1,5), (5,7), (5,8) and these outside edges, which are best dawn inside again with dotted lines to appreciate the symmetry (3,5), (3,6), (3,7), (7,1), (7,2).

On the computer program and the missing graph...

Despite repeated runs, one of the n=10 Hamiltonian graphs is missing.  The program finds 232 instead of 233.  Perhaps there is an undiscovered n=10 non-Hamiltonian graph!  To help others check this and in other ways, here are the details. [Edit: the list is complete now, thanks Will].

To check for isomorphism the program makes an ID set and used two 'tests' initially.  Test1 was the sum of the squares of the degrees of all nodes, typically about 250 for n=10.  If two graphs are different for Test1, they are not isomorphic.

The second test assigned a value test2(i) to each node, made up of summing, for each connecting node, j, (excluding itself) deg(j)*[11+deg(j)-deg(i)].  Where deg(j) is the degree of node j.  Test2 is the sum of all these values.  If two graphs are different for Test2, again,they are not isomorphic.  the 11 is random to increase the size and make it less likely that the same number can be got by summing a different set of numbers the -deg(i) is included for a similar reason.

So for two graphs to be isomporphic they should have identical Test1 and Test2.

This system didn't distinguish and find all 50 for n=9, it found 48.  So another test, Test3, was introduced.

The third test assigned a value test3(i) to each node, made up of summing, for each connecting node, j, (excluding itself) test2(j)*[test2(j)+2-deg(i)].  Test3 is the sum of all these values.

Now all 50 were found for n=9, but 232 out of 233 for n=10.  So Test4 was introduced, which is like Test3, test4(i) is by summing test3(j)*[test3(j)+2-deg(i)] and Test4 is the sum of these.  [Edit, after Will's 'edge ID' was added, all 233 have been found].


问:
this is regarding exponentials distribution
In an office building, the lift breaks down randomly at a mean rate of 3 times per week. The random variable X represents the time in days between successive lift breakdowns.

(i) Calculate the probability that the time interval between successive lift breakdowns is
between 2 and 3 days.

(ii) Find the probability that, after a breakdown has just occurred, at least 1 week will pass
without another breakdown occurring.

答:
The time $X$ between breakdowns, measured in days, has mean $\frac{7}{3}$, so we are dealing with an exponential with parameter $3/7$, and hence density function $\frac{3}{7}e^{-3x/7}$, for $x\ge 0$.
We want the probability that $2\le X\le 3$. This probability is
$$\int_{2}^{3} \frac{3}{7}e^{-3x/7}\,dx.$$
Now it is just a matter of integrating.

The second question is in a sense simpler. We want the probability that $X\ge 7$. This is

$$\int_{7}^{\infty} \frac{3}{7}e^{-3x/7}\,dx.$$

Remark:   In some courses, for people with little knowledge of calculus, people are just told that if $X$ has exponential distribution with parameter $\lambda$, then $\Pr(X\le x)=F_X(x)=1-e^{-\lambda x}$ (for $x\ge 0$).

In such a course, one would note that the probability that $X$ is between $a$ and $b$, where $0\le a\lt b$ is $F_X(b)-F_X(a)$. This is $(1-e^{-\lambda b})-(1-e^{-\lambda a})$, which simplifies to $e^{-\lambda a}-e^{-\lambda b}$.

Similarly, the probability that $X\gt a$ is $e^{-\lambda a}$.


问:
Strategy in a game of drawing cards from a deck
I saw this interview question that I'm trying to do and am clearly missing something. It goes as follows:

Deck of $26$ cards consisting of two suits (say $13\times$Hearts and
$13\times$Clubs). The aim is to get $5$ cards of a given suit. I am
allowed to play in either of these two ways:

draw $1$ card, choose my suit.

draw $2$ cards, choose my suit.

The game then proceeds by turning over successive cards till either me or the opponent get $5$ of a kind.

Which of these is better? What about if this were a full deck of 52 cards?

In situation 1, I will have 4 more to get vs my opponent needing 5 more. In situation 2, either we're even in needing 4 more (with probability $\frac{13}{25}$) or I'm ahead, needing only 3 more cards (with probability $\frac{12}{25}$).

I believe the probability of winning in both cases is the same, because I can expand the first strategy in the second: having chosen the suit, either the next is of the same suit (in which case I would select it in strategy 2), or they are different, which doesn't favour one over the other.

So I assume the question is asking about the expected number of draws. But then this is where I'm having trouble as it seems unnecessarily complicated, so I must be missing something. I considered conditioning on the first two cards ie '1st and 2nd cards are the same suit' (and I'm then looking for the expected number of steps till I reach $3$ of a kind, without my opponent reaching $5$ of a kind) and '1st and 2nd cards are the same suit' (and I'm then looking for the expected number of steps till I reach $4$ of a kind, without my opponent reaching $4$ of a kind).

But computing these by hand looks like a pain, with lots of binomials (I tried to count by picturing the deck as an ordered list, where I'm looking at the first $n$).

So I feel like I'm making a mess of something that shouldn't be difficult. Would love some help.

答:
It doesn't matter which approach you choose, assuming that if only one suit has been seen, you will name that suit.

Let $P_1$ be the probability that you win if two cards have been drawn and they are of different suits, and let $P_2$ be the probability that you win, if two cards have been drawn and they are both of your suit.

Without loss of generality, the first card turned up is a Club.  If you name Clubs, then with probability $\frac{12}{25}$ the next card will be a Club, and with probability $\frac{13}{25}$ it will be a Heart, so by the law of total probability, your probability of winning is $$.48P_2+.52P_1$$

Now suppose instead, you elect to see a second card.  With probability $.48$ it will be a Club, and you will name Clubs, giving you a probability of winning of $P_2$. With probability $.52$, it will be a Heart, and you will name one of the suits, and have probability $P_1$ of winning. By the law of total probability, your overall probability of winning is the same as before.

The simplest approach is simply to name the suit of the first card turned up.

As to the question about a full $52$-card deck, the probabilities are exactly the same, assuming that when you name a suit before any card of another suit has been turned up, your opponent's suit will be the first new suit drawn.  The cards in the other two suits (Diamonds and Spades in the original example,) have no effect on the outcome, so we may simply ignore them.

There's a substantial advantage to going first in this game.  I calculate the probability of a first player win at approximately $0.613272$.


问:
Any good upper bounds for $\sum_{i = 0}^{m} 2^i {k+i \choose i}$?
I am trying to solve a recursion (I faced it when I wanted to analyze the running time of an algorithm precisely). I reduced it to compute a "good" upper bound for $\sum_{i = 0}^{m}2^i {k + i \choose i}$. We have these assumptions that $1 < m \leq Ck$, for some $C\in \mathbb{N}$.
I have tried many approximations but the bounds are not what I want. They are very loose. On the other hand, it doesn't look like a very sophisticated summation but I have so much difficulty solving it!
Does anyone have any ideas?

答:
$$\sum_{i=0}^m2^i\binom{k+i}{i}=\sum_{i=0}^m2^i\binom{k+i}{k}\le \sum_{i=0}^m2^i\cdot \binom{k+m}{k}=\binom{k+m}{k}\cdot (2^{m+1}-1)$$
Since $\sum_{i=0}^m2^i\binom{k+i}{i}$ is at least as big as the last term, $2^m\binom{k+m}{k}$, this bound is at most a factor of $2$ away from correct value.


问:
Question about a tensor product of modules
Let $M=\mathbf{Z}/2$, $N=\mathbf{Z}/3$, the free-module $\mathbf{Z}^{M \times N}$ and his sub-module $H$ generated by elements of the following forms $(m_1+m_2,n)-(m_1,n)-(m_2,n), (m, n_1+n_2)-(m,n_1)-(m,n_2), (am,n)-a(m,n), (m,an)-a(m,n), m, m_1, m_2 \in M, n ,n_1, n_2 \in N, a \in \mathbf{Z}$.

And then consider the quotient-module $\mathbf{Z}^{M \times N}/H=\mathbf{Z}/2 \otimes_{\mathbf{Z}} \mathbf{Z}/3$.
Then a bilinear map $\tau$ from $N \times M$ to the quotient module vanishes on $(1,1) \in M \times N$ and I would like to know if we can find a generator of $H$ that verify the following equality
\begin{equation}
(1,1)=(3.1,1)=(1,3.1)+\text{a generator of} H.
\end{equation}
Many thanks for any suggestions.

答:
I'd prefer a different notation, namely $[x]_2$ and $[x]_3$ for the residue classes modulo $2$ and $3$.

First some general fact: if $M=Rx$ and $N=Ry$ are cyclic modules over the commutative ring $R$, then also $M\otimes_RN$ is cyclic, generated by $x\otimes y$.

Indeed, for a generic element of $M\otimes N$ has the form
$$
\sum_{i=1}^n r_ix\otimes s_iy=\Bigl(\,\sum_{i=1}^n r_is_i\Bigr)(x\otimes y)
$$
because you can move scalars past the tensor product. With more details
$$
\sum_{i=1}^n r_ix\otimes s_iy=
\sum_{i=1}^n r_is_ix\otimes y=
\Bigl(\,\sum_{i=1}^n r_is_ix\Bigr)\otimes y=
\Bigl(\,\sum_{i=1}^n r_is_i\Bigr)(x\otimes y)
$$
In your case $W$ is cyclic, generated by $[1]_2\otimes[1]_3$. On the other hand
$$
3[1]_2=[1]_2
$$
so you have
$$
[1]_2\otimes[1]_3=3[1]_2\otimes[1]_3=[1]_2\otimes 3[1]_3=[1]_2\otimes [0]_3
$$
so the generator is zero and consequently $W$ is the zero module.


问:
Maximum Likelihood Estimate of Laplacian distribution with one parameter $\sigma$
Given variant of laplacian distribution

$p(x|\sigma) = \frac{1}{2 \sigma} e^{\frac{|x|}{\sigma}}, \sigma > 0$ with parameter  $\sigma$

I got MLE for $\sigma$ as $\frac{\sum_{i=1}^n |x_i|}{n}$

calculating

$E[|x|] = \int_{-\infty}^{\infty} \frac{1}{2\sigma} |x| e^{\frac{-|x|}{\sigma}} dx \\ = \int_{0}^{\infty} \frac{1}{\sigma} |x| e^{\frac{-|x|}{\sigma}} dx = \sigma$

$E[|x|^2] = \int_{-\infty}^{\infty} \frac{1}{2\sigma} |x|^2 e^{\frac{-|x|}{\sigma}} dx \\ = \int_{0}^{\infty} \frac{1}{\sigma} |x|^2 e^{\frac{-|x|}{\sigma}} dx = 2\sigma^2$

$\text {var} (|x_i|) = E[|x_i|^2] - (E[|x|])^2 = 2\sigma^2 - \sigma^2 = \sigma^2$

Variance($\hat \sigma$) = variance ($ \frac{\sum_{i=1}^n |x_i|}{n}$) =\frac{1}{n} $Var(|x_i|) =\frac{1}{n} \sigma^2$

Bias($\hat \sigma$) = $E[\hat \sigma] - \sigma = E[\frac{\sum_{i=1}^n |x_i|}{n}] - \sigma = (1/n)n \sigma = \sigma $

Now MSE($\hat \sigma$) = $Bias^2 + \text {variance} = \frac{1}{n} \sigma^2 $

May i know is this correct?

答:
The bias is not correct.  Notice that unless every $X_i = 0$, the sum $$\hat \sigma = \frac{1}{n} \sum_{i=1}^n |X_i| > 0.$$  So the calculation of the expectation is not $0$, because the estimator $\hat \sigma$ is almost surely strictly positive.

In order to compute the bias, you must compute the expectation of the absolute value of a single observation; i.e., $$\operatorname{E}[|X|] = \int_{x=-\infty}^\infty \frac{|x|}{2\sigma} e^{-|x|/\sigma} \, dx = \int_{x=0}^\infty \frac{x}{\sigma} e^{-x/\sigma} \, dx.$$  Then use the linearity of expectation to compute $\operatorname{E}[\hat \sigma]$.

To compute the variance, also begin from a single observation:  $$\operatorname{E}[|X|^2] = \int_{x=-\infty}^\infty \frac{|x|^2}{2\sigma} e^{-|x|/\sigma} \, dx.$$  Then $$\operatorname{Var}[|X|] = \operatorname{E}[|X|^2] - \operatorname{E}[|X|]^2,$$ and then, by independence of the individual observations, $$\operatorname{Var}[\hat \sigma] = \frac{1}{n^2} \sum_{i=1}^n \operatorname{Var}[|X_i|].$$


问:
How would I go about proving discontinuity at multiple points for this function?
f : [0,1] -> Reals, $f(x) = x,$ $x\ne 0,$ and $1/x \in \mathbb N.$ Otherwise $f(x) = 0.$

I want to prove that this function is discontinuous at the points 1/n for all Natural Ns.

Initially I thought to do a proof by contradiction by the sequential definition of continuity but I don't think its possible to find infinite sequences that tend to 1/n for each natural n.

In this case do I negate the epsilon-delta definition. But I don't know how to do this exactly as I don't know what to pick for my epsilon and for my x value?

Any advice?

答:
In order to prove that $f$ isn't continuous at 1 for example, it suffices to show that there exists one sequence of real numbers $x_n \in [0,1]$ with $x_n \to 1$, such that

$$lim_{n\to \infty} f(x_n) \neq f(1)=1$$
Consider for example the sequence $x_n := 1-\frac{1}{n}\in [0,1]$. Note that
$$\frac{1}{x_n} = \frac{1}{1-\frac{1}{n}} = \frac{1}{\frac{n-1}{n}} = \frac{n}{n-1} = 1 +\frac{1}{n-1}$$
isn't a natural number for every $n\geq 3$. In a similar way, you can show that $f$ isn't continuous at $\frac{1}{n}, n\in \mathbb{N}$.


问:
Right angled triangles
Are right angled triangles the only triangles that can be divided into 2,4,8,16- - (2^n)smaller triangles, each being the same shape as the original? In other words is it the only one where infinite descent occurs?</p>

答:
Suppose we have a triangle $T$ specified by a triple of angles $(\alpha, \beta, \gamma)$. Now, clearly the only way to divide $T$ into two triangles is by cutting through one of the vertices of $T$ associated with one of the three angles.
So consider cutting $\alpha$ into 2 smaller angles $\alpha_1$ and $\alpha_2$ such that $\alpha_1 + \alpha_2 = \alpha$, yielding the triangles specified by the angle triples $(\alpha_1, \beta, \pi - \beta - \alpha_1)$ and $(\alpha_2, \gamma, \pi - \gamma - \alpha_2)$.
If those two triangles are to be similar to the original one, we must have $\alpha_1 = \gamma$ and $\alpha_2 = \beta$ and thus $\alpha = \beta + \gamma$ which yields $\alpha = \pi/2$.
This implies that $T$ is right-angled.

A note on dividing into 4 triangles: This can be done with any triangle as pointed out by Crostul's comment.
Indeed by subdividing the triangles gotten by this process we can divide any triangle into $4^n$ subtriangles similar to the original one (for any $n \in \mathbb N$).

Title: Right angled triangles


问:
The value of a limit of a power series: $\lim\limits_{x\rightarrow +\infty} \sum_{k=1}^\infty (-1)^k \left(\frac{x}{k} \right)^k$
What is the answer to the following limit of a power series?

$$\lim_{x\rightarrow +\infty} \sum_{k=1}^\infty (-1)^k \left(\frac{x}{k} \right)^k$$

答:
A simple calculation shows that

\begin{align*}
\sum_{k=1}^{\infty} (-1)^{k} \left( \frac{x}{k} \right)^{k}
&= \sum_{k=1}^{\infty} \frac{(-1)^{k} x^{k}}{(k-1)!} \int_{0}^{\infty} t^{k-1} e^{-kt} \, dt
= \int_{0}^{\infty} \sum_{k=1}^{\infty} \frac{(-1)^{k} x^{k} t^{k-1} e^{-kt}}{(k-1)!} \, dt \\
&= -x \int_{0}^{\infty} \exp \left\{ - t \left( 1 + x e^{-t} \right) \right\} \, dt
= - \int_{0}^{1} x \cdot u^{x u} \, du,
\end{align*}

where $u = e^{-t}$. Now we claim that

$$ \lim_{x\to\infty} \int_{0}^{1} x \cdot u^{x u} \, du = 1. $$

To find the limit, we prove the following lemma:

Lemma. Let $f : [0, \delta] \to [0, 1]$ be a measurable function. Suppose there exists $0 < A  0$, there exists small $\delta > 0$ such that
$$ 1 - (1+\epsilon)(1-u) \leq f(u) \leq 1 - (1-\epsilon)(1-u) $$
for $0 < u < \delta$.

For any large $M > 0$, we can choose small $\delta > 0$ such that
$$f'(u) = u^{u}(1 + \log u) \leq -M$$
for $0 < x < \delta$. In particular, $f(u) \leq 1 - Mu$.

Let $\epsilon > 0$ be small and $M > 0$ be large. Let $\delta > 0$ be a sufficiently small number satisfying the conditions simultaneously. Then we have

$$ 0 \leq x \int_{\delta}^{1-\delta} u^{xu} \, du \leq x \max\{ f(\delta)^{x}, f(1-\delta)^{x} \} \xrightarrow{x\to\infty} 0. $$

Also, Lemma shows that

$$ \frac{1}{1+\epsilon} \leq \liminf_{x\to\infty} \left( x \int_{1-\delta}^{1} u^{xu} \, du \right) \leq \limsup_{x\to\infty} \left( x \int_{1-\delta}^{1} u^{xu} \, du \right) \leq \frac{1}{1-\epsilon} $$

and

$$ 0 \leq \limsup_{x\to\infty} \left( x \int_{0}^{\delta} u^{xu} \, du \right) \leq \frac{1}{M}. $$

Putting together, we have

$$ \frac{1}{1+\epsilon} \leq \liminf_{x\to\infty} \left( x \int_{0}^{1} u^{xu} \, du \right) \leq \limsup_{x\to\infty} \left( x \int_{0}^{1} u^{xu} \, du \right) \leq \frac{1}{1-\epsilon} + \frac{1}{M}. $$

Therefore, letting $M \to \infty$ and $\epsilon \to 0^{+}$, we obtain

$$ \lim_{x\to\infty} \left( x \int_{0}^{1} u^{xu} \, du \right) = 1 $$

as desired.

Proof of Lemma. For any $0 < \eta < \delta$, we have
  $$ 0 \leq x \int_{\eta}^{\delta} f(t)^{x} \, dt \leq x \int_{\eta}^{\delta} \max \{ 1- B\eta, 0 \}^{x} \, dt \leq \max \{ x \delta (1- B\eta)^{x}, 0 \} \xrightarrow[]{x\to\infty} 0. $$
  Thus we may assume that $\delta$ is sufficiently small so that $1 - A\delta \geq 0$. Then
  \begin{align*}
x \int_{0}^{1/A} (1 - At)^{x} \, dt + o(1)
&= x \int_{0}^{\delta} (1 - At)^{x} \, dt \\
&\leq x \int_{0}^{\delta} f(t)^{x} \, dt \\
&\leq x \int_{0}^{\delta} (1 - Bt)^{x} \, dt = \leq x \int_{0}^{1/B} (1 - Bt)^{x} \, dt + o(1).
\end{align*}
  Evaluating, we obtain
  $$ \frac{x}{A(x+1)} + o(1) \leq x \int_{0}^{\delta} f(t)^{x} \, dt \leq \frac{x}{B(x+1)} + o(1), $$
  proving the lemma.

Body:
A simple calculation shows that

\begin{align*}
\sum_{k=1}^{\infty} (-1)^{k} \left( \frac{x}{k} \right)^{k}
&= \sum_{k=1}^{\infty} \frac{(-1)^{k} x^{k}}{(k-1)!} \int_{0}^{\infty} t^{k-1} e^{-kt} \, dt
= \int_{0}^{\infty} \sum_{k=1}^{\infty} \frac{(-1)^{k} x^{k} t^{k-1} e^{-kt}}{(k-1)!} \, dt \\
&= -x \int_{0}^{\infty} \exp \left\{ - t \left( 1 + x e^{-t} \right) \right\} \, dt
= - \int_{0}^{1} x \cdot u^{x u} \, du,
\end{align*}

where $u = e^{-t}$. Now we claim that

$$ \lim_{x\to\infty} \int_{0}^{1} x \cdot u^{x u} \, du = 1. $$

To find the limit, we prove the following lemma:

Lemma. Let $f : [0, \delta] \to [0, 1]$ be a measurable function. Suppose there exists $0 < A < B$ such that
  $$ 1 - Ax \leq f(x) \leq 1 - Bx. $$
  Then we have
  $$ \frac{1}{A} \leq \liminf_{x\to\infty} \left( x \int_{0}^{\delta} f(t)^{x} \, dt \right) \leq \limsup_{x\to\infty} \left( x \int_{0}^{\delta} f(t)^{x} \, dt \right) \leq \frac{1}{B}. $$

Assume this lemma holds. Let $f(u) = u^{u}$. Then we observe that

$f(u)$ decreases for $[0, 1/e]$ and increases for $[1/e, 1]$.

For any small $\epsilon > 0$, there exists small $\delta > 0$ such that
$$ 1 - (1+\epsilon)(1-u) \leq f(u) \leq 1 - (1-\epsilon)(1-u) $$
for $0 < u < \delta$.

For any large $M > 0$, we can choose small $\delta > 0$ such that
$$f'(u) = u^{u}(1 + \log u) \leq -M$$
for $0 < x < \delta$. In particular, $f(u) \leq 1 - Mu$.

Let $\epsilon > 0$ be small and $M > 0$ be large. Let $\delta > 0$ be a sufficiently small number satisfying the conditions simultaneously. Then we have

$$ 0 \leq x \int_{\delta}^{1-\delta} u^{xu} \, du \leq x \max\{ f(\delta)^{x}, f(1-\delta)^{x} \} \xrightarrow{x\to\infty} 0. $$

Also, Lemma shows that

$$ \frac{1}{1+\epsilon} \leq \liminf_{x\to\infty} \left( x \int_{1-\delta}^{1} u^{xu} \, du \right) \leq \limsup_{x\to\infty} \left( x \int_{1-\delta}^{1} u^{xu} \, du \right) \leq \frac{1}{1-\epsilon} $$

and

$$ 0 \leq \limsup_{x\to\infty} \left( x \int_{0}^{\delta} u^{xu} \, du \right) \leq \frac{1}{M}. $$

Putting together, we have

$$ \frac{1}{1+\epsilon} \leq \liminf_{x\to\infty} \left( x \int_{0}^{1} u^{xu} \, du \right) \leq \limsup_{x\to\infty} \left( x \int_{0}^{1} u^{xu} \, du \right) \leq \frac{1}{1-\epsilon} + \frac{1}{M}. $$

Therefore, letting $M \to \infty$ and $\epsilon \to 0^{+}$, we obtain

$$ \lim_{x\to\infty} \left( x \int_{0}^{1} u^{xu} \, du \right) = 1 $$

as desired.

Proof of Lemma. For any $0 < \eta < \delta$, we have
  $$ 0 \leq x \int_{\eta}^{\delta} f(t)^{x} \, dt \leq x \int_{\eta}^{\delta} \max \{ 1- B\eta, 0 \}^{x} \, dt \leq \max \{ x \delta (1- B\eta)^{x}, 0 \} \xrightarrow[]{x\to\infty} 0. $$
  Thus we may assume that $\delta$ is sufficiently small so that $1 - A\delta \geq 0$. Then
  \begin{align*}
x \int_{0}^{1/A} (1 - At)^{x} \, dt + o(1)
&= x \int_{0}^{\delta} (1 - At)^{x} \, dt \\
&\leq x \int_{0}^{\delta} f(t)^{x} \, dt \\
&\leq x \int_{0}^{\delta} (1 - Bt)^{x} \, dt = \leq x \int_{0}^{1/B} (1 - Bt)^{x} \, dt + o(1).
\end{align*}
  Evaluating, we obtain
  $$ \frac{x}{A(x+1)} + o(1) \leq x \int_{0}^{\delta} f(t)^{x} \, dt \leq \frac{x}{B(x+1)} + o(1), $$
  proving the lemma.


问:
Show that $\int_1^\infty x^n\sin(x+x^2)dx$ diverges, $n\ge1$.
How do I show that this improper integral diverges? I know certainly it is not always true that if $\int_a^\infty f(x)dx$ converges, then $f(x)\to 0$. My intuition tells me this improper integral diverges because $x^n*\sin(x+x^2)$ oscillates between infinity and -infinity as $x\to \infty$. I am wondering if there is a nice way to prove it is divergent.

答:
We go to prove that the improper integral does not exist for each $n$.
Prove by contradiction. Suppose the contrary that $l=\lim_{t\rightarrow\infty}\int_{0}^{t}f(x)dx\in\mathbb{R}$
exists for some $n\geq1$, where $f(x)=x^{n}\sin(x+x^{2}).$ Define
$F(t)=\int_{0}^{t}f(x)dx$. For $\varepsilon=1/4000$, there exists
$t_{0}>10$ such that $|F(t)-l|<\varepsilon$ whenever $t\geq t_{0}$.

Choose a sufficiently large $k\in\mathbb{N}$ such that there exists
$x_{2}>t_{0}+100$ satisfying that $x_{2}+x_{2}^{2}=2k\pi+\frac{\pi}{2}.$
Let $x_1 \in(0,x_2)$ be such that $x_1 + x_1^2 = 2k\pi+\frac{\pi}{4}$. Such $x_1$ exists and is unique. For, let $g(x) = x + x^2$. Observe that $g(0) < 2k\pi+\frac{\pi}{4}$ and $g(x_2) > 2k\pi+\frac{\pi}{4}$. By intermediate-value theorem, such $x_1$ exists. Since g is strictly increasing on $[0,\infty)$, such $x_1$ is unqiue. We have that
$\frac{\pi}{4}=(x_{2}+x_{2}^{2})-(x_{1}+x_{1}^{2})=(x_{2}-x_{1})(1+x_{1}+x_{2})$
and hence $x_{2}-x_{1}=\frac{\pi}{4(1+x_{1}+x_{2})}<1$. This shows
that $x_{1}>x_{2}-1>t_{0}$. Moreover, $1-\frac{x_{1}}{x_{2}}=\frac{\pi}{4(1+x_{1}+x_{2})x_{2}}$
and hence $\frac{x_{1}}{x_{2}}=1-\frac{\pi}{4(1+x_{1}+x_{2})x_{2}}>\frac{1}{2}$.

Observe that $\sin(x+x^{2})$ increases from $\frac{1}{\sqrt{2}}$
to $1$ when $x$ increases from $x_{1}$ to $x_{2}$, so $f(x)\geq x_{1}^{n}\cdot\frac{1}{\sqrt{2}}$
for all $x\in[x_{1},x_{2}]$. Now
\begin{eqnarray*}
F(x_{2})-F(x_{1}) & = & \int_{x_{1}}^{x_{2}}f(x)dx\\
 & \geq & \frac{1}{\sqrt{2}}x_{1}^{n}(x_{2}-x_{1})\\
 & = & \frac{\pi}{4\sqrt{2}}\frac{x_{1}^{n}}{1+x_{1}+x_{2}}\\
 & \geq & \frac{\pi}{4\sqrt{2}}\cdot\frac{x_{1}}{x_{2}+x_{2}+x_{2}}.\\
 & > & \frac{\pi}{4\sqrt{2}}\cdot\frac{1}{6}\\
 & > & \frac{1}{1000}\\
 & = & 4\varepsilon.
\end{eqnarray*}
On the other hand, since $x_1,x_2 \in[t_0,\infty)$, we have
\begin{eqnarray*}
 &  & \left|F(x_{2})-F(x_{1})\right|\\
 & \leq & \left|F(x_{2})-l\right|+\left|F(x_{1})-l\right|\\
 & < & 2\varepsilon
\end{eqnarray*}
which is a contradiction.


答:
I'm pretty sure there is no closed form for this sum and it is far from simple.  This sum looks like one involved in finding the expected value of the length of the longest run of successes of a bernoulli random variable.  See for instance this question, unfortunately the it's pretty opaque and it's been a while since I was trying to do that sum.

Here's a way of converting the problem to a derivative problem, although I don't know how useful it will be.  Recall $\binom{k+i}{i}=\binom{k+i}{k}=[x^k y^i](x+y)^{k+i}$, where $[m](p)$ denotes the coefficient on the term $m$ in the polynomial/series $p$.  So now we want to find
$$\sum_{i=0}^m 2^i[x^k y^i](x+y)^{k+i}.$$
Notice if we take the $k$th derivative of $(x+y)^{k+i}$ with respect to $x$ at $x=0$ and $y=1$, we get the coefficient we want times $k!$.  Thus we can write the sum as
$$\sum_{i=0}^m\frac{2^i}{k!}\frac{d^k}{dx^k}(x+1)^{k+i}|_{x=0}$$
Now a lot of this stuff can be pulled out of the sum, giving us
$$\frac{1}{k!}\frac{d^k}{dx^k}\left((x+1)^k\sum_{i=0}^m 2^i(x+1)^i\right)|_{x=0}$$
The inside is now a geometric series so we can find its sum
$$\frac{1}{k!}\frac{d^k}{dx^k}\left((x+1)^k\frac{(2(x+1))^{m+1}-1}{2(x+1)-1}\right)|_{x=0}$$
$$\frac{1}{k!}\frac{d^k}{dx^k}\left(\frac{2^{m+1}(x+1)^{m+k+1}-(x+1)^k}{2x-1}\right)|_{x=0}$$
It may be possible to find an explicit form for this derivative or at least a recurrence relation, although I couldn't.

However, if $k$ is fixed you can find a closed form: the binomial coefficient $\binom{k+i}{k}$ is a degree $k$ polynomial, and $\sum_n b^n P(n)$ can be computed for any base $b$ and polynomial $P$ using a trick.  Take $\frac{d^k}{db^k}\sum_n b^n$ for $k$ ranging from 1 to the degree of $P$.  The derivatives of the summands form a basis for polynomials of degree $k$, and the derivatives of the corresponding sums let us calculate the sum for $b^n$ times any polynomial.

As far as an upper bound, a VERY rough one can be gotten from the approximation $\binom{mn}{n}\approx\frac{m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}\sqrt{n}}$.  Because $i\le m\le Ck$, we can rewrite the sum as $$\sum_{i=0}^m\frac{2^i(C+1)^{Ck-C+k}}{C^{Ck-C}\sqrt{k}}=\frac{(2^{m+1}-1)(C+1)^{Ck-C+k}}{C^{Ck-C}\sqrt{k}}.$$
Notice this is equivalent to using the upper bound from the other answer and then applying the approximation I mentioned, so this will also be over by a factor of about 2.  Depending on what you need (ie if you just want big O), a factor of 2 may not matter to you.

Title: Any good upper bounds for $\sum_{i = 0}^{m} 2^i {k+i \choose i}$?

Body:
I am trying to solve a recursion (I faced it when I wanted to analyze the running time of an algorithm precisely). I reduced it to compute a "good" upper bound for $\sum_{i = 0}^{m}2^i {k + i \choose i}$. We have these assumptions that $1 < m \leq Ck$, for some $C\in \mathbb{N}$.
I have tried many approximations but the bounds are not what I want. They are very loose. On the other hand, it doesn't look like a very sophisticated summation but I have so much difficulty solving it!
Does anyone have any ideas?