问:
Optimal strategy for game: two players on a 1d board, determine fraction of troop deployment
There is a 1 dimension board with 7 tiles. You and the enemy are on tile 4.

You win if you reach tile 7 and you lose if the enemy reaches tile 1.

In a single turn you determine the fraction of your own army to deploy. Same with your enemy. Whoever deploys more troops wins, advances 1 square, and loses all troops that were deployed. The losing army retreats a square and loses no troops. If both of you deploy the same number of soldiers, you lose. What percentage of troops should you deploy on the first turn?

I have no idea on how to approach this type of question as I've never seen anything like it.

答:
I tried to solve the problem using Dynamic Programming. However, the formulation is a bit ambiguous (maybe this is what user26 was talking about in the comments when he asked about poker theory). The ambiguity arises from the fact that we don't know which strategy the opponent will use. So I tried to play against different strategies.

Mathematical formulation

I tried to write the rules in a mathematical way. Each situation of the game is identified from three parameters:

-$x$ is the tile where both the players are in (an integer from 1 to 7);

-$\bar{u}$ is the amount of army that player A still has (a real in $[0,1]$);

-$\bar{v}$ is the amount of army that player B still has (a real in $[0,1]$).

The initial situation is $(4,1,1)$.

The "dynamics" of the game can be formulated as follows. Starting from a situation $(x,\bar{u},\bar{v})$, the players choose two moves $u$ and $v$ respectively. Then:

-if $u≥ v$, player A advances, so the next state will be $(x-1,\bar{u}-u,\bar{v}-v)$;

-if $u<v$, player B advances, so the next state will be $(x+1,\bar{u}-u,\bar{v}-v)$.

The game ends at the first turn $t \in \mathbb{N}$ such that either $x=1$ or $x=7$.

1° case: Player A moves after Player B and optimally

A characteristic of this game which makes it harder to me is that the moves are taken simultaneously. In fact, in other even more complex games like chess, players move one at a time.

I tried to re-formulate the game in this way, so that player A (which is pushing towards 1) plays always after player B (which is pushing towards 7). This allows a differential game formulation of the problem and allows the use of dynamic programming with two players, where each of them tries to maximize his own chance of victory.

In this case, one can define the value function, which player B wants to maximize. The value function quantifies how good is a certain situation $(x,\bar{u},\bar{v})$ for player B. Starting from a situation $(x,\bar{u},\bar{v})$, we define the best or optimal move the one which maximizes the worst possible case.

From dynamic programming, the value function solves this set equations (it should be a particular case of the so-called Hamilton-Jacobi-Isaacs equation of differential games):

$$ \left\{ \begin{aligned}
V(x,\bar{u},\bar{v}) &= \max_{v \in [0,\bar{v}]} \min_{u \in [0,\bar{u}]} F_{x,\bar{u},\bar{v}}(u,v) \qquad && x = 2, \dots, 6, \ \bar{u} \in [0,1], \ \bar{v} \in [0,1] \\
V(1,\bar{u},\bar{v}) &= -1 \qquad && \bar{u} \in [0,1], \ \bar{v} \in [0,1] \\
V(7,\bar{u},\bar{v}) &= +1 \qquad && \bar{u} \in [0,1], \ \bar{v} \in [0,1]
\end{aligned} \right.
$$

where
$$ F_{x,\bar{u},\bar{v}}(u,v) =
\begin{cases}
V(x+1,\bar{u}-u,\bar{v}-v), \qquad \textrm{if $u<v$} \\
V(x-1,\bar{u}-u,\bar{v}-v), \qquad \textrm{if $u≥v$} .
\end{cases} $$

I will try to explain why this formula makes sense:

I am assuming that player A moves after player B, so for each move $v \in [0,\bar{v}]$ that player B can make, we consider all possible moves $u \in [0,\bar{u}]$ that player A will be able to do and choose the best move from the point of view of player A. Then, among all possible moves $v$, we pick the one which maximizes the worst case possible. The argument $F$ of the max-min operator is the value function computed on the next state of the system. The "boundary conditions" on $V(1,\bar{u},\bar{v})$ and $V(7,\bar{u},\bar{v})$ are natural and explicit the fact that player B wins a positive price when the game ends in 7 and a negative price when the game ends in 1.

The formula above is implicit, since the RHS depends on the value function $V$ itself. However, usually these kinds of equations are contraction operators (I didn't check that this is actually a contraction) and admits a unique fixed point by the Banach-Caccioppoli theorem.

At this time, I discretized the moves space $[0,1]$ (for instance, using 11 nodes you get $U = \{0,0.1,\dots,0.9,1\}$ but you can use even 101 or 1001 nodes) and I solved the fixed point equation in Matlab. In order to solve it, I used a classical fixed point method.

The result is that if both players start with an army of 1, player A will always win, since we are assuming that he moves in second position. However, when the army of player A starts smaller than the one of player B (for instance 0.5 vs 1), there exists a winning strategy for player B (and he will always win using that strategy, because he is trained against the worst scenario!).

2° case: Player A moves randomly (but simultaneously)

If we assume that player A picks a random move at each turn, we can see the game as a 1-player optimal control problem, where player B tries to maximize the average price, averaging over the possible moves of player A.

The dynamic programming equation will become
$$ \left\{ \begin{aligned}
V(x,\bar{u},\bar{v}) &= \max_{v \in [0,\bar{v}]} \frac{1}{\bar{u}} \int_0^\bar{u} F_{x,\bar{u},\bar{v}}(u,v)du \qquad && x = 2, \dots, 6, \ \bar{u} \in [0,1], \ \bar{v} \in [0,1] \\
V(1,\bar{u},\bar{v}) &= -1 \qquad && \bar{u} \in [0,1], \ \bar{v} \in [0,1] \\
V(7,\bar{u},\bar{v}) &= +1 \qquad && \bar{u} \in [0,1], \ \bar{v} \in [0,1]
\end{aligned} \right.
$$

Notice that if we discretize the moves space, the integral becomes a finite sum and the functional to minimize becomes an arithmetic average.

I simulated this problem as well and obtained more interesting results. The value function in $(4,1,1)$ equals 0.95. This means that starting from $(4,1,1)$ and following the optimal strategy for the whole game, player B manages to win 95% of the games, assuming that player A moves randomly. The best first move for B is given again by the dynamic programming, minimizing that average. In this case player B should start using 0.17 of the army.

3° case: Player A and B play optimally and simultaneously

This seems the correct way to interpret the text, or at least this is what I understand from the text. However, if A and B start both with an army of 1 and play the same optimal strategy, the game will certainly end with A winning. In fact, one of the rule is that in case that the two players use the same amount of soldiers, player A advances.

It may be that this little imbalance will produce also different optimal strategies, but player A will win anyway (if they both play optimally).

Finally, if we allowed player B to start with a larger army, the problem would become more interesting and less trivial. But honestly I didn't think about this variant.


问:
The basis of the combination of two subspaces
I am currently reading through Halmos' Finite dimensional vector spaces. On page 18 a theorem (corollory) is stated based on a previous theorem. This previous theorem states that "*If $S$ is any set of vectors in a vector space $V$ and if $M$ is the subspace spanned by $S$, then $M$ is equivalent to the set of all linear combinations of the elements in $S$.

This makes sense to me, but the corollory is the following: "If $K$ and $X$ are any two subspaces, and $M$ is the subspace spanned by $K$ and $X$ together (I had to assume the author here means the union of $X$ and $K$), then $M$ is equivalent to the set of all vectors of the form $x + k$, where $x\in{X}$ and $k\in{K}$.

But then, surely, the corollory is identical to the theorem if the union of $X$ and $K$ is equal to $S$, then $M$ is spanned by $X\cup{K}$, and by the theorem, $M$ is equivalent to the linear combination of all the vectors in $S$. Then, rather than just $x + k$, should it not be $a\cdot x + b\cdot k$?

Is it the linear combination of $x$ and $k$ or just the elements of $x$ and $k$?

答:
Here the notation $x+k$ means that the generic element of the spanned subspace $M$ can be written as a generic sum of an element of $X$ plus one of $K$. Indeed $M$ is generated, as you say, by the union $X\cup K$, thus it's pretty clear the result holds.

The theorem is basically telling you $M$ is the smallest subspace of $V$ which contains both $X$ and $K$, so it's nothing unexpected its elements are written as $x+k$. Just observe that $M$ needs to contain $X$ and $K$, thus since $M$ is a subspace it must contain sums of elements of $X$ and $K$.

ContentLicense: CC BY-SA 4.0


答: Since $X $ and  $K $ are subspaces, the set of all $x+k $ is the same as the set of all  $ax+bk $ (by closure under scalar multiplication).

Title: The basis of the combination of two subspaces

Body:
I am currently reading through Halmos' Finite dimensional vector spaces. On page 18 a theorem (corollory) is stated based on a previous theorem. This previous theorem states that "*If $S$ is any set of vectors in a vector space $V$ and if $M$ is the subspace spanned by $S$, then $M$ is equivalent to the set of all linear combinations of the elements in $S$.

This makes sense to me, but the corollory is the following: "If $K$ and $X$ are any two subspaces, and $M$ is the subspace spanned by $K$ and $X$ together (I had to assume the author here means the union of $X$ and $K$), then $M$ is equivalent to the set of all vectors of the form $x + k$, where $x\in{X}$ and $k\in{K}$.

But then, surely, the corollory is identical to the theorem if the union of $X$ and $K$ is equal to $S$, then $M$ is spanned by $X\cup{K}$, and by the theorem, $M$ is equivalent to the linear combination of all the vectors in $S$. Then, rather than just $x + k$, should it not be $a\cdot x + b\cdot k$?

Is it the linear combination of $x$ and $k$ or just the elements of $x$ and $k$?


问:
Property of Determinant
If any two rows or columns of a determinant are interchanged, the sign of the value of the determinant is changed.

What is the intuition of this? I can see from algebra perspective thats right, but I want a geometrical visualization. I tried to think in terms of linear transformation but I was not able to visualize that transformation.

答:
Geometrically, the determinant gives you the signed volume of the image of the unit cube under the linear transformation described by the matrix.

Let $R_{ij}$ denote an identity matrix with its $i$th and $j$th rows are switched. Note that for a compatible column vector, $R_{ij}x$ switches the $i$th and $j$th entry of $R$. Correspondingly, going from $A$ to $R_{ij}A$ switches the $i$th and $j$th entry of each column of $A$, which is to say that it switches the $i$th and $j$th rows of $A$. The determinant we are interested in is the determinant of the product $R_{ij}A$.

Recall that $R_{ij}A$ is a matrix corresponding to the application of two successive transformations; the first transformation is described by $A$, the second is described by $R_{ij}$. Geometrically, $R_{ij}$ is a refection across the hyperplane $x_i = x_j$. For example, in two dimensions, switching the $x$ and $y$ coordinates reflects across the line $y = x$.

A reflection will not change the absolute volume of any shape, but it will change the sign of any volume: the image of a positive volume under $R_{ij}$ is negative, and the image of a negative volume under $R_{ij}$ is positive. Now, the determinant of $A$ is the signed area of the unit cube under the first transformation. Applying a reflection to this volume will maintain its absolute value but change its sign, which means that the determinant of $R_{ij}A$ indeed has the same absolute value as the determinant of $A$ but has the opposite sign.

Title: Property of Determinant


问:
Two gamblers in a casino, with different conditions for stopping, which one has greater expected loss?
The following question was given in the exercises in the martingale chapter of a textbook by Koralev-Sinai. I'm having trouble formalizing this problem in terms of martingale theory

Ann and Bob are gambling at a casino. In each game the probability of winning a dollar is 48%, and the probability of losing a dollar is 52%. Ann decided to play 20 games, but will stop after 2 games if she wins them both. Bob decided to play 20 games, but will stop after 10 games if he wins at least 9 out of the first 10. What is larger: the amount of money Ann is expected to lose, or the amount of money Bob is expected to lose?

My idea is to appeal to the optional stopping theorem, by defining a stopping time $\tau_{A}$ for Ann and a stopping time $\tau_{B}$ for Bob. But I'm not quite sure how to define these times. Any help or hints along these lines should be helpful.

Just thinking, if $X_{j}$ is the random variable representing the amount gained/lost at the $j$th game, that is taking $1$ with probability $.48$ and $-1$ with probability $.52$, then $$ \tau_{A} = \inf\{n : X_{n} = X_{n+1} =1 \}$$
and I think $\tau_{B} = 10$ if $\sum^{10}_{k=1}X_{k}  \geq 9$? We can then account for them stopping at 20 games by taking the minimum with respect to a constant stopping of $T=20$.

答: The expected loss is directly proportional to the expected number of games played. Therefore, the person who plays, on average, fewer games is expected to lose less. Thus, it is clear that Ana is expected to lose less.</p>


问:
Which one of $n!$ or $e^{n^2}$ grows faster?
I would expect $n!$ to grow faster because factorial growth is generally faster than exponential growth, but wolfram alpha says that $\lim _{x\to \infty }\left(\frac{x!}{e^{x^2}}\right)=0$, so I would appreciate if anyone can explain why this occurs.

答: Famously $\ln n!\sim n\ln n\in o(n^2)$, so $n!\in o(\exp n^2)$. Indeed,$$\ln n!=\sum_{k=1}^n\ln k\sim\int_1^n\ln kdk=n\ln n-n\sim n\ln n.$$


问:
What is an example analytic expression for a function whose plot qualitatively looks as follows?
What is an example analytic expression for a function whose plot qualitatively looks as follows?

Here, I mean that the function asymptotes to $y=0$ for $x\to -\infty$ and $x\to +\infty$.

答:
The function is odd.
it has two extremas.
it has two inflection points.
It could be defined by

$$f(x)=\frac{x}{1+x^2}$$


答:
While $e^{x^2}$ uses an exponential, it's a function that grows (much) faster than exponentially. In fact, you can show your limit without needing to know any details of the asymptotics of the factorial; it's almost trivially the case that $n!\lt n^n$. But by taking logs, we see that $n!\lt
n^n = e^{n\ln n} \lt e^{n^2}$.

Title: Which one of $n!$ or $e^{n^2}$ grows faster?

Body: I would expect $n!$ to grow faster because factorial growth is generally faster than exponential growth, but wolfram alpha says that $\lim _{x\to \infty }\left(\frac{x!}{e^{x^2}}\right)=0$, so I would appreciate if anyone can explain why this occurs.


问:
How to verify that a function is a pmf of a discrete random variable?
I am preparing for a prob/stats exam and have encountered this practice question:

I am confused about what it means to "verify that $p(x)$ is a pmf of a discrete random variable" for a few reasons:

A pmf, by definition, is a function that gives the probability of a discrete random variable...

It literally shows that the values x can take are discrete.

Do I need to use probability axioms or something? Is there some notational description of a pmf I need to compare this to?

答:
Since this is a discrete random variable you have to verify that $\sum_{x=0}^{\infty} p(x) =1$.
In doing so remember the geometric series $\sum_{x=0}^{\infty} (\frac{1}{4})^x=\frac{4}{3}$.

Similarly, if you had to verify that some function $f$ represented a pdf you would have to show that $\int f(x) dx=1$


问:
Norm attaining functionals on a Banach space
Do every linear functional on a Banach space attains its norm? In case of finite-dimension, the argument follows via compactness of the unit ball. What about in infinite-dimensional case? Is there any any general version of it?

Any help will be appreciated!

答:
It is not necessary that an functional on a Banach space $X$ would attain its norm. However, in case of a reflexive Banach space, the unit ball remains compact under the weak topology (the minimum topology needed to maintain the continuity of each member of the $X^*$).

A general version of this is every compact operator on a reflexive Banach space attains its norm. In particular, the continuous linear functionals are compact.

Whenever, $X$ is not reflexive, no such conclusion is true. However, still we can say something about $X^*$. Every member of $X^{**}$, which are image of any member of $X$, under canonical isomorphism, attains their norm. This is because of Banach-Alaoglu Theorem, which says:

Given any Banach space $X$, unit ball of $X^{*}$ is compact with respect to the weak$^*$ topology.

Weak$^*$ topology: The minimum topology on $X^*$, needed to maintain the continuity of each member of $\psi(X)$, where $\psi: X \to X^{**}$ denotes the canonical embedding.


问:
Gaussian integral by Taylor series?
I found a document with a long list of proofs of Gaussian integral converging to $\sqrt \pi$. Interestingly it did not contain a proof by Taylor expansion. Let's try...

$$\int_0^\infty e^{-x^2}dx=\text{lim}_{y\rightarrow \infty}\int_0^y \sum_{n=0}^\infty \frac{(-1)^nx^{2n}}{n!}dx$$

We can exchange the sum and integral by Fubini as $e^{x^2}$ converges for finite integral.

$$=\text{lim}_{y\rightarrow \infty} \sum_{n=0}^\infty\int_0^y \frac{(-1)^nx^{2n}}{n!}dx$$
$$=\text{lim}_{y\rightarrow \infty} \sum_{n=0}^\infty \frac{(-1)^ny^{2n+1}}{n!(2n+1)}$$

And we are looking to prove that this is equal to $\sqrt{\sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1}}=\frac{\sqrt \pi}{2}$. To make things easier we can square both sides. Then, for all $\epsilon$ we need $n_0(k),n_1$

$$|\sum_{n=0}^{m}\frac{(-1)^n}{2n+1}- (\sum_{n=0}^{m} \frac{(-1)^n k^{2n+1}}{n!(2n+1)})^2|<\epsilon, \space \space \space \space \space \space n_0<m,n_1<k$$
$$\Leftrightarrow |\sum_{n=0}^{m}\frac{(-1)^n}{2n+1}- \sum_{i=0}^{m}\sum_{j=0}^{m} \frac{(-1)^{(i+j)} k^{2(i+j)+1}}{i!j!(2i+1)(2j+1)}|<\epsilon, \space \space \space \space \space \space n_0<m,n_1<k$$

... and here I get stuck for now. Can it be done?

Edit: Solution seems to be approximately in range of $n_0(k)=3^k$, and $n_1=ceil(\frac{1}{\epsilon})$.

答:
There are many different reasons why this idea won't work. First of all observe that actually you can NOT interchange the integral sign with the power series:
$$\lim_{y\rightarrow+\infty}\int_{0}^{y}\sum_{n=0}^{+\infty}\frac{(-1)^{n}x^{2n}}{n!}dy$$
it is actually a finite value, but here is the problem: the generic term of the sum is not a $L^{1}$ function on $(0,+\infty)$, i.e. the integral:
$$\int_{0}^{+\infty}\Bigg|\frac{(-1)^{n}x^{2n}}{n!}\Bigg|dx$$
is NOT finite, thus the equality between the integral of power series and the series of integral does not hold (you can't even hope to apply dominated convergence theorem).

Nice idea, but unfortunately won't work.

Title: Gaussian integral by Taylor series?


问:
Prove that if a function is both monotone and even, the function is a constant function
So we would have $f(x) = f(-x)$ and $f$ can either be ascending or descending.

My approach to the problem  would be by Reduction To Absurdity. I would start off by saying that: "Suppose there actually is a function $f$ that meets those 2 requirements and is not constant". To make things easier I'd probably make a choice and say we're working with an increasing function.
We then take two values $x > y > 0$ therefore $f(x) \geq f(y)$ due to the function being increasing.
$-x < -y < 0$ is a pretty obvious deduction => $f(-x) \leq f(-y)$. But the function is even therefore: $f(-x) = f(x)$ and $f(-y) = f(y)$. Due to the inequality mentioned a bit earlier, we would have:
$f(x) \geq f(y)$ and $f(x) \leq f(y)$ therefore $f(x) = f(y)$.

Am I on the right track? These were my ideas so far.

答: There is not need to mention $0$. Suppose that $f$ is increasing. If $f$ is not constant, then there are two numbers $x$ and $y$ with $x\ne y$ and $f(x)<f(y)$. Suppose that $x<y$. Then $-y<-x$ and$$f(-y)=f(y)>f(x)=f(-x).$$But this is impossible, since $f$ is increasing and $-y<-x$. If $x>y$ or if $f$ is decreasing, the argument is similar.


问:
How can one find such probability for this round table problem?
$10$ individuals including $x$ and $y$ seat at random at a round table. All possible orders are equally likely. Let $W$ be the event that there are exactly two people seated between $x$ and $y$. What is the probability of this event?

答: Let's say $x$ sits somewhere (it doesn't matter where). There are $9$ seats left. There are $2$ of these seats where $y$ can seat so that there are two people between them. So the answer is $2/9$. In the image bellow these would be the red seats:


答:
hint

Let $ x>0$.

then if $ f $ is for example, increasing,

$$f(-x)\le f(0)\le f(x)$$

or

$$f(x)=f(0)$$

Title: Prove that if a function is both monotone and even, the function is a constant function

Body:
So we would have $f(x) = f(-x)$ and $f$ can either be ascending or descending.

My approach to the problem  would be by Reduction To Absurdity. I would start off by saying that: "Suppose there actually is a function $f$ that meets those 2 requirements and is not constant". To make things easier I'd probably make a choice and say we're working with an increasing function.
We then take two values $x > y > 0$ therefore $f(x) \geq f(y)$ due to the function being increasing.
$-x < -y < 0$ is a pretty obvious deduction => $f(-x) \leq f(-y)$. But the function is even therefore: $f(-x) = f(x)$ and $f(-y) = f(y)$. Due to the inequality mentioned a bit earlier, we would have:
$f(x) \geq f(y)$ and $f(x) \leq f(y)$ therefore $f(x) = f(y)$.

Am I on the right track? These were my ideas so far.


答:
A stopping time is a random variable which is measurable with respect to $\mathcal{F}_n$, meaning that at time $n$ I know if the stop has occurred or not. You should then define
$$ \tau_A = \inf \{ n: X_n = X_{n-1} = 1 \} , $$
or even
$$ \tau_A = \min( 20, \inf \{ n: X_n = X_{n-1} = 1 \} ) .$$

This is a stopping time, while the one you defined is not.

For Bob you could even not use a stopping time, but do the calculation conditioning on the event $$E = \left\{ \sum_{k=1}^{10} X_k ≥ 9 \right\}.$$

Title: Two gamblers in a casino, with different conditions for stopping, which one has greater expected loss?

Body:
The following question was given in the exercises in the martingale chapter of a textbook by Koralev-Sinai. I'm having trouble formalizing this problem in terms of martingale theory

Ann and Bob are gambling at a casino. In each game the probability of winning a dollar is 48%, and the probability of losing a dollar is 52%. Ann decided to play 20 games, but will stop after 2 games if she wins them both. Bob decided to play 20 games, but will stop after 10 games if he wins at least 9 out of the first 10. What is larger: the amount of money Ann is expected to lose, or the amount of money Bob is expected to lose?

My idea is to appeal to the optional stopping theorem, by defining a stopping time $\tau_{A}$ for Ann and a stopping time $\tau_{B}$ for Bob. But I'm not quite sure how to define these times. Any help or hints along these lines should be helpful.

Just thinking, if $X_{j}$ is the random variable representing the amount gained/lost at the $j$th game, that is taking $1$ with probability $.48$ and $-1$ with probability $.52$, then $$ \tau_{A} = \inf\{n : X_{n} = X_{n+1} =1 \}$$
and I think $\tau_{B} = 10$ if $\sum^{10}_{k=1}X_{k}  \geq 9$? We can then account for them stopping at 20 games by taking the minimum with respect to a constant stopping of $T=20$.


问:
Sequences converges if series converges proof
Let $\{x_n\}$ for $n \geq 1$ be a sequence of positive real numbers and let $s_n = \frac{x_n}{n}$. Let $\{y_n\}$ for $n \geq 1$ be another sequence such that $y_n = n^{-1} \sum_{i = 1}^{n} x_i$. Prove that if $\sum_{j = 1}^{\infty} s_j$ converges, then $\{y_n\}$ converges to $0$.

My attempt:

Assume that $\sum_{j = 1}^{\infty} s_j$ converges. Because it converges we can infer that $\lim_{n \rightarrow \infty} s_n = 0 \implies \lim_{n \rightarrow \infty} \frac{x_n}{n} = 0$. By the definition of limits, for all $\epsilon > 0$, there is some $N \in \mathbb{N}$ so that for $n \geq N$, we have $|s_n| < \epsilon \implies |\frac{x_n}{n}| < \epsilon$.

We need to show that $\lim_{n\to\infty} y_n = y$ for some $y$. So for all $\epsilon_2 > 0$ we need to find some $N_2$ such that for all $n \geq N_2$, we have $|y_n - y| < \epsilon_2$. But $y_n = n^{-1} \sum_{i = 1}^{n} x_i$ so $|n^{-1} \sum_{i = 1}^{n} x_i - y| < \epsilon_2$

Not too sure what to do from here and I am hoping that somebody can point me in the right direction. I don't think my method of using $\epsilon$ and limits is correct and instead think that the problem could involve some manipulation of series? Any assistance is appreciated.

Update:

Let $S_n = \sum_{j=1}^{n} s_j = \sum_{j=1}^n \frac{x_j}{j}$. Because it converges there is some $S$ such that $\lim_{n \rightarrow \infty} S_n = \sum_{j=1}^{\infty} \frac{x_j}{j} = S$.

We can also write:

$$y_n  =n^{-1}\sum_{k=1}^n x_k = n^{-1} \sum_{k=1}^nk \frac{x_k}{k} = n^{-1} \sum_{k=1}^nk s_k$$

Using summation by parts, with $S_0 := 0$,

$$y_n = n^{-1} \sum_{k=1}^nk(S_k- S_{k-1})= n^{-1}\left(nS_n + \sum_{k=1}^{n-1}S_k (k - (k+1)) \right) = S_n - n^{-1}\sum_{k=1}^{n-1}S_k$$

We need to show $n^{-1}\sum_{k=1}^{n-1}S_k \to S$ as $n \to \infty$ when $S_n \to S$.

Since $S_n$ converges to $S$, there is some $N \in \mathbb{N}$ such that for $n \geq N$

$$|n^{-1} \sum_{k=1}^n S_k- S_{k-1}| \leq n^{-1} \sum_{k=1}^N |S_k- S_{k-1}| + n^{-1} \sum_{k=N + 1}^n |S_k- S_{k-1}| = ^{-1} \sum_{k=1}^N |S_k- S_{k-1}| + \epsilon(1 - \frac{N}{n})$$

Indeed by taking the limsup for both sides we see that for any $\epsilon > 0$

$$0 \leq \limsup_{n \rightarrow \infty} |n^{-1} \sum_{k=1}^n S_k- S_{k-1}| \leq \epsilon$$

By squeeze theorem, $\lim_{n \rightarrow \infty} |n^{-1} \sum_{k=1}^n S_k- S_{k-1}| = \limsup_{n \rightarrow \infty} |n^{-1} \sum_{k=1}^n S_k- S_{k-1}| = 0$

It then follows that $y_n \to S-S=0$ as $n \to \infty$.

QED.

Credits to user RRL.

答:
We have $S_n = \sum_{j=1}^n s_j \to S$ as $n \to \infty$, and

$$y_n  =n^{-1}\sum_{k=1}^n x_k = n^{-1} \sum_{k=1}^nk \frac{x_k}{k} = n^{-1} \sum_{k=1}^nk s_k$$

Using summation by parts, with $S_0 := 0$,

$$y_n = n^{-1} \sum_{k=1}^nk(S_k- S_{k-1})= n^{-1}\left(nS_n + \sum_{k=1}^{n-1}S_k (k - (k+1)) \right) = S_n - n^{-1}\sum_{k=1}^{n-1}S_k$$

It is easy to show $n^{-1}\sum_{k=1}^{n-1}S_k \to S$ as $n \to \infty$ when $S_n \to S$. It then follows that $y_n \to S-S=0$ as $n \to \infty$.


答:
Hint:
A valid placement is

```<code>... i-1  i    i+1  i+2  i+3  i+4  ...
... a    X    b    c    Y    d    ...
</code>```

another is

```<code>... i-1  i    i+1  i+2  i+3  i+4  ...
... a    Y    b    c    X    d    ...
</code>```

where $10$ must be subtracted from the seat number $i+k$ if it is larger then $10$.

The first placement is related to the placement

```<code>1    2   3   4   5 ... 10
X    b   c   Y   d ...  a
</code>```

Annotation:

I thought you want to calculate the number of placements where 2 people are seated between $x$ and $y$. If you have this number you divide it by $10!$ and get the probability that you really want. But of course this probability can be calculated by the way this post shows us in a simpler way.

Title: How can one find such probability for this round table problem?

Body: $10$ individuals including $x$ and $y$ seat at random at a round table. All possible orders are equally likely. Let $W$ be the event that there are exactly two people seated between $x$ and $y$. What is the probability of this event?

Body:
Hint:
A valid placement is

... i-1  i    i+1  i+2  i+3  i+4  ...
... a    X    b    c    Y    d    ...

another is

... i-1  i    i+1  i+2  i+3  i+4  ...
... a    Y    b    c    X    d    ...

where $10$ must be subtracted from the seat number $i+k$ if it is larger then $10$.

The first placement is related to the placement

1    2   3   4   5 ... 10
X    b   c   Y   d ...  a

Annotation:

I thought you want to calculate the number of placements where 2 people are seated between $x$ and $y$. If you have this number you divide it by $10!$ and get the probability that you really want. But of course this probability can be calculated by the way this post shows us in a simpler way.


问:
Prove that in two trees with same vertices there exists a vertex that the sum of its' degree in both trees is maximum $3$
I came across this question and I tried to give myself a direction but couldn't:

Given $T1 = (V, E_1)$ and $T2 = (V, E_2)$ two trees with same group of vertices. Prove that there is a vertex $v$ such that $deg(v)_{T1} + deg(v)_{T2} \leq 3$.

Now I thought about that in a tree there are at least two leafs, we take one and we show that its' degree in $T2$ is less or equal 2, but that is obviously not a condition and not always correct.

I would be happy for a direction!

答:
I have solved this afterall. We want to prove that in $G=(V, E_1 \cup E_2)$ there is a vertex $v$ such that $deg(v) \leq 3$. We assume that all the vertices in $G$ are greater than $3$ (at least $4$.) Let $|V| = n$. Then $\sum_{v \in V} {deg(v)} \geq 4n$. Now, $T_1$ and $T_2$ are trees so each one of them has $n-1$ edges, so $|E_1| = |E_2| = n-1$. We know that $|E_1 \cup E_2| \leq |E_1| + |E_2|$ which means $|E_1 \cup E_2| \leq 2n-2$. But the sum of degrees is $\geq 4n$, sp in $E_1 \cup E_2$ there are at least $2n$ edges (coming from the fact that $\sum_{v\in V} {deg(v)} = 2|E|$,) which means that our assumption that all vertices in $G$ have a degree greater than $3$ is wrong.
Thus, there exists a vertix $v$ whose degree is less or equal to $3$.</p>

ContentLicense: CC BY-SA 3.0


问:
Is the line measure operator bounded in $W^{1,p}(\mathbb{R}^2)$
Consider the linear funtional $S_l: W^{1,p}(\mathbb{R}^2) \to \mathbb{R}$ for some segment $l \in \mathbb{R}^2$ such that $S_l (\mu)$ measures the length of $l$ with respect to $\mu dx$. In other words, it performs the line integral of the function $\mu$ on $l$. I'm curious if $S_l$ is a bounded functional for all finite $l$ for some $p > 1$? I know that for point evaluation operator it is true, since for $p > n$, there is continuous injection of $W^{1,p}(\mathbb{R}^n)$ to $L^\infty(\mathbb{R}^n)$. I wonder if it's also the case for evaluating the function on a line segment.

答: Not only does $W^{1, p}(\mathbb{R}^{n})$ embed continuosly in $L^{\infty}(\mathbb{R}^{n})$ for $p > n$, but we also have (due to Morrey) that it embeds continuously into the Holder space $C^{0, 1 - \frac{n}{p}}$. This should give us that $S_{l}$ is bounded for all finite $l$ whenever $p > 2$ (since in this case we're working in $\mathbb{R}^{2}$).


问:
Finding the number of balls in an urn from the probability of it being chosen
An urn contains $4$ green balls and $6$ blue balls. A second urn contains $16$ green and $N$ blue balls. A single ball is drawn at random from each urn. The probability that both balls are of the same colour is $0.58$. Find $N$.

My progress so far:
We know that choosing balls of the same colour is the union fo the two disjoint events of choosing two green or two blue balls. So we simply need to find the probability of each of those events and then we are finished.

However, we don't know how to find the probability of the second balls chosen being either green or blue, as we don't know $N$, so how could I calculate that?

答:
The probability of both balls being green is:

$P(bothGreen) = \frac{4}{4+6}*\frac{16}{16+N}$

The probability of both balls being blue is:

$P(bothBlue) = \frac{6}{4+6}*\frac{N}{16+N}$

And you know that $P(bothGreen) + P(bothBlue) = 0.58$, so you just need to solve the equation:

$\frac{4}{10}*\frac{16}{16+N} + \frac{6}{10}*\frac{N}{16+N} = 0.58$


答:
The determinant of a matrix is the $n$-dimensional signed volume of a parallelepiped whose edge vectors are the columns of the matrix. If we move one of the edge vector in the plane of the other $n-1$ vectors, the altitude on the base of the $n-1$ other vectors has not changed, so the altitude times the area of the base is unchanged. That is,
$$
\begin{align}
\det\begin{bmatrix}
u_1&v_1&\cdots&w_1\\
u_2&v_2&\cdots&w_2\\
\vdots&\vdots&\ddots&\vdots\\
u_n&v_n&\cdots&w_n
\end{bmatrix}
&=\det\begin{bmatrix}
u_1+v_1&v_1&\cdots&w_1\\
u_2+v_2&v_2&\cdots&w_2\\
\vdots&\vdots&\ddots&\vdots\\
u_n+v_n&v_n&\cdots&w_n
\end{bmatrix}\tag1\\[6pt]
&=\det\begin{bmatrix}
u_1+v_1&-u_1&\cdots&w_1\\
u_2+v_2&-u_2&\cdots&w_2\\
\vdots&\vdots&\ddots&\vdots\\
u_n+v_n&-u_n&\cdots&w_n
\end{bmatrix}\tag2\\[6pt]
&=\det\begin{bmatrix}
v_1&-u_1&\cdots&w_1\\
v_2&-u_2&\cdots&w_2\\
\vdots&\vdots&\ddots&\vdots\\
v_n&-u_n&\cdots&w_n
\end{bmatrix}\tag3\\[6pt]
&=-\det\begin{bmatrix}
v_1&u_1&\cdots&w_1\\
v_2&u_2&\cdots&w_2\\
\vdots&\vdots&\ddots&\vdots\\
v_n&u_n&\cdots&w_n
\end{bmatrix}\tag4
\end{align}
$$
Explanation:

$(1)$: slide the first vector in the plane of the remaining $n-1$ vectors

$\phantom{\text{(1):}}$ (add the second column to the first)

$(2)$: slide the second vector in the plane of the remaining $n-1$ vectors

$\phantom{\text{(2):}}$ (subtract the first column from the second)

$(3)$: slide the first vector in the plane of the remaining $n-1$ vectors

$\phantom{\text{(3):}}$ (add the second column to the first)

$(4)$: the determinant is linear in each column

Title: Property of Determinant

Body:
If any two rows or columns of a determinant are interchanged, the sign of the value of the determinant is changed.

What is the intuition of this? I can see from algebra perspective thats right, but I want a geometrical visualization. I tried to think in terms of linear transformation but I was not able to visualize that transformation.


问:
How does the symmetric group act on tuples?
Given a set $X$, I've seen people write the action of a permutation $ \sigma \in S_{n}$ on an $n$-tuple of elements of $X$ as
$$ \;\; \sigma (x_{1},...,x_{n})=(x_{\sigma^{-1}(1)},...,x_{\sigma^{-1}(n)}). \;\;$$
But this does not seem to me to give a left action of $S_{n}$ on $n$-tuples, since
$$\sigma(\tau(x_{1},...,x_{n}))=\sigma(x_{\tau^{-1}(1)},...,x_{\tau^{-1}(n)})=(x_{\sigma^{-1}\tau^{-1}(1)},...,x_{\sigma^{-1}\tau^{-1}(n)})$$
is not in general equal to
$$(\sigma \tau)(x_{1},...,x_{n})=(x_{(\sigma \tau)^{-1}(1)},...,x_{(\sigma \tau)^{-1}(n)})=(x_{\tau^{-1}\sigma^{-1}(1)},...,x_{\tau^{-1}\sigma^{-1}(n)}).$$

On the other hand, if we don't write out symbols, but think of a tuple as a map from
the $n$-element set $\{1,...,n\}$ to $X$, then the first formula seems to make sense:
the $\sigma^{-1}$ comes from precomposing with the right action of $S_{n}$ on the set $\{1,...,n\}$ determined by the left action of $S_{n}$ on $\{1,...,n\}$, where we use the convention that functions act on the left of elements.

So the question is whether the first formula defines a left or a right action on tuples.
The symbols seem to suggest a right action while interpreting tuples as maps seems to suggest a left action. I think that in my formulas above I must be getting confused.

答:
The first formula defines a left action on tuples. Note that $\sigma \in S_n$ acts on the positions, not on the indices. You did wrong in computing $\sigma\bigl(\tau(x_1, \ldots, x_n)\bigr)$.

We have $\tau(x_1, \ldots, x_n) = (x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)})$ by definition. Now $\sigma$ acts from the left on this tuple. Acting on a tuple, $\sigma$ "moves" the entry in position $\sigma^{-1}(1)$ to the front, right? But which $x_j$ is that? If we write $y_i = x_{\tau^{-1}(i)}$ we have
$$ \sigma(x_{\tau^{-1}(1)}, \ldots, x_{\tau^{-1}(n)}) = \sigma(y_1, \ldots, y_n)
 = (y_{\sigma^{-1}(1)}, \ldots, y_{\sigma^{-1}(n)}) $$
So the new first entry is $y_{\sigma^{-1}(1)} = x_{\tau^{-1}\sigma^{-1}(1)}$, giving
$$ \sigma\bigl(\tau(x_1, \ldots, x_n)\bigr) = (x_{\tau^{-1}\sigma^{-1}(1)}, \ldots, x_{\tau^{-1}\sigma^{-1}(n)}) = (x_{(\sigma\tau)^{-1}(1)}, \ldots, x_{(\sigma\tau)^{-1}(n)}). $$


问:
$\sum\limits_{n=2}^{\infty}\frac{1}{(\ln n)^p}$ converge value
There's $\sum\limits_{n=2}^{\infty}\frac{1}{(\ln n)^p}$, $p \in \mathbb{R}$. For what values p converge? Notice n=2 at the beginning. Since it's to be decreasing and always >0, I think integral testing is good. So I calculate it, I had final answer is $p>0$ converges. Yes or no?

答:
If $ p\le 0$ then

$$\lim_{n\to+\infty}\frac{1}{(\ln(n))^p}\ne 0$$
$\implies $ the series diverges.

If $ p>0 $, observe that

$$\lim_{n\to+\infty}\frac{\sqrt{n}}{(\ln(n))^p}=+\infty$$

$$\implies \frac{\sqrt{n}}{(\ln(n))^p}>1$$
for $ n $ large enough.

$$\implies \frac{1}{\sqrt{n}}<\frac{1}{(\ln(n))^p}$$

$\implies $ the series is divergent by comparison test of positive series.

So, your series is never convergent.


问:
Choi Lam homogeneous polynomials as sums of squares
I came across two polynomials that Choi and Lam gave in 1976, that are not sum of squares of polynomials, despite being evidently non-negative by AM-GM
$$ S(x,y,z) = x^4 y^2 + y^4 z^2 + z^4 x^2 - 3 x^2 y^2 z^2 $$
$$Q(w,x,y,z) = w^4 + x^2 y^2 + y^2 z^2 + z^2 x^2 - 4wxyz $$
The sextic was asked about in 2015 Representing as sum of squares of polynomials  From what I can see, proving a polynomial is not sos can be done by hand.

From a 2003 article by Reznick, I know that
$$   S_8(x,y,z) = (x^2 + y^2 + z^2) S(x,y,z)   $$
really is the sum of squares of (quartic homogeneous) polynomials.

That is question 1, can anybody supply an sos version of $S_8 \; ? \;$

From context, it seems likely that
$$   Q_6(w,x,y,z) = (w^2 +x^2 + y^2 + z^2) Q(w,x,y,z)   $$
is also the sum of polynomial squares. The context is that Delzell's examples are rather later, I would think some author would point out that the ``bad points'' property holds for this Choi-Lam example, if it were true.

That would be question 2, can anybody supply an sos version of $Q_6 \; ? \;$

I have requested a book edited by Delzell from the library, and ordered a used copy of his (2003?) book Positive Polynomials (with Prestel)

confirming Willie's answer for $Q_8$ by CAS:

```<code>? g= 2* x^2* y^2 * (x^2-z^2)^2 +  y^4 * (x^2-z^2)^2 + 2* y^2* z^2 * (y^2-x^2)^2 +  z^4 * (y^2-x^2)^2 + 2* z^2* x^2 * (z^2-y^2)^2 +  x^4 * (z^2-y^2)^2
%1 = 2*y^2*x^6 + (2*y^4 - 4*z^2*y^2 + 2*z^4)*x^4 + (-4*z^2*y^4 - 4*z^4*y^2 + 2*z^6)*x^2 + (2*z^2*y^6 + 2*z^4*y^4)
?
? h = ( x^2 + y^2 + z^2) * (x^4*y^2 + y^4*z^2 + z^4 * x^2 - 3 * x^2 * y^2 * z^2 )
%2 = y^2*x^6 + (y^4 - 2*z^2*y^2 + z^4)*x^4 + (-2*z^2*y^4 - 2*z^4*y^2 + z^6)*x^2 + (z^2*y^6 + z^4*y^4)
?
? 2*h
%3 = 2*y^2*x^6 + (2*y^4 - 4*z^2*y^2 + 2*z^4)*x^4 + (-4*z^2*y^4 - 4*z^4*y^2 + 2*z^6)*x^2 + (2*z^2*y^6 + 2*z^4*y^4)
? g
%4 = 2*y^2*x^6 + (2*y^4 - 4*z^2*y^2 + 2*z^4)*x^4 + (-4*z^2*y^4 - 4*z^4*y^2 + 2*z^6)*x^2 + (2*z^2*y^6 + 2*z^4*y^4)
? 2*h - g
%5 = 0
?
</code>```

Might as well: Reznick proved that a positive definite polynomial can changed into an sos by multiplying by $(\sum x_i^2)^N.$   Eventually an example of Delzell showed up, for which that failed; in this case the source gave the altered product that does become an SOS.

$$  D = z^8 + w^2 x^4 y^2 + w^2 y^4 z^2 + w^2 z^4 x^2 - 3 w^2 x^2 y^2 z^2 $$

However, $D_{10}=(x^2 + y^2 + z^2)D$ really is an sos of polynomials, the article says eight squares, integer or rational coefficients with small denominatros.

Body:
Question 1 can be done by hand pretty simply.

$$ S_8 = (x^2 + y^2 + z^2) (x^4 y^2 + y^4 z^2 + z^4 x^2 - 3 x^2 y^3 z^2) $$

So

$$ = x^6 y^2 + x^4 y^4 - 2 x^4 y^2 z^2 + \text{cyclic cycle indices} $$

Observe that

$$ x^6 y^2 - 2 x^4 y^2 z^2 + x^2 y^2 z^4 = x^2 y^2 (x^2 - z^2)^2 $$

And that

$$ \frac12 z^4 y^4 + \frac12 x^4 z^4 - x^2 y^2 z^4 = \frac12 z^4 (x^2 - y^2)^2 $$

we find

$$ S_8 = x^2 y^2 (x^2 - z^2)^2 + \text{ cyclic } + \frac12 x^4 (y^2 - z^2)^2 + \text{ cyclic } $$


问:
Suppose $S \subset \mathbb{R}$ is bounded above but has no maximum element. Prove that sup $S \notin S$.
I've been trying to prove this and I just can't seem to figure it out. I'm just totally lost as to where to even start. I tried applying a method that was shown here but I know that $S$ does not have to necessarily be of the form $[a,b)$ (or $(a,b)$, etc.)

So I'm pretty much stuck, I'd really appreciate some help, or someone to point me in the right direction.

Thanks in advance.

答:
Just approach the problem via contradiction. Let $sup S=d$. Then $d\geq s$ (by definition of supremum) for every $s\in S$. Now, if $d\in S$, then it is trivial to see that $d$ is a maximum of $S$. However, this is a contradiction to the fact that $S$ has no maximum.

Consequently $d\notin S$.

Actually, supremum of a set is called maximum if it is one of the member of the set.


答:
A fancy way to do it: let $\;a_n:=\cfrac{n!}{e^{n^2}}\;$ , then

$$\frac{a_{n+1}}{a_n}=\frac{(n+1)!}{e^{(n+1)^2}}\cdot\frac{e^{n^2}}{n!}=\frac{n+1}{e^{2n+1}}\xrightarrow[n\to\infty]{}0$$

since exponential grows way faster than polynomial.

Thus, by the ratio (D'Alembert) test, the series $\;\sum\limits_{n=1}^\infty\cfrac{n!}{e^{n^2}}\;$ converges, which means

$$\frac{n!}{e^{n^2}}\xrightarrow[n\to\infty]{}0\implies n!<e^{n^2}\;\;\text{for all large enough}\;\;n$$


Body:
$$e^{n^2}=(e^n)^n\gg n^n\gg n!$$

E.g. $$e^{10^2}=2.688117\cdots 10^{43}\gg 10!=3628800.$$


问:
Currency launch probability
Two individuals, $ A $ and $ B $ will play heads or tails with an '' honest '' coin. They agree to flip the coin $ 5 $ times, and the one who wins in 3 or more rolls wins the game. Each bets $ 2800$. After the first two launches, in which both $ A $ wins, they decide to end the game. From a probabilistic point of view, how should the 5600 dollars be distributed?

Solution: The probability that B will win the next three rolls is $\frac{1}{2^3} = \frac18$. So the dollars should be distributed in a $1:7$ ratio. This means that A will get $4900$ dollars, and B will get $700$ dollars.

Is this solution correct? Why would the ratio be 1: 7? Could someone explain it to me better?

答:
If the $A$ player is risk neutral then he will accept the expected value of the game not to play which is

$$E_A = \frac{7}{8}\cdot5600+\frac{1}{8}\cdot0 = 4900$$

A similar reasoning can be used with $B$. The ratio can be seen to originate from this reasoning.

Consider also that the expected value measures how much the player would win on average partecipating at the game.

Title: Currency launch probability


问:
Is (im)predicativity decidable
The distinction between predicative and impredicative definitions is
important in mathematics. As first approximation, impredicativity
means circularity. Let me give you an example of an impredicative
definition.

Let $V$ be a vector-space over a field $K$, and $S \subseteq V$ a set
of vectors. The ${span}$ of $S$ is the intersection of all
sub-vector-spaces $V'$ of $V$ that also contain $S$.

$$
\operatorname{span}(S) = \bigcap \{V'\ |\ S \subseteq V', V'\ \text{is a sub-vector-space of}\ V\}
$$

In a set theory like ZF(C), this definition is impredicative
because $\operatorname{span}(S)$ is itself a member of $\{V'\ |\ S \subseteq V',\
\text{is a sub-vector-space of}\ V\}$.  In some sense this definition
is circular. In this particular case, we can easily get around this
impredicativity, for example by defining

$$
\operatorname{span}(S) = \{\Sigma _{i=1}^{n} k_i.v_i\ |\ n \geq 0, k_i \in K, v_i \in S\}
$$

but it's not always that easy. For example in ZF(C) the natural numbers are often defined as follows.

$$
  \mathbb{N} = \bigcap \{S \ |\ S\ \text{is an inductive set}\}
$$

where $S$ set is inductive if it contains $0$ and is closed
under successor. Clearly, $\mathbb{N}$ is itself inductive.

Such circularities are not considered problematic in classical
mathematics, in the sense that no contradictions have ever been
derived from such impredicative definitions. Nevertheless,
impredicate definitions don't always sit well with constructive
mathematics. This leads to my question: is it always easy to see if a
definition is (im)predicative? More precisely:

Is it decidable if a formula $F$ is predicative in a theory $T$?

I'm most interested in the case where the theory $T$ is some set theory.

Note that I have not formally defined (im)predicativity. Such a
definition itself appears to be difficult, but I would be happy to
hear about answers to my question for any of the extant formal
or informal notions of (im)predicativity.

答:
1] The usual characterization of an impredicative definition is that it defines some object (property, relation, function, etc.) by means of a quantification over some domain which, if the definition succeeds, contains that object (property, relation, function, etc.). Here quantifications will be taken to include Russellian definite descriptions, as when we define an object as the unique object such that ...

In the context of a formalized theory with typed variables, we typically implement a ban on impredicative definitions by banning definitions of things of type $t$ via formulas that involve quantifiers of type $t$. Thus, predicative second-order arithmetic is characterised by only allowing instances of the comprehension schema defining a numerical property [or set of numbers] to contain first-order quantifiers over numbers (and not second-order quantifiers over properties [sets of numbers]). And in such a context it is readily decidable by inspection whether a formula is predicative and can feature in the comprehension scheme or other kind of definition.

2] But, as the OP hints, it can be interesting to ask when an impredicative definition has a co-extensive predicative counterpart. There's surely not usually going to be a decidable routine to determine that even within a fixed formalized theory (if only because we can't usually effectively determine co-extensionality).

3] As a footnote, pace Russell, it isn't particularly helpful to think of impredicativity as a species of circularity. To use Ramsey's example, if I pick out Jane as the tallest woman in the room, that's impredicative (I pick her out by a quantification over a totality including her); but in what sense is that circular?

Title: Is (im)predicativity decidable


问:
Topological entropy of non-hyperbolic toral automorphism
I have a matrix $ A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and its associated toral automorphism $f_A$. That is;

$\begin{equation} {f}^{n}_A := ( x + ny \text{ mod } 1 , y ) \end{equation}$

I am trying to show that its topological entropy, $h_{\text{top}}(f_A) = 0$. My thought process would be to construct its $(n,\epsilon)$ - spanning sets and then show that their exponential growth rate is 0, and thus the topological entropy is equal to 0. However I am struggling to construct them, so any tips would be appreciated.

I cannot use that if an toral automorphism has a repeated eigenvalue of 1 then $h_{\text{top}}(f_A) = \log(1) = 0$.

答:
Since $f$ is a continuous map on the compact metric space $\mathbb{T}^2$, one form of the variational principle says that
$$
h_{top}(f) = \sup_{\mu \in \mathscr{M}^f_e(\mathbb{T}^2)} h_\mu(f)
$$
where $\mathscr{M}^f_e(\mathbb{T}^2)$ is the set of all ergodic $f$-invariant probability measures on $\mathbb{T}^2$.  So it is enough to show that $h_\mu(f) = 0$ for any ergodic $f$-invariant measure $\mu$.

A key observation is the following.  If $L_y = \{(x,y): x \in \mathbb{T}\}$ is the horizontal line in $\mathbb{T}^2$ at height $y$, then each $L_y$ is an $f$-invariant set.  Therefore if $\mu$ is any ergodic measure, there is a unique $y$ such that $\mu$ is supported on $L_y$.  Now when restricted to the line $L_y$, the action of $f$ is clearly isomorphic to the circle rotation $x \mapsto x+y$ on $\mathbb{T}$.  Since $\mu$ is supported on a line, it is naturally identified with a measure on $\mathbb{T}$, and so our system $(\mathbb{T}^2, f, \mu)$ is naturally isomorphic to the circle rotation $(\mathbb{T}, x \mapsto x+y, \mu)$.

It's well known that 1-dimensional circle rotations have zero topological entropy, so in particular any invariant measure for a circle rotation has zero measure entropy as well.  Therefore $h_\mu(f) = 0$.  Since this holds for any ergodic $f$-invariant measure $\mu$ we are done.


问:
Are straight lines obtained as conics unique to the specific double cone
It's intuitive to know how arbitrary circles, and ellipses, hyperbola of varying eccentricities can be obtained through a plane and double cone intersection.
However, I am not able to figure how one might obtain straight lines that intersect at arbitrary angles (or even parallel lines for that matter) as conics?

I currently understand that only a pair of straight lines can be obtained as a conic that intersects at an angle which is same as the vertex angles of the double cone, but I am not able to find a visual model that can show otherwise.

答:
Given two lines in a common plane in Euclidean space, there are
only two possible cases. Either they are parallel and have no
intersection or else they intersect at exactly one point. In the
first case, extending to projective space, the parallel lines
do intersect at a single point at infinity. Consider the locus of all
points equidistant from the two lines. In the first case the locus
is a line parallel to both and midway between them. In the second
case they are on two perpendicular lines passing through the common
intersection point. Pick any one of them. In both cases use the
line of equidistant points as a rotation axis to rotate the two
lines into a surface of revolution. In the first case it is an
infinite circular cylinder.

In the second case it is a circular
double cone. In the first case, for any plane that intersects the
cylinder, the points of intersection form a conic section --
either a circle, ellipse, or two parallel lines. For the second case,
every plane intersects the double cone in at least one point. The
points of intersection form a conic section -- either a single point,
a circle, an ellipse, a parabola, a hyperbola, a single line, or a pair
of intersecting lines.

In the case of intersecting lines, the plane
passes through the vertex of the double cone and the angle
of their intersection is less than or equal to the angle of the two
generating lines. The angles are only equal if the rotation axis lies
in the intersecting plane. As for visualization, try a web search for
conic section images.


问:
Disconnected metric space proof
Let $(A, d)$ be a metric space. Show that if $A$ is connected then $A$ is not countable.

Note about the definition of countable: A set $X$ is countable if it has the same cardinality as $\mathbb{N}$.

My attempt:

I use a contrapositive argument:

Assume instead that $A$ is a countable set. We need to show that $A$ is disconnected/not connected.

Take $a \in A$. The set $E := \{d(a, b): b \in E\}$ is countable. So there exists $a_n \rightarrow 0$ where $a_n \notin E$. The ball of radius $a_n$ about $a$, denoted $B(a, a_n)$, is empty so $B(a, a_n)$ is both open and closed. Therefore $a$ the largest set containing itself. We may conclude that $A$ is totally disconnected.

Does totally disconnected imply disconnected? If so, is this proof correct? If not, what would a correct proof look like? Any assistance is much appreciated.

答:
Your argument is basically correct, but you don’t need a sequence, and do need to make sure that your ball doesn’t include the whole space. Pick a point $b\in A\setminus\{a\}$, and let $r=d(a,b)$. Then the interval $(0,r)$ in $\Bbb R$ is uncountable, while the set $E=\{d(a,x):x\in A\}$ is only countable, so there is an $s\in(0,a)\setminus E$. Then $B(a,s)$ is clopen, $a\in B(a,s)$, and $b\in A\setminus B(a,s)$, so $A$ is not connected: $B(a,s)$ and $A\setminus B(a,s)$ are disjoint non-empty open subsets of $A$ whose union is $A$.

And you can use that last argument in general to show that a totally disconnected space is not connected.

Title: Disconnected metric space proof


答:
At the time they decided to end the game, if they continued then the odds of a win for A are 50%. For B are 12.5% because it needs to win the next 3 events of coin toss.

We need a pondered average. Since 50% is 4x12.5%, then A takes 4 times the amount B takes.

A takes 4480 while B takes the rest, 1120.

Title: Currency launch probability

Body:
Two individuals, $ A $ and $ B $ will play heads or tails with an '' honest '' coin. They agree to flip the coin $ 5 $ times, and the one who wins in 3 or more rolls wins the game. Each bets $ 2800$. After the first two launches, in which both $ A $ wins, they decide to end the game. From a probabilistic point of view, how should the 5600 dollars be distributed?

Solution: The probability that B will win the next three rolls is $\frac{1}{2^3} = \frac18$. So the dollars should be distributed in a $1:7$ ratio. This means that A will get $4900$ dollars, and B will get $700$ dollars.

Is this solution correct? Why would the ratio be 1: 7? Could someone explain it to me better?


问:
How to get an original function from the limit definition of a derivative?
Say I have
$$\lim_{h\to0} \frac{e^h-1}{h}$$

If $$\frac{d}{dx}(e^x)|_{x=0} =
\lim_{h\to0} \frac{e^{0+h}-e^0}{h},$$

how would I “back engineer” the derivative limit definition to satisfy the expression meaning expression-I equals expression-II. But we’re only given expression-II the limit expression so how do we find the “mystery” expression-I from expression-II.

I basically want to remove the guess work required to satisfy the two expressions, and if there’s even a general “algorithm” to follow?

答:
If I'm understanding your question correctly, it boils down to (1) identifying that a given limit is the derivative of a function $f(x)$ at some point $x=a$, namely

$$f'(a)=\lim_{h\to0}\frac{f(a+h)-f(h)}h$$

and (2) precisely picking out what the function $f(x)$ is supposed to be.

In the given example,

$$\lim_{h\to0}\frac{e^h-1}h=\lim_{h\to0}\frac{e^{\color{red}{0+h}}-e^{\color{red}0}}h=\lim_{h\to0}\frac{f(0+h)-f(0)}h\implies f(x)=e^x\text{ and }a=0$$

and hence this limit is exactly the derivative of $e^x$ at $x=0$. If you know that $(e^x)'=e^x$, then the limit is simply $e$.

So the strategy is to recast the given limit into an expression involving the forward difference $f(a+h)-f(a)$.

Another example:

$$\lim_{h\to0}\frac{(1+h)^{\frac13}-1}h=\lim_{h\to0}\frac{(\color{red}{1+h})^{\frac13}-\color{red}{1}^{\frac13}}h\implies f(x)=x^{\frac13}\text{ and }a=1$$

Then this limit would be $\frac13$, or the derivative $\left(x^{\frac13}\right)'=\frac1{3x^{\frac23}}$ at $x=1$.


答:
The derivative of a function $f$ at a  point $a$ is defined as
$$f'(a)=\lim_{h\to 0}\frac{f(a+h)-f(a)}{h}.$$

Setting $f(x)=e^x$ and $a=0$ this yields
$$\frac{d}{dx}e^x\mid_0 = \lim_{h\to 0}\frac{e^{0+h}-e^{0}}{h}=\lim_{h\to 0}\frac{e^{h}-1}{h}.$$

This would be the solution to your problem.

If I understood you correctly you want to have a step by step derivation, from the limit to the derivative. I don't think that's the aim of the book, it's about observing that these two expressions are equal and not about calculations.

Title: How to get an original function from the limit definition of a derivative?

Body:
Say I have
$$\lim_{h\to0} \frac{e^h-1}{h}$$

If $$\frac{d}{dx}(e^x)|_{x=0} =
\lim_{h\to0} \frac{e^{0+h}-e^0}{h},$$

how would I “back engineer” the derivative limit definition to satisfy the expression meaning expression-I equals expression-II. But we’re only given expression-II the limit expression so how do we find the “mystery” expression-I from expression-II.

I basically want to remove the guess work required to satisfy the two expressions, and if there’s even a general “algorithm” to follow?


问:
Linear Independence and Subspaces

I'm currently looking at problem #2. I wrote $W$ in the form

$$W=a\begin{bmatrix}
2\\ 1\\ 4\end{bmatrix}+b\begin{bmatrix}1\\ 0\\ 1\end{bmatrix}+c\begin{bmatrix}-1\\ 1\\
 1\end{bmatrix}$$

and then I took the determinant of the matrix formed by these vectors, that is,
$$\det\begin{bmatrix}2 & 1 &-1 \\  1&  0& 1\\  4&  1&1 \end{bmatrix}=0$$

Yet the study guide solutions say

$$ W=Col \begin{bmatrix}2 & 1 &-1 \\  1&  0& 1\\  4&  1&1 \end{bmatrix}$$
is a subspace of $\mathbb{R}^3$. I don't understand how it can be if these vectors are not linearly independent as the determinant is zero. What am I missing?

答: The fact that they are not linearly independent does not mean that W is not a subspace. It is only mean that they are not the basis of the subspace - they aren't the minimal set that span w. . In order to show that W is subspace, you only need to take two vector, u and v in w, and show that u+v contains in w.</p>

Title: Linear Independence and Subspaces


答:
You have already written
$W= a.x+b.y+c.z$, where $x=[2~ 1 ~4]^t$ $y= [1~ 0~ 1]^t$ and $z= c[-1~ 1~ 1]^t$, $a,b,c \in \mathbb{R}$.

That simply means $W$ is given by the column space of the mentioned matrix and that is what you guide's solution addresses. Note that column space of the matrix is a subspace of $\mathbb{R}^3$, since the matrix can be thought of a linear transformation from $\mathbb{R}^3$ to $\mathbb{R}^3$ and colum space of the matrix is the range of the linear transformation.

Note that "determinant of matrix is zero" means that the vectors $x$, $y$, $z$ are not linearly independent. However, it does not deny the fact that $W$ is spanned by them. Of course, the set of vectors $\{x,y,z\}$ is not the minimal spanning set of $W$, i.e., not a basis of $W$. If it was, you would have obtained the determinant to be non-zero.

Title: Linear Independence and Subspaces

Body:
I'm currently looking at problem #2. I wrote $W$ in the form

$$W=a\begin{bmatrix}
2\\ 1\\ 4\end{bmatrix}+b\begin{bmatrix}1\\ 0\\ 1\end{bmatrix}+c\begin{bmatrix}-1\\ 1\\
 1\end{bmatrix}$$

and then I took the determinant of the matrix formed by these vectors, that is,
$$\det\begin{bmatrix}2 & 1 &-1 \\  1&  0& 1\\  4&  1&1 \end{bmatrix}=0$$

Yet the study guide solutions say

$$ W=Col \begin{bmatrix}2 & 1 &-1 \\  1&  0& 1\\  4&  1&1 \end{bmatrix}$$
is a subspace of $\mathbb{R}^3$. I don't understand how it can be if these vectors are not linearly independent as the determinant is zero. What am I missing?


问:
Determining information in minimum trials (combinatorics problem)
A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the real exam. After each mock exam the teacher tells the student how many right answers he got, and when the student feels ready, he can pass the real exam. Show that if the student is good at combinatorics he can guess all the answers after only $2^{k}$ mock exams.

For those who prefer a more formal presentation of the problem: if $E=\{1,-1\}^{N}$ we seek $n$ so that for some vectors $v_{1},v_{2}, \ldots, v_{n}\in E$
\begin{align*}
\phi\colon E &\rightarrow \mathbb{N}^{n},\\
v &\mapsto (\langle v,v_{1}\rangle, \langle v,v_{2}\rangle, \ldots, \langle v,v_{n}\rangle)
\end{align*}
is injective. Show that it is possible to find such vectors when $N=k2^{k-1}$ and $n=2^{k}$.

It is possible to use duality to transform again the problem. We seek a $n\times N$ matrix $M$ such that $v\mapsto Mv$ is injective over $E$. If $X$ is the formal polynomial vector $X=(X_{1},X_{2}, \ldots,X_{n})$ then $v\mapsto Mv$ is injective iff $v\mapsto \langle X,Mv \rangle$ also is. But $\langle X,Mv \rangle = \langle M^{T}X, v \rangle$ and it is easily seen that $v\mapsto \langle M^{T}X,v \rangle$ is injective iff the $N$ column vectors $x_{i}$ of $M$ are such that $\sum_{i\in I} x_{i}\neq \sum_{j\in J} x_{j}$ for any two different subsets $I$, $J$ of $\{1,\dots,N\}$.

This problem comes from an olympiad-like contest. The original problem was formulated with 30 questions and the aim was to prove that the student could guess with 24 trials. One of my teachers came up with the result above (which would give 16 trials for 30 questions), but I can't remember his proof or find another one by myself.

I tagged this information theory because some probabilistic arguments show that it is impossible to do better than this asymptotically. More precisely, if we choose the coordinates of the $v$ defined above randomly, then
\begin{equation*}
N =  H(\phi(v))
\leqslant  \sum_{i} H(\langle v,v_{i} \rangle) = nH(B(N,1/2)) \sim (n/2)\log_{2}(N)
\end{equation*}
where $H$ designates entropy. With $N=k2^{k-1}$ we get $n\geqslant c\frac{k2^{k}}{k-1+\log_{2}(k)}\geqslant c2^{k}$ for all $c<1$ and $k$ large enough.

答:
You set up a grid:
3x4 in case k=3 or
9x256 in case k = 9, etc.
In each first mock exam you fill out only one row. The entire row.
In each second (alternate) mock exam you fill out only one column.
You never fill out the same column or row.
Always fill with "yes" or always fill with "no", all your choices, never change once you committed to fill all rows and columns by the same "yes" (or "no") answer.
IN the first example you will fill out 3 rows (each separately) and 4 columns, (each separately) which is fewer the 8.
IN the second example, you fill out 9 rows and 256 columns. That is 265 mock exams, which is fewer than 512. Both cases we fulfilled the "minimum" required exams.
When we guess "wrong" on the mock exam, then we got a "no" (if our choice was to fill out only "Yes"-es in the mock exams.) Simply match up the rows and columns where there is a non-null number of score is given for the given row and the given column by the prof for our faulty answers.

And bob is your uncle.

This is a solution. I am not sure if this constitutes a proof, or how many more steps is required to make this into a proof.

My observation is that the original question of this problem resembles the society board game "Mastermind". This is a simplified version of it, with fewer colours of pegs (if you want to think of this problem that way) but with larger boards, but the same principle applies.


问:
What use is $L^2$-convergence for Fourier series?
I'm working through some notes for my signal processing class and there's something elementary that baffles me. We spent lots of hours and dozens of pages setting up the entire theory of Hilbert spaces in order to define the Fourier series of a square integrable periodic function in terms of the orthogonal basis of exponentials $ e_n(t):[0,2\pi] \to \mathbb{C}: t \to e^{int} $.

Then all of the sudden, out of the blue, the notes assault me with a seemingly unrelated theorem about pointwise convergence of the series, and I find out that pointwise convergence isn't guaranteed by $L^2$-convergence. So my (probably naive) question is: what was all that work good for? What use is $L^2$-convergence if it doesn't guarantee pointwise convergence?

答:
A good question! First, even though $L^2$ convergence does not imply pointwise convergence, Parseval's theorem says that the Fourier series converges in that sense, whether or not pointwise. The standard elementary curriculum does seem to urge us to think that the only reasonable notion of convergence of a sequence or infinite sum of functions is pointwise, but that is toooo naive/optimistic.

So, one point is that various manipulations of Fourier series do indeed give correct results with or without pointwise convergence.

"Not all is lost", also, because "Sobolev space theory" is an $L^2$-based extension of the basic $L^2$ theory which does capture pointwise convergence, if one wants.

But/and a very useful technical virtue of $L^2$ is that it is a Hilbert space, in which a (true) "Dirichlet/minimum" principle holds (as opposed to Banach spaces, such as $C^o[0,1]$, which might seem more natural, but in which the Dirichlet/minimum principle fails violently...) Thus, the $L^2$-Sobolev theory can recover pointwise features (continuity, for example), within a Hilbert space context. A good thing.

But/and, again, yes, it was a shock to me years ago when it finally got through to me that $L^2$ convergence and pointwise convergence (e.g., of Fourier series) were not literally/immediately/provably the same thing. Crazy! Who knew? :)

EDIT: while we're here, as @leslietownes rightly comments, there are results about getting pointwise convergence from $L^2$, namely, Lennart Carleson's result that the Fourier series of an $L^2$ function does converge to it almost everywhere. This is a very difficult theorem.

And, while we're here, Kolmogorov constructed a rather tricky $L^1$ function whose Fourier series diverges everywhere. His example is so crazy that it is not possible to succinctly describe it, and I can't even remember the key mechanism. Something number theoretic, in the vein of Diophantine approximation, if I remember at all correctly... Fun stuff, but not easy.


问:
Prove the inequality $(a+b)(b+c)(a+c)\ge8$ if $a^2+b^2+c^2+abc=4$.
I noted $a=2\cos A,b=2\cos B,c=2\cos C$ because of the identity $\cos^2(x)+\cos^2(y)+\cos^2(z)+2\cos(x)\cos(y)\cos(z)=1$,but the calculations looked really bad, so I gave up. Any another suggestion?

答: You're on the right track in terms of strategy, but the stated inequality is the wrong way round: for example, an isosceles right-angled triangle gives$$a=b=\sqrt{2},\,c=0\implies(a+b)(b+c)(c+a)=4\sqrt{2}<8.$$With your parameterization,$$a+b=2(\cos A+\cos B)=4\cos\tfrac{A+B}{2}\cos\tfrac{A-B}{2}=4\sin\tfrac{C}{2}\cos\tfrac{A-B}{2}$$etc., so$$(a+b)(b+c)(c+a)=64\sin\tfrac{A}{2}\sin\tfrac{B}{2}\sin\tfrac{C}{2}\underbrace{\cos\tfrac{A-B}{2}\cos\tfrac{B-C}{2}\cos\tfrac{C-A}{2}}_{\in[0,\,1]}.$$Applying Jensen's inequality to $\ln\sin\tfrac{x}{2}$ implies $\sin\tfrac{A}{2}\sin\tfrac{B}{2}\sin\tfrac{C}{2}\le\tfrac18$, achieving its maximum for an equilateral triangle.


问:
Calculate Taylor Series function and converges
Calculate the Taylor series of the function $f(x) = 3/x$ about $a = 3$.
Where (if anywhere) does the series converge to $3/x$?</p>

答:
To calculate the Taylor series you need to find the derivatives of the function and evaluate them in the point a=3:

$$\frac{d^nf}{dx^n}=3(-1)^n(n!)x^{-(n+1)}$$

The series is:

$$\sum_{n=0}^{\infty} \frac{(-1)^n}{3^n}(x-3)^n$$

The series converges, if you want to look for uniform convergence you can use the Cauchy-Hadamard criteria but in this case is simple to show that it converges for $x \neq 0$ because that's the only point in which the solution becomes unbounded.


答:
Okay so you got that $W$ is exactly equal to the solution set of this equation.

$$W=a\begin{bmatrix}
2\\ 1\\ 4\end{bmatrix}+b\begin{bmatrix}1\\ 0\\ 1\end{bmatrix}+c\begin{bmatrix}-1\\ 1\\
 1\end{bmatrix}$$

But this is saying that $W$ is equal to the span of those three vectors. Anytime you have the a subset defined by the span of a set of vectors, that subset is a subspace.

Theorem:
Let $W = span\{v_1,..,v_m\}$ be in $\mathbb{R}^n$. Then $W$ is a subspace of $\mathbb{R}^n$

Now, what YOU did was check to see if those vectors are linearly independent. Since $det=0$, they are not linearly independent. That just means that $W$ is not going to be a $3$ dimensional subspace (and so it isn't equal to the whole space, but rather it is a PROPER subspace).

Title: Linear Independence and Subspaces


问:
Define a relation $R$ on $\mathbb{Z}$ by $aRb$ iff $3a - 5b$ is even. Prove $R$ is an equivalence relation and describe equivalence classes.
I think I got most of the proof, but feel free to critique anything you would like :).

First, notice that $aRa$ means $3a - 5a = a(3 - 5) = 2(-a)$. This is even, thus, $R$ is reflexive.

Second we show that $aRb \implies bRa$. Well, $aRb$ means that $3a - 5b$ is even. Then we have $3a - 5b = 2k$ for some integer k. Rearrange like so
$$
\begin{equation} \begin{split}
3a - 5b &= 2k \\
-5b &= 2k - 3a \\
-5b &= 2(k - a) + (-a)
\end{split} \end{equation}
$$
Since, we stated that the LHS and RHS were both even in the beginning and still are (i think?), this forces $a$ and $b$ to be even. Thus, $3b - 5a$ is even because we are dealing with two even numbers. Therefore $bRa$ which means $R$ is symmetric.

Now for transitive. We have show that $(aRb \wedge bRc) \implies aRc$. Since $aRb \wedge bRc$, we have $3a - 5b$ even and $3b - 5c$ even. Note when we add, the sum is even. Observe
$$
(3a - 5b) + (3b - 5c) \\
3a - 2b - 5c \\
2(-b) + (3a - 5c)
$$
$2(-b)$ is even and this forces $3a - 5c$ to be even. Therefore $R$ is transitive. QED.

For the equivalences classes we know that if $a$ is even we have that $b$ must be even. Similarly, if $a$ is odd then $b$ is odd. Therefore, the equivalence classes are the set of odd integers and the set of even integers.

My question is on proving that $R$ is symmetric. Is it mathematically sound?

答:
3a-5b is even implie 3a=5b[2]

a$R$a implie $3a=5a[2]$$\Rightarrow $$-2a=0[2]$ so R is reflexive

a$R$b$\Rightarrow $$3a=5b[2]$$\Rightarrow $$ 9a=15b[2] $$\Rightarrow $$5a=3b[2]$$\Rightarrow $b$R$a

(because $9a=5a[2] $ and $15b=3b[2] $)

So R is symmetry

a$R$b$\Rightarrow $$3a=5b[2]$

and

b$R$c$\Rightarrow $$3b=5c[2]$ that implies $9b=15c[2]$$\Rightarrow $$5b=5c[2] $

So $3a=5c[2]$$\Rightarrow $ a$R$c

So a$R$b and b$R$c $\Rightarrow $a$R$c

So R is Transitive

Finally
After (reflexivity, symmetry, transitivity) we Kan see R is equivalence relation


问:
What is the intergal of $\int {\dfrac{1}{(x^2+9)^2}}\,dx$ with recursive formula?
I used partial integration and I got this:

${\dfrac{x}{(x^2+9)^2}} + 4  $$\int {\dfrac{x^2}{(x^2+9)^3}}\,dx$

According to the recursice formula I should continue like this:

${\dfrac{x}{(x^2+9)^2}} + 4  $$\int {\dfrac{x^2 +9-9}{(x^2+9)^3}}\,dx$

${\dfrac{x}{(x^2+9)^2}} + 4  $$\int {\dfrac{x^2 +9-9}{(x^2+9)^3}}\,dx$ - 4$\cdot 9 $$\int {\dfrac{1}{(x^2+9)^3}}\,dx$

And then end up with something like that:

${\dfrac{1}{2 \cdot 9} \cdot \dfrac{1}{x^2+9} + \dfrac{1}{2 \cdot 27}} arctg{\dfrac{x}{3}}\,$ + C

But I'm sure that I'm doing this wrong or just I'm too confused?

答: You have found the integral of $(x^2+9)^{-3}$ in terms of the integral of $(x^2+9)^{-2}$.  So, instead, integrate $(x^2+9)^{-1}$ by parts


问:
What structure is preserved in a vector space isomorphism?
The definition of an isomorphism is "a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping".

In my linear algebra class, an isomorphism is defined as "a bijective linear transformation." I understand some of the structure that is preserved between the spaces, but is there some exact fixed set of things that are preserved by a bijective linear transformation? (or an isomorphism in general).  Further, before we can say that a bijective linear transformation is an isomorphism, do we not need to prove that all of the structure is actually preserved? I ask this because we seem to just assume that a lot of things are preserved between different vector spaces, but never have we proven that these things are preserved between spaces. Below are a few things that I am a little confused about is they need to be proven or follow from the fact that $T$ is a bijective linear transformation.

Let $T: V \to W$ be an isomorphism.  I understand that since $T$ is linear, scalar multiplication and addition will be preserved. Must it be shown that if there is a linear transformation $A$ in $V$ such that for all $x \in V$, there exists a unique transformation $B$ in $W$ such that $A(x) = T^{-1}(B(T(x))$, or that if $S$ is a basis of $W$ of where $S = (S_1, \dots, S_n)$, then $(T^{-1}(S_1), \dots, T^{-1}(S_n))$ is a basis of $V$?

I'm not exactly sure where this preservation of structure stops, and when I am no longer using the fact that we have an isomorphism, and rather sort of just saying things that are not proven true. Maybe I am not entirely sure what constitutes as structure that needs to be preserved in terms of vector spaces.

Any help clearing up this idea of isomorphism is greatly appreciated.

答:
The structure that is preserved in a vector space isomorphism are exactly the linear relations:
$$
\lambda_1 v_1 + \lambda_2 v_2 + \cdots + \lambda_m v_m = 0 \text{ in } V
\iff
\lambda_1 w_1 + \lambda_2 w_2 + \cdots + \lambda_m w_m = 0 \text{ in } W
$$
An isomorphism $V \to W$ just renames the elements of $V$ into elements of $W$ subject to the condition above.

Make sure you understand that the claim above is equivalent to the standard definition: $T: V \to W$ is an isomorphism iff $T$ is a bijection such that $T(\lambda v)=\lambda T(v)$ and $T(v_1 + v_2) = T(v_1) + T(v_2)$.


问:
Path-connected subsets of Q
It is my understanding that the connected subsets of Q (subset of R containing rational numbers) are all sets that contain one element of Q.

However, I was wondering why this is the case? And further to that, how we can explain that the path-connected subsets of Q are also single elements.

答: Singletons are always path connected by the constant path $f(t)=c$ for some constant $c$. The irrationals are dense in the reals so every two distinct rational numbers have an irrational between them which impedes the path connecting them.

Title: Path-connected subsets of Q


问:
Determine counterclockwise moving
in my app, I let user touch and move to draw an arc. After drawing, I got a set of points. Is there any way to determine that user draw the arc counterclockwise or reverse counter clock wise?</p>

答: The set of points will obviously be stored in an order. Circular array/list or even a plain array. Just compare the coordinates of consecutive points.</p>

Title: Determine counterclockwise moving


Title: What is the intergal of $\int {\dfrac{1}{(x^2+9)^2}}\,dx$ with recursive formula?

Body:
I used partial integration and I got this:

${\dfrac{x}{(x^2+9)^2}} + 4  $$\int {\dfrac{x^2}{(x^2+9)^3}}\,dx$

According to the recursice formula I should continue like this:

${\dfrac{x}{(x^2+9)^2}} + 4  $$\int {\dfrac{x^2 +9-9}{(x^2+9)^3}}\,dx$

${\dfrac{x}{(x^2+9)^2}} + 4  $$\int {\dfrac{x^2 +9-9}{(x^2+9)^3}}\,dx$ - 4$\cdot 9 $$\int {\dfrac{1}{(x^2+9)^3}}\,dx$

And then end up with something like that:

${\dfrac{1}{2 \cdot 9} \cdot \dfrac{1}{x^2+9} + \dfrac{1}{2 \cdot 27}} arctg{\dfrac{x}{3}}\,$ + C

But I'm sure that I'm doing this wrong or just I'm too confused?

Body:
Integrate as follows

\begin{align}
\int {\dfrac{1}{(x^2+9)^2}}\,dx
&= \frac19 \int {\dfrac{1}{x^2+9}}\,dx - \frac19\int {\dfrac{x^2}{(x^2+9)^2}}\,dx\\
 &= \frac19 \int {\dfrac{1}{x^2+9}}\,dx + \frac1{18}\int x\>d({\dfrac{1}{x^2+9}})\\
 &= \frac1{18} \frac x{x^2+9} + \frac1{18}\int {\dfrac{1}{x^2+9}}\,dx\\
 &= \frac1{18} \frac x{x^2+9} + \frac1{54}\tan^{-1}\frac x3+C
\end{align}


问:
$\text{Tot}$ is not computably enumerable
I'm trying to show that $Tot=\{e: \phi_e \text{ is total}\}$ is not c.e.

<s> Suppose that $Tot$ is c.e. Then its semi-characteristic function is computable. Then the following function $\eta$ is computable:$$\eta(x)\uparrow \text{if } x\in Tot\\ \eta(x)\downarrow \text{ if } x\notin Tot$$

Let $U$ be a universal function. Since $\eta$ is computable, there is $p$ such that $$U(p,x)=\eta(x)$$ for all $x$. $Tot$ can be written as $\{e: U(e,-) \text{ is total}\}$ so setting $x=p$ above we have

$$U(p,p)\uparrow \text{ if } U(p,x)\downarrow\text{ for all } x\\ U(p,p)\downarrow \text{ if } U(p,x_0)\uparrow \text{ for some } x_0$$

There's a contradiction in the first line (but not in the second). Is that enough to conclude that $Tot$ is not c.e.? If not, then how to prove the required result properly? </s>

Actually, now that I've written this proof I started to doubt that $\eta$ is computable. In fact, I don't think that it's computable. How to prove the claim then? (One way is to show that $Tot$ is $\Pi_2$-complete, and hence cannot be $\Sigma_1$, but I wanted a direct proof using some kind of diagonilization argument.)

答:
Straightforward proof:

Let $f : \mathbb{N} \to Tot$ be a computable surjection. Then consider the function $g(x) = \phi_{f(x)}(x) + 1$. $g$ is also a computable total function. Therefore, there must exist $n$ such that $\phi_n = g$. Then in particular, there must exist some $x$ such that $\phi_{f(x)} = g$. But in that case, we would have $g(x) = \phi_{f(x)}(x) = \phi_{f(x)}(x) + 1$; contradiction.

Since there is no computable surjection $\mathbb{N} \to Tot$, and since $Tot$ has infinitely many elements, we see that $Tot$ is not computably enumerable.


问:
How can one compute the joint probability of A and B with the information provided?
Let $(A, B)$ be a discrete R.V. (vector) with the set {$(0,0),(0,1),(1,0),(1,1)$}
Their marginal distributions are $A∼Binomial(1, \frac{1}{2})$ and $B∼Bin(1, \frac{1}{2})$. Given that $P(A=B)=0.8$. Find $P(AB = 0)$.

Body:
You have
$
P(A=0,B=0)+P(A=0,B=1) +P(A=1,B=0)+P(A=1,B=1)=1
$
This gives you
$
P(A=0,B=1) +P(A=1,B=0) +P(A=B)=1,
$
thus using $P(A=B)=0.8$,
$$P(A=0,B=1) +P(A=1,B=0)=0.2.$$
Also $0.5=P(A=1)= P(A=1,B=1)+P(A=1,B=0)$ and $0.5=P(B=1)= P(A=0,B=1)+P(A=1,B=1)$, summing the last two equations get $1=2P(A=1,B=1)+P(A=1,B=0)+P(A=0,B=1)$, plug in the value $P(A=0,B=1) +P(A=1,B=0)=0.2$ and get $P(A=1,B=1)=0.4$. Now $$P(AB=0)=1-P(A=1,B=1)= 0.6.$$


答:
It is, perhaps, easier to show that the only connected components of $\mathbb{Q}$ are the singletons. This can be done via a contradiction:

Assume that $C$ is a connected subset of $\mathbb{Q}$ with two distinct elements, say, $p,q\in C$. We may assume that $p<q$. Then let $x$ be an irrational number with $p<x<q$. Then the two sets $(-\infty,x)\cap C$ and $(x,\infty)\cap C$ form a separation of $C$, and this contradicts the fact that $C$ was connected. Therefore, if $C$ is connected, it can only contain a single element.

This line of reasoning extends to the path connected case: namely, any path connecting $p$ to $q$ must go through the point $x$.

Title: Path-connected subsets of Q

Body:
It is my understanding that the connected subsets of Q (subset of R containing rational numbers) are all sets that contain one element of Q.

However, I was wondering why this is the case? And further to that, how we can explain that the path-connected subsets of Q are also single elements.


问:
Characterizing elements of a collection closed under countable intersections
Suppose we have a collection $\mathcal{E}$ containing some subsets of a nonempty set $E$. Assume $E \in \mathcal{E}$. Define $\hat{\mathcal{E}}$ to be the smallest collection containing elements of $\mathcal{E}$ and closed under countable intersections. It is clear that $\hat{\mathcal{E}}$ is simply the intersection of all collections containing elements of $\mathcal{E}$ and closed under countable intersections.

What can we say about the elements of $\hat{\mathcal{E}}$?

My hunch is that if $A \in \hat{\mathcal{E}}$, then $A$ is a countable intersection of elements of $\mathcal{E}$. I am unable to prove or disprove this claim though.

If the claim is false, then when can we say the above property holds? If $\mathcal{E}$ is countable, then the above property can be shown to be true.

答:
Your conjecture is correct.

Let $\mathscr{C}$ be the family of all countable intersections of members of $\mathscr{E}$, and let $\mathscr{A}$ be a countable subset of $\mathscr{C}$. Then for each $A\in\mathscr{A}$ there is a countable $\mathscr{E}_A\subseteq\mathscr{E}$ such that $A=\bigcap\mathscr{E}_A$. Let $\mathscr{B}=\bigcup_{A\in\mathscr{A}}\mathscr{E}_A$; then $\mathscr{B}$ is the union of countably many countable subsets of $\mathscr{E}$, so $\mathscr{B}$ is a countable subset of $\mathscr{E}$, and $\bigcap\mathscr{B}\in\mathscr{C}$. Finally,

$$\bigcap\mathscr{B}=\bigcap_{A\in\mathscr{A}}\bigcap\mathscr{E}_A=\bigcap_{A\in\mathscr{A}}A=\bigcap\mathscr{A}\,,$$

so $\bigcap\mathscr{A}\in\mathscr{C}$, and $\mathscr{C}$ is closed under countable intersections.

Now let $\mathfrak{C}$ be the collection of all families of subsets of $E$ that are closed under countable intersection and contain $\mathscr{E}$; we’ve just shown that $\mathscr{C}\in\mathfrak{C}$. If $\mathscr{F}\in\mathfrak{C}$, then $\mathscr{E}\subseteq\mathscr{F}$, and $\mathscr{F}$ is closed under countable intersection, so $\mathscr{C}\subseteq\mathscr{F}$. Thus, $\mathscr{C}\subseteq\bigcap\mathfrak{C}\subseteq\mathscr{C}$, so $\mathscr{C}=\bigcap\mathfrak{C}=\hat{\mathscr{E}}$.


答:
Let $\mathcal{E}'$ be the collections of all countable intersections of elements of $\mathcal{E}$. We would like to show that $\mathcal{E}' = \hat{\mathcal{E}}$.

By definition $\mathcal{E}'$ contains all elements on $\mathcal{E}$ and is closed under countable intersections because a countable intersection of countable intersections is still a countable intersection. Since $\hat{\mathcal{E}}$ is the smallest collection with these properties, we have $\hat{\mathcal{E}} \subseteq \mathcal{E}'$. But $\hat{\mathcal{E}}$ contains all elements of $\mathcal{E}$, and hence must contain all countable intersections of elements in $\mathcal{E}$, so $\mathcal{E}' \subseteq \hat{\mathcal{E}}$, thus we have shown $\mathcal{E}' = \hat{\mathcal{E}}$.

Title: Characterizing elements of a collection closed under countable intersections

Body:
Suppose we have a collection $\mathcal{E}$ containing some subsets of a nonempty set $E$. Assume $E \in \mathcal{E}$. Define $\hat{\mathcal{E}}$ to be the smallest collection containing elements of $\mathcal{E}$ and closed under countable intersections. It is clear that $\hat{\mathcal{E}}$ is simply the intersection of all collections containing elements of $\mathcal{E}$ and closed under countable intersections.

What can we say about the elements of $\hat{\mathcal{E}}$?

My hunch is that if $A \in \hat{\mathcal{E}}$, then $A$ is a countable intersection of elements of $\mathcal{E}$. I am unable to prove or disprove this claim though.

If the claim is false, then when can we say the above property holds? If $\mathcal{E}$ is countable, then the above property can be shown to be true.


问:
Vector Calculus - Curl of Vector
I'm asked to prove the following identity, using index notation:

$(\nabla\times A)\times A=A \cdot\nabla A - \nabla(A \cdot A)$

However, when I work it out, I find that the actual solution should be:

$(\nabla\times A)\times A=A \cdot\nabla A - \frac{1}{2}\nabla(A \cdot A)$

Am I missing something, or is the book wrong?

答:
There is a nice identity for smooth vector fields: $\newcommand{\b}{\boldsymbol}$

$$
\nabla (\b{u}\cdot \b{v}) = (\b{u}\cdot \nabla) \b{v} + (\b{u}\cdot \nabla) \b{v} - (\nabla \times\b{u})\times\b{v} - (\nabla \times\b{u})\times\b{v} .\tag{1}
$$

For a component wise proof like robjohn gave, you can check Balanis's book. A more physical and geometrical proof would be using Feynman subscript notation:
$$
\nabla(\b{u} \cdot \b{v})=  \nabla_{\b{u}}(\b{u}  \cdot \b{v}) +  \nabla_{\b{v}} (\b{u} \cdot \b{v}) ,
$$
where the notation $\nabla_{\b{u}}$ means the gradient is applied only on $\b{u}$ and we keep $\b{v}$ fixed.

Geometrically, $\nabla_{\b{u}}(\b{u}  \cdot \b{v}) $ can be decomposed into the normal derivative and the tangential derivative along $\b{v}$:
$$
 \nabla_{\b{u}}(\b{u}  \cdot \b{v}) = (\b{v}\cdot\nabla)\b{u}-  (\nabla \times \b{u})\times \b{v} ,
$$
hence (1) holds.

Now in your case $\b{u} = \b{v} = \b{A}$:
$$
\nabla (\b{A}\cdot \b{A}) = (\b{A}\cdot \nabla) \b{A} + (\b{A}\cdot \nabla) \b{A} - (\nabla \times\b{A})\times\b{A} - (\nabla \times\b{A})\times\b{A},
$$
thus
$$
(\nabla \times\b{A})\times\b{A} = (\b{A}\cdot \nabla) \b{A} - \frac{1}{2}\nabla (\b{A}\cdot \b{A}) .
$$

Title: Vector Calculus - Curl of Vector


问:
Show that the sequence $5, 12, 19, 26, ...$ contains no terms of the form $2^n$ or $2^n-1$.
Show that the sequence $5, 12, 19, 26, ...$ contains no terms of the form $2^n$ or $2^n-1$.

I know that this is an arithmetic progression, $a_n=7n-2$. In order to show what is asked I tried setting $7n-2=2^n$ and $7n-2=2^n-1$ and tried to show that either no $n$ satisfies either equation or a contradiction arises, but I'm having a hard time. I have a feeling this problem is really simple too. For $7n-2=2^n$ I found that $n$ needs to be even and for $7n-2=2^n-1$ I found that $n$ needs to be odd. I also think that this approach might not be valid. Any hints or solutions are greatly appreciated.

答:
Note that for all $n$, $2^n$ must be equivalent to either $2$, $4$, or $1$ mod 7. This can be shown by induction on $n$.

And therefore, $2^n - 1$ is equivalent to either $1$, $3$, or $0$ mod 7.

But elements of the sequence $a$ are equal to $5$ mod 7. So $2^n$ and $2^n - 1$ can never be elements of this arithmetic sequence.


问:
Finding the coefficient of $x^2$ in an expansion
I was given this question as a practise assignment and I am unsure of my answer.

The coefficient of $x^2$ in the expansion of $(x+\frac{1}{ax})^8$ is 7. Find the possible value of $a$.

I did $(x+\frac{1}{ax})^8$ = $(x (1+\frac{1}{ax^2}))^8$

Given my answer, does that mean that $a=7$?

Edit: Thank you for everyone's help! I think I understand it a little bit now. I will have to review this question again and practise more.

答:
hint

$$(x+\frac{1}{ax})^2=x^2+\frac{1}{a^2x^2}+\frac{2}{a}$$

So, you just need to find the coefficient of $ X $ in the expansion

$$(X+\frac{1}{a^2X}+\frac{2}{a})^4$$


答: In addition to paul's answer, one thing to keep in mind is that Hilbert spaces are typically meaningless when it comes to function values at individual points. An often glanced over fact is that if you take a function $f\in L^2$ and modify it at a single point $x_0$ calling the result $g$, then $\|f-g\|_2=0$. More generally, the elements of $L^2$ are representatives of the equivalence relation $f\equiv g$ defined by $\|f-g\|_2=0$. This can also be expressed in terms of measure theory, in that $\|f-g\|_2=0$ iff $f$ and $g$ differ on a set of measure 0. So, when speaking about convergence in these spaces, typically the best you can do is almost-everywhere convergence, and not point-wise.

Title: What use is $L^2$-convergence for Fourier series?

Body:
I'm working through some notes for my signal processing class and there's something elementary that baffles me. We spent lots of hours and dozens of pages setting up the entire theory of Hilbert spaces in order to define the Fourier series of a square integrable periodic function in terms of the orthogonal basis of exponentials $ e_n(t):[0,2\pi] \to \mathbb{C}: t \to e^{int} $.

Then all of the sudden, out of the blue, the notes assault me with a seemingly unrelated theorem about pointwise convergence of the series, and I find out that pointwise convergence isn't guaranteed by $L^2$-convergence. So my (probably naive) question is: what was all that work good for? What use is $L^2$-convergence if it doesn't guarantee pointwise convergence?


答: Set isomorphisms are just bijective functions and you can think of them as a relabeling of their elements. Algebraic isomorphisms are a relabeling that also map the binary operations in a way that allows you to do the algebra in either set and translate back and forth between them. For vector spaces this will look like $f(x+y)=f(x)+f(y)$ and $f(cx)=cf(x)$ where the addition and multiplication on both sides of the equations are each done in their own space. They can be entirely different in their computational properties but the isomorphic mapping keeps them compatible with each other. Linear transformations in general are homomorphisms and bijective linear transformations are isomorphism. They just use different terminology for historical reasons just as the nullspace is a linear version of the kernel of a homomorphism.

Title: What structure is preserved in a vector space isomorphism?

Body:
The definition of an isomorphism is "a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping".

In my linear algebra class, an isomorphism is defined as "a bijective linear transformation." I understand some of the structure that is preserved between the spaces, but is there some exact fixed set of things that are preserved by a bijective linear transformation? (or an isomorphism in general).  Further, before we can say that a bijective linear transformation is an isomorphism, do we not need to prove that all of the structure is actually preserved? I ask this because we seem to just assume that a lot of things are preserved between different vector spaces, but never have we proven that these things are preserved between spaces. Below are a few things that I am a little confused about is they need to be proven or follow from the fact that $T$ is a bijective linear transformation.

Let $T: V \to W$ be an isomorphism.  I understand that since $T$ is linear, scalar multiplication and addition will be preserved. Must it be shown that if there is a linear transformation $A$ in $V$ such that for all $x \in V$, there exists a unique transformation $B$ in $W$ such that $A(x) = T^{-1}(B(T(x))$, or that if $S$ is a basis of $W$ of where $S = (S_1, \dots, S_n)$, then $(T^{-1}(S_1), \dots, T^{-1}(S_n))$ is a basis of $V$?

I'm not exactly sure where this preservation of structure stops, and when I am no longer using the fact that we have an isomorphism, and rather sort of just saying things that are not proven true. Maybe I am not entirely sure what constitutes as structure that needs to be preserved in terms of vector spaces.

Any help clearing up this idea of isomorphism is greatly appreciated.


答:
Let $\mathcal{E}'$ be the set of countable intersections of members of $\mathcal{E}$.

Facts: $\mathcal{E} \subseteq \mathcal{E}'$ as $\{E\}$ is a countable (even finite) subcollection of $\mathcal{E}$ and its intersection is $E$; $\mathcal{E}'$ is closed under countable intersections. (uses that a countable union of countable subfamilies is still countable).

As $\hat{\mathcal{E}}$ is the minimal collection with those properties, $\hat{\mathcal{E}} \subseteq \mathcal{E}'$, so your property holds.
The other inclusion is also true: if $\mathcal{E}' \ni E' = \bigcap_n E_n$ is a countable intersection of members of $\mathcal{E}$, then as $E_n \in \hat{\mathcal{E}}$ and the latter collection is closed under countable intersections, $\mathcal{E}' \subseteq \hat{\mathcal{E}}$ and we have equality.


问:
How to extend the 1-d z-transform, describing a function on the unit circle, to two dimensions to describe a function on the unit sphere?
I'm an electrical engineer with a background in digital signal processing. I know the one-dimensional Z-transform as a tool to describe discrete-time signals/sequences. For instance, if a discrete-time sequence $h(k), k \in \mathbb{Z}$ is given, its Z-transform is given by
$$
H(z) = \sum_{k=-\infty}^{\infty} h(k) z^{-k}.
$$
Neatly, the discrete-time Fourier transform (DTFT) can be found by substituting $z = e^{j \omega}$. I recently found that a Z-transform (and Laplace transform for the continuous case) can be defined as an expected value, but I have not understood this completely yet. Frequently, Z-transforms are represented by a rational function
$$
H(z) = \frac{ A(z) }{B(z)} = H_0 \frac{ \prod_i \left( z - z_{0,i} \right) }{\prod_j \left( z - z_{\infty,j} \right)},
$$
where $z_{0,i}$ describe the zeros and $z_{\infty,j}$ describe the poles.

If I wanted to describe a complex-valued function on the unit circle, $g: \mathbb{S}^1 \rightarrow \mathbb{C}$, I could perfectly describe it via the zeros and poles of a Z-transform.

Now I would like to extend this concept in order to describe a function on the unit sphere, $f: \mathbb{S}^2 \rightarrow \mathbb{C}$, instead of on the unit circle. I have complex-valued data (measurements of the function) on a very dense grid on the sphere, where each point is specified by two angles, e.g., azimuth and elevation. My question is if there is a higher-dimensional version of the Z-transform which I could use for this purpose. Or how could I define it? I would like to obtain a representation using poles and zeros again because that seems to be suitable for my application. I suspect that the poles and zero would then lie inside or outside the unit sphere.

2-D Z-transforms are used in image processing. However, the two dimensions are separable for rectangular images. I don't that would be the case for the two-dimensional extension of the Z-transform I look for here because the dimensions on the sphere are not separable but "interconnected".

Thank you for your help.

答:
Well, I suppose you could start with this formulation:

$$H(z, w) = \sum_{l=-\infty}^\infty \sum_{k=-\infty}^\infty h[k,l] z^{-k} w^{-l}$$

With the following substitutions for the unit sphere:

$$ z=e^{j\omega}$$
$$ w = e^{j\xi} \text{ or } w= e^{j\xi/2}$$

How were you actually going to specify the function on the unit sphere?  I assume you need a function of 2 angles unless you have a high degree of symmetry.


答:
Write the expression as ${1 \over a^8 x^8} (1+a x^2)^8$ and find the coefficient of $x^{10}$ in $(1+a x^2)^8$.

Use the binomial theorem to compute the coefficient of $x^{10}$ in $(1+a x^2)^8$. Hint: It is the 5th coefficient.

Call this expression $E$ (it will be a formula involving $a$ and some numbers). Then the coefficient of $x^{2}$ in the original expression is ${1 \over a^8}E$.

Then solve the expression ${1 \over a^8}E = 7$ for $a$. (You will need to replace $E$ by the expression you computed first before solving.)

Title: Finding the coefficient of $x^2$ in an expansion

Body:
I was given this question as a practise assignment and I am unsure of my answer.

The coefficient of $x^2$ in the expansion of $(x+\frac{1}{ax})^8$ is 7. Find the possible value of $a$.

I did $(x+\frac{1}{ax})^8$ = $(x (1+\frac{1}{ax^2}))^8$

Given my answer, does that mean that $a=7$?

Edit: Thank you for everyone's help! I think I understand it a little bit now. I will have to review this question again and practise more.


答: Hint: Consider powers of $2 \bmod{7}$ (i.e. remainders when divided by $7$). What pattern do you notice?

Body:
Show that the sequence $5, 12, 19, 26, ...$ contains no terms of the form $2^n$ or $2^n-1$.

I know that this is an arithmetic progression, $a_n=7n-2$. In order to show what is asked I tried setting $7n-2=2^n$ and $7n-2=2^n-1$ and tried to show that either no $n$ satisfies either equation or a contradiction arises, but I'm having a hard time. I have a feeling this problem is really simple too. For $7n-2=2^n$ I found that $n$ needs to be even and for $7n-2=2^n-1$ I found that $n$ needs to be odd. I also think that this approach might not be valid. Any hints or solutions are greatly appreciated.


问:
How does the symmetric group act on tuples?
Given a set $X$, I've seen people write the action of a permutation $ \sigma \in S_{n}$ on an $n$-tuple of elements of $X$ as
$$ \;\; \sigma (x_{1},...,x_{n})=(x_{\sigma^{-1}(1)},...,x_{\sigma^{-1}(n)}). \;\;$$
But this does not seem to me to give a left action of $S_{n}$ on $n$-tuples, since
$$\sigma(\tau(x_{1},...,x_{n}))=\sigma(x_{\tau^{-1}(1)},...,x_{\tau^{-1}(n)})=(x_{\sigma^{-1}\tau^{-1}(1)},...,x_{\sigma^{-1}\tau^{-1}(n)})$$
is not in general equal to
$$(\sigma \tau)(x_{1},...,x_{n})=(x_{(\sigma \tau)^{-1}(1)},...,x_{(\sigma \tau)^{-1}(n)})=(x_{\tau^{-1}\sigma^{-1}(1)},...,x_{\tau^{-1}\sigma^{-1}(n)}).$$

On the other hand, if we don't write out symbols, but think of a tuple as a map from
the $n$-element set $\{1,...,n\}$ to $X$, then the first formula seems to make sense:
the $\sigma^{-1}$ comes from precomposing with the right action of $S_{n}$ on the set $\{1,...,n\}$ determined by the left action of $S_{n}$ on $\{1,...,n\}$, where we use the convention that functions act on the left of elements.

So the question is whether the first formula defines a left or a right action on tuples.
The symbols seem to suggest a right action while interpreting tuples as maps seems to suggest a left action. I think that in my formulas above I must be getting confused.

答:
Your computation is wrong. You read $\sigma (x_1,...,x_n)=(x_{\sigma^{-1}(1)},...,x_{\sigma^{-1}(n)})$ as if the index $i$ is an atttribute of the entry $x_i$, and as if $\sigma$ acts on individual entries (leaving them in place!) by applying $\sigma^{-1}$ to the attribute. The way it is written, that interpretation is tempting, but if you look at what you really want to describe it is clear that this cannot be right.

The index is a selection key that tells you which one of the values is chosen; the values themselves are not affected at all. So you should interpret the rule as a follows: the first component of the result is the one that was previously at position $\sigma^{-1}(1)$, and more generally the component at position$~i$ of the result  is the one that was previously at position $\sigma^{-1}(i)$. Therefore one gets
$$
 \sigma(x_{\tau^{-1}(1)},...,x_{\tau^{-1}(n)})=(x_{\tau^{-1}(\sigma^{-1}(1))},...,x_{\tau^{-1}(\sigma^{-1}(n))}),
$$
because the component that is in position $\sigma^{-1}(1)$ in the argument tuple on the left is $x_{\tau^{-1}(\sigma^{-1}(1))}$: more generally the component that is in position $k$ on the left is $x_{\tau^{-1}(k)}$, and with $k=\sigma^{-1}(i)$ this gives that the component that is in position $\sigma^{-1}(i)$ on the left is $x_{\tau^{-1}(\sigma^{-1}(i))}$, which is the value that goes to position$~i$ on the right.

See also this answer.