问:
Solving anagrams using math.
On Hacker Rank, there is Sherlock and Anagrams coding test.

The opening statement of the coding test is:

Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string. Given a string, find the number of pairs of substrings of the string that are anagrams of each other.

There is this example:

kkkk

There are 6 anagrams of the form [k,k] at positions [[0],[1]], [[0],[2]], [[0],[3]], [[1],[2]],[[1],[3]] and [[2],[3]]

There are 3 anagrams of the form [kk,kk] at positions [[0,1],[1,2]],[[0,1],[2,3]] and [[1,2],[2,3]]

There are 1 anagrams of the form of [kkk,kkk] at positions [[0,1,2],[1,2,3]]

Equally 10 anagrams.

Can this be solved with one or more mathematical equations?

From Googling around, I have found this reference that this is a simple combinatoric question with a known answer: binominal coefficient of $(n,2)$ which is $n(n-1)/2$.

I am not a mathematician so can someone tell me if it is possible please and show the maths equations involved?

答:
One way to think of this is to realize that in order for two substrings to be an anagram of each other, they must be the same length. Given a string of length $n$, the number of substrings of length $k$ is precisely $n-k+1$ as Phicar pointed out.

It would not be hard to write code to create a list of these substrings of a given length. You'd want to do this for all possible $k = 1,...,n-1$. For a fixed $k$, once you have the list of substrings of that length, you're looking for anagrams so order of the elements in the string no longer matters.

So you can sort the elements in each substring. Then all you care about it how many of those pairs are the same. To get all the anagram pairs you just need to select pairs of these sorted substrings that are the same. This gives you the factorial you mentioned. In general $\binom{n}{2}$ gives you the number of unique subsets of size $2$ from a set of size $n$, so it's exactly the number of pairs of elements in a set of size $n$. As an example consider

$aababa$

First we compile the list of all substrings of length $3$, there are $6-3+1 = 4$ such substrings.

$\{aab, aba,bab,aba\}$

Now you're looking for anagrams, so you can sort (by assigning each letter an arbitrary number, or order) each substring since order doesn't matter, to get

$\{aab,aab,abb,aab\}$

You can then sort this list

$\{aab,aab,aab,abb\}$.

This is now the key step that differs from your example. You now want to choose all the pairs from this list that are the same. In your example they were always the same, in this example the first three are the same, then the last is different. So the number of anagram pairs of length $3$ is $\binom{3}{2} + \binom{1}{2} = 3$.

You could write a program that would do this for a fixed $k$, then sum over $k = 1,...,n-1$ to get the final answer. No step of the code would be particularly demanding.

In the example you gave, every substring of the same length is an anagram of another substring of the same length. So if we follow the above process we for $k = 3$ we get

$\{kkk,kkk\}$.

You then want to choose all pairs that are the same, in your case this is always choosing all pairs from this set which is $\binom{4-3+1}{2} =1$. As you noticed. The above process is the generalization.

So in your case the number of anagram pairs is

$\sum_{k=1}^{n-1} \binom{n-k+1}{2}$.

Where $n$ is the number of copies of the same letter. Each summand amounts to the anagram pairs of length $k$. In general, a nice equation may not be possible because it will heavily depend on the word you start with. But some fun and not overly complicated code would produce a quick answer.

Title: Solving anagrams using math.


问:
Variance of Poisson distributed variables $\leq1$
If $Z_n$ is the number of sample observations of $X\leq1$ where $X \sim \text{Poisson}(\mu)$, then what is $\text{Var}(\frac{Z_n}{n}$)?

答:
Hints:

$\text{Var}(Z_n/n) = \frac{1}{n^2} \text{Var}(Z_n)$

$Z_n$ can be written as $I_1 + I_2 + \cdots + I_n$ where $I_j$ is a random variable that equals $1$ if $X_j \le 1$, and equals $0$ otherwise.

If $I_1, \ldots, I_n$ are independent then $\text{Var}(I_1 + \cdots + I_n) = \text{Var}(I_1) + \cdots + \text{Var}(I_n)$.

ContentLicense: CC BY-SA 4.0


问:
Finding the last $17$ digits of $1707 \uparrow \uparrow 1783$.
The objective is to find the last $17$ digits of : $1707 \uparrow \uparrow 1783$. In other words:

$$
1707 \uparrow \uparrow 1783 \pmod{10^{17}}
$$

where $\uparrow \uparrow$ represents tetration or repeated exponentiation.

I have thought of a process that goes like this:

Find $k$ such that:

$$
1707^{k} \equiv 1 \pmod{10^{17}}
$$

Since $\text{gcd}(10^{17}, 1707) = 1 \longrightarrow k = \varphi(10^{17}) = 4 \cdot 10^{16}$

Store that $k$ and repeat step $1$ for $\pmod{k}$.

After $51$ iterations, $k$ will be continuously $\varphi(1) = 1$ and there's no point in going further.

However I cannot think how to use these $51$ values of $k$ to yield the result. Can one elaborate on how to continue or suggest another method?

答:
For reference the number $1707 \uparrow \uparrow 1783$ uses Knuth's up-arrow notation for tetration. For every $n\in\Bbb{N}$, the number $1707\uparrow\uparrow n$ is the $n$-th term in the sequence $(s_n)_{n\in\Bbb{N}}$ defined by $s_0=1$ and $s_{n+1}=1707^{s_n}$.

To determine the remainder of $s_{1783}=1707 \uparrow \uparrow 1783$ after division by $10^{17}$ we repeatedly use Euler's theorem, which tells us that if $s_{1782}\equiv t_0\pmod{\varphi(10^{17})}$ then
$$s_{1783}=1707^{s_{1782}}\equiv1707^{t_0}\pmod{10^{17}}.$$
Repeating the same argument we see that, if $s_{1782-k}\equiv t_k\pmod{\varphi^k(10^{17})}$ then
$$s_{1783-k}=1707^{s_{1782-k}}\equiv1707^{t_k}\pmod{\varphi^{k-1}(10^{17})}.$$
Of course for positive integers $a$ and $b$ we have $\varphi(2^a5^b)=2^{a+1}5^{b-1}$,
so
$$\varphi^k(10^{17})=\begin{cases}
2^{17+k}5^{17-k}&\text{ if }k\leq17,\\
2^{51-k}&\text{ if }17\leq k\leq51,\\
1&\text{ if }k\geq51\end{cases},$$
and hence we may take $t_{50}=1$ as $\varphi^{50}(10^{17})=2$ and $s_{1732}\equiv1\pmod{2}$. As $\varphi^{49}(10^{17})=4$ it follows that
$$s_{1733}=1707^{s_{1732}}\equiv1707^1\equiv3\pmod{4},$$
and so we may take $t_{49}=3$. Repeating then yields
\begin{eqnarray*}
t_{49}=s_{1734}&=&1707^{s_{1733}}&\equiv&1707^3&\equiv&3^3\equiv3&\pmod{8},\\
t_{48}=s_{1735}&=&1707^{s_{1734}}&\equiv&1707^3&\equiv&11^3\equiv3&\pmod{16},\\
\vdots\\
t_{18}=s_{1765}&=&1707^{s_{1765}}&\equiv&1707^{5418148179}&\equiv&14008082771&\pmod{2^{34}},
\end{eqnarray*}
and now repeat a few more times to compute $t_0=s_{1783}\pmod{10^{17}}$.


问:
a probability/ random walk brain teaser
A random walk $S_n = X_1+\cdots+X_n$ with independent and identically distributed steps $X_i$'s.

Assume $X_i$ is uniform distributed on integer values $\{1,2,3,\cdots, L\}$, i.e $P(X_i = l) = \frac{1}{L}$ for $l\in\{1,2,3,\cdots, L\}$.

Now consider the path $S_n, n\in\mathbb{N}$, i.e each path will take infinite steps and approach to $+\infty$. Let $p_m = P(\text{the path of the random walk path reaches integer m})$

Does $\lim_{m\rightarrow\infty} p_m$ exist? If it does, then what's the value of it?

答:
This is an elaboration of Ross's answer.  We can write $$\begin{bmatrix}p_{m+1}\\p_{m}\\\vdots\\\vdots\\p_{m+2-L}\end{bmatrix}=\begin{bmatrix}
\frac1L&\frac1L&\frac1L&\dots&\frac1L\\
1&0&0&\dots&0\\
0&1&0&\dots&0\\
\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&\dots&1&0
\end{bmatrix}
\begin{bmatrix}p_{m}\\p_{m-1}\\\vdots\\\vdots\\p_{m+2-L}\end{bmatrix}$$

Let $P$ be the $L\times L$ matrix in the above equation.  Then we are interested in $$\lim_{n\to\infty}P^nV$$ where $V$ is the initial vector, with a $1$ in the first row, and $0$ in all the other rows.

Now, $P$ is the transition matrix of an $L$-state Markov chain.  If the chain is in state $1$, it chooses the next state uniformly at random.  If it is in state $k>1$ it moves to state $k-1$.

It's not hard to guess the stationary probabilities.  Let $q_k$ be the stationary probability that the chain is in state $k$, for $k=1,\dots,L$.  The chain is in state $L-1$ if either it just jumped to that state or it jumped to state $L$ at the previous step.  Thus, $q_{L-1}=2q_L$.  Similarly, $q_{L-2}=3q_L$, and so on.  We have $$1=\sum_{k=1}^Lq_k=\sum_{k=1}^Lkq_L\implies q_L=\frac2{L(L+1)}$$ One can easily verify that these are indeed the stationary probabilities.  Then, $$\lim_{n\to\infty}P^n=\begin{bmatrix}
q_1&q_2&\dots&q_L\\
q_1&q_2&\dots&q_L\\
\vdots&\vdots&\dots&\vdots\\
q_1&q_2&\dots&q_L\\
\end{bmatrix}$$ and each entry of $\lim_{n\to\infty}P^nV$ is $$q_1=Lq_L=\frac2{L+1}$$

Title: a probability/ random walk brain teaser


问:
Given a convex set $S\subset\mathbb{R}^2$ of unit area, how small of a quadrilateral can we inscribe it in?
Every bounded convex planar body $S$ of area $A$ can be inscribed in a triangle of area at most $2A$, with the upper bound attained by the parallelograms. See Wolfram MathWorld for citations.

What constant do we obtain for quadrilaterals? Obviously, we can guarantee an upper bound of $2$ by the above result. In fact, one can bound the area by $2$ just in the case of rectangles, by placing the sides parallel or orthogonal to the diameter of $S$.

Conversely, the circle provides a lower bound of $4/\pi\approx 1.273$. I think the regular hexagon may give $A=4/3\approx 1.333$ by lining up the sides of the quadrilateral with four sides of the hexagon, but I haven't proven this is optimal for the hexagon.

The answer in the worst case has to be strictly less than $2$, as the only shapes that attain the bound in the triangular case allow for $A=1$ in the quadrilateral case. One might worry about a series of shapes approaching but never attaining this bound, but the Blaschke selection theorem guarantees this will not happen (because we can use affine transformations to restrict our attention to a bounded region).

In the event that the quadrilateral case is solved, I'm curious about the general case of $k$-gons for all $k\ge3$ (both our best proven upper bounds, and the hardest-to-inscribe known shapes that approach this bound - I would be surprised if these coincide for large $k$).

答:
Even for quadrilateral, it is probably still an open problem.

For any convex region $K$ with unit area, let

$C_n(K)$ be a circumscried $n$-gon of $K$ with minimum area.

$c_n = \sup\limits_{K}\verb/Area/(C_n(K))$

According to a 2009 paper Circumscribed Polygons of Small Area by Dan Ismailescu,
$$\frac{3}{\sqrt{5}} \le c_4 \le \sqrt{2}$$
The lower bound $\frac{3}{\sqrt{5}}$ is attained by a regular pentagon.
In $1983$, Kuperberg has asked the question whether  $c_4 = \frac{3}{\sqrt{5}}$. As least up to $2013$, this has not been settled.

According to above paper, we also have

$c_n \le \sec\frac{\pi}{n}$ for $n \ge 3$

$c_n \le \frac{n-2}{\pi} \tan\frac{\pi}{n-2}$ for $n \ge 5$

The first bound was proved in above paper, it beat the second bound for $5 \le n \le 11$. The second bound was proved by Fejes Tóth in 1940s.


问:
Boolean algebra: why does the distributive property not make intuitive mathematical sense?
I'm trying to understand the distributive law of Boolean algebra by relating it to what I know from ordinary algebra, and it seems to only work for one form of the law.

Ordinary algebra:

$x(y+z) = xy + xz$

This holds true for the first part of the distributive law.

Ordinary algebra:

$x + (yz)$

It's just that. I don't see any way of simplifying this more.

But in Boolean Algebra:

$x + (yz) = x\vee (y \wedge z) = (x\vee y) \wedge (x\vee z) = (x+y)(x+z)$

And in ordinary algebra, if you expand this, it's:

$xx+xz+xy+yz$

Could someone please help me understand this? Am I wrong in trying to relate ordinary algebra to Boolean algebra? Subquestion: if I am wrong in trying to make this connection, why?

答:
It looks weird to you because of the convention of two variables side-by-side meaning "multiply".

First, rewrite the boolean multiplicative (AND) distributive rule, the "x(y+z) = xy + xz" one that looks normal to you, as follows:

x * (y + z) = (x * y) + (x * z)

Now, you can see that the boolean additive (OR) distributive rule is exactly the same in form as the multiplicative one above, just with the "+" and "*" symbols swapped. It looks like this:

x + (y * z) = (x + y) * (x + z)

This should clear up why these two distributive properties are really the same property. Also, don't forget that the "+" here does not mean add. Boolean AND (*) is more similar to our familiar arithmetic multiplication than boolean OR (+) is to arithmetic addition. You can see this by the fact that all the statements made by the truth table for AND (*) are also valid in arithmetic, using "*" to mean multiply. This is not true for OR (+), as 1 + 1 does not equal 1 in ordinary arithmetic.

See what I mean about the boolean truth tables:

0 * 0 = 0  ----->  true in boolean and arithmetic

0 * 1 = 0  ----->  true in boolean and arithmetic

1 * 0 = 0  ----->  true in boolean and arithmetic

1 * 1 = 1  ----->  true in boolean and arithmetic

0 + 0 = 0  ----->  true in boolean and arithmetic

0 + 1 = 1  ----->  true in boolean and arithmetic

1 + 0 = 1  ----->  true in boolean and arithmetic

1 + 1 = 1  ----->  not true in ordinary arithmetic

It is this difference for OR (+) that makes the identity false in ordinary arithmetic, while the corresponding AND (*) identity is true.


问:
Use the pumping lemma to show that the language is not context-free
I want to show that this language is not context-free:

I struggle with the pumping lemma for CFL and i would like to know how to solve this problem. Thank you

(skipping the classic introductory text of the proof)

During my proof i chose the word $z = a^pb^pc^{p-1}$ ( correct me if this isn't a good choice)

The word z can be cut as $sv^iuw^it$

Let's take i = 2

From there i know that we have to explore all cases:

Case 1: v and w are only made of a's so we have $a^{p+|vw|}b^pc^{p-1}$ so this isn't in the language because $|vw| >= 1$

Case 2: it's the same thinking but v w are only made of b's

Case 3: v and w are only made of c's, if $i=2$ then we have $v^2$and $w^2$ so $|vw|=4$ so we have $a^pb^pc^{p-1+|vw|}$ = $a^pb^pc^{p-1+4}$ which mean here that it won't be in the language since we need $m>=n$

From there ( if everything yet makes sens) i am not too sure on how to continue this problem, could anyone help out ? Thanks a lot.

答:
Choose the string w =  a^p b^p c^p  clearly w is in L , we provide an easy way to show that w cannot be pumped  ( we cut the string into u v^i x y^i z)

either v or y has more than one type of symbol :

If either v or y has more than one type of symbol , then when pumping w , the string w' = u v^2 x y^2 z will not have symbols in correct order , so v and y each must contain only one type of symbols ( ex v has only as and y has only bs , or both have only as , etc )

either v or y has cs :

Assume y has cs , from 1 we know y can have only cs , now v also can have one type of symbols , consider the string      w' = u v^2 x y^2 z , if we choose v to be also cs , then w' has more cs than as and bs , if we choose v to be bs , w' has more bs than as , if we choose v to be as ( which we cannot since |vxy| > p , but anyway ) we have more as than bs , so v and y cannot have cs

3 ) final case

From 2 we know that v and y cannot have cs , and from 1 we know each must have one type of symbols , if both v and y have only as or only bs , then w' = u v^2 x y^2 z would have more as than bs , or more bs than as , if v has only as and y has only bs , then , w'' = u v^0 x y^0 z ( a very useful case which is usually forgotten)  , would have more cs than as and bs

Conclusion :

tells us v and y each must contain only one type of symbols

tells us v and y cannot contain cs

tells us any way we choose v and y to be as or bs fails

So w cannot be pumped and L is not a CFL


问:
What is the probability of measure(n) returns value x?
```<code>def rand():
  return random.choice([0, 1, 1, 1])

def measure(n):
  c = 0
  for x in range(0, n):
    if(rand() == 1):
      c += 1
  return c
</code>```

I'm trying to find the probability of every possible return from measure(n).

At first I assume that it would be something akin to $\frac{3}{4}^{x+1}$, but that doesn't fit the expected curve of a peak towards the end before it drops off- then I assume something akin to $\frac{3}{4}^{|x-(n+1)|}$ but that doesn't fit either. (+1 to include a return of 0.)

Additionally, I think the expected value of measure(n) is $\frac{1}{\frac{1}{4}} = 4$, am I close there or way off?

答:
measure($n$) just returns the number of times, out of $n$ trials, that $1$ was selected by your rand() function.  Since on each trial the probability of rand() choosing $1$ is $3/4$, measure($n$) simply follows the binomial distribution Bin($n, 3/4$).

So the answers to your questions are:

$$
\mathbb{P}(\text{measure}(n) = x) = \binom{n}{x} (3/4)^x (1/4)^{n-x} \quad   \text{and}  \quad \mathbb{E}(\text{measure}(n)) = 3n/4.
$$


问:
Counting such functions
How many total functions are there from a set with $3$ elements to a set with $4$ elements?

Just as a reminder, "total" functions are simply functions defined on all the elements of given domain. I calculated it as $4^3$ from multiplication principle, but unsure on that solution. Moreover, I am also curious on if we replaced "total" function with "one-to-one" and "onto", would the same answer be correct in both cases?

Would be welcomed to know your thoughts on this! Thanks!

答:
You are correct, by the definition of a function you must use all $3$ elements and there are four choices for each resulting in $4^{3}$ distinct possibilities. For one-to-one we must use all $3$ elements in the domain but the number of possibilities decreases for each element used (since one-to-one means that $ x \neq y \implies f(x) \neq f(y)$ so that for the first element there are $4$ possibilities, for the second, $3$ possibilities, and for the third, $2$ possibilities giving us $4 \cdot 3\cdot 2 = 24
$ possibilities. There are no surjective functions since if we map each element to a single element of the codomain (as is required by a function), there is always some element that is left over in the codomain since $4>3$.

Title: Counting such functions


问:
How to evaluate $\int_C (x+y)^2dx - (x^2+y^2)dy$ over a triangle
Could someone help me to evaluate
$$\int_C (x+y)^2dx - (x^2+y^2)dy$$ where C is the positively oriented triangle with vertices at (1,1), (3,2) and (2,5)?

I tried to use Green's theorem to solve it and I got $\iint_D (-4x+2y) dA$  and I have no idea that what should I do next step.

Thanks in advance.

答:
First of all, your integrand is not correct.

$Pdx + Qdy = (x+y)^2dx - (x^2+y^2)dy$

So, $P = (x+y)^2, Q = -(x^2+y^2)$

$\frac{\partial Q}{\partial x} = -2x, \frac{\partial P}{\partial y} = 2x + 2y$

$\frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} = -4x - 2y$

Now your region is positively oriented triangle with vertices $(1, 1), (3,2)$ and $(2, 5)$. Here is a sketch of your region -

Taking two points at a time, you can find the equations of lines that form this triangle. It is clear from the sketch that you have to either do a change of variable or just split your integral into two parts.

For integrating first over $y$ and then over $x$, your bounds for two integrals become $\frac{x + 1} {2} \leq y \leq (4x-3), 1 \leq x \leq 2$ and $\frac{x + 1} {2} \leq y \leq (11-3x), 2 \leq x \leq 3$


问:
Big O notation compare inequality
This seems very basic but can not figure it out.
I have

$a = C_{1} \delta
\\
|b| = \sqrt{B} \delta, \ B \neq 0$

where $\delta >0$

so both can be written as

$a = O(\delta)
\\b = O(\delta)$

and $\delta \to 0$

Why can't I say

$\exists \ C\geq (>?) 0: \quad |a| \leq C |b|$.

I could write
$\delta = \frac{|b|}{\sqrt{B}}$

and
$|a| = | C_{1} \delta| \leq | C_{1} | \delta = |b| \frac{| C_{1} |}{\sqrt{B}}$

Why is this wrong?

答:
Let me bring example for sequences. Consider
$$g(n)= \begin{cases}{}
\frac{1}{n}, & n=2k\\
0, & n=2k-1
\end{cases}$$
and
$$f(n)= \begin{cases}{}
0, & n=2k\\
\frac{1}{n}, & n=2k-1
\end{cases}$$
then both holds $f,g \in O\left(\frac{1}{n}\right)$, but you cannot write $f \leqslant C g$ or $g \leqslant C f$.

Title: Big O notation compare inequality


问:
Approximate increase in circumference of circle giving increase in area of 3%
Find the percentage increase in the circumference of a circle, which will result in an increase in the area of the circle of approximately 3%.

I have assumed the percentage change in circumference is the same as the percentage change in r, since circumference is $2\pi r$.

I have said $A = \pi r^2, \frac{dA}{dr} = 2\pi r$

$\frac{\delta A}{\delta r} \approx \frac{dA}{dr}$

where $\delta$ refers to "a small increase".

$\delta A = \frac{dA}{dr}.dr$

$\frac{3A}{100} \approx 2\pi r.\delta r$

But I cannot get this to equal the answer in the book, which is 1.5%.

答:
As we have relative variations, we can drop any constant factor. Then we take $r=1$ and compare

$$\frac{(1+\delta)-1}{1}=\delta$$ to $$\frac{(1+\delta)^2-1}{1}=2\delta+\delta^2\approx 2\delta.$$


问:
Three player combinatorial game - minimizing communication between Alice and Bob
Consider the following game between three parties: Alice, Bob and a Referee. The game starts with $n$ closed boxes. For some fixed $k<n$ known to all parties, the Referee freely chooses $k$ distinct boxes and places a prize inside each of them. Alice sees the Referee do this and thus, she knows which boxes have a prize. Bob now enters the room. He can talk to Alice, then choose one box and if this box has a prize, he can keep it.

What is the smallest number of bits of information that Alice needs to convey to Bob such that Bob is guaranteed to win a prize?

The naive strategy is for Alice to pick a prize-containing box at random and give the ID of this box to Bob. This costs $\log n$ bits of information since she picks one box out of $n$ choices. But given that there are $k$ choices and any of them would do the job, can Alice and Bob win the game with less than $\log n$ bits of communication? If yes, what should their strategy be?

EDIT: I am happy to assume the Referee is not adversarial if that admits a better strategy for Alice and Bob.

答:
Here is a "negative" result under these assumptions:

The game is deterministic, i.e. all 3 have no access to any randomizer (dice etc).

The referee is adversarial and knows Alice & Bob's strategy.

There is only 1 round of interaction between Alice & Bob.  So Bob doesn't even need to ask his question (since it's deterministic anyway) and can simply walk into the room and hears Alice's single answer, which is $b$-bits long.

Under these assumptions, the result is IMHO negative: $b$ must satisfy $k + 2^b > n$, or equivalently, $b \ge \log_2(n-k+1)$.

Reason: each of the $2^b$ possible answers deterministically maps to one box.  So if $k + 2^b \le n$ the adversary can place all prizes in boxes which correspond to none of the possible answers.

I consider this a "negative" result because this shows the "obvious" strategy to be optimal.  (The obvious strategy being: eliminate $k-1$ boxes before hand and then just encode the remaining $n-k+1$, since at least one of these must contain a prize.  This is equivalent to the lowest-ID strategy of @leonbloy, which eliminates the highest $k-1$ boxes.)

In fact, I think assumption #3 is not needed.  Suppose Alice & Bob can interact for multiple rounds, i.e. Bob asks a question, Alice answers, then based on the answer Bob chooses what question to ask in the next round.  Some of the answers can be long, some can be short.

However, if we use worst-case (not "average" in some sense) total number of bits as the criterion, it is still true that the $b$ bits encode a particular sequence of questions and answers.  (Remember: Bob has no access to random bits, so his questions are deterministically based on Alice's previous answers).  Thus with $b$ total bits it is still only possible to encode $2^b$ different boxes at most.


问:
Boolean functions satisfying a condition
What is the total number of Boolean functions $f :\{0,1\}^n \rightarrow \{1,-1\}$ such that

\begin{equation}\tag{1}\label{e}
\sum_xf(x)f(x+y) = 0
\end{equation}

for all $0\neq y$?

Is there some closed form construction to obtain them all? Or even one specific example if it exists at all? I tried to use inverse Fourier transform but no luck.

For $n = 2$ one such example is $f(00) = f(10) = f(01) = 1$ and $f(11) = -1$. But for larger $n$ it seems very difficult.

Note that $f$ cannot be additive.

EDIT: Alex below claims that no such functions exist for $n >2$. However, for $n =4$, I was able to construct (very ad-hoc) the following

Columns 1 through 14

```<code> 0     0     0     0     0     0     0     0     1     1     1     1     1     1
 0     0     0     0     1     1     1     1     0     0     0     0     1     1
 0     0     1     1     0     0     1     1     0     0     1     1     0     0
 0     1     0     1     0     1     0     1     0     1     0     1     0     1
 1    -1     1     1     1     1    -1     1     1     1     1    -1     1    -1
</code>```

Columns 15 through 16

```<code> 1     1
 1     1
 1     1
 0     1
-1    -1
</code>```

One way to to think of this is by considering the function $f_y: x \mapsto f(x)f(x+y)$ and impose that $f_y$ is additive for all $y$. So the question now becomes:

Question: Does there exist $\hat{y}$ such that $f_y = \chi_{\hat{y}}: x\mapsto (-1)^{\hat{y}x^T}$.

Then \eqref{e} becomes a simple consequence of characters.

答:
I have tried to find solutions using the Python interface of Microsoft's Z3 solver.

My Z3PY model:

```<code>from z3 import *

n = 2
noOfMinterms = 2 << (n-1)

print("n = %s" % n)
print("minterm rows = %s" % noOfMinterms)

Minterms = [i for i in range(noOfMinterms)]

#  define truth table with one Bool variable for every row
table = []

for i in Minterms:
    table += [Bool("b" + str(i))]

def f(x):
    return If(table[x % noOfMinterms], 1, -1)

s = Solver()

for y in range(1, noOfMinterms):
    s.add(Sum([Product(f(x), f(x + y)) for x in Minterms]) == 0)

solutions = 0

while s.check() == sat:
    m = s.model()
    solutions += 1
    print(str(solutions) + ": ", [" 1 " if is_true(m[table[i]]) else "-1 " for i in Minterms])
    #  prevent the solution to be found again
    s.add(Or([table[i] != m[table[i]] for i in Minterms]))

if solutions == 0 :
    print("No solutions found. Sorry")
else:
    print("Solutions: %s" % solutions)
</code>```

Output for $n = 2$:

```<code>n = 2
minterm rows = 4
1:  [' 1 ', '-1 ', ' 1 ', ' 1 ']
2:  ['-1 ', ' 1 ', ' 1 ', ' 1 ']
3:  [' 1 ', '-1 ', '-1 ', '-1 ']
4:  [' 1 ', ' 1 ', ' 1 ', '-1 ']
5:  [' 1 ', ' 1 ', '-1 ', ' 1 ']
6:  ['-1 ', ' 1 ', '-1 ', '-1 ']
7:  ['-1 ', '-1 ', ' 1 ', '-1 ']
8:  ['-1 ', '-1 ', '-1 ', ' 1 ']
Solutions: 8
</code>```

The solution mentioned in the question is number $4$ of the $8$ solutions.

For $n$ larger than $2$, no solution was found.

MiniZinc also does not find solutions for $n \gt 2$:

```<code>include "globals.mzn";

int: n = 2;
int: noOfMinterms = pow(2, n);
set of int: Minterms = 0 .. noOfMinterms - 1;

array[Minterms] of var bool: X; %  true = 1; false = -1

constraint
forall(y in Minterms where y != 0) (
   sum([f(x) * f(x+y) | x in Minterms]) == 0
);

function var int: f(int: x) = if X[x mod noOfMinterms] then 1 else -1 endif;

function int: f2(Minterms: x) = if fix(X[x]) then 1 else -1 endif;

solve satisfy;

output ["\(n): "] ++
       [show_int(3, f2(i)) | i in Minterms];
</code>```

Check code in C# for given solutions:

```<code>int n = 4;
int noOfMinterms = (2 << (n - 1));
int[] f = { 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, -1, -1 };

for (int y = 1; y < noOfMinterms; y++)
{
    int sum = 0;

    for (int x = 0; x < noOfMinterms; x++)
    {
       sum += f[x] * f[(x + y) % noOfMinterms];
    }

    Console.WriteLine($"{y} {sum}");
}
</code>```

Body:
I have tried to find solutions using the Python interface of Microsoft's Z3 solver.

My Z3PY model:

from z3 import *

n = 2
noOfMinterms = 2 << (n-1)

print("n = %s" % n)
print("minterm rows = %s" % noOfMinterms)

Minterms = [i for i in range(noOfMinterms)]

#  define truth table with one Bool variable for every row
table = []

for i in Minterms:
    table += [Bool("b" + str(i))]

def f(x):
    return If(table[x % noOfMinterms], 1, -1)

s = Solver()

for y in range(1, noOfMinterms):
    s.add(Sum([Product(f(x), f(x + y)) for x in Minterms]) == 0)

solutions = 0

while s.check() == sat:
    m = s.model()
    solutions += 1
    print(str(solutions) + ": ", [" 1 " if is_true(m[table[i]]) else "-1 " for i in Minterms])
    #  prevent the solution to be found again
    s.add(Or([table[i] != m[table[i]] for i in Minterms]))

if solutions == 0 :
    print("No solutions found. Sorry")
else:
    print("Solutions: %s" % solutions)

Output for $n = 2$:

n = 2
minterm rows = 4
1:  [' 1 ', '-1 ', ' 1 ', ' 1 ']
2:  ['-1 ', ' 1 ', ' 1 ', ' 1 ']
3:  [' 1 ', '-1 ', '-1 ', '-1 ']
4:  [' 1 ', ' 1 ', ' 1 ', '-1 ']
5:  [' 1 ', ' 1 ', '-1 ', ' 1 ']
6:  ['-1 ', ' 1 ', '-1 ', '-1 ']
7:  ['-1 ', '-1 ', ' 1 ', '-1 ']
8:  ['-1 ', '-1 ', '-1 ', ' 1 ']
Solutions: 8

The solution mentioned in the question is number $4$ of the $8$ solutions.

For $n$ larger than $2$, no solution was found.

MiniZinc also does not find solutions for $n \gt 2$:

include "globals.mzn";

int: n = 2;
int: noOfMinterms = pow(2, n);
set of int: Minterms = 0 .. noOfMinterms - 1;

array[Minterms] of var bool: X; %  true = 1; false = -1

constraint
forall(y in Minterms where y != 0) (
   sum([f(x) * f(x+y) | x in Minterms]) == 0
);

function var int: f(int: x) = if X[x mod noOfMinterms] then 1 else -1 endif;

function int: f2(Minterms: x) = if fix(X[x]) then 1 else -1 endif;

solve satisfy;

output ["\(n): "] ++
       [show_int(3, f2(i)) | i in Minterms];

Check code in C# for given solutions:

int n = 4;
int noOfMinterms = (2 << (n - 1));
int[] f = { 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, -1, -1 };

for (int y = 1; y < noOfMinterms; y++)
{
    int sum = 0;

    for (int x = 0; x < noOfMinterms; x++)
    {
       sum += f[x] * f[(x + y) % noOfMinterms];
    }

    Console.WriteLine($"{y} {sum}");
}


问:
LCM of 3 numbers is given then what can't GCD be
This question was asked to me by a junior and I was unable to solve it and in fact couldn't even start despite of having studied considerable number theory.

$\text{lcm}$ of three different numbers is $120$ then which of the following can't be it's HCF?

(A) $8$

(B) $12$

(C) $24$

(D) $35$

I have studied elementary number theory from David Burton but I am absolutely clueless about this particular problem.

I could think of $\gcd(a,b) \text{lcm}(a,b)=ab$ , but is this extendable  to more than two variables? and even if it is extendable it doesn't seem to be useful.

Thanks for any help!!

Body: Note that $\gcd(x_{1},x_{2},...,x_{n})\vert\ \text{lcm}(x_{1}, x_{2}, ..., x_{n})$ because $\gcd(x_{1},x_{2},...,x_{n})\vert\ x_{1}, x_{2}, ..., x_{n}$ and $x_{1}, x_{2},...,x_{n}\vert\ \text{lcm}(x_{1}, x_{2}, ..., x_{n})$. Thus, if a number does not divide the $\text{lcm}$, it cannot be the $\gcd$, so the answer must be $\boxed{(D)\ 35}$


问:
Constructing a line perpendicular to one of two given intersecting lines by first drawing a circle

Suppose there are two intersecting lines $\ell$ and $m$ in the plane. Using only a compass and straightedge, first draw a circle $c$ and then a line $p$ so that the line $p$ is perpendicular to the line $\ell$. Justify your answer.

It seems you draw lines from center to the intersection points of the line with circle then this is isosceles triangle what will be an angle bisector to the line from center.

Am I right?

答:
Use the property of the circumscribed right angled triangles:

Let $l\cap m=A$.

Choose any point $O\in m$.

Draw a circle $c$ centered at $O$ through the point $A$.

Let $l \cap c =C$, $m \cap c =B$, $AB$ is the diameter of $c$.

Then $\triangle ABC$ is right angled, and $p=BC \perp l$.


问:
Why do we need to find the intersection between these lines?
We have the functions

$$ x = -1 + 2 \cos(t)$$

$$ y = 3 + 2 \sin(t)$$

They give P's orbit

with $t$ on $\left[0, \dfrac{3}{2} \pi\right]$

Find (to 2 decimal places accurate) for which values of t the Point t is left of the line $x=-2.$

So we're allowed to use our calculators, and the answer model says that to find the solution you first need to find the intersection between $\;y=-2\;$ and $\;y=-1 + 2\cos (x)$.

My question is; why does this work?

答: I don't know.  To be left of $x=-2$ you need $\cos t \lt -\frac 12$  You should be able to find appropriate $t$ without worrying about $y$.  I think they are finding the intersection between $x=-2$ and $x=-1+2 \cos t$ and the $y$ is a typo.</p>

ContentLicense: CC BY-SA 3.0


答: The answer is D.  If $7$ is a divisor of each of the numbers, then it would also divide any common multiple.

Title: LCM of 3 numbers is given then what can't GCD be

Body:
This question was asked to me by a junior and I was unable to solve it and in fact couldn't even start despite of having studied considerable number theory.

$\text{lcm}$ of three different numbers is $120$ then which of the following can't be it's HCF?

(A) $8$

(B) $12$

(C) $24$

(D) $35$

I have studied elementary number theory from David Burton but I am absolutely clueless about this particular problem.

I could think of $\gcd(a,b) \text{lcm}(a,b)=ab$ , but is this extendable  to more than two variables? and even if it is extendable it doesn't seem to be useful.

Thanks for any help!!


问:
Convert a uniform distribution to two uniform distributions
I have a distribution function:
$$ F(x) = \begin{cases} 0 & x \leqslant 0, \\ \frac{x}{2} & 0 < x \leqslant 1 \\ \frac{2}{3} & 1 < x \leqslant 2 \\ \frac{2}{3} + \frac{x-2}{3} & 2 < x \leqslant 3, & \\ 1 & x > 3 \end{cases} $$
I want to find such $ f $ so that $ \xi \in U _ {[0; 1]} $, $ U $ is uniform, so that $ f (\xi) $ is distributed like $ F $, I know that in the strictly monotone case, take $ F ^ {- 1} $ as $ f $, but here I don't know what to do, although I see that $ F $ is a union of two uniform ones, I don't know what to do.

答:
If I understood well, the problem is correct but it is bad explained. Moreover, usually the CDF is right continuous, yours is left continuous....it is not forbidden but rare to see...

The question, IMHO, is the following:

"Is it possible, starting from a uniform distribution $Y\sim U[0;1]$ ,
with a transformation derive $F_X(x)$?"

The answer is Yes, using $F_X^{-1}(y)$ that is the following transformation function

$$F_X^{-1}(y) =
\begin{cases}
2y,  & \text{if $0\leq y<\frac{1}{2}$} \\
2,  & \text{if $\frac{1}{2}\leq y<\frac{2}{3}$} \\
3y,  & \text{if $\frac{2}{3}\leq y<1$} \\
3, & \text{if $y \geq 1$}
\end{cases}$$


问:
General structure quotient of two rank-2 abelian groups
Bernstein, Sloane $\&$ Wright, Discrete Mathematics 170 (1997) 23-29 states the following property concerning a two dimensional lattice $\Lambda$:

Let $\Gamma$ be a sublattice of $\Lambda$ of index $N$ $\ldots$ Since $\Lambda$ has rank 2, the quotient group $Q=\Lambda/\Gamma$ is either a cyclic group $C_N$, $\ldots$, or a direct product $C_{N/m} \times C_{m}$ of a pair of groups with $m$ dividing $N/m$, so $m^2|N$.

Lacking any suitable reference, how does one prove this?

答:
References are legion. It follows, for example, from this (Theorem II.1.6, from Thomas Hungerford's Algebra, Springer-Verlag GTM 73):

Theorem. If $F$ is a free abelian group of finite rank $n$ and $G$ is a nonzero subgroup of $F$, then there exists a basis $\{x_1,\ldots,x_n\}$ of $F$, an integer $r$, $1\leq r\leq n$, and positive integers $d_1,\ldots,d_r$ such that $d_1|d_2|\cdots|d_r$ and $G$ is free abelian with basis $\{d_1x_1,\ldots,d_rx_r\}$.

From this it follows that $F/G$ is isomorphic to $\mathbb{Z}^{n-r}\times C_{d_1}\times\cdots\times C_{d_r}$. If $G$ has finite index, then you must have $n=r$. Your case is the case $n=2$. The quotient will have the form $C_{d_1}\times C_{d_2}$ with $d_1|d_2$, and $d_1d_2=N$. You can then express $d_2=N/d_1$ with $d_1$ dividing $N/d_1$.

Hungerford includes the proof, so you can find it there. Similar theorems can be found in Rotman's An Introduction to the Theory of Groups 4th Edition, Springer-Verlag GTM 148, Theorem 10.21.


问:
Derivation of $t$-distribution Entropy closed-form analytical solution
A closed-form analytical solution for the entropy of the Normal distribution's pdf was derived here. But how about for the t-distribution? How is it derived?

\begin{align}h(X) &=-\int \frac{\mathrm{\Gamma}\left(\frac{\nu+1}{2}\right)}{\sqrt{\nu \pi} \mathrm{\Gamma}\left(\frac{\mathrm{v}}{2}\right)}\left(1+\frac{x^{2}}{\nu}\right)^{-\frac{\nu+1}{2}} \ln  \frac{\mathrm{\Gamma}\left(\frac{\nu+1}{2}\right)}{\sqrt{\nu \pi} \mathrm{\Gamma}\left(\frac{\mathrm{v}}{2}\right)}\left(1+\frac{x^{2}}{\nu}\right)^{-\frac{\nu+1}{2}} dx\\
& = ?
\end{align}

答:
When we plug in the t-distribution into the definition of the entropy we have to do an integral of the form

$$H=-C_{\nu}\int_{-\infty}^{\infty}\left(1+\frac{t^2}{\nu}\right)^{-\frac{1+\nu}{2}}\left[\ln C_{\nu}-\frac{\nu+1}{2}\ln\left(1+\frac{t^2}{\nu}\right)\right]=H_1+H_2$$

where the normalization constant is denoted by $C_{\nu}^{-1}=\sqrt{\nu}B\left(\frac{1}{2},\frac{\nu}{2}\right)$. The integrals $H_1$ and $H_2$ denote the integrals generated by the two terms in the brackets respectively. For $H_1$ it suffices to note that it is proportional to the normalization condition of the function so we easily get
$$H_1=\ln C_{\nu}^{-1}$$
For the second term we perform a change of variables $x=\frac{t^2}{\nu}$:
$$H_2=\frac{\nu+1}{2}\sqrt{\nu}C_{\nu}\int_{0}^{\infty}(1+x)^{-\frac{1+\nu}{2}}\ln(1+x)\frac{dx}{\sqrt{x}}$$
This integral can be written in terms of the Beta function
$$\int_{0}^{\infty}(1+x)^{-\frac{1+\nu}{2}}\ln(1+x)\frac{dx}{\sqrt{x}}=-2\frac{d}{d\nu}\int_{0}^{\infty}dx\frac{x^{-1/2}}{(1+x)^{\frac{\nu+1}{2}}}=-2\frac{dB\left(\frac{1}{2},\frac{\nu}{2}\right)}{d\nu}
$$
So the second integral is equal to
$$H_2=-(\nu+1)\frac{d}{d\nu}\ln B\left(\frac{1}{2},\frac{\nu}{2}\right)=-(\nu+1)\frac{d}{d\nu}\left[\ln\Gamma\left(\frac{\nu}{2}\right)-\ln\Gamma\left(\frac{\nu+1}{2}\right)\right]=\frac{\nu+1}{2}\left[\psi\left(\frac{\nu+1}{2}\right)-\psi\left(\frac{\nu}{2}\right)\right]$$
Combining everything together we get the desired result
$$H=\ln \left(\sqrt{\nu}B\left(\frac{1}{2},\frac{\nu}{2}\right)\right)+\frac{\nu+1}{2}\left[\psi\left(\frac{\nu+1}{2}\right)-\psi\left(\frac{\nu}{2}\right)\right]$$


答:
We first observe that $120 = 2^4 \cdot 3^1 \cdot 5^2$. Additionally, we know that the gcd of any $n$ numbers must divide the lcm of those numbers.

Therefore, we see that choices $a$, $b$, and $c$ all divide the lcm. However, 35 does not divide the lcm and therefore it cannot be the gcd.


问:
Strongly monotone, Lipschitz continuous and contractivity
Let $(V,||.||)$ be a Hilbert space and the operator $T:V \rightarrow V$, strongly monotone and Lipschitz continuous, specifically it satisfies:
$$ (T(v_1)-T(v_2),v_1-v_2)\ge c_1 ||v_1-v_2||^2,$$
$$ ||T(v_1)-T(v_2)||\le c_2||v_1-v_2||,$$
with $c_1,c_2>0$ and $v_1,v_2 \in V$.
Now given $b\in V$ we define the operator $T_\theta: V \rightarrow V$ by
$$T_\theta(v)=v-\theta(T(v)-b),$$
where $\theta\neq0$.
I want to show that for $\theta \in (0,2c_1/c_2^2)$ the operator $T_\theta$ is a contraction. I have tried several times but I can not get the requested upper bound for $\theta$.

答:
By the Pythagorean Theorem we have,

$$
\begin{split}
\| T_\theta(v)-T_\theta(w)\|^2 & = \| v-w\|^2 -2\theta(T(v)-T(w), v-w) + \theta^2\| T(v)-T(w)\| \\
& \leq \left( 1- 2\theta c_1 + \theta^2c_2^2\right)\| v-w\|^2.
\end{split}
$$

Therefore, it's enough to show that $\theta^2c_2^2-2\theta c_1<0$. This is exactly your condition on $\theta$.


问:
Is there a sharper upper bound of the spectral norm of Hilbert matrix than $3+2\sqrt{2}$?

$A_n$ is a real symmetric $n \times n$ matrix defined by

$$ A_n =  \begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{3} & \cdots &
 \frac{1}{n} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{3} & \cdots &
 \frac{1}{n} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & \cdots &
 \frac{1}{n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\
 \frac{1}{n} & \frac{1}{n} & \frac{1}{n} & \cdots & \frac{1}{n} \\
 \end{bmatrix} $$

Find an upper bound of the eigenvalues of $A_n$ as tight as possible.

Let $A_n = U+U^T-D,$ where $U$ is the upper triangular part of $A_n$ and $D$ is the diagonal of $A_n$.

Suppose $\lambda$ is the largest eigenvalue of $A_n = U^T U$.

For any $X \in \mathbb{R}^n$,
$$X^T A_n X = X^T U^T U X = \left\Vert UX \right\Vert^2 \leq \lambda \left\Vert X \right\Vert^2 \implies \left\Vert UX \right\Vert \leq \sqrt{\lambda} \left\Vert X \right\Vert.$$
Since $U^T U$ is similar to $U U^T$, $\lambda$ is also the largest eigenvalue of $ U U^T $.

Hence we also have
$$ \left\Vert U^T X \right\Vert \leq \sqrt{\lambda} \left\Vert X \right\Vert.$$
Similarly, $$ \left\Vert D X \right\Vert \leq \left\Vert X \right\Vert.$$

Thus

$$ \left\Vert A_n X \right\Vert = \left\Vert U X + U^T X - D X \right\Vert \leq \left\Vert U X \right\Vert + \left\Vert  U^T X \right\Vert + \left\Vert  D X \right\Vert \leq \left( 2 \sqrt{\lambda} + 1 \right) \left\Vert X \right\Vert.$$

Take $X$ to be the eigenvector of $A_n$ corresponding to $\lambda$, then

$$ \left\Vert A_n X \right\Vert = \lambda \left\Vert X \right\Vert \leq \left( 2 \sqrt{\lambda} + 1 \right) \left\Vert X \right\Vert,$$

we have $\sqrt{\lambda} \leq 1+\sqrt{2} \implies \lambda \leq 3+2\sqrt{2}.$

Is there any tighter upper bound?

答:
The matrix $A_n$ is semi-famous because its inverse is a tridiagonal matrix: $$A_n^{-1}=2B_n=2\begin{pmatrix}
1 & -1 & 0 & \cdots & 0 \\
 -1 & 4 & -3 & 0 & \\
 0 & \ddots & \ddots & \ddots & 0 \\
 0 & 0 & -t_{n-2} & (n-1)^2 & -t_{n-1} \\
 0 & 0 & 0 & -t_{n-1} & n^2/2\end{pmatrix}$$ where $t_n=n(n+1)/2$ are the triangular numbers. It seems easier to find the smallest eigenvalue of $B_n$ than the largest eigenvalues of $A_n$. If $v=(u_1(x),u_2(x),\ldots,u_n(x))$ is an eigenvector of $B_n$ with eigenvalue $x$, then the components satisfy the recurrence relation $$u_{k+1}(x)=\frac{k^2-x}{t_k}u_k(x)-\frac{t_{k-1}}{t_k}u_{k-1}(x),\quad u_1(x)=1,u_2(x)=1-x$$ $$\left(\frac{n^2}{2}-x\right)u_n(x)=t_{n-1}u_{n-1}(x)\tag{1}$$ the last being the characteristic polynomial equation of $B_n$. To find the smallest root of this polynomial one might use more sophisticated techniques, but for brevity let's keep only the constant and $x$ term. The proofs are omitted but it is not hard to see that $$u_n(x)=1-2(H_n-1)x+\cdots$$ where $H_n$ are the harmonic numbers. Substituting these into $(1)$ and neglecting higher order terms gives $x\approx \frac{n}{2 \left(n H_{n-1}+1\right)}$, so the largest eigenvalue of $A_n$ is less than $$\lambda\le H_n$$ A comparison of the actual largest eigenvalue and $H_n$ is below: $$\begin{matrix}n&1&2&3&4&5&\ldots&20\\
\lambda_n&1&1.31&1.49&1.62&1.71&&2.22\\
H_n&1&1.5&1.83&2.08&2.28&&3.66\\
\end{matrix}$$


问:
Completely stuck at integrating $\int x\sqrt{\cos x}\,dx$
I am currently learning Calculus and I just started studying Integrals. I want to find the general indefinite integral $$\int x\sqrt{\cos x}\,dx$$

I have tried using some substitution such as letting $u=\cos x$ or $u=\sqrt x$, etc. but it seems like none of them is effective here.

I have also tried using online integral calculators to solve this question, but all I got is something like "steps are currently not supported for this problem."

Since even an integral calculator couldn't handle this, I wondered if this question can be solved. Therefore I came back to MathSE to seek help.

Is it solvable? If so, then how? Thanks in advance.

答:
Wolfram's calculation is ugly: https://www.wolframalpha.com/input/?i=integrate+x*sqrt%28cos%28x%29%29+dx

But to answer your question directly: yes it can be solved.


问:
Raising entries to $k$th power

Let $A$ be an $n \times n$ real matrix, and define $A_k$ to be the matrix whose entires are $(a_{ij})^k$. Prove that if $A^k = A_k$ for $k = 1, \ldots, n + 1$, then $A^m = A_m$ for all $m$.

My attempt:

We prove by induction on induction on $m$. $m = 1$ is true by assumption. Suppose it's true for $m = 1, \ldots, n + 1$ . Considering $A^{n+2}$ and defining $X = A^{n+1} = A_{n+1}$, we have:
\begin{align*}
(A^{n+2})_{i,j} & = ((A^{n+1})A)_{ij} \\
& =  (XA)_{ij} \\
& = \sum\limits_{k=1}^n x_{ik} a_{kj} \\
& = \sum\limits_{k=1}^n (a_{ik})^n (a_{kj})
\end{align*}

How does this look?

答:
Using the minimal polynomial of $A$ or Cayley-Hamilton, we get some relation like
$$ A^n = \sum_{k < n} c_{k + 1} A^k. $$

If we multiply both sides by $A$ then all the powers of $A$ are between $1$ and $n + 1$ so we obtain also

$$ A^{n+1} = \sum_{k = 1}^n c_k A^k \quad \Longleftrightarrow \quad a_{i,j}^{n + 1} = \sum_{k = 1}^n c_k a_{i,j}^k$$

Now multiply both sides by $A$ again to get
\begin{align}
(A^{n + 2})_{i,j} &= \sum_{k = 1}^{n} c_k (A^{k + 1})_{i,j} \\
&= \sum_{k = 1}^{n} c_k a_{i,j}^{k+1} \\
&= a_{ij} \sum_{k = 1}^n c_k a_{i,j}^k \\
&= a_{ij} \cdot a_{ij}^{n + 1} = a_{ij}^{n + 2}.
\end{align}

And you can write this induction step more generally.

Title: Raising entries to $k$th power


问:
Is restriction of compact operator always compact?
Question 1: Is a compact operator $T:X\to Y$ 's restriction on a subspace $Z\subset X$ still compact? (I think I've got the answer)

I think the compact operator's restriction on any subspace must still be compact since for any bounded sequence $\{ x_n\}\subset Z$, it's also bounded in $X$ since the subspace shares the norm.

However a subspace can be equipped with a different norm. For example, it's not immediately clear whether the injection $i: (C^\infty,\| \cdot\|_\infty )\to (L^2,\| \cdot\|_{L^2})$ is compact. But we know that the injection: $i_2: (C^\infty,\| \cdot\|_{L^2} )\to (L^2,\| \cdot\|_{L^2})$ is compact by the above argument and $i_1: (C^\infty,\| \cdot\|_\infty )\to (C^\infty,\| \cdot\|_{L^2} )$ is continuous. Therefore $i=i_2\circ i_1$ is compact. (Such argument won't work for $H^1\to L^2$, you can try by yourself)

The lesson is we can't discuss the operator's compactness ignoring the norm of the space. The definition of compactness heavily depends on them(bounded, convergent). Maybe someone can furnish us with an example that the operator is compact in one norm but not in the other.

Question 2: From Fredholm alternative, we know that the range of $\lambda I -T$ is always closed if $\lambda \neq 0$. So how about the range of a compact operator itself? Is it always closed or open? Are there any examples?

答:
Your intuition about the restriction of a compact operator to a subspace looks correct to me. A linear operator $T : X \to Y$ is compact if, for every bounded sequence $\{x_n\}$ in $X$, the sequence $\{Tx_n\}$ has a subsequence which is Cauchy in $Y$. So, if you have a subspace $Z$ of $X$, any bounded subsequence in $Z$ is also a bounded subsequence in $X$, so its image under $T$ will have a Cauchy subsequence in $Y$ too.

For your second question, I don't think the range of a compact operator is always closed. Consider the operator $T : \ell^2 \to \ell^2$,

$ (Tx)_n = e^{-|n|}x_n$.

(Pretty sure that's a compact operator.) For all $y$ in the range of $T$, $y_n$ decays exponentially fast as $n \to \pm\infty$. Now consider the sequence $z_n = (1+n^2)^{-1}$, which is in $\ell^2$; since it doesn't decay exponentially fast, it can't be in the range of $T$. On the other hand, there is a sequence of points in the range of $T$ which converge to $z$. If you're stumped, I can write down what the sequence is.

Someone who's less rusty on functional analysis can probably give you a deeper insight here. You should note that an operator have a closed range and being a closed operator are two different things. For example, it's shown here that an operator is closed if its domain is complete with respect to the graph norm

$\|x\|_T = \sqrt{\|x\|^2+\|Tx\|^2}$.

You can verify that, by this criterion, the counterexample I gave you before is a closed operator, even though its range isn't closed.


问:
How would you find the maximum directional derivative in this case?

I have gotten this down to 3a/2 + 4b/5 = 5, but now I'm stuck. Do I use the fact that the maximum directional derivative is in the direction of the gradient to set that equal (2a, b) equal to (3/5, 4/5) to find a second equation?

答:
$f(x, y) = ax^2 + by$

Partial derivatives at $(1, 1), \frac{f(x, y)}{\partial x} = 2a, \frac{f(x, y)}{\partial y} = b$.

So gradient is $\nabla f(1,1) = (2a, b)$.

As the gradient points in the direction of the max directional derivative,

$\sqrt{4a^2 + b^2} = 5$ (pls note that the max directional derivative is same as the magnitude of the gradient).

And unit vector which is the direction of max directional derivative is

$(\frac{2a}{\sqrt{4a^2 + b^2}}, \frac{b}{\sqrt{4a^2 + b^2}}) = (\frac{3}{5}, \frac{4}{5})$.

And that gives value of $a$ and $b$.


问:
Does $A(x, m) = 1 - A(m, x)$ imply some symmetry in partial derivatives?
This is a self-made problem. I have a function $A$ of variables $x, m \geq 0$. A satisfies the following symmetry:

$$A(x, m) = 1 - A(m, x)$$

Is there an equation that relates the partial derivative of $A$ wrt the first argument to the partial derivative of $A$ with respect to the second argument? It seems like there should be something straightforward but I'm not sure how to deduce it.

Thank you!

答:
Another way to look at this is to note that the function $B(x,m):=A(x,m)-\tfrac12$ is antisymmetric;
$$B(x,m)=A(x,m)-\tfrac12=(1-A(m,x))-\tfrac12=\tfrac12-A(m,x)=-B(m,x).$$
What does that tell you about the partial derivatives?


问:
How to find $\sum_{l=2}^{100} \frac{1} {\log_{l} 100! }$
I am trying some question in sequence and series of an institute in which I don't study and I was unable to solve this particular question .

Question: Find the sum :$\sum_{l=2}^{100} \frac{1} {\log_{l} 100!}$ .

A 0.01

B 0.1

C 1

D 10

I am sorry but I would not be able to provide an attempt on this because I am absolutely clueless On how to aproach this even though I am good in Logarithms and sequence and series.

Body:
$\log_i 100!=\frac{\log_{100!}100!}{\log_{100!}i}=\frac{1}{\log_{100!} i}$. So
$$\sum_{i=2}^{100} \frac{1}{\log_i 100!}=\sum_{i=2}^{100}\log_{100!} i= \log_{100!}\prod_{i=2}^{100} i=\log_{100!} 100!=1.$$


问:
Notation for General n-Simplex Number
I'm looking to see if there is a standard notation for the following other than Binomial coefficient notation...

The triangular numbers $1,3,6,10,15,21,...$ are notated as $T_n$ and represented as $\binom{n+1}{2}$

The tetrahedral numbers $1,4,10,20,35,56,...$ are notated (per Wikipedia) as $Te_n=\sum{T_n}$ and represented binomially as $\binom{n+2}{3}$

Then there are the 5-cell numbers $1,5,15,35,70,126,...$.  These would naturally be represented as $\sum{Te_n}$, but was wondering if there was any other representation of this family of sequences of higher order n-simplex numbers...

答:
As you already know, these simplicial polytopic numbers are readily expressed as binomial coefficients.  The $n^{\text{th}}$ number in the sequence of $d$-dimensional simplex figurates is $\binom{n+d-1}{d}$, which is also called a stars-and-bars number as it also arises in that context.

Some authors employ an emphasized variant of the binomial coefficient notation to mean this closely related expression.  For example the OeisWiki page linked above uses doubled parentheses:

$$ \left(\! \! \binom{n}{d} \! \! \right) := \binom{n+d-1}{d} $$

while the WolframMathworld page uses single bold parentheses for what it terms "multichoose". When I try to recreate these bolded delimiters with $\LaTeX$ here, the effect is rather too subtle:

$$ \mathbf{\bigg{(}} \genfrac {}{}{0pt}{}{n}{d} \mathbf{\bigg{)}} $$

Title: Notation for General n-Simplex Number


问:
Question on a French math text by P. Masani
I'm trying to translate a paper on matrix-valued functions by P. Masani, published in C. R. Acad. Sci. Paris, 249, 1959, p. 873. (see http://temp-share.com/show/FHKd40yi6 for scanned pdf). My specific question is now as follows:

On the first page, in the first section after the abstract, he writes

"(..) et rang $\Psi$=Cte $\rho$, p.p. où $1\le\rho\le q$, (..)"

where $\Psi$ is a $q\times q$ matrix-valued function on the unit circle.
What does "Cte $\rho$" mean?

答: "Cte" is an abbreviation for "constante", which means, as you can guess, constant. </p>


问:
Example of convex sets

Give an example of an infinite family of convex sets in $\mathbb{R}^d$ such that
any $d + 1$ of them have a common point but all of them do not have.
It is enough to find such a family for some $d$.

I am not able to understand the question here. Could someone please say what does this mean and what will be its answer?

答:
I suppose that "having a common point" means they share at least one point.

Here is an answer on $\mathbb{R}$, I will let you do the job to expand the reasonning to arbitrary dimensions but it is not that hard if you think correctly...

Define $I_n = (0, \frac 1 n)$. Each $I_n$ is convex and any intersection of $2$ of them have a common point. But if you make the intersection of the whole family it will be empty.

Indeed, let $A$ be that intersection and suppose $x \in A$. Then $x< \frac 1n$ for all $n$ so $x\le 0$ but every non-positive element is not in $I_1=(0,1)$ for example. Hence a contradiction.

Title: Example of convex sets


Title: How to find $\sum_{l=2}^{100} \frac{1} {\log_{l} 100! }$

Body:
I am trying some question in sequence and series of an institute in which I don't study and I was unable to solve this particular question .

Question: Find the sum :$\sum_{l=2}^{100} \frac{1} {\log_{l} 100!}$ .

A 0.01

B 0.1

C 1

D 10

I am sorry but I would not be able to provide an attempt on this because I am absolutely clueless On how to aproach this even though I am good in Logarithms and sequence and series.

Body: $$\sum_{l=2}^{100} \frac{1} {\log_{l} 100!}=\sum_{l=2}^{100} \log_{100!}{l}=\log_{100!}{2}+\log_{100!}{3}+\log_{100!}{4}+...+\log_{100!}{100}=\log_{100!}({2\times3\times4\times...\times100})=\log_{100!}{100!}=1$$ .


Body:
$$S=\sum_{k=2}^{100} \frac{1}{\log_k100!}=\sum_{k=2}^{100} \frac{\log k}{\log 100!}=\frac{\log 2+\log 3+\log 4+\log 5+....+\log 100}{\log100!}$$ $$=\frac{\log (2.3.4....100)}{\log 100!}=\frac{\log 100!}{\log 100!}=1.$$
Option (C) is correct.


答:
Hint: There is a polynomial $\phi_A$ (the characteristic polynomial of $A$) of degree $n$ such that $\phi_A(A)=0$. Also, for any polynomial $p$, you can divide $p$ by $\phi_A$ with remainder $r$ of degree $<n$ so that $p(X)=\phi_A(X)q(X)+r(X)$ (for some quotient $q$). This means that $p(A)=\phi_A(A)q(A)+r(A)=r(A)$.

In particular, you can take $p(X)=X^{m-1}$ and you can write $r(X)=\sum_{k=0}^{n-1}r_kX^k$. Now try three things:

(1) Prove that for any pair of indices $i,j$ you have $A_{ij}\phi_A(A_{ij})=0$. This should follow from $\phi_A(A)=0$ (which implies $A\phi_A(A)=0$) and the assumption given in the problem. If you need to, write the characteristic polynomial explicitly: $\phi_A(X)=\sum_{k=0}^{n}\phi_kX^k$.

(2) Prove that $(A^m)_{ij}=\sum_{k=0}^{n-1}r_k(A^{k+1})_{ij}=\sum_{k=0}^{n-1}r_k(A_{k+1})_{ij}$. This should follow from $A^m=A\cdot A^{m-1}=A(\phi_A(A)q(A)+r(A))=A\cdot r(A)$.

(3) Prove that $(A_m)_{ij}=\sum_{k=0}^{n-1}r_k(A_{k+1})_{ij}$ as well! This should follow from (1) above.

Title: Raising entries to $k$th power

Body:
Let $A$ be an $n \times n$ real matrix, and define $A_k$ to be the matrix whose entires are $(a_{ij})^k$. Prove that if $A^k = A_k$ for $k = 1, \ldots, n + 1$, then $A^m = A_m$ for all $m$.

My attempt:

We prove by induction on induction on $m$. $m = 1$ is true by assumption. Suppose it's true for $m = 1, \ldots, n + 1$ . Considering $A^{n+2}$ and defining $X = A^{n+1} = A_{n+1}$, we have:
\begin{align*}
(A^{n+2})_{i,j} & = ((A^{n+1})A)_{ij} \\
& =  (XA)_{ij} \\
& = \sum\limits_{k=1}^n x_{ik} a_{kj} \\
& = \sum\limits_{k=1}^n (a_{ik})^n (a_{kj})
\end{align*}

How does this look?


问:
LCM of 3 numbers is given then what can't GCD be
This question was asked to me by a junior and I was unable to solve it and in fact couldn't even start despite of having studied considerable number theory.

$\text{lcm}$ of three different numbers is $120$ then which of the following can't be it's HCF?

(A) $8$

(B) $12$

(C) $24$

(D) $35$

I have studied elementary number theory from David Burton but I am absolutely clueless about this particular problem.

I could think of $\gcd(a,b) \text{lcm}(a,b)=ab$ , but is this extendable  to more than two variables? and even if it is extendable it doesn't seem to be useful.

Thanks for any help!!

答:
Let lcm be $l$ and gcd (hcf) be $d$, $l = \dfrac{abc}{d}$, where $a, b, c$ are your three numbers.

Since $d|a, d|b, d|c$, $d$ must also divide divide $l$. Of the four answers, 35 is only one that does not divide 120.


问:
Final step in proving $(C[0, 1], \|\cdot\|_1)$ is not a Banach space
My professor did the following proof in my functional analysis lecture:
Check that $(C[0, 1], \|\cdot\|_1)$ is not a Banach space, where $\|f\|_1 = \int_0^1 |f(x)|\,{\rm d}x.$

Proof: taking  $(f_n)_{n \geq 1}$ a sequence in $C[0, 1]$ given by: $$f_n(x) = \begin{cases} \frac{1}{\sqrt x}, &\text{ if }  \frac{1}{n} \le x  \le 1 \\ \sqrt n, &\text{ if } 0 \le x  \le \frac{1}{n} \end{cases} $$

If $n > m$, I computed: $$\|f_m - f_n\|_1 = \frac{1}{\sqrt m} - \frac{1}{\sqrt n}$$

Sending $m,n$ to $+\infty $ , $$\|f_m - f_n\|_1 \rightarrow 0$$ which proves that the sequence is Cauchy

Then if $\exists f \in C[0, 1]$ such that when  $ n\rightarrow \infty , \|f_n - f\|_1\rightarrow 0 $
now when $ k\rightarrow \infty , f_{n_k} \rightarrow  f  $ almost everywhere in $[0,1]$, then $f(x) = \lim_{k \to \infty } f_{n_k}(x)= \frac{1}{\sqrt x}$ almost everywhere in $[0,1]$

but no continuous function $f$ in $[0,1]$  exists that coincides almost everywhere with the function  $\frac{1}{\sqrt x}, x \in [0,1]$ , therefore  $C[0, 1]$ is not complete

I don't understand the part after Cauchyness of $(f_n)$ is proven
Where did that $k$ variable come from? Looks like it has to do with a subsequence but I don't get what they are doing and where did that "almost everywhere" come from too ? How did they get the function out of the 1-norm?  From this, how does it follow $\lim_{k \to \infty } f_{n_k}(x)= \frac{1}{\sqrt x}$ almost everywhere in $[0,1]$ ?
And then he writes "but no continuous function $f$ in $[0,1]$  exists that coincides almost everywhere with the function  $\frac{1}{\sqrt x}, x \in [0,1]$", how can you know that if that is precisely what we are trying to prove here ?
Can someone help me clear this up?

Note: I am just starting with measure theory, so I know "almost everywhere" means "except in a zero-measure set", but I have no experience, so please be explicit if using some known property or theorem

Thanks.

答:
The norm that is used is the $L^1([0,1])$ norm.

It is known in measure theory, that if a sequence of functions converges in $L^1([0,1])$,
that there exists a subsequence that converges pointwise almost everywhere to the same limit.
This subsequence is most likely where the $k$ comes from.

The convergence $\lim_k f_{n_k}(x) = \frac1{\sqrt{x}}$
can be concluded from the pointwise convergence
$\lim_n f_n(x)=\frac1{\sqrt{x}}$ for all $x\in (0,1]$.

No continuous function from $C[0,1]$ exists which coincides with $\frac1{\sqrt{x}}$
almost everywhere because
all functions from $C[0,1]$ are bounded.
But if a function is equal to $f(x)=\frac1{\sqrt{x}}$ almost everywhere,
then it cannot be bounded by some $M>1$, because $f(x)>M$ holds for $x\in (0,1/M^2)$,
and the set $(0,1/M^2)$ has positive measure.


问:
Whether the limit on representable functors be non-representable?
I'm looking for examples of the following situation:

Let $A$ be a complete and cocomplete category, $B$ is a small category and $T\colon B\to\mathbf{Set}^{A^{op}}$ be a functor, such that for any $b\in B$ functor $T(b)$ is representable. Could it be that the functor $\varprojlim T$ is not representable?

答: By the Yoneda-Lemma, $T$ lifts to a diagram $X : B \to A$, which has a limit $\{L \to X_b\}$. Then one easily checks that $\{\hom(-,L) \to T_b\}$ is a limit (in fact the Yoneda embedding preserves all limits).</p>


问:
prove the dimension of invariant vectors set is constant
When I read the proof of “the fixed point set of an isometric map in Riemannian manifold is a totally geodesic submanifold”, there is a question about invariant vectors set.

Let $\phi:M\to M$ be an isometry provided M is a Riemannian manifold. For $x\in M$, defining invariant vectors set
$$H:=\{v\in T_x M|(\text{d}\phi)_x(v)=v\}\,,$$
prove dim(H) is a constant.

I am not sure this question is definitely right, looking forward to some hints and ideas, thank you!

答:
I think your statement is true on connected component of $\mathrm{Fix}(\phi)$, though I don't have a counter example for different components with different dimensions if $M$ is connected.

Suppose $\phi(x)=x$, and suppose its connected component in $\mathrm{Fix}(\phi)$ is not reduced to $\{x\}$. Let $v \in T_xM$ such that $\mathrm{d}\phi(x)v = v$. Let $\gamma$ be the unique geodesic with $\gamma(0) = x$ and $\gamma'(0) = v$. Then $\phi\circ \gamma$ is a geodesic (as $\phi$ maps geodesics to geodesics), with same initial data than $\gamma$. Thus, $\phi\circ \gamma = \gamma$.

Now, consider $H_x \subset T_xM$ the set of all fixed vectors of $\mathrm{d}\phi(x)$. It is a linear subspace. Let $U\subset T_xM$ be a convex neighbourhood of the origin on which  the exponential map $\exp_x$ is a diffeomorphism onto its image. Suppose moreover that $\exp_x(U)$ is geodesically convex (one can assume this by reducing $U$). The idea is to prove that $\exp_x(U\cap H_x) = \mathrm{Fix}(\phi)\cap \exp_x(U)$. If this result is true, this shows that $\mathrm{Fix} (\phi)$ is a submanifold of $M$ with $H_x = T_x \mathrm{Fix}(\phi)$. Thus, $\dim H_x$ is locally constant as the rank of the tangent space of a submanifold.

The first inclusion $\exp_x(H_x\cap U) \subset \mathrm{Fix}(\phi)\cap \exp_x(U)$ is clear because of the first paragraph: the entire geodesic $\gamma$, with $\gamma(0) = 0$ and $\gamma'(0) = v$ is fixed by $\phi$, thus $\phi(\gamma(t)) = \gamma(t)$ for all $t$ and $\exp_x(tv) \in \mathrm{Fix}(\phi)$.

Conversly, suppose $p \in \mathrm{Fix}(\phi)\cap \exp_x(U)$. As $\exp_x(U)$ is geodesically convex, and $\exp_x$ is a diffeomorphism from $U$ to $\exp_x(U)$, let $\gamma$ be the unique minimizing geodesix from $x$ to $p$. Then $\phi\circ \gamma$ is also a minimizing geodesic from $x$ to $p$. By the assumptions on $U$, $\gamma = \phi\circ \gamma$, and as $\gamma(0)$ is a fixed point of $\phi$, this shows that $\gamma'(0)$ is fixed by $\mathrm{d}\phi(x)$ and $v \in H_x$.

We have shown that $\exp_x\left(H_x \cap U \right)$ is diffeomorphic to $\mathrm{Fix}(\phi) \cap \exp_x(U)$, and then it is a submanifold. The results follow.

Notice that we have shown more than that: we have shown that $\mathrm{Fix}(\phi)$ is a geodesic submanifold.


问:
Singular Value Decomposition of $A^{T}A$
How to show that the singular values of $A^{T}A$ are $σ_{1}^{2},...,σ_{n}^{2}$, and thus $∥A^{T}A∥_{2}$ = $σ_{max}^{2}$.
In order to do this I have to find a singular vale decomposition for $A^{T}A$ ?

答:
Note that
$$
A^TA=(U\Sigma V^T)^T(U\Sigma V^T=V\Sigma^TU^TU\Sigma V^T=V(\Sigma^T\Sigma)V^T
$$
and that $\Sigma^T\Sigma$ is a diagonal matrix with nonnegative entries on the diagonal. Thus this is a singular value decomposition of $A^TA$. The entries on the diagonal of $\Sigma^T\Sigma$ are $\sigma_i^2$, where $\sigma_1,\dots,\sigma_n$ are the singular values of $A$.

Recall that the singular value decomposition is essentially unique, in the sense that if $A=U_1\Sigma_1V_1^T=U_2\Sigma_2V_2^T$, with $\Sigma$ (pseudo)-diagonal with nonnegative entries and $U_1,U_2,V_1,V_2$ are orthogonal, then $\Sigma_1$ equals $\Sigma_2$ up to permutation of the (pseudo-)diagonal elements. The orthogonal matrices are not unique, though.


问:
Is set difference commutative and associative?

Given question:

The set difference of two sets $A$ and $B$ is $A \setminus B = \{x \in A \;|\; x \not\in B \}.$

Recall that we would say that set difference is commutative if $A \setminus B = B \setminus A$ for all sets $A$ and $B$, and we would say that set difference is associative if $A \setminus (B \setminus C) = (A \setminus B) \setminus C$ for all sets $A$, $B$, and $C$.

Which of the following is true?

(a) Set difference is neither commutative nor associative.

(b) Set difference is commutative but not associative.

(c) Set difference is associative but not commutative.

(d) Set difference is both commutative and associative.

My actual problem: I understand the commutative and associative properties of sets, but I don't really understand the first sentence of the question.

Can someone please explain this question to me? And can someone guide me through this question? Thank you!

答:
The associativity might be understood with a geometrical counter example. Consider $A$ as the disk in $\mathbb{R}^2$ of finite radius, $B$ the infinite line at $45$ degrees and $C$ the $x$-axis.

$B-C$ is $B-\lbrace 0\rbrace$. $A-(B-C) = (A-B)\cup \lbrace 0 \rbrace$ (the disk $A$ without its diagonal but with the element zero).

$A-B$ is the disk without its diagonal, and $(A-B)-C$ is the disk without its diagonal and the intersection with the $x$ axis.

Thus $A-(B-C)\neq (A-B)-C$.

It will hold only for a certain case described here.


问:
Path of particles moving from the corners of an equilateral triangle toward each other at a constant rate
So I just was solving this standard problem when a question struck my mind. What is the nature of this path? I tried my best and all i was able to do was to prove that it is not a circle. Here is the pic:

Basically three particles starts moving with a constant speed from their respective corner of an equilateral triangle such that velocity is one particle is always directed to another.
Once again, I am trying to find the nature of the path followed by any particle.

答:
Let's choose a coordinate system with the origin $O$ at the centre of the triangle and with a particle initially at $(1,0)$.
At every moment the particles lie at the vertices of an equilateral triangle, their distances $r$ from $O$ being equal and their polar angles $\theta$ differing by $120°$.

Velocity vector $\vec v$ of the first particle is directed towards the second particle: its projection along the radial direction is $v_r=\dot r=-v\cos30°=-(\sqrt3/2)v$, while its projection along the azimuthal direction is $v_\theta=r\dot\theta=v\cos60°=(1/2)v$.
It follows that:
$$
{dr\over d\theta}={\dot r\over\dot\theta}=-\sqrt3r,
$$
which can be solved to yield
$$
r=e^{-\sqrt3\theta}.
$$
This is the polar equation of a logarithmic spiral.


问:
If vectors are linear independence they span the space?
is it possible to assume
span just because the vectors are

Linear independence?

or in other words any set of n vectors
 that are linear independence span Rn?

答:
No. Counter-example: $(1,0,0)$ and $(0,1,0)$ are linearly independent but do not span $\Bbb R^3$, only the plane $z=0$.

The correct fact is: if $V$ is a vector space with $\dim V = n$, and $S \subseteq V$ is a set with $n$ elements, then the following are equivalent:

$S$ is linearly independent;

$S$ spans $V$;

$S$ is a basis for $V$.

The crucial assumption is that $S$ has exactly $n$ elements.


问:
Can an absorbing CTMC be reversible?
Can a CTMC with an absorbing state be reversible? I guess not, as the product of rates through any loop cannot be equal when the loop involves the absorbing state (Kolmogorov criterion). Is my intuition correct? Is there any way of formalising this intuition?</p>

答:
It's reversible with respect to the probability measure concentrated on the absorbing state.

There's a famous paper by Chung and Walsh on how to construct more sensible Markov chains that

may be considered the reversed process in this sort of situation.

Title: Can an absorbing CTMC be reversible?


问:
What does it mean to divide?
So I'm in year 11 (10th grade for americans) and I have a really stupid question..

What does it mean to divide in maths?

I recently looked it up and it said "To divide means to slit the number up into equal groups". However, other sites said "To divide means to see how many times the divisor fits into the dividend"

Could someone please tell me which one it is?

Thanks, sorry for such a stupid question

答:
It's both!  Technically speaking, for real numbers $a,b,c$, with $b\neq 0$, we say that $a/b = c$ means that $a = b\cdot c$, i.e division is the inverse operation of multiplication.  Now as to how we can interpret this operation, there are several possibilities, and you've hit on two of them.

$1.)$ "To divide means to split the number up into equal groups"

Suppose you have $15$ objects which you want to split into $3$ equal groups.  Then we can think of $15/3 = 5$ as telling us that in order to have three equal groups we need each group to contain five items, because $15 = 5 + 5 + 5$.

$2.)$ "To divide means to see how many times the divisor fits into the dividend"

Now let's say we want to see how many times $3$ fits into $15$.  Again we compute $15/3 = 5$, which we interpret as meaning that $3$ fits into $15$ five times, i.e. $15 = 3 + 3 + 3 + 3 + 3$.

Note, however, that because $5 + 5 + 5$ and  $3 + 3 + 3 + 3 + 3$ are both perfectly valid ways of thinking about $15$, neither way of thinking of division is necessarily better than the other, though depending on the context we may find one interpretation easier to think about/visualize that the other.

Title: What does it mean to divide?


问:
Prove $\sin x\ge x-\frac{x^3}{3!}$

Prove $$\sin x\ge x-\frac{x^3}{3!}$$ for $x\ge 0$.

I know that a calculus/continuity proof exists, but I am curious if this can be proved without that. Here is a sketch I have made.;

we will use for $x\ge 0$;

$$\sin x\le x\le \tan x$$

proof of this see here

I got a weaker bound :
$$\tan\left(\frac{x}{2}\right)\ge \frac{x}{2}$$
$$\sin\left(\frac{x}2\right)\cos\left(\frac{x}2\right)\ge \frac{x}{2}\cos^2\left(\frac{x}{2}\right)$$
$$\sin x= x\left[1-\sin^2\left(\frac{x}{2}\right)\right]\ge x\left(1-\frac{x^2}{4}\right)= x-\frac{x^3}{4}$$
Thus $$\sin x \ge x-\frac{x^3}{4}$$
As you can see is there any way I can take this to strengthen the inequality, to get $$\sin x\ge x-\frac{x^3}{6}.$$
Also could this possibly be extended by strengthening inequality further to get the Taylor series. I think I am going too far!

答:
Well, from the celebrated triplication formula, we get $$\sin3x=3\,\sin x-4\,\sin^3x.$$ This, of course, means that $$3^{k}\sin x/3^k-3^{k+1}\sin x/3^{k+1}=-4\cdot3^{k}\,\sin^3 x/3^{k+1}.$$ Summing the telescopic series and observing $3^{k}\sin x/3^k\to x$ as $k\to\infty$, we get
$$\sin x-x= -4\,\sum^\infty_{k=0}3^{k}\,\sin^3 x/3^{k+1},$$ i.e.
$$x-\sin x= 4\,\sum^\infty_{k=0}3^{k}\,\sin^3 x/3^{k+1}.$$
Since $\sin x\le x$ for non-negative $x$, this means
$$x-\sin x\le4\,\sum^\infty_{k=0}3^k\,\left(x/3^{k+1}\right)^3=4\cdot\frac1{27}\cdot\frac1{1-\frac19}\,x^3=\frac16\,x^3.$$

Title: Prove $\sin x\ge x-\frac{x^3}{3!}$


问:
clarification of continuous functions and Cauchy sequences
A continuous function need not preserve a Cauchy sequence. For instance,

$f : (0,1) \to (e,\infty)$ where $a_n = \frac{1}{n}$ and $f(x) = e^{1/x}$

If $f$ is uniformly continuous then it will preserve.

My question is:

If the domain is complete or the co-domain is complete does this have an effect on preserving a Cauchy sequence?

答:
Continuous functions preserve Cauchy sequences if their domain is complete. If that's the case and $x_n$ is a Cauchy sequence in the domain, then $x_n$ converges to some $x$ in the domain. But then due to continuity, $f(x_n)$ converges to $f(x)$ and is thus a Cauchy sequence.

The codomain has no influence on this. For a counterexample where the domain is incomplete and the codomain is complete, yet a continuous function doesn't preserve Cauchy sequences, take any arbitrary continuous function which doesn't preserve Cauchy sequences, and replace its codomain by its own closure. The function still doesn't preserve Cauchy sequences, even though the codomain is now complete.


问:
Proving the duplication formula
I'm trying to prove the famous Legendre duplication formula:

$$ \Gamma(2z) = \frac{2^{2z-1} \Gamma(z) \Gamma(z+\frac{1}{2})}{\sqrt{\pi}}   $$

I have to prove this using these two identities/theorems:

$$ \Gamma(z)= \lim_{n \rightarrow \infty}  \frac{n! n^{z}}{z(z+1)...(z+n)}$$

and

$$ (2n)! \sim \frac{2^{2n} (n!)^2}{\sqrt{\pi n}}   $$ as $n \rightarrow \infty $

I put in $ z = 2z $ in the first one and obtained:

$$ \Gamma(2z) = \lim_{n \rightarrow \infty}  \frac{n! n^{2z}}{2z(2z+1)...(2z+n)} $$.

I then tried multiplying both the numerator and denominator by various factors to try to incorporate the other identity, but it was of no use. Can anyone tell me what direction I'm supposed to go from here?

答:
Hint:

now do the same for the product $\Gamma(z) \Gamma(z+1/2)$ and compare

Title: Proving the duplication formula


问:
Is this a proper use of induction? ($(n^2+5)n$ is divisible by 6)
Just want to get input on my use of induction in this problem:

Question. Use mathematical induction to prove that $(n^2+5)n$ is divisible by $6$ for all integers $n \geqslant 1$.

Proof by mathematical induction.

(1) show base case ($n=1$) is true:
$$
((1)^2 + 5) (1) = 6
$$
$6$ is indeed divisible by $6$, so base case ($n=1$) is true

(2a) Assume case $n$ is true: $(n^2+5)n$ is divisible by $6$.

(2b) Show that case $n$ $\implies$ case $(n+1)$
$$
\begin{align*}
((n+1)^2+5)(n+1)
&\rightarrow
((n^2+2n+1)+5)(n+1)
\\ &\rightarrow
[(n^2+5)+(2n+1)](n+1)
\\ &\rightarrow
(n^2+5)n + (n^2+5)+(2n+1)n+ (2n+1)
\\ &\rightarrow
(n^2+5)n + [(n^2+5)+(2n^2+n)+ (2n+1)]
\\ &\rightarrow
(n^2+5)n + [(3n^2+3n)+6]
\end{align*}
$$

Now we can see case $(n+1)$ $= (n^2+5)n + (3n^2+3n)+6$.

We know $6$ is divisible by $6$ and we are assuming $(n^2+5)n$ is divisible by $6$ already, so all we need to do is show $(3n^2+3n)$ is divisible by $6$:

Letting $n=1$ for $(3n^2+3n)$ gives: $(3(1)^2+3(1)) = 6$

Thus, it has been demonstrated that $(n^2+5)n$ is divisible by $6$ for all integers $n \geqslant 1$.

I'm not sure if letting $n=1$ for that last expression is enough to prove it is divisible by $6$

答: $(n^{2} + 5)n \equiv (n^{2}-1)n \equiv (n-1)n(n+1) \pmod 6$. Since these are three consecutive integers, one of them must be congruent to $0\pmod 3$ and one must also be even, or congruent to $0 \pmod 2$. Then as $\gcd (2,3) = 1$, the product $(n-1)n(n+1) \equiv 0 \mod 6$. Altogether meaning that $6 | (n^{2}+5)n$ for all $n$.


问:
Why do $e^i$ and $i^e$ both have absolute value 1?
Why do $e^i$ and $i^e$ both have absolute value 1? I don't know how to view $i^e$ as a complex number. What is its real part and imaginary part?

答: Complex exponentiation is in general multivalued. Since $e^z=i$ iff $z=\pi i(1+4n) /2$ for some $n\in\Bbb Z$, the branches of $\ln z$ give $i^e=\exp(e\pi i(1+4n) /2)$. All such values are of modulus $1$.


答:
We define $z^w$ as $z^w=e^{w\log(z)}$ where $\log(z)$ is the multivalued function

$$\log(z)=\text{Log}(|z|)+i\arg(z)$$

where $\arg(z)$ is the multivalued argument of $z$.

Here, we have $i^e=e^{e\log(i)}$.  Inasmuch as $\text{Log}(|i|)=\text{Log}(1)=0$ and $\arg(i) =\frac\pi2+2n\pi$, $n\in \mathbb{Z}$, we have

$$\begin{align}
i^e&=e^{e\log(i)}\\\\
&=e^{e\left(\text{Log}(|i|)+i\arg(i)\right)}\\\\
&=e^{e\left(0+i\left(\frac\pi2+2n\pi\right)\right)}\\\\&=e^{ie(\pi/2+2n\pi)}
\end{align}$$

which clearly has unit magnitude.

Body: Why do $e^i$ and $i^e$ both have absolute value 1? I don't know how to view $i^e$ as a complex number. What is its real part and imaginary part?


问:
How do I show a function has a unique positive root?
I have to show that the function: $f(x) = x^3 + x^2 - 1$ has a unique positive root. It’s for numerical methods, would anyone have any tips? I’ve been trying to use fixed point methods but I’m not getting anywhere.

答: Note that the number of sign changes between nonzero coefficients is $1$. Thus, by Descartes' Rule of Signs, we have that the number of positive real roots is either $1$, or an even number less than $1$. However, since we cannot have a negative number of roots, there must be $\boxed{1\text{ positive root.}}$


答:
You have
$$f'(x)=3x^2+2x=x(3x+2)>0$$
if $x>0$ so that $f$ is increasing on $[0,\infty[$. Moreover $f(0)=-1<0$ and $f(1)=1>0$. By the intermediate value theorem there is a root on $[0,1]$ and by monotonicity it is the only positive root.

Title: How do I show a function has a unique positive root?

Body: I have to show that the function: $f(x) = x^3 + x^2 - 1$ has a unique positive root. It’s for numerical methods, would anyone have any tips? I’ve been trying to use fixed point methods but I’m not getting anywhere.


问:
Prove that this graph with 20 edges on 11 vertices is not 3-colorable.

Let $G$ be the graph with $11$ vertices labeled $0, 1, 2,..., 10$ and $20$ edges
$$(1, 2),(2, 3),(3, 4),(4, 5),(5, 1),\\
(1, 7),(2, 8),(3, 9),(4, 10),(5, 6),\\
(1, 10),(2, 6),(3, 7),(4, 8),(5, 9),\\
(0, 6),(0, 7),(0, 8),(0, 9),(0, 10).$$
Prove that $G$ is not $3$-colorable.

I have tried to find the clique number to show that the lower bound is at least $4$; however, the largest clique I could find was on $2$ vertices, so that was not a helpful strategy. I then tried to find that the independence number was less than $3$ so that
$$\chi(G)\geq \frac{|V|}{\alpha(G)}$$
where $\alpha(G)$ is the independence number. Again, however, I found an independent set on $4$ vertices, that of $\{2,5,7,10\}$, so I am nowhere closer to proving what I'm supposed to. Any help would be great!

答:
As I suggested in the comments; this graph is the Grötzsch graph. It is triangle free and its independence number is $5$. Here's a nicely symmetric drawing of the graph, with vertex $i$ labeled $v_i$:

Suppose the graph is $3$-colorable, with colors $1$, $2$ and $3$. Let $c_i$ denote the color of $v_i$. First note that the five vertices of the inner star cannot all be the same color, so without loss of generality $c_2\neq c_5$. Relabeling the colors and reflecting we may assume that $c_0=1$, $c_6=2$, $c_5=1$ and $c_2=3$. Then necessarily $c_8=2$, and continuing along the outer star we find that $c_4=3$ and then $c_{10}=2$, and now $v_1$ cannot be colored.


问:
Polygamma function approximation to infinity
Be $\psi_0(s)$ the polygamma function of order zero in $s \in C$. Do you think is correct to write
$
\psi_{0}(s) + \psi_{0}(-s) = \sum_{n=1}^{\infty} \frac{1}{-s+n} + \sum_{n=1}^{\infty} \frac{1}{s+n} = lim_{n \rightarrow \infty} \psi_0(-s + n + 1) + \psi_0,(s + n + 1) -\psi_0 (1 - s) - \psi_0(s + 1)  =  -\psi_0 (1 - s) - \psi_0(s + 1)$

where partial sum is given by mathwolfram site
rappresenting $\psi(s),\psi(-s)$ as series
$\sum_{m=1}^n(1/(-s + m) + 1/(s + m)) = \Psi_0(-s + n + 1) + \Psi_0,(s + n + 1) -\Psi_0 (1 - s) - \Psi_0(s + 1) $

答:
The correct approximation  as $n\to\infty$ is
$$\sum _{k=1}^{n } \frac{1}{k-s}+\sum _{k=1}^{n } \frac{1}{k+s}\sim \frac{1}{n}+2 \log n -\psi ^{(0)}(s+1)-\psi ^{(0)}(1-s)$$


问:
proving summation using induction
we need to prove that for ever $n∈N$ the following equality is right
$$\frac{3\sum_{i=1}^n i^5}{{\sum_{i=1}^n i^3}} = 2n^2+2n-1$$
so first of i checked for n=1 and we get
$$\frac{3\sum_{i=1}^1 i^5}{{\sum_{i=1}^1 i^3}} = 2*1^2+2*1-1$$ which is $3=3$

now I assume for $n=k$

$$\frac{3\sum_{i=1}^k i^5}{{\sum_{i=1}^k i^3}} = 2k^2+2k-1$$
and next is to solve for $n=k+1$
$$\frac{3\sum_{i=1}^{k+1} (i^5)}{{\sum_{i=1}^{k+1} i^3}} = 2(k+1)^2+2(k+1)-1$$

$$\frac{3\sum_{i=1}^{k+1} (i^5)}{{\sum_{i=1}^{k+1} i^3}} = 2k^2+6k+3$$

now I tried to separate the $\sum_{i=1}^{k+1}$

$$\frac{3\sum_{i=1}^{k} (i^5)+{3\sum_{i=k+1}^{k+1} (i^5)}}{{\sum_{i=1}^{k} i^3}+{\sum_{i=k+1}^{k+1} (i^3)}} = 2k^2+6k+3$$

now since $$\frac{3\sum_{i=1}^k i^5}{{\sum_{i=1}^k i^3}} = 2k^2+2k-1$$ i tried putting it instead of what i have in the fraction and i got stuck

$$\frac {2k^2+2k-1+{3\sum_{i=k+1}^{k+1} (i^5)}}{{\sum_{i=k+1}^{k+1} (i^3)}} = 2k^2+6k+3$$

sorry for my English mistakes hope it is understandable , appreciate any help and tips!

答:
Let us denote $\sum_{i=1}^k i^3$ by $S_3$ and $\sum_{i=1}^k i^5$ by $S_5$

Given $$\frac{3S_5}{S_3} = 2k^2+2k -1$$

you are required to prove (RTP) that

$$\frac{3S_5 + (k+1)^5}{S_3 + (k+1^3)} = 2k^2+6k +3$$

In the numerator of the above expression, put $$3S_5 = S_3(2k^2+2k -1)$$ and solve for $S_3$

You'll find that $$S_3 = \frac{k^2(k+1)^2}{4}$$
which is always true.

That completes the proof.

Title: proving summation using induction


Title: Why do $e^i$ and $i^e$ both have absolute value 1?

Body:
From definition, $|e^z| = e^{\text{Re} \ z}$
$$ |i^e| = |e^{\frac{i\pi e}{2}}| = e^{\text{Re} \ \left(\frac{i\pi e}{2}\right) } = e^0 = 1$$
$$|e^i|= e^{\text{Re} \ i}= e^0= 1$$


问:
Exercise 3.4 in Jaynes' Probability Theory
I am having trouble solving exercise 3.4 from E. T. Jaynes' Probability Theory: The Logic of Science.

There are M urns numbered 1 to M, and M balls, also numbered one to M, which are thrown into them, one in each urn. If the numbers of a ball and its urn are the same, we have a match. Show that the probability for at least one match is:
$$h = ∑_{k=1}^M{ \frac{(-1)^{(k+1)}}{k!} }$$

How do I solve it?

Body:
It is a generalization of expression (2.82) in the book. If $M_i$ is a match in urn $i$, then the question reduces to finding $P(M_1+M_2+...+M_m)$, where $m$ is the total number of urns. Using the sum rule of probability
$P(M_1+M_2+...+M_m)=P(M_1)+P(M_2)+...+P(M_m) - P(M_1M_2)-P(M_1M_3) - ... - P(M_{m-1}M_m)+P(M_1M_2...M_m)$.

Given (3.7),(3.39) and (3.40), $P(M_i)=P(M_j), \forall$ $i$ and $j$, and so are $P(M_iM_j)$ and so on.
In  $P(M_1+M_2+...+M_m)$, there are $\left(\begin{array}{ccc}m\\1\end{array}\right)$ $P(M_i)$'s, $\left(\begin{array}{ccc}m\\2\end{array}\right)$ $P(M_iM_j)$'s, $\left(\begin{array}{ccc}m\\3\end{array}\right)$ $P(M_iM_jM_k)$'s, so on, and $\left(\begin{array}{ccc}m\\m\end{array}\right)$ $P(M_1M_2...M_m)$'s.

Ex. For $m=3$, we have $P(M_1+M_2+M_3)=P(M_1)+P(M_2)+P(M_3)- P(M_1M_2)-P(M_1M_3)-P(M_2M_3)+ P(M_1M_2M_3)$.

There are 3! 3-tuples, which are
(1,2,3)
(1,3,2)
(2,1,3)
(2,3,1)
(3,1,2)
(3,2,1).
$P(M_1)$=2/6, $P(M_2)$=2/6, $P(M_3)$=2/6. $P(M_2|M_1) = 1/2$, $P(M_3|M_1) = 1/2$, and $P(M_3|M_2) = 1/2$, and $P(M_3|M_1M_2) = 1$.

Using the product rule of probability,
$P(M_1+M_2+M_3)=3*2/6 - 3*2/6*1/2 + 1*2/6*1/2 = \sum_{k=1}^{m=3} (-1)^{k+1}/k!=2/3$.


问:
Distribution of $n$ items among $k$ compartments (tennis game)
I'm having a little trouble solving this particular exercise.

Before a tennis game the referee randomly distributes $n$ tennis balls among $r$ ball boys with $n \geq r$. Though not precisely specified in the exericse, I assume we can number the ball boys. (evident from the $J \subseteq \{1,\ldots,r\}$ notation)

(a) For each $J \subseteq \{1,\ldots,r\}$, calculate the probability that all ball boys in $J$ do not get a tennis ball.

(b) Using (a) and the sieve formula (Inclusion–exclusion principle) show the probability that at least one ball boy receives no tennis ball is
$$
    \sum_{k=1}^r (-1)^{k-1} {r \choose k} \left( 1 - \frac{k}{r} \right)^n
$$

For (a) my approach is as follows:
Consider the example $n=10$ balls and $r=5$ ball boys and let $J = \{1,2,3\}$. Then we can imagine the following sequence
$$
    0 0 0 k_1 k_2
$$
where each number from left to right represents the number of balls ball boy $i = 1, \ldots, 5$ receives
with the additional condition that $k_1 + k_2 = 10$ and $k_1, k_2 > 0$. Using the stars and bars method we know that the number of possibilities for the above sequence is
$$
    {n-1 \choose r - |J| - 1} = {9 \choose 1} = 9
$$
and the probability is
$$
    \frac{{n-1 \choose r - |J| - 1}}{r^n}
$$
Can somebody confirm this is right? Is $|\Omega|$ actually $r^n$ in this context?
Am I overcomplicating this? The formula from (b) suggests so to me (somehow).

答:
The stars and bars method should never be used when computing probabilities. There is no plausible random process which would choose uniformly among the outcomes counted by stars and bars.

(Obvious exception: your random model is "the coach lists all the possible distributions of $n$ balls to $r$ ball boys, and selects one uniformly". That's not what's happening here.)

In this case, judging by the answer to (b), the coach independently assigns each ball to one of the $r$ ball boys. For one ball, the probability that none of the ball boys in the set $J$ get it is $1 - \frac{|J|}{r}$. So the overall probability is $(1 - \frac{|J|}{r})^n$.


问:
How would you find the maximum directional derivative in this case?

I have gotten this down to 3a/2 + 4b/5 = 5, but now I'm stuck. Do I use the fact that the maximum directional derivative is in the direction of the gradient to set that equal (2a, b) equal to (3/5, 4/5) to find a second equation?

答:
The directional derivative in the direction of $(\frac{3}{5}, \frac{4}{5})$ at $(1,1)$ is given by

$$\nabla f(1,1)\cdot(\frac{3}{5}, \frac{4}{5})=\frac{6a}{5} + \frac{4b}{5}=5\implies 6a+4b=25$$

We also know that the gradient $(2a,b)$ is in the same direction as $(\frac{3}{5}, \frac{4}{5})$ which means, preserving ratio of rise over run, $$\frac{b}{2a}=\frac{4}{3}\implies b=\frac{8a}{3}$$

Plugging that into our first equation gives $a=\frac{3}{2}$ and $b=4$


问:
Proving by contradiction

Consider the statement:  For all $x, y, z ∈ Z$.  At least one of
$x−y$, $x−z$ and $y−z$ is even. Prove this statement by contradiction.

So the contradictory statement would be that neither one of $x−y$, $x−z$ and $y−z$ is even, eg they're all odd. I know how to do the proof, but with proof by contradiction, would I be allowed to let $x$,$y$, and $z$ equal actual integers, eg $1,2,3$ or would I have to make them equal eg. $2k+3$, $2m+6$ and $2n+8$ to complete this proof?

答:
By the way of contradictio, assume that $x-y$, $z-x$ and $y-z$ are odd numbers.

By adding all three, you get: $(x-y)+(z-x)+(y-z)=0$. But the sum of three odd numbers must be odd. And here you have a contradiction.

MOREOOVER. This proof says that it is also impossible to have exactly 1 odd numbers among them.

Title: Proving by contradiction


问:
Showing convergence in probability for poisson distribution
Given random variable X and N so that, N ∼ Poisson(λ), and X|N ∼ Bin(N,p) where p is a constant (Assume that X = 0 when N = 0 and 0 < p < 1). Note that the moment generating function of a Bernoulli random variable with parameter p is 1 − p + etp, and the moment generating function for Poisson(λ) distribution is exp[λ(et − 1)].

Show that X/λ → p, as λ → ∞

I believe I found the pmf of X not conditioned on N below

$ P(x=x) = \frac{e^{-\lambda p}(\lambda p)^x}{x!} $

Then used $ E(e^{tx}) $ to find the mgf

$ M_x(t) = e^{\lambda p(e^t-1) }  $

But I am no unsure of how to show convergence in distribution.

答:
You've shown $M_X(t) = e^{\lambda p (e^t-1)}$

Show that consequently, $M_{X/\lambda}(t) = e^{\lambda p (e^{t/\lambda} - 1)}$.

Note that $\lim_{\lambda \to \infty} \frac{e^{t/\lambda} - 1}{t/\lambda} = 1$ to conclude that $\lim_{\lambda \to \infty} M_{X/\lambda}(t) = e^{pt}$


问:
Does this proof contain a contradiction?
I have made the following proof and I am asking if there is anything wrong in my steps:

Let $f:\mathbb{R}\to\mathbb{R}$ be a real analytic function with infinitely many zeros. Let $a\neq 0$ be a real number. We know that the set $f^{-1}(a)$ is discrete. I want to make a bijection between (not necessarily an isomorphism) $f^{-1}(a)$ and a finite Abelian group $T$. I have two cases:

1) If the set $f^{-1}(a)$ is finite, then a bijection exists if the two sets $f^{-1}(a)$ and $T$ have the same number of elements.

2) If the set $f^{-1}(a)$ is infinite, then we can find a bijection between $f^{-1}(a)$ and $ℤ$, hence we can mod out  (http://en.wikipedia.org/wiki/Modulo_(jargon)) $ℤ$ by an integer $n≠0$ to obtain a smaller and finite structure whose elements are the classes, namely we obtain the finite group $ℤ/nℤ$. Hence in this cases we can construct a bijection between $ℤ/nℤ$ and a finite Abelian group $T$.

答: I have to object to the second part of your proof. If you have an infinite set, you can't construct a bijection with a finite set, essentially by definition. It also seems to me that it woud be more natural in this problem to consider a bijection between $f^{-1}(a)$ and some finite set $S$, as you are not trying to construct an isomorphism (or homomorphism). The end result would be the same, and it seems that this would be less confused. Trying to relate the set $f^{-1}(a)$ to a group is only causing confusion: the part when you construct a bijection and then mod out doesn't make sense (in the context of this problem/proof). If you want to show that there exists a bijection between $f^{-1}(a)$ and a finite set, you will have to show that case $2$ cannot occur.</p>


答: Assume WLOG that $x-y$ and $y-z$ are both odd (if at least one is even, we are done). However, this means that $(x - y) + (y - z) = x - z$ is even. $\blacksquare$

Title: Proving by contradiction

Body:
Consider the statement:  For all $x, y, z ∈ Z$.  At least one of
$x−y$, $x−z$ and $y−z$ is even. Prove this statement by contradiction.

So the contradictory statement would be that neither one of $x−y$, $x−z$ and $y−z$ is even, eg they're all odd. I know how to do the proof, but with proof by contradiction, would I be allowed to let $x$,$y$, and $z$ equal actual integers, eg $1,2,3$ or would I have to make them equal eg. $2k+3$, $2m+6$ and $2n+8$ to complete this proof?


问:
Least Singular Value of bidiagonal matrix
Consider the $n \times n$, bidiagonal matrix
$$
\left(\begin{array}{ccccc}
x & \\
1 & x \\
& 1& x \\
& & & \ddots \\
& & & 1 & x
\end{array} \right)
$$
It is claimed that the least singular value for this matrix is less than $O(2^{-n})$ when $x$ is fixed and $|x-1| > 1/2$.  Is there a simple way to see this?  I have thought about it as a diagonal shift of a nilpotent matrix, but this does not seem to help.

答: In case I have not made mistake and your matrix has only two non-zero diagonals, since it is lower triangular, its eigenvalues and singular values would be $x$ and $|x|$ which are constant, not $O(2^{-n})$.


问:
Sequence $13^{a_{n+2}}=12^{a_{n+1}}+5^{a_n}$ converges
Let the sequence $(a_n)$, $a_0=0$, $a_1=1$, and $13^{a_{n+2}}=12^{a_{n+1}}+5^{a_n}$. Prove that this sequence is convergent.

It is easy to observe that $a_n\in [0,2]$ so $a_n$ is a bounded sequence. Thus, it is only left to prove that it is monotone. I tried by induction (if $a_{n+1}>a_n$ I tried to prove $a_{n+2}>a_{n+1}$) but I failed. Can you please help me prove that the sequence is monotonous? Or help with any proof that the sequence converges. Thank you so much!

答:
You have
$$
 a_{n+2} = f(a_{n+1}, a_n)
$$
where $f$ is a function which is increasing in both variables. So
$$
 a_n \le a_{n+1} \le a_{n+2}
$$
implies
$$
 a_{n+3}= f(a_{n+2}, a_{n+1}) \ge f(a_{n+1}, a_n) = a_{n+2} \,.
$$
So what you can show with induction is that
$$
 \forall n: \, a_n \le a_{n+1} \le a_{n+2} \, .
$$


问:
Infinite Geometric Series Involving Squares
How to evaluate an expression of form

$$\sum_{n=1}^\infty \frac{n^2}{6^n}$$

Is there any way to generalize this for any natural number $i$?

$$\sum_{n=1}^\infty \frac{n^i}{6^n}$$

答:
The infinite geometric series is pretty well known:

$$\sum_{i = 1}^{\infty} r^i = \frac{r}{1 - r} \;\;  0 \leq r < 1$$

The next more complicated sum is known as Gabriel's staircase or the Arithmetico-geometric series, and its sum is also well known:

$$\sum_{i = 1}^{\infty} ir^i = \frac{r}{(1 - r)^2}$$

The term you ask about, which is $\sum_{i = 1}^{\infty} \frac{i^2}{6^i}$ (I just changed your variable names) is a special case of this sequence:

$$S = \sum_{i = 1}^{\infty} i^2r^i$$

Where $r = \frac16$. The first part of your question then asks is there a general [closed form] formula for such sums? The answer is yes. Using the above results we can derive such a formula:

$$S(1 - r) = S - rS = \sum_{i = 1}^{\infty} i^2r^i - \sum_{i = 1}^{\infty} i^2r^{i+1} = \\
\sum_{i = 1}^{\infty} i^2r^i - \sum_{i = 1}^{\infty} (i - 1)^2r^i = \\
\sum_{i = 1}^{\infty} i^2r^i - (i - 1)^2r^i = \sum_{i = 1}^{\infty} (2i - 1)r^i = \\
2\sum_{i = 1}^{\infty} ir^i - \sum_{i = 1}^{\infty} r^i$$

Now we've reduced to terms we already know: a geometric series plus an arithmetico-geometric series. Applying the formulas we've already seen for those:

$$ = 2\left(\frac{r}{(1 - r)^2}\right) - \frac{r}{1 - r}$$

Remember this is the term for $S(1 - r)$ so to get $S$ we divide by $1 - r$ to get:

$$S = 2\left(\frac{r}{(1 - r)^3}\right) - \frac{r}{(1 - r)^2}$$

Now we see a clear pattern, and this leads us to the second part of your question. All series we've seen so far are special cases of the following series:

$$S_{k, r} = \sum_{i = 1}^{\infty} i^kr^i$$

Does a closed form formula exist for every $k$? There's good news and bad news. The good news is yes, I can prove constructively that for each $k$, there exists such a formula. However, I can't prove that there exists a single closed form formula that covers all values of $k$. Subtle difference in the quantifiers. That's not to say such a formula doesn't exist - it's just I, the author, don't know of one.

To prove the existence of a closed form formula for $S_{k, r}$, we do induction on $k$. Clearly we've already seen closed form formulas for $k = 0, 1, 2$, which is more than enough for our base case. So we only need to prove the inductive case. Take:

$$S_{k+1, r} = \sum_{i = 1}^{\infty} i^{k + 1}r^i$$

We now apply the trick of multiplying by $1 - r$ and apply the binomial theorem to reduce this to a closed form expression involving sums we already know, by our inductive hypothesis.

$$S_{k+1, r}(1 - r) = S_{k+1, r} - rS_{k+1, r} = \sum_{i = 1}^{\infty} i^{k+1}r^i - \sum_{i = 1}^{\infty} i^{k+1}r^{i+1} = \\
\sum_{i = 1}^{\infty} i^{k+1}r^i - \sum_{i = 1}^{\infty} (i - 1)^{k+1}r^i = \\
\sum_{i = 1}^{\infty} i^{k+1}r^i - (i - 1)^{k+1}r^i$$

At this point we notice that by expanding the second term via the binomial expansion, the two powers of $i^{k+1}r^i$ cancel each other out:

$$ = - \sum_{i = 1}^{\infty} \sum_{j = 1}^{k+1} {k + 1 \choose j} (-1)^j i^{k + 1 - j}r^i
$$

And since summation order can be interchanged:

$$ = - \sum_{j = 1}^{k+1}\sum_{i = 1}^{\infty} {k + 1 \choose j} (-1)^j i^{k + 1 - j}r^i
$$

But we can remove from the inner sum any constant w.r.t. the variable $i$ so:

$$ = - \sum_{j = 1}^{k+1}{k + 1 \choose j} (-1)^j\sum_{i = 1}^{\infty}  i^{k + 1 - j}r^i \\
= - \sum_{j = 1}^{k+1}{k + 1 \choose j} (-1)^jS_{k + 1 - j,r}
$$

But remember this was the term for $S_{k+1, r}(1 - r)$ so we have:

$$S_{k+1, r} = \frac{-1}{1 - r}\sum_{j = 1}^{k+1}{k + 1 \choose j} (-1)^jS_{k + 1 - j,r}$$

By our inductive hypothesis since each $S_{k + 1 - j,r}$ has a closed form expression, then the above is a closed form expression for any given $k$.


问:
Differential Forms on a Symplectic Manifold
Let $M$ be a symplectic (algebraic) variety over a field $k$ of dimension $2n$ with a symplectic form $\omega$. Is the map $\Omega^{k}_{M} \to \Omega^{2n-k}_{M}$ given by a multiplication by $\omega^{n-k}$ an isomorphism? I think so but is there any reference?

答:
Just a hint (not sure about a reference, but it is a standard thing):

It is really a thing from linear algebra. If $V$ is a $2n$-dimensional vector space, and $\omega\in\bigwedge^2 V$ is non-degenerate, then the map $\bigwedge^k V\to\bigwedge^{2n-k}V$, $\alpha\mapsto\alpha\wedge\omega^{n-k}$ is bijective.

One way how to prove it is to introduce 3 linear operators $E,F,H$ on $\bigwedge V$. Namely, $E\alpha:=\omega\wedge\alpha$, $F\alpha:=i_\pi\alpha$ (here $\pi\in\bigwedge^2 V^*$ is the inverse of $\omega$), and finally, $H\alpha:=(m-n)\,\alpha$ for $\alpha\in\bigwedge^m V$. These then satisfy $[H,E]=2E$, $[H,F]=-2F$, $[E,F]=H$ (and it's possible that I'm missing some numerical coefficients in the definitions of $E,F,H$, but it's not essential).

In other words, we have an action of the Lie algebra $sl_2$ on $\bigwedge V$. And $\bigwedge^k V$ is the subspace of the vectors of weight $-(n-k)$ and $\bigwedge^{2n-k}V$ the subspace of the vectors of weight $+(n-k)$.

Now I'll suppose that $k$ is of characteristic $0$.
The fact that $E^{n-k}:\bigwedge^k V\to\bigwedge^{2n-k}V$ is a bijection then follows from the fact that for any irreducible representation $W$ of $sl_2$, and for any weight $m\in\mathbb N$ (in our case $m=n-k$), $E^m:W_{-m}\to W_m$ is bijective ($W_N\subset W$ is the space of vectors of weight $N$, and it is $1$ or $0$ dimensional).


答:
This is almost more word play than mathematics but....

Every non-zero complex number, $z$, may be written in polar form as $z = re^{i\theta}$ were $r = |z|$ and $\theta = \arg z$.  If $Re(z) = a$ and $Im(z) = b$ then $r = \sqrt{a^2 + b^2} = \sqrt{z\overline z}$.  And $\arg = \arctan \frac ba$.

Thus $re^{i\theta} = r(\cos \theta + i \sin \theta) = r\cos \theta + ir\sin \theta = a + bi= z$ assuming that $a=r\cos \theta; b= r\sin \theta$ or alternatively (depending on which way you look at it) that $r = \sqrt{a^2 + b^2}$ and $\theta$ is so that $\cos \theta = \frac {a}{\sqrt {a^2 + b^2}}$ and $\sin \theta = \frac {b}{\sqrt{a^2 + b^2}}$ or when $\tan \theta = \frac ba$.

So.... $$e^i = \cos 1 + i \sin 1 \approx 0.54030230586813971740093660744298 + i 0.8414709848078965066525023216303$$.  And $|e^i| =1$ because that is simply how polar notation works.  The $e^{i\theta}$ are all on the unit circle. And all complex numbers are represented by a point on the unit circle, times a scalar $r$ to represent how large it is.  In this case $z = 1\cdot e^i$ were $r = 1$ means it has a magnitude of $1$.

....

Using polar notation we can make sense of an expression such as $z^w$.

$i = 0 + i*1 = \cos \frac \pi 2 + i\sin \frac \pi 2$ so $i = e^{i\frac \pi 2}$.

So $i^{e} = [e^{i\frac \pi 2}]^e = e^{i(\frac {\pi e}2)} = \cos \frac {\pi e}2+i \sin \frac {\pi e}2\approx-0.42821977341382775376026209125985 -0.90367462377639553660085345933434i$.

And why does $|i^e| = 1$?  Well, simply because $|i|=1$ so $|i^e| = |i|^e = 1^e=1$.

======

More complex:  If $z = re^{i\theta}$ and $w = a+bi$ then

$z = r e^{i\theta} = e^{\ln r}e^{i\theta} = e^{\ln r + i\theta}$ and so

$z^w = [e^{\ln r + i\theta}]^{a+bi} = e^{(\ln r + i\theta)(a+bi)} =$

$e^{(\ln ra-\theta b)+(\ln rb+\theta a)i} =$

$e^{\ln ra-\theta b} e^{i(\ln rb+\theta a)} =$

$\frac {r^a}{e^{\theta b}}(\cos(\ln rb+\theta a)+i\sin (\ln rb+\theta a))$.


问:
Solving $2^{16^x} = 16^{2^x}$

Find $x$ if $2^{16^x} = 16^{2^x}$.

If $x = 0$ we have $2=16$.

$8$ times or $(2^3)$ difference and if $x = 1$ we have $65536=256$.

$256$ or $2^8$ difference. I can't see anything useful in figuring this out.

I have a feeling $x$ must be a fraction. I know only know about logarithm. I haven't learned anything about the number $e$ or $ln$ yet.

Title: Solving $2^{16^x} = 16^{2^x}$

Body:
$$2^{16^x} = 2^{(2^4)^x} = 2^{2^{4x}}$$

$$16^{2^x} = (2^4)^{2^x} = 2^{4\times 2^x} = 2^{2^{x+2}}$$

Now equate the two expressions.