问:
For $0<b \leq a$ prove that $\frac{1}{8}\left(\frac{(a-b)^2}{a} \right) \leq \frac{a+b}{2}-\sqrt{ab} \leq \frac{1}{8}\left(\frac{(a-b)^2}{b} \right) $
For $0<b \leq a$ prove that $$\frac{1}{8}\left(\frac{(a-b)^2}{a} \right) \leq \frac{a+b}{2}-\sqrt{ab} \leq \frac{1}{8}\left(\frac{(a-b)^2}{b} \right) $$

I was trying compare the following expressions
$$\frac{a+b}{2}-\sqrt{ab} =\frac{1}{2}(\sqrt{a}-\sqrt{b})^2$$

$$\frac{1}{8}\left(\frac{(a-b)^2}{a} \right)=\frac{1}{2a}\left(\frac{a-b}{2}\right)^2\leq\frac{1}{a}(a-b)^2$$
and use the fact that $\sqrt{a}  \leq a$ when  $a>0$ but I don´t get good results.

Any hint of how I should start?

答:
Hint:
$$
\frac{1}{2}(\sqrt a  - \sqrt b )^2  = \frac{b}{{2(\sqrt a  + \sqrt b )^2 }}\left( {\frac{{(a - b)^2 }}{b}} \right)
$$
and
$$
\frac{1}{2}(\sqrt a  - \sqrt b )^2  = \frac{a}{{2(\sqrt a  + \sqrt b )^2 }}\left( {\frac{{(a - b)^2 }}{a}} \right).
$$
Use the fact that $0<b\leq a$ to estimate the right-hand sides from above and below.


问:
The Board Football Problem (Part I)
The original question is here (The Board Football Problem (Probability)) and part II is here(The Board Football Problem (Part II)). I was told to segment the question in order to increase the chances of it being answered.

As kids we used to play the game "Board Football". I'm not particularly sure of the popularity of the game but the rules were pretty simple to follow. The basic objective of the game was to score as many goals as possible and you played it with nothing more than dice and a notebook.

It's a two player game, which goes on as long as the players don't bored. ie there isn't any way to win/finish the game.Both you (say A) and the opponent (say B) have a dice. Before starting the game you decide the minimum number of "passes" that need to be completed before a goal is scored(say p).

Let's assume that A starts first.A rolls the dice and gets a certain number, say 5. This means that A completes 5 passes in that round and has to complete p-5 more passes in order to progress to the "Final Stage". However, before the round is completed the opponent(B) has the opportunity to "intercept" you and obtain possession of the ball.

The way to do this is pretty simple. B rolls his dice and if he gets the same number as A, then B obtains possession of the ball and the round is completed. In the next round, B will start off from 0 passes.

We weren't particularly finicky back then so even if we rolled a number to exceed the number of passes made, the player in possession was still allowed to progress to the "Final Stage". It didn't matter in what order the passes in each round were made as long as the required passes was obtained.

Once the required passes were made and the player reached the "Final Stage", they had to flip a coin. If it turns up as heads,the player in possession scores and if it turns up as tails, he doesn't score. In both the cases, the possession is reverted back to B for the next round. We considered the coin-flipping part to take place in the same round as the round in which the player in possession completed the required passes.

For example, let a 6 sided dice be used and the required number of
passes be 9.
(That is n=6,p=9) Let us say that A has the ball in the starting.

In the first round, A rolls 4 and B rolls 5. A completes 4 passes within that round.A now has to complete at least 5 more passes in order to get an opportunity to shoot.

In the second round, A rolls 3 and B rolls 3. Possession is overturned and now B controls the ball.B now has 0 passes completed.

In the third round, B rolls 5 and A rolls 2.B has completed 5 passes in this round and needs to complete at least 4 more passes in order to get an opportunity to shoot.

In the fourth round, B rolls 6 and A rolls 4. Although B has overshot the number of passes,  B is permitted to flip the coin. B tosses the coin and gets heads. B scores a goal.B leads by one goal to nil. Now A starts
off with possession of the ball.

So my question is as follows:If we use an n-sided dice and the number of required passes is p, the what is the probability that the player in possession of the ball(starting off from 0 passes completed) scores a goal without losing possession of the ball. Is it possible to calculate the value for this in a non-computational /formulaic manner?

(BONUS QUESTION) Form a graph with the Y-Axis being the probability that the player in possession scores without losing possession of the ball and the number of required passes be the X-Axis. (Let a 10 sided dice be used for this case.)

If possible, determine how different the graph would look [in a visual sense, no need for deeper calculations] if the number of sides on the dice is made to vary. Is the graph just shifted along the x-axis or do the peaks become more gradual?).

PS This isn't a homework question/problem so please don't close it because an answer is being requested. It is an original question. Consider this to be a challenge of sorts.

答:
Disclaimers

I cannot provide a full explanation of all techniques used in this answer. If there is something I use where searching for the key terms does not provide enough clarity for you to find a good resource explaining the idea, just ask.

I don't have a background in things like numerical approximations, and am not very familiar with theorems about things like Markov models or signal processing, so there may be better approaches to many of the calculations I do below.

At the time of writing, I have the calculations/references for most of the Appendix ready, but have not written up all of the exposition just yet.

Setup

Without loss of generality, call the player in possession "A", and the other player "B". They will use an $n$-sided die. Let $P(p)$ be the probability that A scores before any change in possession, when A needs $p$ more passes to have the opportunity to shoot. The question essentially asks for a nice way to calculate $P(p)$ for arbitrary $n$, as well as graphical insight.

Manual Calculation

Recursive Formula

Note that $P(0)=\dfrac{1}{2}$ since that's the chance of winning the coin flip.

When the $n$-sided die is rolled by the players, there are various possibilities of varying probabilities: One possibility is that of an interception, which happens with probability $\dfrac{1}{n}$ when B rolls the right number. And there are $n$ possibilities are of the form "A makes $i$ passes" for some $i\in\left\{ 1,\ldots,n\right\}$. In each of those cases, there is a $\dfrac1n$ chance that A rolls an $i$, and a $1-\dfrac1n$ chance that B does not roll an $i$. Thus, each one of those occurs with probability $\dfrac{1}{n}\left(1-\dfrac{1}{n}\right)=\dfrac{n-1}{n^{2}}$ by the product rule for probability.

When A makes $i$ passes: if $i\le p$ then there are $p-i$ passes left to go, and if $i\ge p$, there are $0$ passes left to go, only the coin flip. Then the sum rule of probability tells us that, for $p>0$, $P(p)=\dfrac{1}{n}*0+{\displaystyle \sum_{i=1}^{n}}\dfrac{n-1}{n^{2}}P\left(\max\left\{ p-i,0\right\}\right)=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{i=1}^{n}}P\left(\max\left\{ p-i,0\right\}\right)$. The first term of $0$ was because there is no chance of winning before a change in possession when there is an interception.

Computer Code

This formula is relatively straightforward to plug into a computer. For example, if we wanted to calculate $P(7)$ for $n=10$, the following Python code outputs 0.41614499445795. Try it online!

```<code>    n=10
    p_init=7
    def prob(p):
        if p==0:
            return 1/2
        else:
            return ((n-1)/(n*n))*sum([prob(max(p-i,0)) for i in range(1,n+1)])
    print(prob(p_init))
</code>```

And the following translation into Wolfram Language code outputs the exact answer of $\dfrac{8322899889159}{20000000000000}$. Try it online!

```<code>    n = 10;
    pInit = 7;
    prob[0] = 1/2;
    prob[p_] :=  prob[p] = (n - 1)/n^2 Sum[prob[Max[p - i, 0]], {i, 1, n}];
    Print[prob[pInit]];
</code>```

However, I don't think this qualifies as a "non-computational /formulaic manner", as requested in the question.

Mathematical Formula

General Information

The "$\max$" part makes this challenging to fit into existing theory about recurrences. So, for convenience, define $P\left(1-i\right)=\dfrac{1}{2}$ for $1\le i\le n$ . With those as initial values (sometimes called "initial conditions"), we can simply write $P(p)=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{i=1}^{n}}P\left(p-i\right)=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{j=p-n}^{p-1}}P(j)$ for $p>0$. This is now a "linear homogeneous recurrence relation of order $n$ with constant coefficients", which is a well-studied situation.

Our relation has "characteristic equation" $x^{n}=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{j=0}^{n-1}}x^{j}$. It turns out that this equation always has $n$ distinct complex  roots $r_{1},\ldots,r_{n}$ (see the Appendix below for a proof). That means that $P(p)$ has a particularly nice form: $P(p)={\displaystyle \sum_{i=1}^{n}}C_{i}r_{i}^{p}$ for some constants $C_{i}$. In fact, the symmetry allows us to write the constants $C_{i}$ explicitly in terms of the roots $C_{i}=\dfrac{1}{2}r_{i}^{n-1}{\displaystyle \prod_{j\ne i}}\dfrac{1-r_{j}}{r_{i}-r_{j}}$. And Using the theory of symmetric polynomials, we can express this in terms of just $r_i$ and $n$, if desired. See the Appendix for all details.

Small $n$

For $n=1$, there is always an interception if $p>0$, so $P(p)=0$ for $p>0$, and we might still take $P(0)=\dfrac{1}{2}$. This is actually consistent with the approach and formula outlined above. The characteristic equation becomes $x^{1}=\dfrac{1-1}{1^2}{\displaystyle \sum_{j=0}^{1-1}}x^{j}=\dfrac01*x^{0}=0$, with root $r_{1}=0$. Then we have $P(p)=\dfrac{1}{2}0^{1-1}[\text{empty product}]0^{p}$. Assuming the combinatorics conventions that $0^{0}=1$ in discrete situations and the empty product is $1$, this reduces to $P(p)=\dfrac{1}{2}*\begin{cases}1 & \text{ if }p=0\\0 & \text{ otherwise}\end{cases}$, as expected.

For $n=2$, the characteristic equation becomes $x^{2}=\dfrac{2-1}{2^2}{\displaystyle \sum_{j=0}^{2-1}}x^{j}=\dfrac{1}{4}\left(x+1\right)$. The roots of this quadratic are $r_{1,2}=\dfrac{1\pm\sqrt{17}}{8}$. Then $C_{1,2}=\dfrac{1}{2}\left(\dfrac{1\pm\sqrt{17}}{8}\right)\dfrac{1-\dfrac{1\mp\sqrt{17}}{8}}{\dfrac{1\pm\sqrt{17}}{8}-\dfrac{1\mp\sqrt{17}}{8}}=\dfrac{17\pm3\sqrt{17}}{68}$. So we have $P(p)=\dfrac{17+3\sqrt{17}}{68}\left(\dfrac{1+\sqrt{17}}{8}\right)^{p}+\dfrac{17-3\sqrt{17}}{68}\left(\dfrac{1-\sqrt{17}}{8}\right)^{p}$. For $p$ from $0$ to $9$, this produces expressions which simplify down to $\frac{1}{2},\frac{1}{4},\frac{3}{16},\frac{7}{64},\frac{19}{256},\frac{47}{1024},\frac{123}{4096},\frac{311}{16384},\frac{803}{65536},\frac{2047}{262144}$.

Note that for large $p$, $\left(1+\sqrt{17}\right)^{p}\approx5^{p}$ is much larger in size than $\left(1-\sqrt{17}\right)^{p}\approx\left(-3\right)^{p}$, so we can approximate by dropping the term with the minus sign: $P(p)\approx\dfrac{17+3\sqrt{17}}{68}\left(\dfrac{1+\sqrt{17}}{8}\right)^{p}$ for large $p$.

For $n=3$, the roots $r_{1,2,3}$ of the characteristic equation $x^{3}=\dfrac{8}{81}\left(1+r+r^{2}\right)$ are given (via the cubic formula) by $r_{k}=\dfrac{1}{27}\left(2+\omega^{k}\sqrt[3]{2357+81\sqrt{817}}+\omega^{-k}\sqrt[3]{2357-81\sqrt{817}}\right)$ where $\omega=\dfrac{-1+i\sqrt{3}}{2}$ (so that $\omega^{-1}=\omega^{2}=\overline{\omega}=\dfrac{-1-i\sqrt{3}}{2}$). We have $c_{1}=\dfrac{r_{1}^{2}\left(1-r_{2}\right)\left(1-r_{3}\right)}{2\left(r_{1}-r_{2}\right)\left(r_{1}-r_{3}\right)}$ and similarly for the other constants. Then $P(p)=c_{1}r_{1}^{p}+c_{2}r_{2}^{p}+c_{3}r_{3}^{p}$. For $p$ from $0$ to $7$, this produces expressions which simplify down to $\frac{1}{2},\frac{1}{3},\frac{8}{27},\frac{61}{243},\frac{428}{2187},\frac{3250}{19683},\frac{24086}{177147},\frac{176008}{1594323}$.

Note that $\left|27r_{1}\right|\approx22$ but (using complex absolute value), $\left|27r_{2,3}\right|\approx14$. So for large $p$, we may write $P(p)\approx c_{1}r_{1}^{p}$. This approximate formula can be written using real numbers alone. Let $s_{1,2}=\sqrt[3]{2357\pm81\sqrt{817}}$, so that $r_{1}=\dfrac{1}{27}\left(2+s_{1}+s_{2}\right)$. Then $c_{1}$ simplifies to $\dfrac{74358+2438\left(s_{1}+s_{2}\right)+243\left(s_{1}^{2}+s_{2}^{2}\right)+25\left(s_{1}s_{2}^{2}+s_{1}^{2}s_{2}\right)}{1458\left(58+s_{1}^{2}+s_{2}^{2}\right)}$.

Higher $n$

For $n=4$, we can do something similar to $n=3$, but the expressions become worse since we're dealing with quartics. For $n=5,6$, and probably all higher $n$, we cannot write $r_{i}$ in terms of radicals. (Abel's Theorem gives us reason to expect that.) We can still use approximations of the roots and evaluate $P(p)={\displaystyle \sum_{i=1}^{n}}c_{i}r_{i}^{p}$. These powers of complex numbers are not so bad if we use something like De Moivre's formula.

If we want to avoid taking so many powers, we can always use a single term approximation as we used for low values of $n$. By Descartes' rule of signs, there is always a single positive real root of the characteristic equation. By a result of Cauchy (discussed in the Appendix), this will be the root of largest absolute value of a polynomial like the characteristic polynomials we have here. So we can always approximate $P(p)\approx c_{1}r_{1}^{p}$ by choosing $r_{1}$ to be the positive real root of the characteristic equation $x^{n}=\dfrac{n-1}{n^{2}}\left(1+x+\cdots+x^{n-1}\right)=\dfrac{\left(n-1\right)\left(1-x^{n}\right)}{n^{2}\left(1-x\right)}$. The last expression comes from the sum of a geometric progression.

Graphs

Form a graph with the Y-Axis being the probability that the player in
possession scores without losing possession of the ball and the number
of required passes be the X-Axis. (Let a 10 sided dice be used for
this case.)

If possible, determine how different the graph would look [in a visual
sense, no need for deeper calculations] if the number of sides on the
dice is made to vary. Is the graph just shifted along the x-axis or do
the peaks become more gradual?).

Graph for $n=10$

When $n=10$, we can first look at low values of $p$ ($0\le p\le 15$, say), for which $P(p)$ is a little erratic: $\frac{1}{2},\frac{9}{20},\frac{891}{2000},\frac{88119}{200000},\frac{8704971}{20000000},\frac{858841839}{2000000000},\frac{84613760451}{200000000000},\frac{8322899889159}{20000000000000
   },\frac{817196087918331}{2000000000000000},\frac{80074373583098079}{200000000000000000},\frac{7828106720557690611}{20000000000000000000},\frac{763263632540788276599}{2000000000000000000000}
   ,\frac{75095735946945922149291}{200000000000000000000000},\frac{7383535218217105514272719}{20000000000000000000000000},\frac{725498238785664501055726371}{2000000000000000000000000000},\frac
   {71244834127637430615074174439}{200000000000000000000000000000}$

But things smooth out for higher values of $p$. For $15\le p\le100$, we have a graph like:

By the analysis worked out earlier, for large $p$, this can be approximated by an exponential function $E(p)$. For $n=10$, $E(p)$ happens to be approximately $0.472463*.981288^p$. This fits extremely well for $p\ge 15$ (the approximation is in dashed orange):

We can understand the fit better by looking at the signed relative error $\dfrac{E(p)-P(p)}{P(p)}$, plotted for $15\le p\le100$ here:

For the record, the approximation is not very good for small $p$:

Graphs for arbitrary $n$

We can plot various $n$ ($1\le n\le 20$) together for the various $p$ ranges.

$0\le p \le 15$:

$0\le p \le 100$:

$0\le p \le 500$:

One other way to look at things collectively is to examine the approximations $E(p)=C(n)*r(n)^p$. Plotting $r(n)$ (approaching $1$) and $C(n)$ (approaching $\frac12$) for $2\le n\le50$ yields:

Appendix

Distinct roots

The characteristic polynomial is $x^{n}-\dfrac{n-1}{n^{2}}\left(x^{n-1}+\cdots+1\right)$. We would like to show that this has no repeated roots. It doesn't take much extra effort to show a slight generalization: For any positive constant $t$, $\chi\left(x\right)=x^{n}-t\left(x^{n-1}+\cdots+1\right)$ has no repeated roots.

Let $r$ be a multiple root of $\left(x-1\right)\chi\left(x\right)=x^{n+1}-\left(t+1\right)x^{n}+t$ (the simplification comes from the telescoping sum caused by the finite geometric series), so that $\left(x-r\right)^{2}$ is a factor of $\left(x-1\right)\chi\left(x\right)$. Then either $r$ is a multiple root of $\chi\left(x\right)$ or $r$ is a single root of $\chi\left(x\right)$ and $r=1$.

Since $\left(x-r\right)^{2}$ is a factor of $\left(x-1\right)\chi\left(x\right)$, the product rule tells us that $r$ must be a zero of the derivative $\dfrac{\mathrm{d}}{\mathrm{d}x}\left(x-1\right)\chi\left(x\right)=\left(n+1\right)x^{n}-\left(t+1\right)nx^{n-1}=x^{n-1}\left(\left(n+1\right)x-\left(t+1\right)\right)$. This forces $r=0$ or $r=\dfrac{n\left(t+1\right)}{n+1}$. Since $t>0$, $0$ cannot be a root of $\left(x-1\right)\chi\left(x\right)=x^{n+1}-\left(t+1\right)x^{n}+t$, so we must have $r=\dfrac{n\left(t+1\right)}{n+1}$.

This value of $r$ must also be a root of the original $\left(x-1\right)\chi\left(x\right)$, so that $\left(\frac{n(t+1)}{n+1}\right)^{n+1}-(t+1)\left(\frac{n(t+1)}{n+1}\right)^{n}+t=0$. Multiplying through by $\left(n+1\right)^{n+1}$, we obtain $0$ $=n^{n+1}\left(t+1\right)^{n+1}-\left(n+1\right)n^{n}\left(t+1\right)^{n+1}+t\left(n+1\right)^{n+1}$ $=\left(n^{n+1}-\left(n+1\right)n^{n}\right)\left(t+1\right)^{n+1}+t\left(n+1\right)^{n+1}$ $=t\left(n+1\right)^{n+1}-n^{n}\left(t+1\right)^{n+1}$. As a polynomial in $t$, the coefficient of $t$ is $\left(n+1\right)\left(\left(n+1\right)^{n}-n^{n}\right)>0$, and all other coefficients (including the constant term) are negative. By Descartes' rule of signs, either two or zero positive values of $t$ are possible, counting multiplicities. Observe that $t=\dfrac{1}{n}$ is a zero of $t\left(n+1\right)^{n+1}-n^{n}\left(t+1\right)^{n+1}$. And it is also a zero of $\dfrac{\mathrm{d}}{\mathrm{d}t}\left(t\left(n+1\right)^{n+1}-n^{n}\left(t+1\right)^{n+1}\right)=\left(n+1\right)^{n+1}-\left(n+1\right)n^{n}\left(t+1\right)^{n}$. Therefore, the possible positive values of $t$ are both $\dfrac{1}{n}$.

In the original characteristic polynomial, $t=\dfrac{n-1}{n^{2}}\ne\dfrac{1}{n}$, so it has no repeated roots. But we can continue to show the more general result. If $t=\dfrac{1}{n}$, then $r=\dfrac{n\left(t+1\right)}{n+1}=1$ and $\chi\left(x\right)=x^{n}-\dfrac{1}{n}\left(x^{n-1}+\cdots+1\right)=\dfrac{1}{n}\left(x-1\right)\left(nx^{n-1}+\left(n-1\right)x^{n-2}+\cdots+2x+1\right)$ by synthetic division, say. But $1$ cannot be a repeated root of $\chi(x)$ since $n*1^{n-1}+\left(n-1\right)*1^{n-2}+\cdots+2*1+1>0$.

Formulas for $C_i$

Formula in terms of all roots

We have $P(p)={\displaystyle \sum_{i=1}^{n}}C_{i}r_{i}^{p}$ and $P\left(1-i\right)=\dfrac{1}{2}$ for $1\le i\le n$. This yields a linear system of $n$ equations in $n$ unknowns $C_{i}$, so linear algebra can help us approach this. The equations are \begin{align*}C_{1}+\cdots+C_{n}&=\dfrac{1}{2}\\\dfrac{1}{r_{1}}C_{1}+\cdots+\dfrac{1}{r_{n}}C_{n}&=\dfrac{1}{2}\\\vdots&\\\dfrac{1}{r_{1}^{n-1}}C_{1}+\cdots+\dfrac{1}{r_{n}^{n-1}}C_{n}&=\dfrac{1}{2}\end{align*} These can be rewritten into the matrix equation $$\begin{bmatrix}r_{1}^{0} & \cdots & r_{n}^{0}\\
\vdots & \ddots & \vdots\\
r_{1}^{1-n} & \cdots & r_{n}^{1-n}
\end{bmatrix}\begin{bmatrix}C_{1}\\
C_{2}\\
\vdots\\
C_{n}
\end{bmatrix}=\begin{bmatrix}\dfrac{1}{2}\\
\dfrac{1}{2}\\
\vdots\\
\dfrac{1}{2}
\end{bmatrix}$$

Incidentally, the square matrix is the transpose of the Vandermonde matrix with $\alpha_{i}=r_{i}^{-1}$. I had tried to form the augmented matrix and to use the beginning steps of Gaussian elimination, but it was too complicated to work through manually. Since the roots $r_{i}$ are distinct, the Vandermonde matrix is invertible and hence so is its transpose. Unfortunately, the inverse of a Vandermonde matrix is quite complicated, so I will not be deriving $C_{i}=\dfrac{1}{2}r_{i}^{n-1}{\displaystyle \prod_{j\ne i}}\dfrac{1-r_{j}}{r_{i}-r_{j}}$ in this answer. It can be confirmed for small $n$ by a CAS like Mathematica. You can see verification for $n\le7$ online.

Formula in terms of $n$ and $r_i$

Taking that formula on faith, we can exploit the symmetry to write $C_{i}$ in terms of the elementary symmetric polynomials in the $r_i$: $s_{0}=1,s_{1}={\displaystyle \sum_{j=1}^{n}}r_{j},\ldots,s_{n}={\displaystyle \prod_{j=1}^{n}}r_{j}$. We have \begin{align*}C_{i}&=\dfrac{1}{2}r_{i}^{n-1}{\displaystyle \prod_{j\ne i}}\dfrac{1-r_{j}}{r_{i}-r_{j}}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{{\displaystyle \prod_{j}\left(1-r_{j}\right)}}{{\displaystyle \prod_{j\ne i}}\left(r_{i}-r_{j}\right)}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{\sum_{j=0}^{n}\left(-1\right)^{j}s_{j}}{\left(-1\right)^{n-1}\dfrac{s_{n}}{r_{i}}+\sum_{j=1}^{n-1}\left(-1\right)^{j-1}\left(n-j\right)r_{i}^{n-j}s_{j-1}}\text{.}\end{align*} (I suspect this is very close to the form one would obtain using the inverse of the Vandermonde matrix.)

Then we can use Vieta's formulas to write the $s_{j}$s in terms of the coefficients of the characteristic polynomial. For convenience, set $t=\dfrac{n-1}{n^{2}}$, so that the characteristic polynomial is $x^{n}-t\left(x^{n-1}+\cdots+1\right)$. This means $s_{0}=1,s_{1}=-\left(-t\right),s_{2}=-t,\ldots$ with $s_{j}=\left(-1\right)^{j+1}t$ for $j>0$. As such, \begin{align*}C_{i}&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{s_{0}+\sum_{j=1}^{n}\left(-1\right)^{j}s_{j}}{\left(-1\right)^{n-1}\dfrac{s_{n}}{r_{i}}+\left(n-1\right)r_{i}^{n-1}s_{0}+\sum_{j=2}^{n-1}\left(-1\right)^{j-1}\left(n-j\right)r_{i}^{n-j}s_{j-1}}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1+\sum_{j=1}^{n}\left(-1\right)^{j}\left(-1\right)^{j+1}t}{\left(-1\right)^{n-1}\dfrac{\left(-1\right)^{n+1}t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}+\sum_{j=2}^{n-1}\left(-1\right)^{j-1}\left(n-j\right)r_{i}^{n-j}\left(-1\right)^{j}t}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1-\sum_{j=1}^{n}t}{\dfrac{t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}-\sum_{j=2}^{n-1}\left(n-j\right)r_{i}^{n-j}t}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1-nt}{\dfrac{t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}-t\sum_{k=1}^{n-2}kr_{i}^{k}}\text{.}\end{align*} The remaining summation resembles a geometric series, and indeed there is trick (often used when dealing with generating functions) involving the derivative of the geometric series formula (see this MathSE question) which allows us to write ${\displaystyle \sum_{k=1}^{n-2}}kr_{i}^{k}=\dfrac{r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}}{\left(1-r_{i}\right)^{2}}$. Then we have:
\begin{align*}C_{i}&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1-nt}{\dfrac{t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}-t\dfrac{r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}}{\left(1-r_{i}\right)^{2}}}\\&=\dfrac{1}{2}r_{i}^{n-1}\dfrac{1-nt}{\dfrac{t}{r_{i}}\left(1-r_{i}\right)+\left(n-1\right)r_{i}^{n-1}\left(1-r_{i}\right)-t\dfrac{r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}}{\left(1-r_{i}\right)}}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}\left(1-nt\right)\left(1-r_{i}\right)}{\dfrac{t}{r_{i}}\left(1-r_{i}\right)^{2}+\left(n-1\right)r_{i}^{n-1}\left(1-r_{i}\right)^{2}-t\left(r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}\right)}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n}\left(1-nt\right)\left(1-r_{i}\right)}{t\left(1-r_{i}\right)^{2}+\left(n-1\right)r_{i}^{n}\left(1-r_{i}\right)^{2}-t\left(r_{i}^{2}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n}\right)}\text{.}\end{align*}

This can be written in many different forms, especially after substituting $\dfrac{n-1}{n^{2}}$ back in for $t$. One form (for $n>1$) is $$\boxed{C_{i}=\dfrac{n}{2\left(n-1\right)}*\dfrac{1-r_{i}}{r_{i}^{-n}-2r_{i}^{1-n}+n^{2}+n-1-\left(2n^{2}+n-2\right)r_{i}+n^{2}r_{i}^{2}}}$$

Large $p$ approximation

As discussed in On finding the largest root of a polynomial by Davenport and Mignotte and New Bounds on the Real Polynomial Roots by Prodanov, Cauchy showed that the absolute values of the zeros of $a_{n}x^{n}+\cdots+a_{0}$ are bounded by the unique positive root of $\left|a_{n}\right|x^{n}-\left(\left|a_{n-1}\right|x^{n-1}+\cdots+\left|a_{0}\right|\right)$. As a consequence, the unique positive root $r\left(n\right)$ of the characteristic polynomial $x^{n}-\dfrac{n-1}{n^{2}}\left(x^{n-1}+\cdots+1\right)$ has the greatest absolute value of any root. However, we need it to be strictly greater than that of the other roots in order to justify a large-$p$ approximation of the form $C\left(n\right)*r\left(n\right)^{p}$.

We can extract more information from a proof of Cauchy's result (see Theorem 8.1.3 in Analytic Theory of Polynomials by Rahman and Schmeisser): If $r$ is a zero of $x^{n}-\dfrac{n-1}{n^{2}}\left(x^{n-1}+\cdots+1\right)$, then $r^{n}=\dfrac{n-1}{n^{2}}\left(r^{n-1}+\cdots+1\right)$, so that $\left|r\right|^{n}=\dfrac{n-1}{n^{2}}\left|r^{n-1}+\cdots+1\right|\le\dfrac{n-1}{n^{2}}\left(\left|r\right|^{n-1}+\cdots+1\right)$ by the triangle inequality, so that $x=\left|r\right|$ makes the characteristic polynomial nonpositive. If we had $\left|r\right|=\left|r(n)\right|$ then we would need equality in the triangle inequality, which would require the powers of $r$ to all point in the same direction. This is impossible (for $n>1$) if $r$ is not a positive real by De Moivre's theorem or similar.

In conclusion, for large $p$ we can indeed approximate $P(p)$ by $C(n)*r(n)^{p}$ where $r(n)$ is the unique positive root of the characteristic polynomial, and $C(n)$ is given by, say, $C(n)=\dfrac{n}{2\left(n-1\right)}*\dfrac{1-r(n)}{r(n)^{-n}-2r(n)^{1-n}+n^{2}+n-1-\left(2n^{2}+n-2\right)r(n)+n^{2}r(n)^{2}}$.

However, it would be helpful to be able to approximate $r(n)$, too. For even moderately large $n$, $r(n)$ is just barely less than $1$. We can use Newton's method starting at $1$ to get approximations. Our first approximation is $1$. Then a better approximation is $1-\dfrac{1^{n}-\dfrac{n-1}{n^{2}}\left(1^{n-1}+\cdots+1\right)}{n1^{n-1}-\dfrac{n-1}{n^{2}}\left(\left(n-1\right)1^{n-2}+\cdots1\right)}$ $=1-\dfrac{1-\dfrac{n-1}{n^{2}}*n}{n-\dfrac{n-1}{n^{2}}*\dfrac{\left(n-1\right)n}{2}}$ $=1-\dfrac{1-\dfrac{n-1}{n}}{n-\dfrac{\left(n-1\right)^{2}}{2n}}$ $=1-\dfrac{2}{n^{2}+2n-1}$.

This approximation $r_{\approx}(n)$ is already quite good (relative error less than $0.5\%$) for $n\ge10$. The corresponding approximation to $C(n)$ simplifies to $C_{\approx}(n)=\dfrac{\left(n^{2}+2n-1\right)^{n+1}\left(n^{2}+2n-3\right)}{2\left(n-1\right)\left(n^{2}+4n-1\right)r_{\approx}(n)^{n}}$.

Now, $C_{\approx}(n)r_{\approx}(n)^{p}$ is not a good approximation to $P(p)$ when $p$ is much greater than $n$. For example, when $n=10$ and $p=100$, we have about $35\%$ relative error. But $n=70$ and $p=100$ brings the relative error below $2\%$, so $C_{\approx}(n)r_{\approx}(n)^{p}$ is a straightforward way to approximate $P(p)$ for large $n$ and $p$ of comparable size.

ContentLicense: CC BY-SA 4.0

Title: The Board Football Problem (Part I)

Body:
Disclaimers

I cannot provide a full explanation of all techniques used in this answer. If there is something I use where searching for the key terms does not provide enough clarity for you to find a good resource explaining the idea, just ask.

I don't have a background in things like numerical approximations, and am not very familiar with theorems about things like Markov models or signal processing, so there may be better approaches to many of the calculations I do below.

At the time of writing, I have the calculations/references for most of the Appendix ready, but have not written up all of the exposition just yet.

Setup

Without loss of generality, call the player in possession "A", and the other player "B". They will use an $n$-sided die. Let $P(p)$ be the probability that A scores before any change in possession, when A needs $p$ more passes to have the opportunity to shoot. The question essentially asks for a nice way to calculate $P(p)$ for arbitrary $n$, as well as graphical insight.

Manual Calculation

Recursive Formula

Note that $P(0)=\dfrac{1}{2}$ since that's the chance of winning the coin flip.

When the $n$-sided die is rolled by the players, there are various possibilities of varying probabilities: One possibility is that of an interception, which happens with probability $\dfrac{1}{n}$ when B rolls the right number. And there are $n$ possibilities are of the form "A makes $i$ passes" for some $i\in\left\{ 1,\ldots,n\right\}$. In each of those cases, there is a $\dfrac1n$ chance that A rolls an $i$, and a $1-\dfrac1n$ chance that B does not roll an $i$. Thus, each one of those occurs with probability $\dfrac{1}{n}\left(1-\dfrac{1}{n}\right)=\dfrac{n-1}{n^{2}}$ by the product rule for probability.

When A makes $i$ passes: if $i\le p$ then there are $p-i$ passes left to go, and if $i\ge p$, there are $0$ passes left to go, only the coin flip. Then the sum rule of probability tells us that, for $p>0$, $P(p)=\dfrac{1}{n}*0+{\displaystyle \sum_{i=1}^{n}}\dfrac{n-1}{n^{2}}P\left(\max\left\{ p-i,0\right\}\right)=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{i=1}^{n}}P\left(\max\left\{ p-i,0\right\}\right)$. The first term of $0$ was because there is no chance of winning before a change in possession when there is an interception.

Computer Code

This formula is relatively straightforward to plug into a computer. For example, if we wanted to calculate $P(7)$ for $n=10$, the following Python code outputs 0.41614499445795. Try it online!

    n=10
    p_init=7
    def prob(p):
        if p==0:
            return 1/2
        else:
            return ((n-1)/(n*n))*sum([prob(max(p-i,0)) for i in range(1,n+1)])
    print(prob(p_init))

And the following translation into Wolfram Language code outputs the exact answer of $\dfrac{8322899889159}{20000000000000}$. Try it online!

    n = 10;
    pInit = 7;
    prob[0] = 1/2;
    prob[p_] :=  prob[p] = (n - 1)/n^2 Sum[prob[Max[p - i, 0]], {i, 1, n}];
    Print[prob[pInit]];

However, I don't think this qualifies as a "non-computational /formulaic manner", as requested in the question.

Mathematical Formula

General Information

The "$\max$" part makes this challenging to fit into existing theory about recurrences. So, for convenience, define $P\left(1-i\right)=\dfrac{1}{2}$ for $1\le i\le n$ . With those as initial values (sometimes called "initial conditions"), we can simply write $P(p)=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{i=1}^{n}}P\left(p-i\right)=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{j=p-n}^{p-1}}P(j)$ for $p>0$. This is now a "linear homogeneous recurrence relation of order $n$ with constant coefficients", which is a well-studied situation.

Our relation has "characteristic equation" $x^{n}=\dfrac{n-1}{n^{2}}{\displaystyle \sum_{j=0}^{n-1}}x^{j}$. It turns out that this equation always has $n$ distinct complex  roots $r_{1},\ldots,r_{n}$ (see the Appendix below for a proof). That means that $P(p)$ has a particularly nice form: $P(p)={\displaystyle \sum_{i=1}^{n}}C_{i}r_{i}^{p}$ for some constants $C_{i}$. In fact, the symmetry allows us to write the constants $C_{i}$ explicitly in terms of the roots $C_{i}=\dfrac{1}{2}r_{i}^{n-1}{\displaystyle \prod_{j\ne i}}\dfrac{1-r_{j}}{r_{i}-r_{j}}$. And Using the theory of symmetric polynomials, we can express this in terms of just $r_i$ and $n$, if desired. See the Appendix for all details.

Small $n$

For $n=1$, there is always an interception if $p>0$, so $P(p)=0$ for $p>0$, and we might still take $P(0)=\dfrac{1}{2}$. This is actually consistent with the approach and formula outlined above. The characteristic equation becomes $x^{1}=\dfrac{1-1}{1^2}{\displaystyle \sum_{j=0}^{1-1}}x^{j}=\dfrac01*x^{0}=0$, with root $r_{1}=0$. Then we have $P(p)=\dfrac{1}{2}0^{1-1}[\text{empty product}]0^{p}$. Assuming the combinatorics conventions that $0^{0}=1$ in discrete situations and the empty product is $1$, this reduces to $P(p)=\dfrac{1}{2}*\begin{cases}1 & \text{ if }p=0\\0 & \text{ otherwise}\end{cases}$, as expected.

For $n=2$, the characteristic equation becomes $x^{2}=\dfrac{2-1}{2^2}{\displaystyle \sum_{j=0}^{2-1}}x^{j}=\dfrac{1}{4}\left(x+1\right)$. The roots of this quadratic are $r_{1,2}=\dfrac{1\pm\sqrt{17}}{8}$. Then $C_{1,2}=\dfrac{1}{2}\left(\dfrac{1\pm\sqrt{17}}{8}\right)\dfrac{1-\dfrac{1\mp\sqrt{17}}{8}}{\dfrac{1\pm\sqrt{17}}{8}-\dfrac{1\mp\sqrt{17}}{8}}=\dfrac{17\pm3\sqrt{17}}{68}$. So we have $P(p)=\dfrac{17+3\sqrt{17}}{68}\left(\dfrac{1+\sqrt{17}}{8}\right)^{p}+\dfrac{17-3\sqrt{17}}{68}\left(\dfrac{1-\sqrt{17}}{8}\right)^{p}$. For $p$ from $0$ to $9$, this produces expressions which simplify down to $\frac{1}{2},\frac{1}{4},\frac{3}{16},\frac{7}{64},\frac{19}{256},\frac{47}{1024},\frac{123}{4096},\frac{311}{16384},\frac{803}{65536},\frac{2047}{262144}$.

Note that for large $p$, $\left(1+\sqrt{17}\right)^{p}\approx5^{p}$ is much larger in size than $\left(1-\sqrt{17}\right)^{p}\approx\left(-3\right)^{p}$, so we can approximate by dropping the term with the minus sign: $P(p)\approx\dfrac{17+3\sqrt{17}}{68}\left(\dfrac{1+\sqrt{17}}{8}\right)^{p}$ for large $p$.

For $n=3$, the roots $r_{1,2,3}$ of the characteristic equation $x^{3}=\dfrac{8}{81}\left(1+r+r^{2}\right)$ are given (via the cubic formula) by $r_{k}=\dfrac{1}{27}\left(2+\omega^{k}\sqrt[3]{2357+81\sqrt{817}}+\omega^{-k}\sqrt[3]{2357-81\sqrt{817}}\right)$ where $\omega=\dfrac{-1+i\sqrt{3}}{2}$ (so that $\omega^{-1}=\omega^{2}=\overline{\omega}=\dfrac{-1-i\sqrt{3}}{2}$). We have $c_{1}=\dfrac{r_{1}^{2}\left(1-r_{2}\right)\left(1-r_{3}\right)}{2\left(r_{1}-r_{2}\right)\left(r_{1}-r_{3}\right)}$ and similarly for the other constants. Then $P(p)=c_{1}r_{1}^{p}+c_{2}r_{2}^{p}+c_{3}r_{3}^{p}$. For $p$ from $0$ to $7$, this produces expressions which simplify down to $\frac{1}{2},\frac{1}{3},\frac{8}{27},\frac{61}{243},\frac{428}{2187},\frac{3250}{19683},\frac{24086}{177147},\frac{176008}{1594323}$.

Note that $\left|27r_{1}\right|\approx22$ but (using complex absolute value), $\left|27r_{2,3}\right|\approx14$. So for large $p$, we may write $P(p)\approx c_{1}r_{1}^{p}$. This approximate formula can be written using real numbers alone. Let $s_{1,2}=\sqrt[3]{2357\pm81\sqrt{817}}$, so that $r_{1}=\dfrac{1}{27}\left(2+s_{1}+s_{2}\right)$. Then $c_{1}$ simplifies to $\dfrac{74358+2438\left(s_{1}+s_{2}\right)+243\left(s_{1}^{2}+s_{2}^{2}\right)+25\left(s_{1}s_{2}^{2}+s_{1}^{2}s_{2}\right)}{1458\left(58+s_{1}^{2}+s_{2}^{2}\right)}$.

Higher $n$

For $n=4$, we can do something similar to $n=3$, but the expressions become worse since we're dealing with quartics. For $n=5,6$, and probably all higher $n$, we cannot write $r_{i}$ in terms of radicals. (Abel's Theorem gives us reason to expect that.) We can still use approximations of the roots and evaluate $P(p)={\displaystyle \sum_{i=1}^{n}}c_{i}r_{i}^{p}$. These powers of complex numbers are not so bad if we use something like De Moivre's formula.

If we want to avoid taking so many powers, we can always use a single term approximation as we used for low values of $n$. By Descartes' rule of signs, there is always a single positive real root of the characteristic equation. By a result of Cauchy (discussed in the Appendix), this will be the root of largest absolute value of a polynomial like the characteristic polynomials we have here. So we can always approximate $P(p)\approx c_{1}r_{1}^{p}$ by choosing $r_{1}$ to be the positive real root of the characteristic equation $x^{n}=\dfrac{n-1}{n^{2}}\left(1+x+\cdots+x^{n-1}\right)=\dfrac{\left(n-1\right)\left(1-x^{n}\right)}{n^{2}\left(1-x\right)}$. The last expression comes from the sum of a geometric progression.

Graphs

Form a graph with the Y-Axis being the probability that the player in
possession scores without losing possession of the ball and the number
of required passes be the X-Axis. (Let a 10 sided dice be used for
this case.)

If possible, determine how different the graph would look [in a visual
sense, no need for deeper calculations] if the number of sides on the
dice is made to vary. Is the graph just shifted along the x-axis or do
the peaks become more gradual?).

Graph for $n=10$

When $n=10$, we can first look at low values of $p$ ($0\le p\le 15$, say), for which $P(p)$ is a little erratic: $\frac{1}{2},\frac{9}{20},\frac{891}{2000},\frac{88119}{200000},\frac{8704971}{20000000},\frac{858841839}{2000000000},\frac{84613760451}{200000000000},\frac{8322899889159}{20000000000000
   },\frac{817196087918331}{2000000000000000},\frac{80074373583098079}{200000000000000000},\frac{7828106720557690611}{20000000000000000000},\frac{763263632540788276599}{2000000000000000000000}
   ,\frac{75095735946945922149291}{200000000000000000000000},\frac{7383535218217105514272719}{20000000000000000000000000},\frac{725498238785664501055726371}{2000000000000000000000000000},\frac
   {71244834127637430615074174439}{200000000000000000000000000000}$

But things smooth out for higher values of $p$. For $15\le p\le100$, we have a graph like:

By the analysis worked out earlier, for large $p$, this can be approximated by an exponential function $E(p)$. For $n=10$, $E(p)$ happens to be approximately $0.472463*.981288^p$. This fits extremely well for $p\ge 15$ (the approximation is in dashed orange):

We can understand the fit better by looking at the signed relative error $\dfrac{E(p)-P(p)}{P(p)}$, plotted for $15\le p\le100$ here:

For the record, the approximation is not very good for small $p$:

Graphs for arbitrary $n$

We can plot various $n$ ($1\le n\le 20$) together for the various $p$ ranges.

$0\le p \le 15$:

$0\le p \le 100$:

$0\le p \le 500$:

One other way to look at things collectively is to examine the approximations $E(p)=C(n)*r(n)^p$. Plotting $r(n)$ (approaching $1$) and $C(n)$ (approaching $\frac12$) for $2\le n\le50$ yields:

Appendix

Distinct roots

The characteristic polynomial is $x^{n}-\dfrac{n-1}{n^{2}}\left(x^{n-1}+\cdots+1\right)$. We would like to show that this has no repeated roots. It doesn't take much extra effort to show a slight generalization: For any positive constant $t$, $\chi\left(x\right)=x^{n}-t\left(x^{n-1}+\cdots+1\right)$ has no repeated roots.

Let $r$ be a multiple root of $\left(x-1\right)\chi\left(x\right)=x^{n+1}-\left(t+1\right)x^{n}+t$ (the simplification comes from the telescoping sum caused by the finite geometric series), so that $\left(x-r\right)^{2}$ is a factor of $\left(x-1\right)\chi\left(x\right)$. Then either $r$ is a multiple root of $\chi\left(x\right)$ or $r$ is a single root of $\chi\left(x\right)$ and $r=1$.

Since $\left(x-r\right)^{2}$ is a factor of $\left(x-1\right)\chi\left(x\right)$, the product rule tells us that $r$ must be a zero of the derivative $\dfrac{\mathrm{d}}{\mathrm{d}x}\left(x-1\right)\chi\left(x\right)=\left(n+1\right)x^{n}-\left(t+1\right)nx^{n-1}=x^{n-1}\left(\left(n+1\right)x-\left(t+1\right)\right)$. This forces $r=0$ or $r=\dfrac{n\left(t+1\right)}{n+1}$. Since $t>0$, $0$ cannot be a root of $\left(x-1\right)\chi\left(x\right)=x^{n+1}-\left(t+1\right)x^{n}+t$, so we must have $r=\dfrac{n\left(t+1\right)}{n+1}$.

This value of $r$ must also be a root of the original $\left(x-1\right)\chi\left(x\right)$, so that $\left(\frac{n(t+1)}{n+1}\right)^{n+1}-(t+1)\left(\frac{n(t+1)}{n+1}\right)^{n}+t=0$. Multiplying through by $\left(n+1\right)^{n+1}$, we obtain $0$ $=n^{n+1}\left(t+1\right)^{n+1}-\left(n+1\right)n^{n}\left(t+1\right)^{n+1}+t\left(n+1\right)^{n+1}$ $=\left(n^{n+1}-\left(n+1\right)n^{n}\right)\left(t+1\right)^{n+1}+t\left(n+1\right)^{n+1}$ $=t\left(n+1\right)^{n+1}-n^{n}\left(t+1\right)^{n+1}$. As a polynomial in $t$, the coefficient of $t$ is $\left(n+1\right)\left(\left(n+1\right)^{n}-n^{n}\right)>0$, and all other coefficients (including the constant term) are negative. By Descartes' rule of signs, either two or zero positive values of $t$ are possible, counting multiplicities. Observe that $t=\dfrac{1}{n}$ is a zero of $t\left(n+1\right)^{n+1}-n^{n}\left(t+1\right)^{n+1}$. And it is also a zero of $\dfrac{\mathrm{d}}{\mathrm{d}t}\left(t\left(n+1\right)^{n+1}-n^{n}\left(t+1\right)^{n+1}\right)=\left(n+1\right)^{n+1}-\left(n+1\right)n^{n}\left(t+1\right)^{n}$. Therefore, the possible positive values of $t$ are both $\dfrac{1}{n}$.

In the original characteristic polynomial, $t=\dfrac{n-1}{n^{2}}\ne\dfrac{1}{n}$, so it has no repeated roots. But we can continue to show the more general result. If $t=\dfrac{1}{n}$, then $r=\dfrac{n\left(t+1\right)}{n+1}=1$ and $\chi\left(x\right)=x^{n}-\dfrac{1}{n}\left(x^{n-1}+\cdots+1\right)=\dfrac{1}{n}\left(x-1\right)\left(nx^{n-1}+\left(n-1\right)x^{n-2}+\cdots+2x+1\right)$ by synthetic division, say. But $1$ cannot be a repeated root of $\chi(x)$ since $n*1^{n-1}+\left(n-1\right)*1^{n-2}+\cdots+2*1+1>0$.

Formulas for $C_i$

Formula in terms of all roots

We have $P(p)={\displaystyle \sum_{i=1}^{n}}C_{i}r_{i}^{p}$ and $P\left(1-i\right)=\dfrac{1}{2}$ for $1\le i\le n$. This yields a linear system of $n$ equations in $n$ unknowns $C_{i}$, so linear algebra can help us approach this. The equations are \begin{align*}C_{1}+\cdots+C_{n}&=\dfrac{1}{2}\\\dfrac{1}{r_{1}}C_{1}+\cdots+\dfrac{1}{r_{n}}C_{n}&=\dfrac{1}{2}\\\vdots&\\\dfrac{1}{r_{1}^{n-1}}C_{1}+\cdots+\dfrac{1}{r_{n}^{n-1}}C_{n}&=\dfrac{1}{2}\end{align*} These can be rewritten into the matrix equation $$\begin{bmatrix}r_{1}^{0} & \cdots & r_{n}^{0}\\
\vdots & \ddots & \vdots\\
r_{1}^{1-n} & \cdots & r_{n}^{1-n}
\end{bmatrix}\begin{bmatrix}C_{1}\\
C_{2}\\
\vdots\\
C_{n}
\end{bmatrix}=\begin{bmatrix}\dfrac{1}{2}\\
\dfrac{1}{2}\\
\vdots\\
\dfrac{1}{2}
\end{bmatrix}$$

Incidentally, the square matrix is the transpose of the Vandermonde matrix with $\alpha_{i}=r_{i}^{-1}$. I had tried to form the augmented matrix and to use the beginning steps of Gaussian elimination, but it was too complicated to work through manually. Since the roots $r_{i}$ are distinct, the Vandermonde matrix is invertible and hence so is its transpose. Unfortunately, the inverse of a Vandermonde matrix is quite complicated, so I will not be deriving $C_{i}=\dfrac{1}{2}r_{i}^{n-1}{\displaystyle \prod_{j\ne i}}\dfrac{1-r_{j}}{r_{i}-r_{j}}$ in this answer. It can be confirmed for small $n$ by a CAS like Mathematica. You can see verification for $n\le7$ online.

Formula in terms of $n$ and $r_i$

Taking that formula on faith, we can exploit the symmetry to write $C_{i}$ in terms of the elementary symmetric polynomials in the $r_i$: $s_{0}=1,s_{1}={\displaystyle \sum_{j=1}^{n}}r_{j},\ldots,s_{n}={\displaystyle \prod_{j=1}^{n}}r_{j}$. We have \begin{align*}C_{i}&=\dfrac{1}{2}r_{i}^{n-1}{\displaystyle \prod_{j\ne i}}\dfrac{1-r_{j}}{r_{i}-r_{j}}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{{\displaystyle \prod_{j}\left(1-r_{j}\right)}}{{\displaystyle \prod_{j\ne i}}\left(r_{i}-r_{j}\right)}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{\sum_{j=0}^{n}\left(-1\right)^{j}s_{j}}{\left(-1\right)^{n-1}\dfrac{s_{n}}{r_{i}}+\sum_{j=1}^{n-1}\left(-1\right)^{j-1}\left(n-j\right)r_{i}^{n-j}s_{j-1}}\text{.}\end{align*} (I suspect this is very close to the form one would obtain using the inverse of the Vandermonde matrix.)

Then we can use Vieta's formulas to write the $s_{j}$s in terms of the coefficients of the characteristic polynomial. For convenience, set $t=\dfrac{n-1}{n^{2}}$, so that the characteristic polynomial is $x^{n}-t\left(x^{n-1}+\cdots+1\right)$. This means $s_{0}=1,s_{1}=-\left(-t\right),s_{2}=-t,\ldots$ with $s_{j}=\left(-1\right)^{j+1}t$ for $j>0$. As such, \begin{align*}C_{i}&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{s_{0}+\sum_{j=1}^{n}\left(-1\right)^{j}s_{j}}{\left(-1\right)^{n-1}\dfrac{s_{n}}{r_{i}}+\left(n-1\right)r_{i}^{n-1}s_{0}+\sum_{j=2}^{n-1}\left(-1\right)^{j-1}\left(n-j\right)r_{i}^{n-j}s_{j-1}}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1+\sum_{j=1}^{n}\left(-1\right)^{j}\left(-1\right)^{j+1}t}{\left(-1\right)^{n-1}\dfrac{\left(-1\right)^{n+1}t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}+\sum_{j=2}^{n-1}\left(-1\right)^{j-1}\left(n-j\right)r_{i}^{n-j}\left(-1\right)^{j}t}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1-\sum_{j=1}^{n}t}{\dfrac{t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}-\sum_{j=2}^{n-1}\left(n-j\right)r_{i}^{n-j}t}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1-nt}{\dfrac{t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}-t\sum_{k=1}^{n-2}kr_{i}^{k}}\text{.}\end{align*} The remaining summation resembles a geometric series, and indeed there is trick (often used when dealing with generating functions) involving the derivative of the geometric series formula (see this MathSE question) which allows us to write ${\displaystyle \sum_{k=1}^{n-2}}kr_{i}^{k}=\dfrac{r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}}{\left(1-r_{i}\right)^{2}}$. Then we have:
\begin{align*}C_{i}&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}}{1-r_{i}}*\dfrac{1-nt}{\dfrac{t}{r_{i}}+\left(n-1\right)r_{i}^{n-1}-t\dfrac{r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}}{\left(1-r_{i}\right)^{2}}}\\&=\dfrac{1}{2}r_{i}^{n-1}\dfrac{1-nt}{\dfrac{t}{r_{i}}\left(1-r_{i}\right)+\left(n-1\right)r_{i}^{n-1}\left(1-r_{i}\right)-t\dfrac{r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}}{\left(1-r_{i}\right)}}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n-1}\left(1-nt\right)\left(1-r_{i}\right)}{\dfrac{t}{r_{i}}\left(1-r_{i}\right)^{2}+\left(n-1\right)r_{i}^{n-1}\left(1-r_{i}\right)^{2}-t\left(r_{i}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n-1}\right)}\\&=\dfrac{1}{2}\dfrac{r_{i}^{n}\left(1-nt\right)\left(1-r_{i}\right)}{t\left(1-r_{i}\right)^{2}+\left(n-1\right)r_{i}^{n}\left(1-r_{i}\right)^{2}-t\left(r_{i}^{2}+\left(1-n-2r_{i}+nr_{i}\right)r_{i}^{n}\right)}\text{.}\end{align*}

This can be written in many different forms, especially after substituting $\dfrac{n-1}{n^{2}}$ back in for $t$. One form (for $n>1$) is $$\boxed{C_{i}=\dfrac{n}{2\left(n-1\right)}*\dfrac{1-r_{i}}{r_{i}^{-n}-2r_{i}^{1-n}+n^{2}+n-1-\left(2n^{2}+n-2\right)r_{i}+n^{2}r_{i}^{2}}}$$

Large $p$ approximation

As discussed in On finding the largest root of a polynomial by Davenport and Mignotte and New Bounds on the Real Polynomial Roots by Prodanov, Cauchy showed that the absolute values of the zeros of $a_{n}x^{n}+\cdots+a_{0}$ are bounded by the unique positive root of $\left|a_{n}\right|x^{n}-\left(\left|a_{n-1}\right|x^{n-1}+\cdots+\left|a_{0}\right|\right)$. As a consequence, the unique positive root $r\left(n\right)$ of the characteristic polynomial $x^{n}-\dfrac{n-1}{n^{2}}\left(x^{n-1}+\cdots+1\right)$ has the greatest absolute value of any root. However, we need it to be strictly greater than that of the other roots in order to justify a large-$p$ approximation of the form $C\left(n\right)*r\left(n\right)^{p}$.

We can extract more information from a proof of Cauchy's result (see Theorem 8.1.3 in Analytic Theory of Polynomials by Rahman and Schmeisser): If $r$ is a zero of $x^{n}-\dfrac{n-1}{n^{2}}\left(x^{n-1}+\cdots+1\right)$, then $r^{n}=\dfrac{n-1}{n^{2}}\left(r^{n-1}+\cdots+1\right)$, so that $\left|r\right|^{n}=\dfrac{n-1}{n^{2}}\left|r^{n-1}+\cdots+1\right|\le\dfrac{n-1}{n^{2}}\left(\left|r\right|^{n-1}+\cdots+1\right)$ by the triangle inequality, so that $x=\left|r\right|$ makes the characteristic polynomial nonpositive. If we had $\left|r\right|=\left|r(n)\right|$ then we would need equality in the triangle inequality, which would require the powers of $r$ to all point in the same direction. This is impossible (for $n>1$) if $r$ is not a positive real by De Moivre's theorem or similar.

In conclusion, for large $p$ we can indeed approximate $P(p)$ by $C(n)*r(n)^{p}$ where $r(n)$ is the unique positive root of the characteristic polynomial, and $C(n)$ is given by, say, $C(n)=\dfrac{n}{2\left(n-1\right)}*\dfrac{1-r(n)}{r(n)^{-n}-2r(n)^{1-n}+n^{2}+n-1-\left(2n^{2}+n-2\right)r(n)+n^{2}r(n)^{2}}$.

However, it would be helpful to be able to approximate $r(n)$, too. For even moderately large $n$, $r(n)$ is just barely less than $1$. We can use Newton's method starting at $1$ to get approximations. Our first approximation is $1$. Then a better approximation is $1-\dfrac{1^{n}-\dfrac{n-1}{n^{2}}\left(1^{n-1}+\cdots+1\right)}{n1^{n-1}-\dfrac{n-1}{n^{2}}\left(\left(n-1\right)1^{n-2}+\cdots1\right)}$ $=1-\dfrac{1-\dfrac{n-1}{n^{2}}*n}{n-\dfrac{n-1}{n^{2}}*\dfrac{\left(n-1\right)n}{2}}$ $=1-\dfrac{1-\dfrac{n-1}{n}}{n-\dfrac{\left(n-1\right)^{2}}{2n}}$ $=1-\dfrac{2}{n^{2}+2n-1}$.

This approximation $r_{\approx}(n)$ is already quite good (relative error less than $0.5\%$) for $n\ge10$. The corresponding approximation to $C(n)$ simplifies to $C_{\approx}(n)=\dfrac{\left(n^{2}+2n-1\right)^{n+1}\left(n^{2}+2n-3\right)}{2\left(n-1\right)\left(n^{2}+4n-1\right)r_{\approx}(n)^{n}}$.

Now, $C_{\approx}(n)r_{\approx}(n)^{p}$ is not a good approximation to $P(p)$ when $p$ is much greater than $n$. For example, when $n=10$ and $p=100$, we have about $35\%$ relative error. But $n=70$ and $p=100$ brings the relative error below $2\%$, so $C_{\approx}(n)r_{\approx}(n)^{p}$ is a straightforward way to approximate $P(p)$ for large $n$ and $p$ of comparable size.


问:
No flux boundary condition on PDE on surface (Laplace-Beltrami)
What would a Neumann BC on a PDE posed on a surface look like? In the flat case, we have
$\nabla u \cdot N = 0$
where $u$ is the solution of the PDE and $N$ is unit normal vector.

In a surface case, what would it be? Would it involve a conormal vector instead? Would I use Laplace-Beltrami operator instead? Would appreciate any explanations.

答:
As Tomás said the normal is well-defined. There are many types of Neumann boundary condition that can be naturally imposed for Hodge Laplacian operator for a harmonic form $u$. Let $\newcommand{\d}{\mathrm{d}}\d$ and $\newcommand{\de}{\delta}\de$ be the exterior derivative and its codifferential, $\wedge$ and $\vee$ be the exterior and interior product. $n$ is the unit normal vector.

Neumann boundary value could be imposed on the following quantities:
$$
n\wedge \de u, \;\;n\vee \d u,\;\;n\vee \de u,\;\; n\wedge \d u.
$$
Translated into a smooth domain in $\mathbb{R}^3$ using curl and divergence for a $1$-form $u$:
$$
\nabla_{\Gamma} \cdot u,\;\; n\cdot (\nabla \times u),\;\; \nabla_{\perp}\cdot u,\;\; n\times(\nabla \times u),
$$
where the first and the third are surface divergence and divergence of the the normal part of $u$ respectively. <s>Applications would be the boundary value problems for the Maxwell system</s>.

The reference I gave was wrong. The correct reference is Finite element methods for surface PDEs. For example, the integration by parts formula involving co-normal (Theorem 2.10).

ContentLicense: CC BY-SA 3.0


问:
Average revenue from price-demand function?
I came across a calculus question in which I don't even understand what the question is asking. It went something like this:

The price-demand equation is $p(x)=100-15x$. What is the average revenue at $x=5$?

How can you have the average of something at a single point? Do we just do $p(5)=25$ so $R=px=25(5)=125$?

Does average mean revenue per unit in which case we'd divide the $125$ by $5$? If so, I don't see how this is a calculus question. Thanks!

答:
Generally in consumer/producer theory, "average" metrics are per-unit, i.e., divided by quantity demanded/supplied.

So, the demand curve is the average revenue curve. In the absence of price discrimination, at any fixed quantity $x$, the average revenue is simply

$$AR(x) = \frac{R(x)}{x} = \frac{p(x)*x}{x} = p(x) .$$

There's no calculus involved here, the answer is just $p(5) = 25$.


问:
$A^{2m+1}=A+I_n$ then $\det(A)>0$
Let be $A$ an $n \times n$ matrix with real entries and $m$ a positive integer such that:

$$A^{2m+1}=A+I_n$$
Prove that $$\det(A)>0$$

I tried solving this problem and, by rewriting the hypothesis conditions I got that
$$(A-I_n)(A^{2m}+A^{2m-1}+\dots+A+I_n)=A$$
But we know that
$$\det(A^{2m}+A^{2m-1}+\dots+A+I_n)\ge 0$$
So how can I continue from there?

答: Hint. It suffices to show that $A$ has not any zero or negative eigenvalues (i.e. $A$ has only positive eigenvalues or conjugate pairs of non-real eigenvalues). In turn, it suffices to prove that $x^{2m+1}=x+1$ has not any zero or negative roots. Suppose the contrary. Then $-|x|^{2m+1}=-|x|+1$, i.e. $|x|=|x|^{2m+1}+1$. Why is this equation insolvable?

Title: $A^{2m+1}=A+I_n$ then $\det(A)>0$


问:
Show that $f(a) + f(b) = f(\frac{a+b}{1+ab})$
If $f(x) = \log(\frac{1-x}{1+x})$, show that $f(a) + f(b) = f(\frac{a+b}{1+ab})$

Note: base of log is 10

答:
Start with the most complicated term and simplify

\begin{equation*}
\begin{split}
f(\tfrac{a+b}{1+ab}) & =\log{\left(\frac{1-\tfrac{a+b}{1+ab}}{1+\tfrac{a+b}{1+ab}}\right)} = \log{\left(\frac{1+ab-a-b}{1+ab+a+b}\right)} = \log{\left(\frac{1-a}{1+a}\frac{1-b}{1+b}\right)}\\
& =\log{\left(\frac{1-a}{1+a}\right)}+\log{\left(\frac{1-b}{1+b}\right)}= f(a) + f(b)
\end{split}
\end{equation*}

and btw, the base of the logarithm doesn't matter, these properties are true for any base.


问:
How many combinatorially distinct ways are there to tile an equilateral triangle with $k$ $60^\circ-120^\circ$ trapezoids?
I believe there is exactly one way (up to combinatorial equivalence) to arrange 3 trapezoids with angles of $60^\circ$ and $120^\circ$ into an equilateral triangle:

With $4$ trapezoids, I see two ways:

With $5$ trapezoids, there are many more; I count at least $13$ (thanks to Dan Uznanski for discovering the last of these):

In general, how many ways are there to do this with $k$ trapezoids, and what are the corresponding arrangements?

Knowing that the sequence starts $1,2,13?,\ldots$ isn't quite enough to try and find it on OEIS. (I'd also appreciate hearing about any configurations that I may have missed above.)

Edit: It seems that the terminology above was not clear to everyone, so two clarifications:

When I say "trapezoids" here, I am referring only to those pictured above, where there is exactly one pair of parallel sides and the $60^\circ$ angles are adjacent; I am not including parallelograms with angles in cyclic order $(60^\circ, 120^\circ, 60^\circ, 120^\circ)$.

Two arrangements are combinatorially equivalent if there is a bijection between the corners, edges, and faces of the two which preserves inclusion (e.g. of a vertex on a face or one line segment in another), adjacency, overlaps, and maps $60^\circ$ and $120^\circ$ angles in trapezoids to themselves. In other words, we care about the incidence structure of the trapezoids, and whether trapezoids $A$ and $B$ coincide along a shared leg, but not about specific lengths of line segments or a rotation of the large triangle.

答:
Correction and revision added at the end

An equilateral triangle tiled with $k$ $60^o-120^o$ trapezoids can be tiled with $k+1$ such trapezoids in at least six ways: by adding a tile along the whole of one side of the equilateral triangle, or by dividing one of the tiles whose base does not occupy an entire side of the triangle.  But when $k=3$, the first three arrangements for $k+1$ are equivalent under $120^o$ rotation, as are the second three, and so we have only two distinct tilings for $k=4$, as OP notes, which we may denote as $4a$ and $4b$.

We can add a tile to $4a$ in six distinct ways, as in the first six of OP's array for $k=5$ (reading left to right and down). Of the six ways to add a tile to $4b$, four are equivalent to one of the preceding six, and so we have only two distinct new tilings, the seventh and eighth in OP's illustration.

But we can also add a tile to $4b$ by re-dividing the divided trapezoid of $4b$ in one of the three ways shown in OP's ninth, eleventh, and twelfth figures of the array.

Lastly, reducing the number of concurrent lines from the sides of the triangle from three (as in all preceding cases) to two, i.e. by removing one of them, we can re-tile the remaining concave pentagon with four tiles in exactly two distinct ways, as in OP's tenth and thirteenth.

Thus from $4a$ and $4b$ we derive $5a$, $5b_1$ and $5b_2$, with distinct arrangements$$5a+5b_1+5b_2=6+2+5=13$$

If these thirteen distinct tilings for $k=5$ are complete, then for $k=6, 7, 8$ I find, by systematic counting, $68, 283, 1081$ distinct tilings, respectively.

Looking at these totals part by part, i.e. as generated by $5a+5b_1+5b_2$ and their descendants, we have

$$[1+1+1+1+1+1]+[1+1]+[1+1+1+1+1]=13$$for $k=5$,$$[1+2+3+6+6+6]+[3+1]+[8+8+8+8+8]=68$$for $k=6$,$$[1+3+6+24+24+24]+[6+0]+[39+39+39+39+39]=283$$for $k=7$, and$$[1+4+10+82+82+82]+[10+0]+[152+152+152+152+152]=1031$$for $k=8$.

I. In the bracketed $6$-sums on the left, the pattern of the first three (vertical) columns is clear: $1$'s in the first column, consecutive integers in the second, and consecutive triangle numbers in the third, starting from $1$. The greatest addend in each (horizontal) row is equal to the sum of the six addends in the row preceding. As a function of $k$, the sum of the first three terms in each row is thus given by$$\frac{k^2-5k+6}{2}$$The sequence of identical greatest terms in each row, easily extendable to $$1, 6, 24, 82, 261, 804, 2440, 7356, 22115,...$$ is given by the expression$$\Sigma\Sigma\frac{3^{k-4}-1}{2}$$where $k\ge5$. This is clear  since $$\Sigma\frac{3^{k-4}-1}{2}=1, 4, 13, 40, 121, 364,...$$and $$\Sigma\Sigma\frac{3^{k-4}-1}{2}=1(k-4)+4(k-5)+13(k-6)+40(k-7)+121(k-8)+...$$Thus by addition, the sum of the first bracketed row of six terms is$$\frac{k^2-5k+6}{2}+3[1(k-4)+4(k-5)+13(k-6)+40(k-7)+121(k-8)+...]$$II. For $k>6$, the second term derived from $4b_1$ yields no new tilings, and the bracketed middle addend is simply the triangle number given by$$\frac{k^2-7k+12}{2}$$III. Lastly, the sequence of each column of the $5$-sums on the right,$$1,8,39,152,526,1704,5322,16296,...$$is OEIS A097787:$$\frac{3^{n+5}}{32}-\frac{2n^4+32n^3+196n^2+556n+633}{96}$$And since $n=k-5$, this can be written as$$\frac{3^k}{32}-\frac{2k^4-8k^3+16k^2-4k+3}{96}$$

And so we seem to have a method for a $3$-step calculation of the number of distinct tilings of an equilateral triangle by $k$ $60^o-120^o$ trapezoids. It would be good to fuse the above expressions into a single expression in $k$, but I have not yet been able to do it.  The sequence of total distinct tilings $$1,2,13,68,283,1031,3449,10981,33994,103629,313354,943623,2835853,8514355,...$$does not appear in OEIS.

Correction/Revision

I. As OP’s comment points out, the above answer rests on a false premise, that every distinct $k+1$ tiling of the equilateral triangle arises either from the addition of one trapezoid along an entire side of a k-tiled triangle, or from the division of one of the trapezoidal tiles within the triangle by a line parallel to the trapezoid's base, as in the generation below of six $k=6$ tilings from the first of OP's thirteen $k=5$ tilings by adding a trapezoid along bottom, right, and left in the first row, and by bisecting in turn the three inner trapezoids in the second row. I followed this same order in producing and numbering all the arrangements initially found.

But although this method finds (when duplicates are set aside) a portion of the distinct $k+1$ tilings of the triangle, it does not find all of them.  As the comment notes, the following tiling for $k=6$, for example, does not arise in this way from any of the distinct tilings for $k=5$.

Indeed, even from OP's last five tilings for $k=5$, it appears there are at least two other ways to generate a $(k+1)$-tiling: transformation and trisection.

II. OP's #$2$ for $k=5$ arises by addition of one tile to $4a$, as in my method, but #$10$ does not arise from $k=4$ but rather by a transformation of #$2$ for $k=5$,

in which trapezoid $a$ expands into $b$ and $b$ in turn expands into $c$. Similarly, OP's #$13$ rotated is a modification of #$11$,

by expansion of $a$ into $b$ and $b$ into $c$.

The figure above missing from my count for $k=6$ arises by a like transformation of arrangement #$9$ of the sixty-eight I initially found.
where again trapezoid $a$ has displaced some of $b$, and $b$ some of $c$, in the figure on the right compared with #$9$ on the left.

But such transformations commonly involve only two trapezoids, not three, and a single arrangement can yield more than one. Of distinct arrangements found by my method for $k=6$, seven of them yield one or two arrangements I missed. Figures on the left below are numbered by their place in the sixty-eight distinct arrangements I found for $k=6$ by addition/division from the (slightly re-ordered) thirteen figures for $k=5$, followed on the right by the primed figures my method missed.

Each of these transformations is a one-step process in which one trapezoid invades and incorporates part of an adjacent one, e.g. as in #$45$-#$45'$, or #$45$-#$45''$

Just as the last five of the (presumably) thirteen arrangements for $k=5$ were not discoverable by my method from the two arrangements for $k=4$, so for $k=6$ the ten (primed) arrangements above were missed by my method.

III. And the count is still not complete. OP's $9th$, $11th$, and $12th$ arrangements for $k=5$ arise by trisection of one of the trapezoids for $k=3$. Accordingly, if we trisect in turn each trapezoid of $4a$ and $4b$ in each of the three ways seen in OP's $9th$, $11th$, and $12th$ for $k=5$, the following six (of twenty-four possible) arrangements are new, and we now have $68+10+6=84$ distinct tilings for $k=6$.

IV. Similarly, exploring the possible arrangements for $k=7$, besides the $283$ found by addition/division applied to the arrangements for $k=6$, new arrangements appear both by the method of transformation as well as by the addition (by trisection) of two trapezoids to each distinct arrangement for $k=5$.  Since each trapezoid in an arrangement for $k=5$ can be trisected in three different ways, this raises the possibility of$$5\cdot13\cdot3=195$$new arrangements, although this is reduced to $125$ when $70$ duplicates are set aside.  Adding as well the nineteen new arrangements found to result from transformations gives$$283+19+125=427$$distinct arrangements for $k=7$.

It seems, then, there are three ways to generate a $k+1$ tiling: by adding one tile to a $k$-tiling, by adding (through trisection) two tiles to a $(k-1)$-tiling, and by transforming a $(k+1)$-tiling generated in one of the first two ways.  Are there other ways? If not, are the above revised counts accurate? In searching for combinatorially distinct arrangements, I find the systematic survey of possible transformations more difficult than that of possible trisections. OEIS does not recognize sequence$$1, 2, 13, 84, 427$$ so it seems an expression in $k$ for the number of distinct tilings of the triangle must await an accurate count at least through $k=8$, if a general rule is to appear.


问:
Probability question involving colored dice
This question is really getting to me, a friend of mine has suggested a solution but I believe it is incorrect.
Anyway here's the question:

You throw 9 coloured dice. Every dice has 2 white sides, 2 red sides and 2 blue sides. What is the chance to get every color three times?

I'd be over the moon if you can help me find the solution as it's been getting to me. Thanks.

答:
The probability we get exactly $3$ white is, by the standard "binomial distribution" formula, equal to
$$\binom{9}{3}\left(\frac{1}{3}\right)^3 \left(\frac{2}{3}\right)^6.$$
Given that we got exactly $3$ blue, the number of red is equal to $3$ with probability
$$\binom{6}{3}\left(\frac{1}{2}\right)^3 \left(\frac{1}{2}\right)^3.$$
Multiply. There is some simplification, since the $\left(\frac{1}{2}\right)^6$ in the second expression cancels the $2$'s in the first. And the product
$\binom{9}{6}\binom{6}{3}$ "simplifies" to $\dfrac{9!}{(3!)^3}$.


问:
Proof of the existence of generating polynomials of an ideal
I'm going through Shilov's Linear Algebra, and I've come to the chapter on canonical representations of linear operators, which uses polynomial algebras to develop the JCF.

The topic of algebras of polynomials is very close to that of polynomial rings, and much of the terminology is the same. So, the point that I'm interested in relates to generating polynomials of ideals:

Theorem. Every ideal $E \neq {0}$ of the algebra of polynomials $\Pi$ is obtained from some polynomial $Q_0(\lambda)$ by multiplication by an arbitrary polynomial $P(\lambda)$.

The proof is given as follows.

[We] find the nonzero polynomial of lowest degree, say $q$, in the ideal $E$, and denote it by $Q_0(\lambda)$. We then assert that every polynomial $Q(\lambda)\in E$ is of the form $P(\lambda)Q_0(\lambda)$, where $P(\lambda) \in \Pi$. ...

The issue I have with this is the premise that, given a non-empty ideal $E$, we can always find a nonzero polynomial of lowest degree. To be clear, my issue isn't with the concept, but with the formality, i.e. if this proof were given in a formal setting, would it be acceptable?

I think the above can be demonstrated by assigning to every polynomial in $E$ an element $j\in \mathbb{N}$ equal to the degree of the polynomial, then stating that from every sequence (finite or infinite) of natural numbers we can find a smallest element. Is this sufficiently common knowledge that we can consider it evident, while maintaining rigor? At least, in the context of linear algebra and ring theory?

答:
The issue I have with this is the premise that, given a non-empty
ideal $E$ , we can always find a nonzero polynomial of lowest degree.
To be clear, my issue isn't with the concept, but with the formality,
i.e. if this proof were given in a formal setting, would it be
acceptable?

This premise is fine. If $E$ is nonempty, it has polynomials in it, each polynomial has a natural number as its degree, by the well-ordering principle there is a smallest number among the degrees of polynomials in $E$, and there exists a polynomial of that degree. There is nothing informal here. It would be incredibly pedantic to write out all the details I just did every time to make a simple standard argument like this.


问:
Poisson summation formula as a special case of the trace formula
For $f \in L^1(\mathbb R)$, the Fourier transform $\hat{f}: \mathbb R \rightarrow \mathbb C$ is defined by

$$\hat{f}(x) = \int_{\mathbb R} f(y) e^{2\pi i xy}dy.$$

The Poisson summation formula asserts that for $f$ smooth and compactly supported,

$$\sum\limits_{n\in \mathbb Z} f(n) = \sum\limits_{n \in \mathbb Z} \hat{f}(n).$$

I've heard that this formula arises as a special case of a trace formula for an integral operator of trace class on the Hilbert space $L^2(\mathbb R/\mathbb Z)$, or that Selberg or Arthur's trace formula is a "nonabelian Poisson summation formula."  How can the Poisson summation formula be seen as arising in this way?

答:
Generally, if $v_1, v_2, ... $ are an orthonormal basis of a given Hilbert space, and $T$ is a sufficiently nice operator on the given Hilbert space (specifically of "trace-class"), then the trace of $T$ can be defined by the formula

$$\operatorname{Tr}(T) = \sum\limits_{n\in \mathbb Z} \langle Tv_i, v_i \rangle$$

and this is independent of the choice of orthonormal basis.  The Poisson summation formula comes from looking at the trace of a certain operator on the Hilbert space $V = L^2(\mathbb R/\mathbb Z)$ in two ways.

For $f$ smooth and compactly supported on $\mathbb R$, we set $K(x,y) = \sum\limits_{n \in \mathbb Z} f(-x+n+y)$, which is a finite sum for all pairs of real numbers $(x,y)$, and lies in the Hilbert space space $L^2(\mathbb R/\mathbb Z \times \mathbb R/\mathbb Z)$.

We define a bounded linear operator $T$ on $V$ by the formula

$$T(\varphi)(x) = \int\limits_{\mathbb R/\mathbb Z} K(x,y) \varphi(y)dy. \tag{$\varphi \in V$}$$

This operator turns out to be of trace class, so we may compute its trace $\operatorname{Tr}(T)$ in two ways.

First way (spectral expansion)

By the Peter-Weyl theorem, the characters $\phi_m(x) = e^{2\pi i mx} : m \in \mathbb Z$ form an orthonormal basis for $V$.  Each vector $\phi_m$ is actually an eigenvector for the operator $T$, with eigenvalue $\hat{f}(n)$:

$$T(\phi_m)(x) = \int\limits_{\mathbb R/\mathbb Z} \sum\limits_{n \in \mathbb Z} f(-x+n+y) \phi_m(y)dy = \int\limits_{\mathbb R/\mathbb Z} \sum\limits_{n \in \mathbb Z} f(-x+n+y) \phi_m(n+y)dy = \int\limits_{\mathbb R} f(-x+y)\phi_m(y)dy $$

$$ = \int\limits_{\mathbb R} f(y) \phi_m(x+y)dy = \int\limits_{\mathbb R} f(y) e^{2 \pi i m(x+y)}dy = e^{2\pi i mx} \int\limits_{\mathbb R} f(y) e^{2\pi i my}dy =  \hat{f}(m)e^{2\pi i mx}.$$

Therefore, we can compute $\operatorname{Tr}(T)$ as a sum of the eigenvalues $\hat{f}(n)$:

$$\operatorname{Tr}(T) = \sum\limits_{n\in \mathbb Z} \langle T(\phi_n), \phi_n \rangle = \sum\limits_{n\in \mathbb Z} \hat{f}(n) \langle \phi_n, \phi_n \rangle = \sum\limits_{n \in \mathbb Z} \hat{f}(n).$$

Second way (the trace as an integral along the diagonal)

On the other hand, we claim that the trace of $T$ can be calculated by integrating $K(x,y)$ along the diagonal $(x,x)$.  Again by the Peter-Weyl theorem, the characters $\phi_{n,m}(x,y) = \phi_n(x) \overline{\phi_m(y)}$ of $(\mathbb R / \mathbb Z) \times(\mathbb R / \mathbb Z)$ form an orthonormal basis for $L^2(\mathbb R / \mathbb Z \times \mathbb R / \mathbb Z)$, and we may therefore write

$$K(x,y) = \sum\limits_{i,j} c_{ij} \phi_{i,j}(x,y)$$

for some complex numbers $c_{ij}$.  We may compute

$$\int\limits_{\mathbb R/\mathbb Z} K(x,x)dx = \int\limits_{\mathbb R/\mathbb Z} \sum\limits_{i,j} c_{ij} \phi_{i,j}(x,x) dx = \sum\limits_{i,j} \int\limits_{\mathbb R/\mathbb Z} \phi_i(x) \overline{\phi_j(x)}dx = \sum\limits_{i,j} c_{i,j} \delta_{ij} = \sum\limits_i c_{i,i}$$

and at the same time,

$$\operatorname{Tr}(T) = \sum\limits_{n \in \mathbb Z} \int\limits_{\mathbb R/\mathbb Z} T(\phi_n)(x) \overline{\phi_n(x)}dx = \sum\limits_n \int\limits_{\mathbb R/\mathbb Z} \space \int\limits_{\mathbb R/\mathbb Z} K(x,y) \phi_n(y) \overline{\phi_n(x)} dx = \sum\limits_n \int\limits_{\mathbb R/\mathbb Z} \space \int\limits_{\mathbb R/\mathbb Z} \sum\limits_{i,j} c_{i,j} \phi_i(x) \overline{\phi_j(y)} \phi_n(y) \overline{\phi_n(x)}dydx$$

$$ = \sum\limits_{n,i,j} c_{i,j} \Bigg(\int\limits_{\mathbb R/\mathbb Z} \phi_i(x) \overline{\phi_n(x)}dx \Bigg) \Bigg( \int\limits_{\mathbb R/\mathbb Z} \phi_n(y) \overline{\phi_j(y)}dy \Bigg) = \sum\limits_{n,i,j} c_{i,j} \delta_{i,n} \delta_{n,j} = \sum\limits_{i,i} c_{i,i}.$$

Therefore,

$$\operatorname{Tr}(T) = \int\limits_{\mathbb R/\mathbb Z} K(x,x)dx.$$

Third way (geometric expansion):

Now that we have established that the trace of $T$ can be gotten by integrating $K(x,y)$ along the diagonal, we can compute the trace in one more way:

$$\operatorname{Tr}(T) = \int\limits_{\mathbb R/\mathbb Z} K(x,x) dx = \int\limits_{\mathbb R/\mathbb Z} \sum\limits_{n\in \mathbb Z} f(-x+n+x)dx = \int\limits_{\mathbb R/\mathbb Z} \sum\limits_{n\in \mathbb Z} f(n) dx = \sum\limits_{n \in \mathbb Z}f(n).$$

Thus the Poisson summation formula

$$\sum\limits_{n \in \mathbb Z}\hat{f}(n) = \sum\limits_{n \in \mathbb Z}f(n)$$

holds by looking at the trace of $T$ in two ways, first as a sum of eigenvalues, and second as an integral along the diagonal.


Title: Show that $f(a) + f(b) = f(\frac{a+b}{1+ab})$

Body:
If $f(x) = \log(\frac{1-x}{1+x})$, show that $f(a) + f(b) = f(\frac{a+b}{1+ab})$

Note: base of log is 10

Body:
Just do it.

$f(a) + f(b) = \log\frac {1-a}{1+a} + \log \frac{1-b}{1+b} = \log(1-a) - \log(1+a) + \log(1-b)- \log (1+b)$.

And $f(\frac {a+b}{1+ab}) = \log \frac {1-\frac {a+b}{1+ab}}{1+\frac {a+b}{1+ab}}=$

$\log \frac {(1+ab) - (a+b)}{(1+ab)+(a+b)}=\log \frac {1+ab-a-b}{1+ab+a+b}=$

$\log \frac {(1-a) +(ab-b)}{(1+a)+ (ab+b)} = \log \frac {(1-a) + b(a-1)}{(1+a) + b(1+a)} = \log \frac {(1-a)- b(1-a)}{(1+a) + b(1+a)} =\log \frac {(1-a)(1-b)}{(1+a)(1+b)}=$

$\log (1-a) + \log(1-b) - \log (1+a) - \log (1+b)$

And they are both the same thing.


问:
Given $2 \times 2$ matrix A over field $F_p$. How many matrices of fixed determinant there exist?
Note: $p$ is prime number

The idea that I had in mind was to fix the determinant $\Delta$. We can easily say what is determinant of matrix $2 \times 2$. If we put $A = \begin{pmatrix}a & b \\ c & d \end{pmatrix}$, then $\Delta = a \cdot d - b \cdot c$. So, if $\Delta$ is fixed then we can write something like this: $$a = \frac{\Delta + b \cdot c}{d}$$

So, for any fixed $b$, $c$ and $d \not= 0$ we are able to easily calculate determinant. But it doesn't seem so trivial how number of ways to set $b, c$ and $d$ can be calculated.

All help and hints will be much appreciated!

答:
Count the determinant 0 matrices separately.

For the others, notice that the map $A \mapsto \det{A}$ is a group homomorphism from $\mathrm{GL}(2,p) \to \mathbb{F}_{p}^{*}$, so the set of matrices of determinant $a$ is a coset of the kernel (which is the subgroup of matrices with determinant 1). In other words, for each $a \in \mathbb{F}_{p}^{*}$, there are the same number of matrices with determinant $a$.


问:
Prove $\frac{a^2}{b^3}+\frac{b^2}{c^3}+\frac{c^2}{a^3}≥\frac{1}{a}+\frac{1}{b}+\frac{1}{c}$
Question : Prove $$\frac{a^2}{b^3}+\frac{b^2}{c^3}+\frac{c^2}{a^3}\geq \frac{1}{a}+\frac{1}{b}+\frac{1}{c}$$
$(a, b, c \in \mathbb{R}^+)$

I tried to solve it like this :
$$\frac{a^2}{b^3}+\frac{b^2}{c^3}+\frac{c^2}{a^3}+\frac{1}{a}+\frac{1}{b}+\frac{1}{c} \geq 2 \; (\frac{a}{b^2}+\frac{b}{c^2}+\frac{c}{a^2})$$

Am I doing this right? How can I finish this problem?

答:
It can be proven in a straightforward way, just basic inequalities and definition of the real numbers, we'll have the inequality: $0\leq a\leq b\leq c$.

$$c^2\geq a^2 \Rightarrow \frac{c^2}{a^3}\geq\frac{1}{a}$$

$$\text{and} \quad (\frac{c}{b})^n \geq0> \frac{c^2-b^2}{a^2-b^2} \Rightarrow c^3(a^2-b^2)\geq b^3(c^2-b^2)\Rightarrow c^3a^2-c^3b^2\geq b^3c^2-b^5 \\ a^2-b^2\geq \frac{b^3}{c} - \frac{b^5}{c^3} \Rightarrow \frac{a^2}{b^3}-\frac{1}{b}\geq\frac{1}{c}-\frac{b^2}{c^3} \\ \frac{a^2}{b^3}+\frac{b^2}{c^3}\geq\frac{1}{b}+\frac{1}{c}$$

You can see the same thing happening for any order of inequalities between $a,b,c$, and you combine the two equations from above.


问:
Measurable $\rightarrow$ Mahlo
On page 135 of Jech there is a step that I do not understand in the proof of "measurable implies Mahlo". We have already proved that "measurable implies strong limit". Jech writes

"As $\kappa$ is a strong limit, the set of all strong limit cardinals $\alpha < \kappa$ is closed unbounded...."

Surely every strong limit cardinal does not have a club set of strong limit cardinals below it (take the least strong limit cardinal, for example).

Am I missing something?

thank you

答:
You are correct. But you already know that a measurable cardinal has to be regular.

It isn't hard to see that for a strongly inaccessible cardinal, the set of strong limit cardinals is a club.

Generally, the set of strong limit cardinals is always closed, because the limit of strong limit cardinals is a strong limit cardinals. It's just bounded in most cases, but since $\kappa$ is regular, we get the unboundedness as well, to see this:

Let $\lambda<\kappa$, take $\lambda_0=\lambda;\ \lambda_{n+1}=2^{\lambda_n};\ \lambda_\omega=\sup\{\lambda_n\mid n\in\omega\}$. Since $\kappa$ is strong limit, we have that $\lambda_n<\kappa$ for all $n$, and because it is [uncountable] regular, $\lambda_\omega<\kappa$ as well.

It is not hard to see that $\lambda_\omega$ is a strong limit cardinal, and therefore the set of strong limit cardinals is unbounded below $\kappa$, so it has to be a club.

Title: Measurable $\rightarrow$ Mahlo


问:
Is homology an adjoint functor?
Consider the homology functor $H$ defined (say) on the category of complexes of R-modules (where $R$ is unitary commutative ring). Does $H$ admits left or right adjoints? I know that homology preserves direct sums and direct limits, so it seems reasonable to think of it as a left adjoint.

I also believe that homology cannot be a right adjoint, since in general it does not preserve inverse limits. Is this correct?

Sorry if the question is naive, I'm studying homological algbera directly from a course in algebraic topology.

答:
As comments have pointed out, homology does not preserve cokernels for example. The functors that are adjoints, however, and this is a bit more important for example when you're doing model theory and homotopy theory with objects with a differential, are the boundary and cycles functor.

Namely, the functor from the category of complexes $\textsf {Ch}$ that assigns $C$ to $Z_n(C)$ is in fact of the form $\hom_{\textsf {Ch}}(S^n,C)$ where $S^n$ is the complex generated by a single element $z$ in degree $n$ with $dz=0$. Similarly, the functor $C\longmapsto B_n(C)$ is of the form $\hom_{\textsf {Ch}}(D^{n+1},C)$ where $D^{n+1}$ is the complex with two generators $x$ and $y$ in degrees $n+1$ and $n$ and with $dx=y$. The natural inclusion $S^n\subseteq D^{n+1}$ then induces the inclusion map $B_n(Z) \subseteq Z_n(C)$, and homology is, at least, a `quotient of representable functors.'

Title: Is homology an adjoint functor?


问:
Am I missing something in the definition of universal generalization?
Today I came across the definition of universal generalization in first-order logic.

The definition in my script goes as follows (translated):

If we know, that for any element $a \in X: P(a)$ is true, we can conclude, that $\forall x \in X:P(x)$ is true.

Now for my question: Is it legitimate when I just write: $\forall a \in X:P(a)\rightarrow \forall x \in X: P(x)$

This definition of mine seems redundant to me, and therefore I have doubts that it is right. Is it the same, or did I get something wrong?

答:
Is it legitimate when I just write: $\forall a \in X:P(a)\rightarrow \forall x \in X: P(a)$

It would less confusing if you wrote equivalently:  $\forall a \in X:P(a)\rightarrow \forall x \in X: P(b)$

This implication is not necessarily true. It would be true if $X=\{b \}$. It would be false if we had $X=\{c\}$, $c \neq b$ and $\neg P(b)$.


问:
Determine the flux of the field (x,y,z) through the surface z=$\sqrt(x^2+y^2-15)$, 16 ≤$x^2+y^2$≤40 with outward pointing unitnormal
Determine the flux of the field (x,y,z) through the surface z=$\sqrt(x^2+y^2-15)$   ,  16 ≤$x^2+y^2$≤40 with outward pointing unitnormal.

I understand that you need to use Gauss's divergence theorem, but I can't seem to workout the integrals. I bound the region with three surfaces, two circles at the top and bottom and then the surface z=$\sqrt(x^2+y^2-15)$.

I am having troubles working out the flux through the top and bottom surfaces. I am using the formula \begin{equation}
 \iint \limits_{}^{} u N dS
\end{equation}

For the bottom surface I get \begin{equation}
 \iint \limits_{}^{} (x,y,z)(0,0,-1) dxdy= \iint \ -z   dxdy
\end{equation}

I get stuck here. Any help would be appreciated!

答:
Yes close the surface with disks at top (in plane $z = 5$) and bottom (in plane $z = 1$) and apply divergence theorem.

Divergence of the vector field $\nabla \cdot (x,y,z) = 3$.

Using cylindrical coordinates, the surface is

$z = \sqrt{r^2-15} \implies r^2 = z^2 + 15$.

We also know $16 \leq r^2 \leq 40$. That leads to $1 \leq z \leq 5$.

So total flux can be calculated as

$\displaystyle 3 \int_1^5 \pi(z^2+15) \ dz$.

Now we will find flux through the bottom disk.

$\vec F \cdot \hat{n} = (x,y,1) \cdot (0, 0, -1) = -1$

So the surface integral will be equal to the area of the disk with minus sign, which is $ - 16 \pi$.

Similarly for flux through the top surface,

$\vec F \cdot \hat{n} = (x,y,5) \cdot (0, 0, 1) = 5$

So the flux is $5$ times the area of the disk which is $200 \pi$.

Net outward flux through both top and bottom disks $ = 184 \pi$.

Now subtract that from the total flux through closed surface to get the answer.


问:
Example of graph $G=(V,E)$ without a perfect matching where $|N(S)|\geq |S|$ for every $S\subset V$
I have been asked to find a graph $G=(V,E)$ without a perfect matching where $|N(S)|\geq |S|$ for every $S\subset V$. This to show that Halls marriage theorem does not hold for non-biparite graphs but I cannot really find one graph that fulfills this.

I guess this is quite trivial but I have a hard time to really understand how to find graphs such that $|N(S)|\geq |S|$ for every $S\subset V$ without perfect matchings, does anyone have any idea about such graph?

Later on I have seen the following link, but I wonder if there is a less complicated graph?

an example for an arbitrary graph $G$ with even vertices which $\forall S \in V(G) , |N(S)|\geq |S| $ but there is no complete matching .

答: The comment by @bof beat me to it, but $K_3$ will do. In fact, $K_{2k+1}$ for any positive integer $k$ will do as well.


问:
If there is an automorphism between elements in a ring, why does this mean that the quotient ring over certain ideals are isomorphic?
I am looking at the first answer to this question:
How to show $\mathbb Z_2[x]/(x^3+x+1)$ is isomorphic to $\mathbb Z_2[x]/(x^3+x^2+1)$

Why does the existence of an automorphism between $x$ and $x+1$ imply that the quotient rings are isomorphic? I understand that when you substitute $x$ with $x+1$ in the original expression you get
$$(x+1)^3 + x+1 +1 = x^3 + 3 x^2 + 4 x + 3 = x^3 + x^2 +1$$
in $\mathbb{Z}_2[x]$, but I don't understand the connection to the quotient ring.

I am trying to apply the logic to a similar question, to show that
$$\mathbb{Z}_2[x] / \langle x^2 \rangle \cong \mathbb{Z}_2[x]/\langle x^2-1\rangle$$
But I cannot convince myself why this automorphism leads to the conclusion that the quotient rings are isomorphic.

答:
For the first part:

The polynomial ring $\mathbb{Z}_2[x]$ has a universal property:

Given any commutative ring with unity $S$, any ring homomorphism $g\colon\mathbb{Z}_2\to S$, and any $s\in S$, there exists a unique homomorphism $f\colon \mathbb{Z}_2[x]\to S$ such that $f(x)=s$ and $f(a)=g(a)$ for all $a\in\mathbb{Z}_2$.

Here, we start with the ring $S=\mathbb{Z}_2[x]$, $g$ the embedding of $\mathbb{Z}_2\hookrightarrow S$, and take the element $x+1$. So we have a unique morphism $f\colon\mathbb{Z}_2[x]\to\mathbb{Z}_2[x]$ that sends $x$ to $x+1$.

Now compose $f$ with the quotient map $\mathbb{Z}_2[x]\to \mathbb{Z}_2[x]/\langle x^3+x^2+1\rangle$. Call this composite map
$$g\colon \mathbb{Z}_2[x]\to \frac{\mathbb{Z}_2[x]}{\langle x^3+x^2+1\rangle}.$$
The map is surjective, because both $f$ and the projection are surjective. What is its kernel? The kernel is generated by the pre-image of $x^3+x^2+1$: but this is precisely $x^3+x+1$, because as you note $(x+1)^3 +(x+1) + 1 = x^3+x^2+1$. Thus, by the Isomorphism Theorems,
$$\frac{\mathbb{Z}_2[x]}{\langle x^3+x^2+1\rangle} \cong \frac{\mathbb{Z}_2[x]}{\mathrm{ker}(g)} = \frac{\mathbb{Z}_[x]}{\langle x^3+x+1\rangle},$$
proving the desired isomorphism.

For the second part: we use the fact that $(x^2-1) = (x^2+1) = (x+1)^2$. Once again, take the map that sends $x\to x+1$ to get a morphism $f\colon\mathbb{Z}_2[x]\to \mathbb{Z}_2[x]/\langle (x+1)^2\rangle$. Prove the map is surjective, with kernel $\langle x^2\rangle$.

Note this is not going to work over a field that is not of characteristic two, since then $\langle x^2\rangle$ is the square of an ideal, while $\langle x^2-1\rangle = \langle x+1\rangle\langle x-1\rangle$ is the product of two coprime ideals. So the left side would have nilpotent elements, whereas by the Chinese Remainder Theorem the right hand side would be isomorphic to $F\times F$, which does not.


问:
Relations between supremum, infimum the basis of Banach space and its associated sequence of coefficient functionals
Let $E$ be a Banach space with a basis $\{x_n\}$ and let $\{f_n\}$ be the a.s.c.f. Then

The coefficient functionals $\{f_n\}$ associated to the basis $\{x_n\}$ are continuous linear functionals on $E,$ i.e. we have $f_n \in E^*\text{ }(n=1, 2, ...)$. Moreover, there exists a constant M such that
$$ \label{c_fs_are_cts_inequality} 1 \leq \|x_n\|\|f_n\|\leq M (n=1,2,...),$$
and is the unique sequence in $E^*$ that is biorthogonal to $\{x_n\}.$

From that we infer

Corollary

Let $E$ be a Banach space with a basis $\{x_n\}$ and let
$\{f_n\}\subset E^*$ be the associated sequence of coefficient
functionals. Then

a) We have $\displaystyle\inf_{1 \leq n
<\infty}\|x_n\|>0$ if and only if $\displaystyle\sup_{1 \leq n
<\infty}\|f_n\|<\infty.$

b) We have $\displaystyle\sup_{1 \leq n <\infty}\|x_n\|<\infty$ if
and only if $\displaystyle\inf_{1 \leq n <\infty}\|f_n\|>0.$

How can i prove this corollary?

答:
Doesn't the corollary follow immediately from:

$$\frac {1}{\Vert f_n \Vert} \leq \Vert x_n \Vert \leq \frac{M}{\Vert f_n \Vert}$$

If $\Vert f_n \Vert$ is bounded, then $\frac{1}{\Vert f_n \Vert}$ is bounded above $0$ so $\Vert x_n \Vert$ must also be bounded away from $0$.  Conversely, if $\Vert x_n \Vert$ is bounded away from $0$, then $\frac{M}{\Vert f_n \Vert}$ is likewise bounded away from $0$ so $\Vert f_n \Vert$ can't become arbitrarily large.

In other words, suppose $\inf_n \Vert x_n \Vert=0$.  Then for any $\varepsilon \gt 0$, you can find $k$ such that $\Vert x_k \Vert \lt \varepsilon$, which means $\frac{1}{\Vert f_k \Vert} \lt \varepsilon$, which means that $\Vert f_k \Vert \gt \frac{1}{\varepsilon}$.  Since $\varepsilon$ can be arbitrarily small, that means you can find $k$ such that $\Vert f_k \Vert$ is arbitrarily large, so $\sup \Vert f_n \Vert = \infty$.

The remaining direction of part a is proved similarly, using the other inequality.  If $\inf_n \Vert x_n \Vert \gt 0$, then for some fixed $\varepsilon \gt 0$ it's always the case that $\Vert x_n \Vert \gt \varepsilon$, so $\frac {M}{\Vert f_n \Vert} \gt \varepsilon$ for all $n$ and $\Vert f_n \Vert \lt \frac {M}{\varepsilon}$ for all $n$, which means $\sup_n \Vert f_n \Vert \leq \frac {M}{\varepsilon} \lt \infty$.

A similar proof works for part b.


问:
How to interpret/"understand with hands" the fact that $\sum_{n=0}^{\infty} e^{-na}\ne \int_{0}^{\infty} e^{-na}dn$?
Let's consider that $a$ is positive quantity.

We have $\sum_{n=0}^{\infty} e^{-na}=\frac{1}{1-e^{-a}}$.

If we move to a continuous sum, we have : $\int_{0}^{\infty} e^{-na}dn=1/a$.

How to interpret the fact that two results are different ?

(I have in mind Planck demonstration of black body spectrum where he had the idea to use a discrete sum instead of a continuous sum)

答:
Note that $a$ is always positive. Therefore, $e^{-na}$ is strictly decreasing with respect to $n$. It follows that $\int\limits_i^{i + 1} e^{-na} dn < e^{-ia}$.

Therefore, we have

$\int\limits_0^\infty e^{-na} dn = \sum\limits_{i = 0}^{\infty} \int\limits_i^{i + 1} e^{-na} dn < \sum\limits_{i = 0}^\infty e^{-ia} = \sum\limits_{n = 0}^\infty e^{-na}$


问:
true or false test when knowing absolutely nothing
I have to answer a true-or-false test, where each question has probability 0.5 to be true. The bad news is that I don't have the faintest idea of the answers to the questions; the good news is that I can repeat the test until I manage to get all answers correct. At the end of each try, I will know how many questions I got right.

If the test is composed by a single question, I can pass it in at most two tries. With two questions, three tries may be needed: if my first attempt gets one right answer, I don't know which one is. I computed the result for 3 and 4 questions, and I obtained that I may need 4 or 5 tries respectively.

A pattern seems to reveal, but I am not really sure it is the right one. After all, when the number of questions becomes higher, the result of the first attempt gives me more information. Is there some known result about this?

答:
Here's a suggestion, off the top of my head.

Let there be $n$ questions.

a) Answer all questions false. You will score $m$ where $0 \le m \le n$. If $m = n$, job done.

b) Answer all questions false except q1, answer true. If your score is $m - 1$, you know that you answered right on a), so q1 is false. If your score is $m + 1$, you know that you answered wrong on a) but right on b), so q1 is true.

c) Answer all questions false except:

i) q1, with either true or false according to which one is correct

ii) q2, which you answer true. And again, this will be either one more or one less than the score when you answered the other way (taking the correct score of q1 into account). And so you can work out whether q2 is true or false.

d) Now you can do the same with Q3, until all answers are correct.

You will get them all correct after at most $n$ passes through the exam.

There may be further shortcuts you can make. But this will do as a start.


问:
Combinatorics: precomputed all combination without repetition, need fast indexing
I've asked a similar (but not identical) question on SO here https://stackoverflow.com/questions/5984102 but the answers aren't that helpful for I need very fast indexing (and maybe that my question wasn't clear enough).

I precomputed a lot of values that took days to compute (with the load spread on several computers).  Now I've got a huge lookup table that I need to frequently access and that access has to be as fast as possible.

Basically, I've got a problem like this: I precomputed C(38,6) values (i.e. 2 760 681 values)  that are now store in a big lookup table.  Memory ain't an issue.  Precomputing ain't an issue.  The "order" ain't an issue and I can re-order in any way I like.

Also, C(38,6) is just an example, I could be needing C(42,7) as well, etc.

When I did the precomputing, I basically looped like this (the actual code is more complicated for the load needed to be spread across several machines and for the actual computation aren't here but here's the meat of it):

```<code>for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            for (int l = k + 1; l < n; l++) {
                for (int m = l + 1; m < n; m++) {
                    for (int o = m + 1; o < n; o++) {
                       ...
                    }
                }
            }
        }
    }
}
</code>```

The only thing that matters is to have the fastest lookup time possible.

I've got i,j,k,l,m and n all in [0..37] (or [1..38], doesn't matter) and I need to access the corresponding precomputed element in my huge lookup array as fast as possible.

Is there a closed formula for this that is fast to compute?

What I've got now is a binary search: my i shall always be lower than j, j lower than k etc.  I then created an arbitrary index doing:

```<code>(i + 1) * (n exp 5) + (j + 1) * (n exp 4) + (k + 1) * (n exp 3) + (l + 1) * (n exp 2) + (m + 1) * n + o
</code>```

This is probably overkill but guarantees no collisions. I then do a binary search on that index and find where the precomputed value is stored.

This is kinda fast but I was wondering if there was a faster way to "reach" my precomputed index?

Basically because I don't know enumerative combinatorics well enough I'm precomputing my own index and using that index to do a binary search.  This is fast but I'm looking for something faster, like a closed formula (I doubt anything doing "enumerations" and i++ or things like that would be faster than those few multiplication to compute that index + the binary search).

I think the complexity of my method is log(n) but I'm just not sure.

答: If we use 1 based, the critical observation is that of the $\binom{38}{6}=\frac{38!}{32!6!}$ combinations, $\binom{37}{5}$ of them will start with $1$, $\binom{36}{5}$ of them will start with 2, and so on.  So given $(9,12,14,24,33,37)$, the combinations with $9$ in the first place will start after $\binom{37}{5}+\binom{36}{5}+\binom{35}{5}+\binom{34}{5}+\binom{33}{5}+\binom{32}{5}+\binom{31}{5}+\binom{30}{5}$, because that is how many start with $1$ through $8$.  Then within the $9$'s, the ones with $10$ in the second position number $\binom{28}{4}$ and the ones with $11$ in the second position number $\binom{27}{4}$, so the ones starting with $(9,12)$ start after that.  So this is after $\sum_{i=1}^{8}\binom{38-i}{5}+\sum_{i=10}^{11}\binom{38-i}{4}$.  The ones with $13$ in the third position number $\binom{25}{3}=\binom{38-13}{3}$.  The pattern should be clear.  When you get to the end, you will have the index in the table.  You can also go the other way, so you don't have  to precompute your table-as you say next week you could need the same thing for combinations of $\binom{42}{7}$.  To find the millionth combination, the ones with a leading $1$ are $\binom{37}{5}=435897$ and the ones with a leading $2$ are $\binom{36}{5}=376992$ so we want the $187111^{\text{st}}$ one starting with $3$.  Then the second place $4$'s are $\binom{34}{4}=46736$ and we find the second item is $9$ and we want the $4625^{\text{th}}$ and so on giving (3,9,11,16,27,36)</p>


问:
How to solve $e^{ix} = i$
I am taking an on-line course and the following homework problem was posed: $$e^{ix} = i$$ I have no idea how to solve this problem. I have never dealt with solving equations that have imaginary parts. What are the steps to solving such equations? I am familiar with Taylor series and the Euler formula if that is any help.

Thanks.

答:
Well, the geometric meaning of $e^{ix}$ is the weapon here to use.

This is nothing but the point on the complex plane which has length $1$ and angle $x$ measured from the right half of the real axis, in radian. So that $e^{i\pi}=-1$, for example.

Title: How to solve $e^{ix} = i$


问:
Did this real analysis exam question went wrong?
while studieng for my real analysis exam I work through older exams, and stumbled over the following task

(I copied it 1 to 1):

Show that for any $q\in \mathbb{R}$ and $\forall n\in \mathbb{N}_{\ge 1}$ the following identity holds:

$$\sum^n_{k=1}(1-q)^{k-1}q^{n-k}=1$$

I figured they want me to probably use induction on this and worked till the inductionstep with:

$\sum^{n+1}_{k=1}(1-q)^{k-1}q^{n-k}=\sum^n_{k=1}(1-q)^{k-1}q^{n-k}+(1-q)^nq^{-1}=1+(1-q)^nq^{-1}$ (using the induction hypothesis)

Here I kept stucking until I figured maybe the examquestion is wrong.. and for $n=4$ and $q=\frac{1}{3}$

wolfram alpha indeed tells me the identity stated above doesnt hold.

So is the exam question wrong? And if its wrong, what went wrong (what is missing?) I suspect a missing binomial coefficient..

答: There should be a factor $n \choose k$ in the sum.  The proof is expanding $1^n=((1-q)+q)^n$ with the binomial theorem.


问:
Why does an empty intersection (for families) not make sense?
In Halmos' Naive set theory, on p. 35, he writes

An empty union makes sense (and is empty), but an empty intersection
does not make sense.

Suppose my index set is $I = \{1, 2\}$ and my indexed sets are defined as $A_i \equiv \{-i, i\}$. Then $A_1 = \{-1,1\}$, $A_2 = \{-2, 2\}$, $\bigcup A_i = \{-2, -1, 1, 2\}$ and $\bigcap A_i = \emptyset$. I don't see why that doesn't "make sense".

答:
Consider a family of sets $A_i$ indexed by $i \in I$. What is the definition of $\bigcap\limits_{i \in I} A_i$? It is supposed to be $\{x : \forall i \in I, x \in A_i\}$.

In other words, it's the set of all $x$ which are in all of the $A_i$.

Now, we must ask ourselves whether this intersection in fact forms a set.

Theorem: $\bigcap\limits_{i \in I} A_i$ forms a set iff $I$ is nonempty.

Proof: suppose that $I$ is non-empty. That is, we have some $j \in I$. Then we note that $\{x : \forall i \in I, x \in A_i\} = \{x \in A_j : \forall i \in I, x \in A_i\}$. And the latter is always a set.

Now suppose $I$ is empty. Then $\{x : \forall i \in I, x \in A_i\}$ is the set of all sets. But it's well-known that there can be no set of all sets. This is a contradiction. So $\bigcap\limits_{i \in I} A_i$ does not exist.

OP's confusion arises from the term "empty intersection". The author means that the indexing set is empty, not that the resulting intersection is empty.


答:
So, you say that you're okay with Euler's formula:
$$e^{ix}=\cos(x)+i\sin(x),$$ and it should be clear that (for real numbers $a,b,c,d$), we have $$a+bi=c+di\quad\iff\quad a=c\;\text{ and }\;b=d.$$
So, which values of $x$ will satisfy
$$\cos(x)+\sin(x)i=0+1i\quad ?$$</p>

Title: How to solve $e^{ix} = i$

Body:
I am taking an on-line course and the following homework problem was posed: $$e^{ix} = i$$ I have no idea how to solve this problem. I have never dealt with solving equations that have imaginary parts. What are the steps to solving such equations? I am familiar with Taylor series and the Euler formula if that is any help.

Thanks.


问:
Why $S^1$ does not deformation retract to a point
I tried to use the definition of deformation retract, i.e I have a retract $r:S^1\rightarrow {x_0}$ and I define the homotopy between $id_{S^1}$ and $i\circ r$ via $F(s,t) = tx_0 + (1-t)x$. But geometrically, I know it is not contractible because we cannot "tear" the circle and deform it onto a point. Where my argument gets wrong?

答: Your $F(s,t)$ lives in $\Bbb R^2$ not $S^1$.


问:
Maclaurin Series Terms and Convergence or Divergence
This is one of the HW questions I'm trying to solve

Find the first four terms of this Maclaurin Series of $$f(x)=\cos\left(\frac{x}{x+1}\right)$$

I tried using $\sum_{n=0}^\infty (-1)^n  \frac{x^{2n}}{2n!} = \cos x $ and   $ \sum_{n=0}^\infty (-1)^n x^n= \frac{1}{1+x}$ but no luck! I can't properly substitute the derivative of the series in the Maclaurin Series.

Also related to this question is its second part$$ \sum_{} (n)^p (\cos (\frac{1}{n-1})-\cos(\frac{1}{n})$$
for what values of $p$ it converges or diverges.

I would really appreciate it if someone could type in a detailed solution so I can improve my understanding of this topic.

答:
There's only one sensible way to find such expansions (and I guess it's the way Mathematica or Wolfram Alpha do it): Let $$c(x)=\cos\left(\frac{x}{x+1}\right)=c_0+c_1\,x+c_2\,x^2+c_3\,x^3+\ldots\tag1$$ and $$s(x)=\sin\left(\frac{x}{x+1}\right)=s_0+s_1\,x+s_2\,x^2+s_3\,x^3+\ldots\tag2$$
Obviously, $c_0=c(0)=1$ and $s_0=s(0)=0$. Differentiating (1) and (2), we find
$$c'(x)=-\frac1{(1+x)^2}\,s(x)\tag3$$ and $$s'(x)=\frac1{(1+x)^2}\,c(x)\tag4.$$ Since $$\frac1{(1+x)^2}=1-2\,x+3\,x^2-4\,x^3+\ldots,$$ (3) and (4) become
$$c_1+2\,c_2\,x+3\,c_3\,x^2+\ldots=-(1-2\,x+3\,x^2-\ldots)(s_0+s_1\,x+s_2\,x^2+\ldots)\tag5$$ and $$s_1+2\,s_2\,x+3\,s_3\,x^2+\ldots=(1-2\,x+3\,x^2-\ldots)(c_0+c_1\,x+c_2\,x^2+\ldots)\tag6.$$ Comparing coefficients in (5) and (6), we obtain
$c_1=-s_0$, $2\,c_2=-s_1+2\,s_0$, $3\,c_3=-s_2+2\,s_1-3\,s_0, \ldots$ and
$s_1=c_0$, $2\,s_2=c_1-2\,c_0$, $3\,s_3=c_2-2\,c_1+3\,c_0, \ldots$, giving successively $c_1=0, s_1=1\to c_2=-\frac12, s_2=-1\to c_3=-1,\ldots$ It's simple to obtain $$c(x)=1-\frac12\,x^2+x^3+\ldots,\tag7$$ (and quite a few more terms, if necessary) this way. But (7) is sufficient for the second part of the question, because $$\cos\left(\frac1{n-1}\right)=\cos\left(-\frac1{n-1}\right)=c\left(-\frac1n\right)=1-\frac1{2n^2}-\frac1{n^3}+\ldots$$