Prove that a specific inequality holds Let $n \in \mathbb{N}$. Let $z_1, \ldots, z_n$ and $w_1, \ldots, w_n$ be complex numbers such that
$$ \sum_{j = 1}^n |w_j|^2 \leq 1 $$
and
$$ \left| \sum_{j = 1}^n z_j w_j \right| \leq 1 $$
Show that
$$ \sum_{j = 1}^n |z_j|^2 \leq 1$$
The reverse is easy, but I have no clue as to why this is true.

EDIT The question should be:

Let $n \in \mathbb{N}$. Let $z_1, \ldots, z_n$ such that
$$ \left| \sum_{j = 1}^n z_j w_j \right| \leq 1 $$
for all complex numbers $w_1, \ldots, w_n$ with
$$ \sum_{j = 1}^n |w_j|^2 \leq 1 $$
Show that
$$ \sum_{j = 1}^n |z_j|^2 \leq 1$$

There is no reason why this should be true. It certainly isn't.

Take for instance $w_1 = 0.1$, $w_2 = 0.01$, $z_1 = 1$ and $z_2 = 10$.

Edited:

For each $1 \le j \le n$, assume that $z_j \neq 0$ and let:

$$w_j = \frac{|z_j|^2}{z_j \sqrt{\sum_{i=1}^n |z_i|^2}}$$

Then,

$$\sum_{j=1}^n |w_j|^2 = \sum_{j=1}^n \frac{|z_j|^2}{\sum_{i=1}^n |z_j|^2} = 1 $$

Hence,

$$\left| \sum_{j=1}^n z_j w_j \right| \le 1$$

But,

$$\left| \sum_{j=1}^n w_j z_j \right| = \sum_{j=1}^n \frac{|z_j|^2}{\sqrt{\sum_{i=1}^n |z_i|^2}} = \sqrt{\sum_{j=1}^n |z_j|^2}$$

Therefore,

$$\sum_{j=1}^n |z_j|^2 \le 1$$

One doesn't need to take into consideration the case where one of the $z_j$'s is equal to $0$ because it just amounts to reducing $n$ to a smaller number.

The Cauchy-Schwarz inequality states that
$$\left| \sum_{j=1}^n z_j w_j \right|^2 \leq \left( \sum_{j=1}^n |z_j|^2 \right) \left( \sum_{j=1}^n |w_j|^2 \right)$$
with equality if and only if $z = (z_1, \ldots, z_n)$ and $w = (w_1, \ldots, w_n)$ are parallel. You only know that one of the factors to the right is less than zero. If you could make the inequality into an equality for some choice of $w$, then this would do it. Therefore, try to pick $w$ parallel to $z$, but remember that $w$ must have length less than one.


Increasing a number when another number gets smaller than 0 This should be trivial but for some reason I cannot think of a formula which enlarges a number in proportion to another number decreasing in the negative direction

Example:

if value 1 = $-0.1$, value 2 should be set to $0.9$
if value 1 = $-0.2$, value 2 should be set to $0.8$
if value 1 = $-0.4$, value 2 should be set to $0.6$

and so on...

Thanks for any help

How about $$\mathsf{(\text{value 2})}=1+\mathsf{(\text{value 1})}\quad ?$$
It fits all the examples you gave.

In your description you mention that one should be increasing while the other is decreasing. In your examples, both value1 and value2 are getting smaller.


Prove that $5^n \equiv 8n^2-4n+1 \mod 64$ using induction I am trying to prove that $5^n \equiv 8n^2-4n+1 \mod 64 $ using induction. I have seen the post which solves this problem using other methods, but I really need to be able to do it using induction.
Here is what I have so far:
Base step:
$5 \equiv 5 \mod 64$
Then, I assumed that $5^k \equiv 8k^2 -4k+1 \mod 64.$
I want to prove that $5^{k+1} \equiv 8(k+1)^2-4(k+1)+1 \mod 64$.
Note that $8(k+1)^2-4(k+1)+1=8k^2+12k+5$.
Hence,
$5^{k+1} \equiv 5^k *5 \mod 64
\equiv (8k^2-4k+1)*5 \mod 64 \equiv 40k^2 -20k+5 \mod 64.$
I am stuck here.
Any insight would be very useful!!
Thanks

Using binomial expansion,
$$5^n=(1+4)^n=1+\binom n1 4 + \binom n2 4^2 + \binom n3 \color{blue}{4^3} + \binom n4 \color{blue}{4^4} +\cdots + \binom nn \color{blue}{4^n}.$$
Since the binomial coefficients are integers and $4^3=64$, we have
$$5^n\equiv1+4n+8n(n-1)=8n^2-4n+1\bmod64.$$

A generalization
suggested by J. W. Tanner's answer.
If $0 < j < n$ then
$\begin{array}\\
(1+m)^n
&=\sum_{k=0}^n \binom{n}{k}m^k\\
&\equiv\sum_{k=0}^j \binom{n}{k}m^k \bmod m^{j+1}\\
\text{if }
&j=2\\
(1+m)^n
&\equiv\sum_{k=0}^2 \binom{n}{k}m^k \bmod m^{3}\\
&\equiv 1+nm+\frac12n(n-1)m^2\bmod m^{3}\\
&\equiv 1+n(m-\frac12m^2)+\frac12n^2m^2\bmod m^{3}\\
\text{if}
&m=4\\
5^n
&\equiv 1-4n+8n^2 \bmod 64\\
\end{array}
$


Are there some non-complete inner product spaces in which the equality holds:$M^{\perp\perp}=\overline{\operatorname{span} M}?$ Let $X$ be a Hilbert space and  $M\subset X$. We know that the following is true:
$$(M^{\perp})^{\perp}=\overline{\operatorname{span} M}.$$
But  I want to know is it true if $X$ is an inner product space .
Can someone help me prove it or give a counterexample? Thank you in advance.

I have tried some examples such as $X=C[0,1] $ and $M=\{f\in C[0,1]:f \text{ is constant}\}$,but all of them show the positive answer.

This identity holds in all inner product spaces. The usual proof uses Hahn-Banach and no completeness is needed.


Show that a sequence $\{s_n\}$ converges to a limit $L$ if and only if the sequence $\{s_n-L\}$ converges to zero. I'm looking for hints and ideas on how to improve the draft of my proof.

Proof: Let $\{s_n\}$ be any given sequence. Then take the limit of the sequence {$s_n$} as shown.

$$\lim_{n\to \infty} s_n=L $$

Indeed, as $n$ tends to infinity, the sequence converges to $L$.

Once more, we take the difference of the sequence $\{s_n\}$ and the limit $L$.

Lastly, we take the limit of $\{s_n -L\}$, so

$$\lim_{n\to \infty}s_n - L = 0$$

Therefore, the sequence $\{s_n - L\}$ converges to zero.

Hint: First of all, you need a clear definition of what it means for a sequence of real numbers to converge to a limit.

Secondly, using this definition of convergence, show that $s_n$ converges to $L$, if one assumes that $s_n{}-{}L$ converges to $0$.

Finally, using this definition of convergence again, show that $s_n{}-{}L$ converges to $0$, if one assumes that $s_n$ converges to $L$.

This follows the typical structure of an if, and only if, proof Wikipedia.

Let $\epsilon > 0 $ be given. By definition, $s_n \to L$ means that  a positive integer $N$ can be chosen so that for all $n > N $, we have

$$ |s_n - L | < \epsilon $$

Let $a_n = s_n - L $. Hence, $a_n \to 0 $ or $s_n - L \to 0 $. Similarly, you prove the other direction.


Definite integration problem (trig). I have this definite integral:

$$
\int_0^\Pi \cos{x} \sqrt{\cos{x}+1} \, dx
$$

For finding the indefinite integral, I have tried substitution, integration by parts, but I'm having trouble solving it.

By parts

$$
\int \cos{x} \sqrt{\cos{x}+1} \, dx\ = \sqrt{\cos{x}+1}\sin{x} + \frac{1}{2} \int \frac{\sin^{2}{x}}{\sqrt{\cos{x}+1}} \, dx
$$

$
f(x) = \sqrt{\cos{x}+1} \\ f'(x) = \frac{1}{2} \frac{-\sin{x}}{\sqrt{\cos{x}+1}} \\ g(x) = \sin{x} \\ g'(x) = \cos{x}
$

I don't know how to approach this further because of the $\sin^{2}{x}$.

Substitution

$
\cos{x} + 1 = u \\ -\sin{x} \, dx = du
$

But I  have no use for $sin\,x$.

I believe it has something to do with trig manipulations.

WolframAlpha tells me to substitute, but I don't understand how to get the first u-substituted integral like shown:

I would really appreciate any help on this. Thank you.

Note  $\displaystyle \sqrt{\cos x+1}=\sqrt{2\cos^2\frac x2-1+1}=\sqrt2\left|\cos \frac x2\right|$

We have

$$\displaystyle
\int_0^\pi \cos x \sqrt{\cos x+1} \, dx=\sqrt2\int_0^\pi \left(1-2\sin^2{\frac x2}\right) \cos\frac x2  \, dx$$
$$=2 \sqrt2\int_0^\pi \left(1-2\sin^2{\frac x2}\right)   \, d\left(\sin\frac x2\right)$$


Finding the range of launch speeds for which water shot from a hose will enter a tank a distance away A water hose is used to fill a large cylindrical storage tank of diameter $D$ and height $2D$. The hose shoots the water at $45^\circ$ above the horizontal from the same level as the base of the tank and is a distance $6D$ away. For what range of launch speeds $v_0$ will the water enter the tank. Ignore air resistance.

I've made a graphic representing the problem (with $D=1$) showing the trajectory of the water at the minimum launch speed $v_{0\text-m}$ (blue) and maximum launch speed $v_{0\text-M}$ (red) as well as the tank (light gray):

Clearly I've made a mistake in solving for the minimum launch speed - I expect the blue parabola to intersect the rectangle at its top left vertex. I'm not sure where the mistake lies, because as far as I can tell I've used the same approach to solve for $v_{0\text-m}$ as I had for $v_{0\text-M}$, which I'll show first.

The position vector for water particles escaping the hose has components

$$\begin{cases}
x=v_{0\text-M}\cos45^\circ t\\
y=v_{0\text-M}\sin45^\circ t-\frac g2t^2
\end{cases}$$

With $x=7D$, solve for $t$ in the first equation, substitute into the second with $y=2D$ to get

$$t=\frac{7D}{v_{0\text-M}\cos45^\circ}\implies2D=v_{0\text-M}\sin45^\circ\left(\frac{7D}{v_{0\text-M}\cos45^\circ}\right)-\frac g2\left(\frac{7D}{v_{0\text-M}\cos45^\circ}\right)^2$$

$$\implies5=\frac{49Dg}{v_{0\text-M}^2}\implies v_{0\text-M}=7\sqrt{\frac{Dg}5}$$

Now to find $v_{0\text-m}$, the only change in the work above - I would think - would be to set $x=6D$.

$$t=\frac{6D}{v_{0\text-m}\cos45^\circ}\implies2D=v_{0\text-m}\sin45^\circ\left(\frac{6D}{v_{0\text-m}\cos45^\circ}\right)-\frac g2\left(\frac{6D}{v_{0\text-m}\cos45^\circ}\right)^2$$

$$\implies2=\frac{12Dg}{v_{0\text-m}^2}\implies v_{0\text-m}=\sqrt{6Dg}$$

Manipulating the code for the plot of the blue parabola, it would appear the correct answer for $v_{0\text-m}$ is closer to $3\sqrt{Dg}$. How can I salvage my attempt to obtain the right solution?

Minor algebraic mistake...

$$2D=v_{0\text-m}\sin45^\circ\left(\frac{6D}{v_{0\text-m}\cos45^\circ}\right)-\frac g2\left(\frac{6D}{v_{0\text-m}\cos45^\circ}\right)^2$$

should reduce to

$$2D=6D-\frac g2\frac{36D^2}{v_{0\text-m}^2\cos^245^\circ}\implies4D=\frac{36D^2g}{v_{0\text-m}^2}\implies v_{0\text-m}=3\sqrt{Dg}$$

At some point I decided to divide through all terms by $2D$ except for one, which I had mistakenly divided by $3D$ instead.

The equation of trajectory of water jet is $y = x-\dfrac{g}{v^2} x^2$. Let $x$ and $y$ be coordinates of any point in water jet at a height of $2D$. So water to fall we must have $6D < x < 7D$.  By putting $y = 2D$ in above equation we get quadratic in $x$ as $\dfrac{g}{v^2} x^2 - x +2D = O$. Discard negative value of $x$ take only positive value then put value of $x$ in above inequality and solve you will get

$$\sqrt{9gD} < v < \sqrt{9.8gD}$$


Using the definition of a limit to prove 1/n converges to zero. So we define a sequence as a sequence ${a_n}$ is said to converge to a number $\alpha$ provided that for every positive number $\epsilon$ there is a natural number N such that |${a_n}$ - $\alpha$| < $\epsilon$ for all integers n $\geq$ N.

What I'm not understanding is what does this mean. For example, $\frac{1}{n}$ converges to 0. But I don't understand how I use this definition to prove that this converges to 0. It sounds trivial but how do I use the definition to prove that $\frac{1}{n}$ converges to 0. Can you also show the reasoning as to why you use certain steps?

Let's try and fit your definition into the example you mentioned, first. The sequence $a_n$ you gave is $a_n = \frac{1}{n}$, and the limit $\alpha$ is $\alpha = 0$. Therefore, we wish to prove that for any $\varepsilon > 0$ there is a positive integer $N$ such that if $n \geq N$, then $|\frac{1}{n} - 0| = \frac{1}{n} < \varepsilon$.

Let's think about that definition for a moment. What this says is that eventually, every term of the sequence $\frac{1}{n}$ is close to $0$, no matter how arbitrarily close we want to be. And really, that's all we mean by convergence: eventually, the terms of the sequence get "close" to the limit. We are just making that notion of closeness precise.

Now, let's prove the result. Let $\varepsilon > 0$ be given. Then there is a positive integer N such that $\frac{1}{N} < \varepsilon$ (this is the Archimedean Property). Of course, when $n \geq N$, we have that $\frac{1}{n} \leq \frac{1}{N}$ by dividing both sides by $n$ and $N$. This same procedure works for any $\varepsilon$; there is nothing special here about the one we chose (though $N$ might be different in each case; that's not a problem). Therefore, given any $\varepsilon > 0$, we can find a positive integer $N$ such that for $n \geq N$, $|\frac{1}{n} - 0| < \varepsilon$. That is, we showed that $a_n = \frac{1}{n}$ converges to $0$ by definition, as desired.

Frankly speaking, whatever tiny neighborhood of $\alpha$ you choose, almost all terms of the $(a_n)$ sequence (that is all, except possibly finitely many) fall inside that neighborhood.


How to prove that $a^2b+b^2c+c^2a \leqslant 3$, where $a,b,c >0$, and $a^ab^bc^c=1$ $a,b,c >0$, and $a^ab^bc^c=1$, prove
$$a^2b+b^2c+c^2a \leqslant 3$$

I don't even know what to do with the condition $a^ab^bc^c=1$. At first I think $x^x>1$, but I was wrong. This inequality is true, following by the verification from Mathematica

We employ of the rearrangement inequality.
First, since $x\mapsto x^2$ preserves the order for $x>0,$ we have $$a^2b+b^2c+c^2a\le a^3+b^3+c^3.$$
Next write the condition as $$a\ln a+b\ln b+c\ln c=0.$$ Again using the rearrangement inequality, as $x\mapsto\ln x$ preserves the order for $x>0,$ we have the inequalities: $$\begin{cases}a\ln b+b\ln c+c\ln a\le0\\
a\ln c+b\ln a+c\ln b\le0\\
a\ln a+b\ln b+c\ln c=0\end{cases}$$
Adding these together, we have $(a+b+c)\ln(abc)\le0,$ hence $abc\le1.$
Now let $\ln a+\ln b+\ln c=k\le0.$ Apply the Lagrange multiplier method with condition $g(a,b,c):=\ln a+\ln b+\ln c=k$ for a fixed $k\le0,$ to maximize $f(a,b,c):=a^3+b^3+c^3.$
Thus the Lagrange multiplier gives that the extreme of $f$ occurs when $$\begin{cases}3a^2-\lambda\frac{1}{a}=0\\
3b^2-\lambda\frac{1}{b}=0\\
3c^2-\lambda\frac{1}{c}=0\end{cases},$$
i.e. when $a^3=b^3=c^3=\lambda;$ then $a=b=c$ and hence $f(a,b,c)=3abc=3e^k\le3.$
$\square$

Hope this helps.

Edit:
As pointed out in the comment, the final part about Lagrange multipliers is incorrect; in fact, given the constraint $abc<1,$ it does not follow that $a^2b+b^2c+c^2a\le3.$
Also pointed out in the comment is to use Jensen's inequality to obtain $a+b+c\le3,$ but we are not getting answers yet.
Everything we tried so far to fix this fails. We shall update if we find a way to work around.

The condition can be presented in form
$$a\ln a +b\ln b + c\ln c = 0.$$
Let
$$a\leq b\leq c,$$
then
$$\ln a \leq \ln b \leq \ln c,$$
and we can use Chebyshev sum inequality:
$$3(a\ln a +b\ln b + c\ln c) \geq (a+b+c)\ln abc,$$
$$abc\leq 1.$$
Evidently, the expression $a^2b+b^2c+c^2a$ achieves maximum when $abc=1.$

The standard way of solving the problem on a conditional extremum is the method of Lagrange multipliers, which reduces it to a system of equations.

The maximum value of function
$$f(a,b,c,λ)=a^2b+b^2c+c^2a+λ(abc-1)$$
for $a,b,c>0$ on the interval
is reached or at its edges, or in one of the points with zero partial derivatives
$$f'_a=0,\quad f'_b=0,\quad f'_c=0,\quad f'_λ=0,$$
or
$$\begin{cases}
2ab+c^2+\lambda bc = 0\\
2bc+a^2+\lambda ca = 0\\
2ca+b^2+\lambda ab = 0\\
abc-1 = 0,
\end{cases}$$
then
$$\begin{cases}
a(2ab+c^2) = b(2bc+a^2)=c(2ca+b^2),\\
abc=1,
\end{cases}$$
$$\begin{cases}
2b^2c -c^2a = a^2b\\
b^2c -2c^2a = -a^2b\\
abc=1,
\end{cases}$$
$$c^2a = b^2c = a^2b,\quad abc=1,$$
$$\dfrac cb =1, \dfrac ba =1, \quad abc=1,$$
$$a=b=c=1,$$
$$f(a,b,c,\lambda)=3.$$
Note that
$$\lim_{a\to 0} a\ln a = 0,$$
so on the edge $a=0$ we have to minimize
$f(b,c,\lambda) = b^2c + \lambda(bc-1),$
and then we get the system
$$\begin{cases}
2bc+\lambda c = 0\\
b^2+\lambda b = 0\\
bc-1=0
\end{cases}$$
with solution
$$b=2,\quad c=\dfrac12,\quad f = 2 < 3.$$

That means that
$$\boxed{a^2b+b^2c+c^2a \leq 3}$$


Problem understanding a proof (Folland's Real analysis, theorem 6.18) Okay, so as stated here: Issue with proof in Folland's 'Real Analysis' (Theorem 6.18), the text says:

  (Theorem 6.18.) Let $(X,\mathcal{M},\mu)$ and $(Y,\mathcal{N},\nu)$ be $\sigma$-finite measure spaces, and let $K$ be an $(\mathcal{M}\otimes\mathcal{N})$-measurable function on $X\times Y$. Suppose that there exists $C>0$ such that $\int |K(x,y)|\,d\mu(x)\leq C$ for a.e. $y\in Y$ and $\int |K(x,y)|\,d\nu(y)\leq C$ for a.e. $x\in X$, and that $1\leq p\leq\infty$. If $f\in L^p(\nu)$, then the integral
  $$
Tf(x)=\int K(x,y)f(y)\,d\nu(y)
$$
  converges absolutely for a.e. $x\in X$, the function $Tf$ thus defined is in $L^p(\mu)$, and $\|Tf\|_p\leq C\|f\|_p$.

  Proof. Suppose that $1<p<\infty$. Let $q$ be the conjugate exponent to $p$. By applying H$\ddot{\text{o}}$lder's inequality to the product
  $$
|K(x,y)f(y)|=|K(x,y)|^{1/q}\big(|K(x,y)|^{1/p}|f(y)|\big)
$$
  we have
  \begin{align*}
\int |K(x,y)f(y)|\,d\nu(y) &\leq \left[\int|K(x,y)|\,d\nu(y)\right]^{1/q}\left[\int|K(x,y)||f(y)|^p\,d\nu(y)\right]^{1/p}\\
&\leq C^{1/q}\left[\int |K(x,y)||f(y)|^p\,d\nu(y)\right]^{1/p}
\end{align*}
  for a.e. $x\in X$. Hence, by Tonelli's theorem,
  \begin{align*}
\int\left[\int |K(x,y)f(y)|\,d\nu(y)\right]^{p}\,d\mu(x)&\leq C^{p/q}\iint |K(x,y)||f(y)|^p\,d\nu(y)\,d\mu(x)\\
&\leq C^{(p/q)+1}\int |f(y)|^p\,d\nu(y).
\end{align*}
  Since the last integral is finite, Fubini's theorem implies that $K(x,\cdot)f\in L^1(\nu)$ for a.e. $x$, so that $Tf$ is well defined a.e., and
  $$
\int |Tf(x)|^p\,d\mu(x)\leq C^{(p/q)+1}\|f\|_p^p.
$$
  Taking $p$th roots, we are done.

I'm fine with the whole proof except one minor part: Why is $Tf$ a $\mathcal{M}$-measurable function? Could we prove that $K(x,y)f(y)\in L^1(\mu\otimes\nu)$, by Fubini's theorem we would have the desired measurability, but I  don't think this is necessarily true.

(I also don't quite understand where Fubini comes in, as stated in the text. While working out the details, I only used Tonelli's theorem.)

Because the integral is just the limit of serious of sums, so that it must be measurable due to that the limit of a serious of measurable function is measurable.

For Fubini's Theorem. it states that integrable on product space imply a.e.  integrable (as well as measurable) on every original space. So in your problem, $K$ is integrable on product space and so is $f$ because $f$ is a measurable function in one variable so that their product $K(x,y)f(y)$ is integrable on product space. So you could compute its integration. And then, you find it's finite, so by Fubini's Theorem, $\int K(x,y)f(y)dy$ is a.e. defined and integrable.

Is this clear enough? The spirit is to deduce integrability on one variable from integrability on product space.


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

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

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

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

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

Thanks to DeepL translate, I was able to read the article in the Russian journal posted in the comments (https://www.mccme.ru/free-books/matprosf.html), and I can now give the solution. In fact, you can determine the answers to a test with $k2^{k-1}+1$ questions in only $2^k$ non-adaptive attempts.
First, let us reformulate the problem in terms of weighings. Suppose without loss of generality your first submission is a test with all answers being "yes." For any subset $A$ of questions, let the weight of $A$ be the number of questions in $A$ whose answer is "yes." Given the result of this all-"yes" submission, for any subset $A$ of questions, each of these two pieces of information can be deduced from the other:

The score of a test when you answer "yes" for all questions in $A$, and "no" for the other questions

The weight of $A$.

Therefore, I can and will state the strategy in terms of weights.
The fact that you can solve $k2^{k-1}+1$ questions in $2^k$ attempts follows from the following lemma.

Lemma: Suppose you can deduce the answers to a test with $M$ questions in $N$ attempts. Then it is possible to deduce the answers to a test with $2M+N-1$ questions in $2N$ attempts.

Proof: Given a test with $2M+N-1$ questions, divide the questions into three sets $A,B$ and $C$, where $|A|=|B|=M$, and $|C|=N-1$. By assumption, there exist $N-1$ sets $A_1,\dots,A_{N-1}$ such that you could solve a test whose question set is $A$ by submitting the all-"yes" test, and then weighing $A_1,\dots,A_{N-1}$. Similarly, there exist sets $B_1,\dots,B_{N-1}$ for solving a test whose question set is $B$. Finally, let $C=\{c_1,c_2,\dots,c_{N-1}\}$. Then the solution for the $(2M+N-1)$-question test is this:

Answer "yes" to all questions.
Find the weight of $B$.
For each $k\in \{1,\dots,N-1\}$: find the weights of these two sets:

$A_k\cup B_k\cup \{c_k\}$
$A_k\cup (B\setminus B_k)$.

Here is how you deduce the answers to the test. For each $k\in \{1,\dots,N-1\}$, the parity of the sum of the weights of $A_k\cup B_k\cup \{c_k\}$ and $A_k\cup (B\setminus B_k)$ and $B$ determines the answer to $c_k$. We now know the weights of the three sets $A_k\cup B_k$, $A_k\cup (B\setminus B_k)$, and $B$, which gives a simple system of equations to solve for $A_k$ and $B_k$. This gives us the information we need to deduce the answers to the $A$ questions and $B$ questions, using the assumed strategy.$\tag*{$\square$}$ That is, starting with the two-attempt solution to a two-question test, you can derive a four-attempt solution to a test with $2\cdot 2+(2-1)=5$ questions, then an eight attempt solution to a test with $2\cdot 5+(4-1)=13$ questions, and so on, in general leading to $k2^{k-1}+1$ questions in $2^k$ attempts.

The strategy can be modified extend an $N$-attempt strategy for an $M$-question test to a $2N$-attempt strategy for a $2M+r$ test for any $r\in \{0,1,\dots,N-1\}$, by ignoring some of the $C$ questions. This lets you hand the $k2^{k-1}$ question test in $2^k$ questions, as exactly asked in the OP.
Furthermore, it is easy to extend an $N$-attempt strategy for $M$ to an $(N+1)$-attempt strategy for $M+1$. Together with these two rules, you can inductively use the lemma to determine a strategy for any number of tests.

You set up a grid:
3x4 in case k=3 or
9x256 in case k = 9, etc.
In each first mock exam you fill out only one row. The entire row.
In each second (alternate) mock exam you fill out only one column.
You never fill out the same column or row.
Always fill with "yes" or always fill with "no", all your choices, never change once you committed to fill all rows and columns by the same "yes" (or "no") answer.
IN the first example you will fill out 3 rows (each separately) and 4 columns, (each separately) which is fewer the 8.
IN the second example, you fill out 9 rows and 256 columns. That is 265 mock exams, which is fewer than 512. Both cases we fulfilled the "minimum" required exams.
When we guess "wrong" on the mock exam, then we got a "no" (if our choice was to fill out only "Yes"-es in the mock exams.) Simply match up the rows and columns where there is a non-null number of score is given for the given row and the given column by the prof for our faulty answers.
And bob is your uncle.
This is a solution. I am not sure if this constitutes a proof, or how many more steps is required to make this into a proof.
My observation is that the original question of this problem resembles the society board game "Mastermind". This is a simplified version of it, with fewer colours of pegs (if you want to think of this problem that way) but with larger boards, but the same principle applies.


Limit of $\sinh z$ as $z\to i$. I'm trying to understand why

$$\lim_{z\rightarrow\ i} \sinh(z)= i\sin(1)$$

Thanks for any feedback.
I tried using $\sinh(z)=(e^{z}-e^{-z})/2$ but that only seemed to make things more complicated now I'm thinking that L'Hopital may be needed but I don't know how to go about it.

Hint:

\begin{align}
\sin (z)&=\frac{e^{iz}-e^{-iz}}{2i}
\end{align}
Then
\begin{align}
i\sin (1)&=\frac{e^{i}-e^{-i}}{2}
\end{align}

Recall the identity $\sinh(iz)=i\sin z$. Then
$$
\lim_{z \to i} \sinh(z)=\sinh i=\sinh(i\cdot 1)=i \sin(1)
$$


How to solve this quadratic program using the penalty method? example:
$$\min\frac{1}{2}((x_1-3)^2+(x_2-2)^2)$$
s.t.$$-x_1+x_2{\le}0$$
$$x_1+x_2{\le}1$$
$$-x_2{\le}0$$
and we start with $~x^0=[3,2]^T~$ its violate the condition  :
$$q(x,c)=\frac{1}{2}((x_1-3)^2+(x_2-2)^2)+\frac{c}{2}((x_1+x_2-1)^2)$$
and what is next?

calculate $~x_1~$and$~x_2~$ with BFGS, newtons method,....

$\nabla_x q(x,c)=0~$,$~c=~$ a very large number starting with $~10,100,1000,\cdots~$ until the solution has very small difference?

Here are my comments on the method.

The youtube video you mentioned does not describe the example completely. Formally, the $q$-function there is incorrect in the sense that $\nabla_x q(x,c)=0$ does not solve the problem in general. What it does solve is the first iteration minimization only starting from the given initial point. The complete auxiliary function should look as e.g.
\begin{align}
q(x,c)=&\frac{1}{2}((x_1-3)^2+(x_2-2)^2)+\\
&+\frac{c}{2}(\max\{0,-x_1+x_2\}^2+\max\{0,x_1+x_2-1\}^2+\max\{0,-x_2\}^2).
\end{align}
For the given initial point $x^0$ it takes the form as you stated, but at other points of the plane it is (or may be) different.
A solution to $\nabla_x q(x,c)=0$ is the global minimizer in the problem
$$
\min_x q(x,c)
$$
because the function $q(x,c)$ is convex in $x$. It is the known theoretical fact for convex functions. It gives an analytical solution (for lecture's sake). In practice, this step is replaced by Newton/quasi-Newton methods. Moreover, it is often enough to take one iteration of the chosen numerical method to get the next iteration, since it is only one step of the penalty method and to make the exact minimization is too expensive and unnecessary.

Normally the method works like this: for an iteration point $x^k$ do the following

Take $x^k$ and the penalty level $c_k$ and calculate $q_k(x,c_k)$ above for $x$ nearby $x^k$. Depending on where $x^k$ is (what constraints are violated) $\max$-penalties become different, some will disappear if $\max=0$ (i.e. the corresponding constraint is satisfied at $x^k$).
Calculate the next iteration $x^{k+1}$ by taking one step of a Newton-related method for $q_k(x,c^k)$, starting from $x^k$.
If $|x^{k+1}-x^k|$ is small enough then STOP, otherwise update $x^k=x^{k+1}$, $c^k=10*c^k$ and continue with the Step 1.


Alternate definition of singular homology. Instead of defining the spaces $\Delta^n=\{(x_0,...x_{n}) \in \mathbb R^{n+1}:\Sigma_i x_i=1 \ \text{&} \ x_m \geq0\ \forall m\}$ define $s\Delta^n =\{(x_0,...x_{n}) \in \mathbb R^{n+1}:\Sigma_i x_i=1\}$ with the face maps given by $d_i:(x_0,..x_n) \mapsto (x_0,...x_{i-1},0,x_i...,x_n)$. Does this define an isomorphic version of homology? As in if X is a space, do the two definitions coincide. Not necessarily naturally.

I've been struggling with this problem for over two weeks now. I could elaborate on methods I have tried but none have been succesful so I don't see the point. I really only need the result for open subsets of $\mathbb R^n$ so make any assumptions you want about the space X. Thank you in advance!

Yes, this is naturally isomorphic to singular homology.  To prove it, first construct a sequence of retractions $r_n:s\Delta^n
\to\Delta^n$ which are compatible with the face maps.  For instance, $r_1$ will take the line $s\Delta^1$ and contract the ends of it down to just the bounded interval $\Delta^1$.  Then $r_2$ will contract the plane $s\Delta^2$ down to the triangle $\Delta^2$, contracting each line bounding the triangle down to the edge of the triangle according to $r_1$.  In general, having constructed $r_i$ for $i<n$, the existence of such an $r_n$ follows from the Tietze extension theorem (or more geometrically, from obstruction theory, if you triangulate $s\Delta^n$ such that each of the faces are subcomplexes).

These maps $r_n$ will induce a map of chain complexes $r^*:C_*(X)\to sC_*(X)$ where $C_*(X)$ is the ordinary singular chain complex and $sC_*(X)$ is the singular chain complex using $s\Delta^n$ instead of $\Delta^n$.  There is also a map $i^*:sC_*(X)\to C_*(X)$ given simply by restricting from $s\Delta^n$ to $\Delta^n$, and $i^*r^*=1$.  To prove that $i^*$ induces isomorphisms on homology, it thus suffices to show that $r^*i^*:sC_*(X)\to sC_*(X)$ is chain-homotopic to the identity.

To construct the chain homotopy, we just extend the $r_n$'s to a sort of deformation retraction.  Specifically, let $P^n$ be the space obtained by gluing together $n$ copies of $s\Delta^n$ the same way that $n$ copies of $\Delta^n$ are glued together to form the standard triangulation of $\Delta^n\times[0,1]$.  In particular, $P^n$ has two "start and end" faces which correspond to the faces $\Delta^n\times\{0\}$ and $\Delta^n \times\{1\}$ of $\Delta^n\times[0,1]$, and "side" copies of $P^{n-1}$ which correspond to $F\times[0,1]$ for each face $F$ of $\Delta^n$.  We can now construct a sequence of maps $h_n:P^{n+1}\to s\Delta^n$ such that $h_n$ is given by $h_{n-1}$ on each side face (mapping to the corresponding face of $s\Delta^n$), is given by the identity on the bottom face, and is given by $r_n$ on the top face.  Indeed, given $h_i$ for each $i<n$, the existence of $h_n$ with the required properties follows from the Tietze extension theorem.

These maps $h_n$ then induce maps $h_n^*:sC_n(X)\to sC_{n+1}(X)$, sending each simplex to the alternating sum of the $n+1$ simplices of $P^{n+1}$ which are mapped into $X$ by composing with $h_n$.  Since $h_n$ is given by $h_{n-1}$ on the side faces, these maps $h_n^*$ will define a chain homotopy between what the $h_n$'s do on the bottom and top faces, i.e. between the identity and $r^*i^*$.

More generally, similar arguments show that if you replace the simplices $\Delta^n$ with any sufficiently nice levelwise contractible cosimplicial space, the homology you get will be naturally isomorphic to singular homology (or more strongly, the "singular set" you get by mapping out of your cosimplicial space will be naturally weak equivalent to the usual singular set).  Here "sufficiently nice" turns out to mean "Reedy cofibrant"; more generally, if I'm not mistaken, then the following is true:

  Let $C$ be a model category and $A$ be a fibrant object in $C$.  Define $h_A:C^{\Delta}\to(\mathtt{Set}^{\Delta^{op}})^{op}$ by $h_A(X)_n=\operatorname{Hom}(X_n,A)$.  Then $h_A$ is a left Quillen functor for the Reedy model structure on $C^{\Delta}$, and in particular it preserves weak equivalences between Reedy cofibrant objects.

In other words, working very generally in a model category, you could define a "singular homology" theory using maps out of a cosimplicial object, and then the singular homology theories given by weak equivalent Reedy cofibrant cosimplicial objects agree on fibrant objects.

Your question is answered by looking for places where compactness of $\Delta^n$ is applied in singular homology theory. For example, the proof of the excision theorem uses compactness of $\Delta^n$ to guarantee that a certain interated barycentric subdivision operation stops after finitely many steps.

Your affine space $s\Delta^n$ is not compact, so this kind of finiteness argument wouldn't work. In fact, its not at all clear to me how you would even define the barycentric subdivision of $s\Delta^n$.


Possibilities for changing one $1024$ banknote to banknotes from $\{2^i: i = 0,\ldots,9 \} $ How many possibilities do there exist to change one banknote $1024$ to denominations from the set set $\left\{2^i: i = 0,...,9 \right\} $.

I think that there really are a lot, but I don't have any idea on how to calculate it. I will be grateful for any help and hints.

I present a modest contribution. Suppose we treat the problem of decomposing $2^n$ into sums of powers of two excluding the trivial solution $2^n=2^n.$ This can be solved by dynamic programming, here is the algorithm.

#! /usr/bin/perl -w
#

my %memo;

sub change {
    my ($val, $mxpow) = @_;

    my $key = "$val-$mxpow";
    return $memo{$key} if exists $memo{$key};

    my $res = 0;
    my $inc = 2 ** $mxpow;

    if($mxpow>0){
      my $s = 0;
      while($s <= $val){
          $res += change($val-$s, $mxpow-1);
          $s += $inc;
      }
    }
    else{
      $res = 1;
    }

    $memo{$key} = $res;
    return $res;
}

MAIN: {
    my $max = shift || 10;

    my @res;
    for(my $n=1; $n<=$max; $n++){
      push @res, change(2**$n, $n-1);
    }

    print join(', ', @res) . "\n";
}

This algorithm will produce the following sequence:
$$1, 3, 9, 35, 201, 1827, 27337, 692003, 30251721, \\2320518947, 316359580361, 77477180493603,\ldots $$
which is A125792 from the OEIS. You may consult this link for additional references about this problem, including a recurrence for the terms of the sequence.

In particular we have that the count for $2^{10}$ ($n=10$) is
$$2320518947.$$

Let $N(x)$ return the number of ways to write $2^x$ as an ordered sum of powers of two less than or equal to $2^{x-1}$.

If there are $n$ ways to write $2^k$ as the ordered sum of powers of two less than or equal to  $2^{k-1}$, then how many ways are there to write $2^{k+1}$ as the ordered sum of powers of two less than or equal to $2^k$? In other words, if $N(k)=n$, what is $N(k+1)$?

Since $2^{k+1} = 2^k + 2^k$, each of the $2^k$-sized halves can be written as ordered sums in $n + 1$ ways ($n$ from powers less than or equal to $2^{k-1}$, plus the $1$ way that is just $2^k$). Thus, $N(k+1) = (n+1)^2$.

$$N(k+1) = \left(N(k)+1\right)^2$$

Find $N(1)$. Then you should be able to find $N(10)$ by recursively applying the identity above.


Prove that $\sum_{n=1}^\infty\mu(n)z^{\mu(n)n}$ has an essential singularity at the origin, where $\mu(n)$ is the Möbius function Let $\mu(n)$ the Möbius function, see in this MathWorld's article the definition, and $z$ the complex variable. I know how state, but not rigurously, that $$f(z)=\sum_{n=1}^\infty\mu(n)z^{\mu(n)n}\tag{1}$$ has an essential singularity at $z=0$.

  Question. Please state a rigurous proof that the function $f$ has an essential singularity at the origin $z=0$. Many thanks.

For a little radius, let $\delta>0$ $D'(0,\delta)$ the punctured disk around the origin, I know the statement of big Picard theorem, if you can add hints to know, if it is feasible, if $f\left(D'(0,\delta)\right)$ is or well the complex plane $\mathbb{C}$, or well $\mathbb{C}\setminus \left\{ \text{a point} \right\}$, then add remarks as companion of the Question. Because I don't know what of these two distinct cases holds, I am asking to determine $f\left(D'(0,\delta)\right)$.

Actually, your series diverges for every complex $z$. This is a Laurent series (in slight disguise)
$$
\sum_{n=-\infty}^\infty a_n z^n,
$$
where $a_n \in \{ 0, \pm 1 \}$
and you can compute the annulus of convergence $r < |z| < R$ by:
$$
r = \limsup_{n\to\infty} |a_{-n}|^{1/n} = 1
$$
and
$$
1/R = \limsup_{n\to\infty} |a_n|^{1/n} = 1.
$$
This shows that the series doesn't converge anywhere except possibly on the unit circle, but there the terms don't tend to $0$, so we get divergence for $|z|=1$ as well.

We have $\mu(\mathbb N) = \{-1,0,1\}$

If $\mu(n)=0$, then $\mu(n)z^{\mu(n)n}=0$,

if $\mu(n)=1$, then $\mu(n)z^{\mu(n)n}=z^n$

and

if $\mu(n)=-1$, then $\mu(n)z^{\mu(n)n}=-z^{-n}$.

Hence $f$ has an essential singularity at $z=0$ iff $\mu(n)=-1$ for infinitely many $n$.

Its your turn to show that $\mu(n)=-1$ for infinitely many $n$.


Does interval spacing effect Hausdorff dimension of Cantor set? Let $C=\bigcap_{j=0}^{2^n}C_j$, $C_0=[0,1]$, and the intervals in the construction of each stage of $C_j$ consists of removing the center 1/3 from the $j-1$ stage intervals.  In other words, the Cantor middle third set.  The dimension of this set is known to be $\frac{\log 2}{\log 3}$.  Now consider the following adjustment: we now only require allow the spacing between the intervals at each stage, $j$, to be disjoint. That is, we only require spacing between intervals to be >0. It is clear to me, from the definition of Hausdorff dimension that interval spacing should not affect an upper bound calculation on a Cantor Set.

My question is this: Can changing the nonnegative spacing between intervals cause the lower bound calculation to diverge from the upper bound calculation in the context of Cantor sets? For sets in general? If yes for the Cantor sets, can someone direct me to a lower bound technique that explicitly incorporates spacing. If yes only for sets in general, what about Cantor sets makes spacing irrelavant?

I regret having to note that the other answer is wrong. It is well known, since work of Moran in 1946, that the Hausdorff dimension of the particular set that you describe does not depend on the location of the intervals at each step. For a proof you can see the book Dimension and Recurrence in Hyperbolic Dynamics, by Barreira (see Theorem 3.1.1).

Update: see the other answer

You will not be able to get the same lower bound, and for a good reason. Reduced spacing between the remaining 1/3-intervals can make the Hausdorff dimension of the Cantor-type set arbitrarily small. Intuitively, this is because when the intervals are placed nearby, they can be covered more efficiently. Here is a more precise argument.

Fix $s>0$; I will build a Cantor-type set of $s$-dimensional Hausdorff measure zero. To do this, I will arrange to  have a sequence of scales $\delta_j\to 0$ such that generation $m_j$ of the construction can be covered by $N_j$ intervals of size $\delta_j$, with $N_j \delta_j^s\le 1/j$.

For $j=1$ I can take $\delta_1=N_1=1$, which cover the $0$th generation $(m_j=0)$ of the Cantor-type set, namely $[0,1]$. Suppose now that $N_j$, $\delta_j$, $m_j$ are already arranged.

I have $2^{m_j}$ intervals in the $m_j$-generation. Let $N_{j+1}=2^{m_j}$ and choose $\delta_{j+1}$ so that  $N_{j+1} \delta_{j+1}^s\le 1/(j+1)$.

For each of the aforementioned $2^{m_j}$ intervals, repeat the process of replacing the interval by two intervals of $1/3$ its length and leaving only a tiny gap between them: after sufficiently many such steps the resulting set will be contained in $\frac12\delta_{j+1}$-neighborhood of the midpoint of the original interval. At this moment I have generation $m_{j+1}$ of the Cantor-type set, which is covered by $N_{j+1}$ intervals of length $\delta_{j+1}$, as desired.


Can $A + uv^T$ be non-singular if A(order n) has rank n-1 Suppose $A$ is a matrix of order $n$ with rank n-1, $u$ and $v$ are $n$-vectors. Can $A + uv^T$ be nonsingular, if yes then find such $u$ and $v$.

First I wrote Rank$(A + uv^T) <=$ Rank$(A)$ + Rank$(uv^T)$

Then  I wrote $n-1 <=$ Rank$(A + uv^T) <= n$ (which I am not sure of)

Then tried to take $v$ in the kernel of $A$ but to no avail. How to approach?

Trivially, yes: take u=(1,0,0..,0)(column vector), v=(1,0,0...,0) and A to be the matrix that has 1 everywhere on the diagonal except at (1,1) (and 0 everywhere else). Then $A + uv^T= I$.

Adding in my comment, for the (not so trivial)case of an arbitrary fixed matrix A of rank (n-1):

$A$ is of rank (n-1) => there are invertible matrices(corresponding to elementary transforms) X,Y such that $A=XI_{n−1}Y$ where by $I_{n−1}$ I denoted the matrix with 1 on the main diagonal everywhere except at position (1,1). But now choose $u=Xu, v=Y^Tv$, where u,v are the columns I defined above in my answer and then you get that $A+uv^T=X(I_{n−1}+uv^T)Y=XY $ is invertible

If either u or v are in the row space or column space of A respectively then A + uv’ will remain singular.  So if A = ab’  with a and b vectors (A is rank one) and say v=const * b then A + uv’ will remain a rank one matrix.


proving that a function is $\alpha$-Holder Prove that the function $ f(x)=\sqrt{x}$ , is $\alpha$-Holder, with $0<\alpha\le \frac{1}{2} $ , on the set $[0,\infty)$

i.e there exist a constant $K$, such that $|\sqrt{x}-\sqrt{y}| \leqslant K|x-y|^{\alpha} $ for every $x,y \in [0,\infty)$.

It's not true for $\alpha < \frac{1}{2}$. Fix $y = 1$ and see that if $x \geq 1$, $$\frac{\sqrt{x} - 1}{(x-1)^\alpha} \sim x^{\frac{1}{2} - \alpha} \rightarrow \infty.$$

Assuming $x,y\in[0,+\infty)$, with $x\not=y$, then $|\sqrt{x}-\sqrt{y}|=\Big|\frac{|x-y|}{\sqrt{x}+\sqrt{y}}\Big|\leq\frac{\sqrt{|x|+|y|}}{\sqrt{x}+\sqrt{y}}|x-y|^{1/2}\leq \frac{\sqrt{x}+\sqrt{y}}{\sqrt{x}+\sqrt{y}}|x-y|^{1/2}=|x-y|^{1/2}.$
Thus the mapping $x\mapsto \sqrt{x} $ is H\"{o}lder continuous of order $1/2$ on interval $[0,+\infty)$.


Permutations/Combinations: How many different passwords are possible? Hello everyone. I have a couple questions this time, but I think if I understand how to do this one, I'll understand the others.

A particular online banking system uses the following rules for its passwords:
a.  Passwords must be 6-8 characters in length
b.  Passwords must use only alphabetical and numeric characters, and must have at least one alpha and one numeric character.
c.  Letters are case sensitive.Under these rules, how many different passwords are possible?

Count the number of legal passwords of length $6$, $7$, $8$ separately, and then add up.

We do the length $7$ case.

If we are using the standard alphabet, there are $26$ lower case characters, $26$ upper case characters, and $10$ digits, for a total of $62$.

There are $62^7$ words of length $7$ made up by choosing symbols from our $62$-element symbol set.

This is because the first symbol of the word can be chosen in $62$ ways, and for each of these ways the second symbol can be chosen in $62$ ways, and so on.

However, some of these words are forbidden. We count the forbidden words.

There are $52^7$ "all-letter" words. There are $10^7$ "all-digit" words. So there are $52^7+10^7$ forbidden passwords of length $7$. This leaves $62^7 -52^7-10^7$ allowed passwords of length $7$.

Permutation formula for ordered with repetition is n^r where n is the number of things to choose from and r is how many we are choosing to form another set.
Total possible permutations is 62^8
However the rules state one numeric and one alpha must be used.
The largest legal set considering all rules is 52^7 + 10^1.
This is where 7 characters chosen are alpha and 1 character is numeric. The general formula to consider for this problem takes in to consideration sets to be used and the positions and order used.
n1^r1 + n2^r2
where n1 is the number of the first set of characters to used and r1 is the number of positions those characters can be used in. The second term and any subsequent terms used are for how many items are in the that set n2 and how many positions it can occupy r2


Counting the number of Eulerian trails in a connected, directed graph I can't find anything about this online, and I'm beginning to suspect it's a hard problem. I know that counting the number of circuits is #P-complete, but I don't need the number of circuits; I need the number of trails. My current "solution" is to simply walk the graph, find every path, and count them.

Important notes:

The graph is directed.
The graph is connected.
The graph has at most two vertices with different in- and out-degrees.
I'm looking for trails, including but not limited to circuits.

Any information on this, including upper limits, computational complexity, algorithms, etc., would be helpful.

Not enough reputation to leave a comment, but according to Wikipedia,

  The number of Eulerian circuits in digraphs can be calculated using the so-called BEST theorem, named after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted arborescences. The latter can be computed as a determinant, by the matrix tree theorem, giving a polynomial time algorithm.

It is the undirected case which is #P-complete. This doesn't answer the question in the BEST algorithm doesn't directly compute Eulerian trails, but as you said, the two problems are closely related: take your favorite graph with any Eulerian trails (which is an easy check), add an extra vertex adjacent to the odd-degree vertices (if any), and calculate the number of Eulerian circuits.

I'm not sure why I didn't realize this before, but perhaps this will help someone with my same misunderstanding: being able to count Eulerian trails for arbitrary directed, connected graphs would imply being able to count Eulerian circuits for arbitrary directed, connected graphs, which would imply $P=NP$, societies would crumble, and anarchy would reign. (Maybe I'm being a bit hyperbolic but you get the idea.)


Getting the highest product from n terms In other words, you're looking for a partition a+b+c+d of a given quantity x such that the product abcd of the nonzero parts is maximum. Is this interpretation right?

I don't know how to phrase the title of the question because I don't know what I'm actually looking for. Here's the problem (and no it's not homework, it's just something I had to calculate and had no idea how to do it):

I have a set of positive numbers: a, b, c and d. The sum of the variables has to be a fixed value, let's call it x. Let's call the product of a*b*c*d=y

Now I want to find out the distribution of x between the variables a,b,c,d such that the product of a*b*c*d is the highest.

For a concrete example:
x=20, so I want to know at what values of a,b,c,d does y have the highest value?

From what I manually calculated, it seems that 5*5*5*5=625 is the highest I could get. I would like to know if this is true. Also I would like to know the formal name of what I'm describing here.

Suppose we place all the parts ($a_1+a_2+\cdots+a_n=x$) into the AM–GM inequality:
$$(a_1a_2\cdots a_n)^{1/n}\le\frac{a_1+a_2+\cdots+a_n}n$$
The right-hand side is fixed; it is equal to $\frac xn$. We also know that the inequality becomes an equality iff all $a_i$ are equal. Therefore the partition of $x$ that gives the highest product is the one whose parts are all equal to $\frac xn$, and the product is $(x/n)^n$.

In this case there are four parts, and thus the solution is $a=b=c=d=\frac x4$.

OK, here's a geometric solution. I'll explain it for three numbers $a,b,c,$ which may be easily generalised. The condition is the segment of a plane in the first octant. Indeed, it is an equilateral triangle cutting off equal lengths $k$ on each of the axes to get a tetrahedron with the vertex at the origin. The problem is to find the maximum volume $abc$ of the box one of whose vertices $(a,b,c)$ is always on the triangle defined by the condition. Clearly the biggest such box has the vertex touching the triangle at its centre (this may be seen by considering the two-dimensional case as well). This occurs when $a=b=c=k/3,$ which then gives $k^3/27$ as the maximum such product.

For four variables, we find the maximum to be $k^4/256,$ and for $n$ variables we get $k^n/n^n.$ Thus for the particular value $k=20$ which you picked the maximum product is given by the partition $5+5+5+5,$ which gives the product $5^4=625.$


Am I in the right track? Varying annuity interest You are given:

  (i) $X$ is the current value at time 2 of a 20-year annuity-due of 1 per annum.

  (ii) The annual effective interest rate for year $t$ is $\dfrac{1}{8+t}$.

  Find $X$

Here is what I did, since $X$ is the current value at time 2, (denote PV-present value)

  $X = PV(t=0)(1+i_i)(1+i_2)$

Hence I need to find the $PV(t=0)$ first. But finding the $PV$ is a bit of a task, and I don't know if I'm going in the right direction. Since we have an annuity-due

  $PV(t=0) = 1 + (1+i_1)^{-1} + (1+i_1)^{-1}(1+i_2)^{-1}+\cdot\cdot\cdot+(1+i_1)^{-1}\cdot\cdot\cdot(1+i_9)$

  $= 1+(1+\dfrac{1}{9})^{-1}+(1+\dfrac{1}{9})^{-1}(1+\dfrac{1}{10})^{-1}+\cdot\cdot\cdot+(1+\dfrac{1}{9})^{-1}\cdot\cdot\cdot(1+\dfrac{1}{17})^{-1}$

Is this right?

You can ignore the past other than to set the parameters. $X$ is just the PV of the remaining 18 annuity payments. Thus

$X=1+(1+\frac{1}{11})^{-1} + (1+\frac{1}{11})^{-1}(1+\frac{1}{12})^{-1} + \cdots +(1+\frac{1}{11})^{-1}(1+\frac{1}{12})^{-1}\cdots(1+\frac{1}{27})^{-1}$

This can be simplified.

EDIT: I blew it, but leaving my mistake up because that's how we learn.
As @alexjo shows I forgot the definition of current value.
I need to add in $X_{<2}$, the accumulated value of prior payments.
But I think alexjo erred in the value of:
$\begin {align} X_{<2} &= (1+\frac{1}{9})(1+\frac{1}{10})+(1+\frac{1}{10})\\
\text {adding it to my original answer we get:}\\
 \text {corrected } X &= X_{<2} + \text { original }X\\
&=11\bigl(\frac {1}{9}+\frac {1}{10}+\frac {1}{11} + \cdots + \frac {1}{28}\bigr) \end {align}$


Number of ways to label die with opposing faces summing to 7 A friend and I have a disagreement about the number of unique ways to label the faces of a six-sided die with integers from one to six so that each pair of opposing faces sums to seven.

I think the answer is 8 since swapping each pair of opposing faces results in (I think) a different handedness for the two hemi cubes centered on the two faces being swapped, without affecting the other hemi cubes. So I think the problem is represented by the possible independent states of the three opposing pairs, giving $2^3=8$ permutations.

My friend thinks the answer is 2, as he argues that a single swap changes the handedness of the entire die, and that further independent swaps can’t further change the die’s handedness, and thus don’t generate unique states.

Who is right? (Or is neither of us right?)

Note that the faces with labels 1, 2, and 3 must appear in a 3-cycle (share a corner), and labeling these three faces uniquely determines the labels of the other three faces.  There are two ways to do that.

48 ! :-)
(special case)

  A friend and I have a disagreement about the number of unique ways to label the faces of a six-sided die with integers from one to six so that each pair of opposing faces sums to seven.

It is clear from both your initial disagreement and comments and answers here that the question is somewhat ambiguous - the meaning of "unique ways" needs refining. eg does 'handedness' matter, or .... .

So, based on what's been said since, while it's clearly not what you originally intended, here is an interpretation that seems valid (to me :-) ) that yields the result 48!
This is based on the assumption that the unnumbered die is NOT rotation agnostic but itself has uniquely identifiable faces apart from the numbering. While that's not how die are usually made, it's a valid (I think) variation on the original question.

Imagine a cube with faces inlaid with 6 different semi-precious stones. (It could equally well have 6 different colours but Semi precious stones seems more interesting.) If you have multiple copies of a standard die with colours assigned in the alignment specified below, and then assign valid numbers to faces and produce a set of varying dice, how many unique dice can you create?

Assume a standard SPS die, with say topaz up, chalcedony down, beryl left, jasper right,  carnelian front and amethyst back. If we decide this is going to bend the brain we can resort to calling the sides Up, Down, Left, Right, Front, Back - or even U D L R F B.

Start with Up / Topaz.
We have 6 numbers to choose from.
Assigning any number also sets the number of Down/Chalcedony to make the opposing faces sum to 7.

Now assign a number to say Left / Beryl
We have 4 choices - and this also sets the value of Right / Jasper.

That leaves 2 choices for Front / Carmelian
and sets Back / Amethyst accordingly.

Total unique die are 6 x 4 x 2 = 48.

But wait, there's more!
Maybe.

Here's an arguably* new question arising which I may propose as such.
But, it's worth outlining here.
*"Arguably" as this too seems to be a legitimate interpretation of the original question.
Just as I randomly assigned numbers to face-pairs, I could assign stone types to faces. But as there is no sum-to-7 constraint there are 6! assignable patterns.
However, many of these are non unique if the unnumbered cube is rotated.
How many unique numbered cubes can we make if the cubes can be assigned stones to faces randomly before numbering?

________________________________

The special collectors edition

uses a Sapphire, Emerald, Sardonyx, Chrysolite, Chrysoprase & Jacinth die.

Bonus question -  where did I get my two stones lists from?


Limit, solution in unusual way I have a problem with solution of this limit:
$$\lim_{x\to 0}{\frac{\tan{x}-x}{x^2}}$$
Of course, it's a very easy to solve, using (twice) L'Hôpital's rule, but I need to find out, how to do this without this rule.

I stuck in this point:
$$\lim_{x\to 0}{\frac{\frac{\sin^2{x}}{x^2}\cdot\frac{1}{\cos^2{x}} - 1}{2x}}$$
Everything I need to know is how to eliminate $\frac{\sin^2{x}}{x^2}$, because - as my tutor said - I can't simply substitute $1$ for this expression.

Thanks for help.

PS: It's not a homework. My tutor showed this problem as a puzzle and said, that it would be a good exercise to solve this without L'Hôpital's rule.

EDIT: Here is a way I got to the point $\lim_{x\to 0}{\frac{\frac{\sin^2{x}}{x^2}\cdot\frac{1}{\cos^2{x}} - 1}{2x}}$:

\begin{align*}
\lim_{x->0}{\frac{\tan{x}-x}{x^2}} &= \lim_{x->0}{\frac{(\frac{\sin{x}}{\sqrt{1-\sin^2{x}}}-x)\cdot (\frac{\sin{x}}{\sqrt{1-\sin^2{x}}}+x)}{x^2(\frac{\sin{x}}{\sqrt{1-\sin^2{x}}}+x)}}\\
 &= \lim_{x->0}{\frac{\frac{\sin^2{x}}{x^2\cos^2{x}}-1}{x(\frac{\sin{x}}{x}\frac{1}{\cos{x}}+1)}}= \lim_{x\to 0}{\frac{\frac{\sin^2{x}}{x^2}\cdot\frac{1}{\cos^2{x}} - 1}{2x}}
\end{align*}

Here is an attempt at a geometric proof.

(Figure thanks to J.M)

Consider $\triangle ABC$ such that $\angle{BCA} = x$. Let $BC=1$ and so $AB = \tan x$.

Let $BE$ be the arc of radius 1 and angle $x$ drawn with $C$ as the center (note that $E$ is on AC, between $A$ and $D$ and is kind of hidden in the brown region). Note that $CE = 1$.

Now the area of the gray region is $\dfrac{\tan x}{2} - \dfrac{x}{2}$ (area of $\triangle ABC$ - area of the sector $CBE$).

Let $D$ be the perpendicular on the hypotenuse $AC$ from $B$. It can be seen that $CD = \cos x$ and thus distance from $D$ to $C$ is less than distance from $E$ to $C$ (which is $1$).

Thus the area of the gray region is less than the area of $\triangle BAD$ (gray + brown).

Now $AD = \dfrac{\sin^2 x}{\cos x}$ and thus we have that

$$ 0 < \dfrac{\tan x - x}{2} \lt \dfrac{\sin^3 x}{2\cos x}$$

And so

$$ 0 < \dfrac{\tan x - x}{2x^2} \lt \dfrac{\sin^3 x}{2x^2 \cos x}$$

Since we know that $\lim_{x \to 0+} \dfrac{\sin x}{x} = 1$, and that $\dfrac{\tan x - x}{x^2}$ is an odd function, that the limit is $0$, follows.

Previous answer, which was a feeble attempt at being pedantic:

For a way to find the limit without using more advanced concepts like McLaurin series etc...

Consider

$$\dfrac{\tan(2x) - 2x}{(2x)^2} = \dfrac{ \frac{2\tan x}{1-\tan^2 x} - 2x}{4x^2}$$

$$ = \dfrac{(2\tan x - 2x) + 2x \tan^2 x}{4x^2(1 - \tan^2 x)} = (\dfrac{\tan x - x}{2x^2} +  \dfrac{x\tan^2 x}{2x^2}) \dfrac{1}{1-\tan^2 x}$$

Therefore, taking limits as $\displaystyle x \to 0$

$$ L = (\dfrac{L}{2} + 0)\dfrac{1}{1-0}$$

Thus

$$L = 0$$

There is one problem with the above, though. Can you tell what that is?

(Or rather more simply, replace $\displaystyle x$ with $\displaystyle -x$)

$lim_{x \to 0}  \frac{tan(x)−x}{x*x}$ (0/0 Form)

$lim_{x \to 0} \frac{sec(x) * sec(x) -1}{2x}$  (0/0) Form $\frac{d(Numerator)}{d(Denominator)}$

$lim_{x \to 0} \frac{2secx * sec(x) *tan(x)}{2} = sec0 * sec0 *tan0 =1 * 1 * 0 =0$

Ans is 0.


If $f: A \rightarrow B$ and $g: B \rightarrow C$, is $(g \circ f)^{-1}(C) = f^{-1}(B)$? Let $f: A \rightarrow B$ and $g: B \rightarrow C$. I have a question that is asking me to come up with and prove some theorems about the images and inverse images of sets under $g \circ f$. This is a theorem and proof that I have so far (sorry, I'm not great at writing proofs):

Theorem: Suppose $f: A \rightarrow B$ and $g: B \rightarrow C$. Then $(g \circ f)^{-1}(C) = f^{-1}(B)$.

$(\subseteq)$ Suppose $x \in (g \circ f)^{-1}(C)$. This implies that $x \in A$. Since $x \in A$ and $f: A \rightarrow B$ is a function, then $f(x) \in B$. Thus, since $x \in A$ and $f(x) \in B$, it follows that $x \in f^{-1}(B)$.

$(\supseteq)$ Suppose $x \in f^{-1}(B)$. This implies that $x \in A$ and $f(x) \in B$. Since $f(x) \in B$ and $g: B \rightarrow C$ is a function, then $g(f(x)) \in C$. Thus, since $x \in A$ and $g(f(x))=(g \circ f)(x) \in C$, it follows that $x \in (g \circ f)^{-1}(C)$.

Is this a valid theorem and proof, or is this not always true? I'm having trouble trying to come up with a counterexample.

Your proof is valid. However, it would be easier to prove that if $h : X \to Y$ is any function then $h^{-1}(Y) = X$. It then follows that $(g \circ f)^{-1}(C) = f^{-1}(B)$ simply because $g \circ f$ and $f$ have the same domain!

Provided that $f,g$ are both $1-1$ and unto, you can also work this out by first showing that $$(g \circ f)^{-1}(x)=f^{-1}\circ g^{-1}(x).$$
Then it follows that $$(g\circ f)^{-1}(C)=f^{-1}(g^{-1}(C))=f^{-1}(B) $$


How many possible outcomes are there when 5 similar dices are rolled? In this question If I consider first total no of outcomes as $6^5$ , then I divided it be ${6\choose5} *5!$ since there are 5 similar dices so the outcome (1 2  3 4 5 ) will be similar to (5 4 3 2 1) .

Now what's wrong with this approach ?

The answer is $6 + 5 - 1 \choose 5$. The reason is, to exclude re-counting equivalent outcomes, we look at the number of dices that land on $1, 2, 3, 4, 5, 6$. Now, there are $6$ possibilities. There are $5$ dices. Initially, you might think "Aha! The answer is just $6 \choose 5$." But it's a little more complicated than that. Because two dices could land on the same number. So we use the well known, tried and tested, stars and bars method see stars and bars to count allowing for these conincidences, and the answer is as above.

My explanation is that the probability of 1 set of the same value is 1/(number of possible combinations) simply. We are talking about 5 dice with six possible values so the calculation would be 1/(6^5).
In more detail, there are 6 combinations for 1 dice and there are 5 dice so you times the 6 combos by itself 5 times to get to the total combinations possible in the set.
6^5=7776 so the answer is 1/7776.
To calculate the probability from a certain number of throws  add the probabilities of separate throws. Let’s say there is one combination (1, 1, 1, 1, 1). We already know that the probability of getting this is 1/7776, but what about in two throws?
In two throws getting 5 of a kind (for example: 1, 1, 1, 1, 1) you can think of two sets of combinations which give the value of one single combination (for example: 1,1 and 1,1,1). The probability of each part added will give the total and you will find that for this particular example it is 1/250 because it is 1/((6^2)+(6^3)).
However, for the second possible case (1, and 1,1,1,1) the probability is lower because increasing powers don’t follow a sequence and four 1s in one throw has a much lower probability than 1,1,1. This case has a probability of 1/1302.


Is this graph connected Define the following graph on the vertex set ${\mathbb N}_{\geq1}\>$:

Two numbers $a$, $b\in {\mathbb N}_{\geq1}$ are connected by an edge (written  $a \ \mathcal{R} \ b)$ if and only if $a+b \ | \ ab-1$.

Clearly $1$ is isolated. Can we connect all integers greater than $2$ to $2$?
For example: $$2014 \ \mathcal{R} \ 147 \ \mathcal{R} \ 4175 \ \mathcal{R} \ 3891 \ \mathcal{R} \ 142 \ \mathcal{R} \ 43 \ \mathcal{R} \ 7 \ \mathcal{R} \ 3 \ \mathcal{R} \ 2.$$ Therefore $2014$ can be connected to $2$ (written $2014\sim2$).

  Question: Is this graph connected?

Motivation :

I worked on the Machin formula and I wondered if we had $$\arctan \frac{1}{a} + \arctan \frac{1}{b} = \arctan \frac{1}{c}$$ where $a,b,c$ are integers and this happens if  $c=\frac{ab-1}{a+b}$ is an integer.

EDIT : My apologie I forgot to mention that the graph is restricted to positive integer.

A partial answer :

We have $a \sim b$ if and only if there exist a sequence of integers $a_1, \ldots, a_n$ such that  $a \ \mathcal{R} \ a_1 \ \mathcal{R} \ \cdots \ \mathcal{R} \ a_n \ \mathcal{R} \ b$. The relation $ ab-1 = c (a + b) $ can be written as $(a-c)(b-c)=c^2+1$ and can be solves $a=c+d$ and $b=c+ \dfrac{c ^ 2 + 1} d$ where d is a divisor of $c^ 2 +1$.

If $c$ is even: All divisors of $c^2+1$ are congruent to $1$ modulo $4$ then $a$ is congruent to $b$ modulo $4$.

If $c$ is odd: $d$ is congruent to $1$ modulo $4$ and $\dfrac{c^2}d+1$ is congruent to $2$ modulo 4 or vice versa.
If $c=4k+1$ then $a$ is congruent to $2$ modulo $4$ and $b$ is congruent to $3$ modulo $4$ or vice versa.
If $c = 4k +3$ then $a$ is congruent to $0$ modulo $4$ and $b$ to $1$ modulo $4$ or vice versa.

Therefore there is probably three components in the graph (but I did not prove this):

The first formed only by $1$, the second one formed by integer congruent to $0$ modulo $4$ or $1$, and the last by integer congruent to $2$ or $3$ modulo $4$.

If you told me to find for a given set. $c$ - integer of any sign.

Then for the equation.  $$\frac{ab-1}{a+b}=c$$

using factorization. In the following manner.

$$(k-n)(k+n)=4(c^2+1)$$

Then the solutions are.

$$a=c+\frac{k+n}{2}$$

$$b=c+\frac{k-n}{2}$$

$$.........$$

$$a=c-\frac{k+n}{2}$$

$$b=c-\frac{k-n}{2}$$


Could I be using proof by contradiction too much? Lately, I've developed a habit of proving almost everything by contradiction. Even for theorems for which direct proofs are the clear choice, I'd just start by writing "Assume not" then prove it directly, thereby reaching a "contradiction." Is this a bad habit?  I don't know why, but there's something incredibly satisfying about proof by contradiction.

One general reason to avoid proof by contradiction is the following. When you prove something by contradiction, all you learn is that the statement you wanted to prove is true. When you prove something directly, you learn every intermediate implication you had to prove along the way.

More explicitly, if you want to prove that $p \Rightarrow q$ by contradiction, you assume $p$ and $\neg q$ and derive a contradiction. None of the intermediate implications along the way can be reused because your premises were contradictory.

If you want to prove that $p \Rightarrow q$ directly, say by proving that $p \Rightarrow p_1$ and $p_1 \Rightarrow p_2$ and so on until $p_n \Rightarrow q$, then you've also proven that $p_i \Rightarrow p_{i+1}$ for all of the relevant $i$. Many of these statements might be more useful than the original statement you were trying to prove.

Another general reason to avoid a proof by contradiction is that it is often not explicit. For example, if you want to prove that something exists by contradiction, you can show that the assumption that it doesn't exist leads to a contradiction. But this doesn't necessarily give you a method for constructing the actual thing, which you might learn more from trying to do.

A third reason is that frequently, or so it seems to me, a proof by contradiction is really a proof by contrapositive, where you assume $\neg q$ and derive $\neg p$. This feels like a proof by contradiction except that you never make use of the hypothesis $p$ except at the very end, and pretending that these are proofs by contradiction will make you blind to the fact that any intermediate implications you prove in a proof by contrapositive are still valid.

As @azimut says, as long as the reasoning holds, proving by contradiction is fine. However, it is a good idea to develop your proof skills by trying to prove results using other methods, as sometimes contradiction will make the proof more complicated than need be. Other methods can be more elegant and/or more clear. Also, when first learning proof techniques, it is easy to think that something has been proved by contradiction when it really has not. I have seen students get confused by what is being contradicted and even what the contradiction is, so as long as you're proving things by contradiction, be careful to check that it's really a proof: check that the right thing is being contradicted, that what you've done is legal, and that the conclusion you've come to is a contradiction.


if a particle moves at time t $-\pi<t<\pi$ which is given by x(t)=sin(3t) and y(t)=2t, how do i find total distance traveled? If a particle moves at time t $-\pi<t<\pi$ which is given by x(t)=sin(3t) and y(t)=2t, how do i find the total distance traveled?

While I can find the displacement using pythag theorem, I need to find the total distance. If it was x'(t) and y'(t) i could integrate to find total distance but in this case it just gives me the total distance. Any ideas?

In general, the length of this curve is given by
$\int_{-\pi}^{\pi} \sqrt{(x')^{2}+(y')^{2}}dt$, which in this case leads to
$$\int_{-\pi}^{\pi} \sqrt{(x')^{2}+(y')^{2}}dt = \int_{-\pi}^{\pi} \sqrt{(-3\cos(3t))^{2}+(2)^{2}}dt = \int_{-\pi}^{\pi} \sqrt{9\cos^{2}(3t)+4}dt.$$ I don't know if you need this precise answer or a rounded value, which any computer could easily do.

Just to explain both my comment and Kavi Rama Murthy's,

The distance is equal to the arc length of the curve. I hope you can see this. Just sketch out any arbitrary curve and pretend that it's a particle (or a bumblebee!) moving around on the Cartesian plane. The arc length of the curve is the distance travelled by the particle.

The arc length is given by $\displaystyle \int ds = \int \sqrt{dx^2 + dy^2}$

Here $dx = 3\cos 3t dt$ and $dy = 2dt$, so the arc length is $\displaystyle \int_{-\pi}^{\pi}\sqrt{9\cos^2 3t + 4}dt$, where the appropriate bounds have been imposed in the last step.

The problem now is evaluating this integral. The indefinite integral has no elementary form and involves elliptic integrals. Sometimes, a definite integral can be calculated "neatly" and "cleverly" with symmetry and appropriate substitutions if the bounds are just right, but I can't see a way to do so here (and neither can Wolfram Alpha). In any case, the answer is here:

https://www.wolframalpha.com/input/?i=integrate+sqrt(9cos%5E2(3x)+%2B+4)+from+-pi+to+pi


Why a false statement can imply anything? According to the truth table,
If $P$ is false,then $P->Q$ is true.

if pigs fly, then $1+1=3$. Why is this implication true? How do you prove it?

Suppose you say that "If it's raining, then the ground is wet."

Then someone responds: "But the ground is dry."

Your response would be:  "So what?  It's not raining, so my statement is still valid!"

It's a convention, so you can say eg. for all $x\in\mathbb R$ the following is true:

$$x\geq0\Longrightarrow x^2\geq0$$

This would be false if you didn't define it that way, because $-1<0$ even though $(-1)^2>0$.


Prove an inequality in $\mathbb{R}$ Let  $ p,q \in \mathbb{R}, \; \lambda > 0, p \neq q$ (two points).
 For the two points $x_+, x_{-}$ with
\begin{align*}
x_+&=p+\lambda\cdot (q-p)\\
x_{-}&=p-\lambda \cdot (q-p)
\end{align*}
I have to prove:
$$|\;\!  x_+-q \!\;| < |x_--q|$$
I started with
\begin{align*}
|x_+-q|&=|p+\lambda\cdot(q-p)-q|\\
&=|p-q|+|\lambda\cdot (q-p)|\\
|x_{-}-q|&=|p-\lambda \cdot (q-p)-q|\\
&=|p-q|-|\lambda \cdot (q-p)|
\end{align*}

It's quit understanding, why $|x_+-q| < |x_--q|$ holds, but I'm definitely not sure, if my "proof" is finished at this point. In particular I don't know if $<$ is already prooved.

We have
\begin{align*}
|x_+ -q|&= |p+\lambda(q-p)-q|\\
&=|p(1-\lambda ) - q( 1-\lambda)|\\
&=|(p-q)\cdot (1-\lambda)|\\
&=|p-q|\cdot |1-\lambda|
\end{align*}
and
\begin{align*}
|x_- -q|&= |p-\lambda (q-p) -q|\\
&=|p(1+\lambda) - (1+\lambda)q|\\
&=|p-q|\cdot |1+\lambda|
\end{align*}
We know that
$$ |x_--q|> |x_+-q| \iff |x_--q|-|x_+-q|>0$$
and
\begin{align*}
|x_--q|-|x_+-q|&=|p-q|\cdot |1+\lambda|-|p-q|\cdot |1-\lambda|\\
&=|p-q|\cdot (|1+\lambda|-|1-\lambda|)
\end{align*}

As $p\neq q$ we have $|p-q|>0$ hence we only need to prove that
$$|1+\lambda|-|1-\lambda|>0$$
when $0<\lambda \leq 1$ we have
$$|1+\lambda|-|1-\lambda|=1+\lambda - 1 +\lambda = 2 \lambda > 0$$
When $\lambda >1 $ we have
$$|1+\lambda|-|1-\lambda|=1+\lambda +1-\lambda=2 >0$$
Hence $$|x_--q|>|x_+-q|$$

This result is true for any metric space, whether it's Euclidean or not (or, may be not, according to a comment below).

The initial form of the question, didn't demand the sets to be Euclidean, so is my proof focused on earlier version of the question.
My take was something like this:

$d(x_+,q)=d(p+λ(q−p),q)=d(p,q)+ d(λ(q−p),q) \\ =d(p,q) -d(\lambda (q-p),q)+2d(\lambda (q-p),q) \\ =d(p-\lambda(q-p), q)+ 2d(\lambda (q-p),q) \\ =d(x_-,q) +2d(\lambda (q-p),q)$

here,  $x_−=p−λ(q−p)$

(( I used, $d(x\pm z,y) = d(x,y)\pm d(z,y)$))

As $2d(\lambda (q-p),q) \gt 0$  $ \forall p\neq q$ and $\lambda \gt 0$

We have, $d(x_+, q) \gt d(x_-, q) $
$\Box$


The total number of non congruent integer sided triangles whose sides belong to the set{10,11,12,⋯,22} The total number of non congruent integer sided triangles whose sides belong to the set{$10,11,12,\cdots,22$} are---

For a triangle to be formed,sum of any two sided must be greater than the third side,however if 10,11 are the sides of the triangle then 10+11=21,so we cannot have 21 and 22 for the third side.Similarly if we had 10,12 as two of the sides,22 cannot be the third side.Other than this,there seems no restrictions on choosing the three sides.There are 9 options for third side if two sides are (10,11).similar is case for (10,12).Now for number of possible cases for 11 as one of the side is $\binom{11}{2}$(as we have already counted for number of cases with (11,10).Similar is case for 12 as one of the side.The other triangles can be formed by choosing any three sides from {$13,14,\cdots,22$}. hence my answer for total number of scalene triangles formed is-- $$9+9+\binom{11}{2}+\binom{11}{2}+\binom{10}{3}$$It is easy to calculate the number of isosceles triangles and equilateral ones.However I am getting wrong answer.Can anyone suggest where I am wrong.Thanks.

For scalene triangles, the easiest way is to note that you can choose any three sides of the thirteen available except $(10,11,21), (10,11,22), (10,12,22)$ so the count is ${13 \choose 3}-3=283$.  You have counted $(11,12,20)$, for example, twice, once as one of the $11$s and once as one of the $12$s.  You have missed counting the triangles with $10$ as one side unless the second side is $11$ or $12$.  If yo change your second $11 \choose 2$ to be $10 \choose 2$ to skip the double count of $11,12$ and add $10 \choose 2$ for $10$ plus two sides greater than $12$, you again get $283$

the correct answer should be 448
it can be solved as follows:
we have to take three cases:

total equilateral triangle possible is $13$
total isosceles triangle possible are $13\times 12=156$
total scales triangle possible are $^{13}\textrm{C}_3= 13!/10!*3!=
    286$

total possible are $= 455$
but 7 triangles are not possible to form
so final answer$= 455-7 = 448$


Prove that the $n$th roots of unity form a group under multiplication Let $n$ be a positive integer and let $z$ be the complex number $\cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)$. Prove that $G=\{1,z,z^2,...,z^{n-1}\}$ is a group under multiplication in $\mathbb{C}$.

This is a reference to Moivre's formula, because $z^n = 1$. But I do not know how to apply this result so that it complies with the group properties. I have thought about doing induction, but it becomes more extensive.

According to the definition of Group.
A group is a nonempty set $G$ equipped with a binary operation $*$ that satisfies the following axioms:

Clasure: if $a\in{G}$ and $b\in{g}$, then $a*b\in{G}$.
Associativity: $a*(b*c)=(a*b)*C$ for all $a,b,c\in{G}$.
There is an element $e\in{G}$ (called the identity element) such that $a*e=a=e*a$ for every $a\in{G}$.
For every $a\in{G}$, there is an element $d\in{G}$ (called the inverse of $a$) such that $a*d=e$ and $d*a=e$.

A group is said to be abelian if it also satisfies this axiom:

Commutativity: $a*b=b*a$ for all $a,b\in{G}$.

Please help...

More generally, if $C$ is a group and $z \in C$ with $z^n=1$, where $1$ is the identity of $C$, then $G=\{1,z,z^2,\dots,z^{n-1}\}$ is a group (actually, a subgroup of $C$).

Indeed:

Closure: $z^j z^k = z^{j+k} = z^r \in G$, where $r = (j+k) \bmod n$.
Associativity: comes from $C$.
Identity: $1 \in G$ by definition, and $1$ is the identity of $C$.
Inverse: $z^j z^{n-j} =1$.
Commutativity: $z^j z^k = z^{j+k} = z^{k+j} = z^k z^j$.

$$G=\{1,z,z^2,...,z^{n-1}\}$$ Consists of the $n_{th}$ roots of unity.

Note that this is like rotating around the unit circle at an equal angles of $ \frac {2\pi }{n}$

It is closed under multiplication and every element has an inverse, and it has an identity element and the associativity is there.


Pseudospectrum of an $n\times n$ matrix has at most n connected components For $\epsilon>0$, the $\epsilon$ pseudospectrum of an $n\times n$ matrix $A$ is given by $\sigma_{\epsilon}(A)=\{z\in \mathbb{C}:\|(z-A)^{-1}\|>\epsilon^{-1}\}$, with the convention that $\|(z-A)^{-1}\|=\infty$ if $z$ is an eigenvalue of $A$.

It can be shown that $\sigma_{\epsilon}(A)$ is a compact subset of $\mathbb{C}$. It is to be proved that $\sigma_{\epsilon}(A)$ has at most $n$ connected components, each of which contains an eigenvalue of $A$. To prove this, suppose $U$ were a component of $\sigma_{\epsilon}(A)$ that contains no eigenvalue of $A$. We are to use the fact that $\text{log} \|(z-A)^{-1}\|$ is a subharmonic function and thus satisfies the maximum principle. For each $z \in U, \|(z-A)^{-1}\|>\epsilon^{-1}$. How do we use the maximum principle to show that this is possible only if $U$ contains an eigenvalue $\lambda$ for which $\|(\lambda-A)^{-1}\|=\infty$?

If $\sigma_\epsilon(A)$ has $>n$ components each of which contains an eigenvalue of $A$, then the $n\times n$ matrix $A$ would have $>n$ (distinct) eigenvalues.


$$=\frac{\sqrt{2t^2-1}-1}{t^2-1}\sqrt[3]{4t^3-3t}+\frac{\sqrt[3]{4t^3-3t}-1}{t^2-1}$$ now multiply by conjugates and you get the right answer.

As for the second part is possible that the other value of $t$ gives the same value as the limit to 1.


Sum of two absolute values equal to a whole number The following is the equation:

$|x+1|+|x+2|=3$

How can I solve this problem?

Do I have to reformat it to $|x+1|=3-|x-2|$?

I would like a simple answer that by no means uses set theory. The answer must include a step by step explanation

You have three cases to look at:

• Case 1: $x<-1$
• Case 2: $-1\le x<2$
• Case 3: $x\ge 2$

Hint: if $x+1 > 0$ , $x+1 < 0$, $x+1 = 0$  and $x-2 > 0$, $x - 2 < 0$, $x-2 = 0$, etc...There are $9$ possibilities all together.


If $x\sim\mathcal{N}(\mu, \sigma^2)$, what is $E\left(\frac{\exp(x)}{a+\exp(x)}\right)$ for $a>0$? Let $x\sim\mathcal{N}(\mu, \sigma^2)$ be a normal random variable. I'm interested in a new random variable, defined as
$$
z = \frac{\exp(x)}{a+\exp(x)},\quad x\in\mathbb{R}, a>0.
$$
More specifically, I would like to find the closed form (if any) of its expected value, $\mathbb{E}[z]$, but I don't know how to proceed.

As a first step I could use an intermediate random variable $y=\exp(x)$, which follows the log-normal distribution (since $x$ is normal) and its mean and variance are given w.r.t. to $x$'s mean and variance. But again, I'm not sure if that helps.

If we apply a random variable transformation $Z = g(X)$

$f_Z(z)=f_X(g^{-1}(z))|\frac{d}{dz}g^{-1}(z)|$

where $g(X)=\frac{\exp[X]}{a+ \exp[X]}$, $f_X(x) = \frac{1}{\sqrt{2 \, \pi} \, \sigma}\exp[-\frac{(x-\mu)^2}{2\sigma^2}]$, and $g^{-1}(z)=\log\left(\frac{1}{\frac{1}{a\,z}-\frac{1}{a}}\right)$

$f_Z(z)= \frac{e^{-\frac{\left(\mu -\log \left(-\frac{a z}{z-1}\right)\right)^2}{2 \sigma
   ^2}}}{\sqrt{2 \pi } \sigma  \left| (z-1) z\right| }$

Finally

$E[Z]=\int z\,f_Z(z)dz = \frac{\int \frac{z e^{-\frac{\left(\mu -\log \left(-\frac{a z}{z-1}\right)\right)^2}{2
   \sigma ^2}}}{\left| (z-1) z\right| } \, dz}{\sqrt{2 \pi } \sigma }$

$F_Z(z)=P(Z\le z)=P(\frac{1}{1+ae^{-X}}\le z) = P(Ln(\frac{az}{1-z}) \le X) = F_X(Ln(\frac{az}{1-z}) )$

So $f_Z(z)=\frac{\partial}{\partial z}F_X(Ln(\frac{az}{1-z}) )  = \frac{1}{z(1-z)} f_X(Ln(\frac{az}{1-z}))$. Where $f_X$ is the usual normal density function.
I don't think this will leave you much wiser so better to go after $E[Z]$ directly.


Finding the complex number Find the complex number $z$ satisfying the system of equations $z^2 +
 \bar{w}^7=0$ and $z^5 w^{11}= 1$

Using Euler's form made it really complicated because we don't know the values of the modulus of z and w. Also, taking modulus on both sides of each equation didn't help too.

Answer is $i$

Note: $w$ is not cube root of unity.

Let $|z|=a$ and $|w|=b$.

We have $$z^5 w^{11}=1 \implies |z|^5 \cdot |w|^{11}=1 \implies \color{blue}{a^5b^{11}=1} \tag 1$$

Also,

$$z^2=-\bar{w}^{7} \implies |z|^2 = |w|^7 \implies \color{blue}{a^2=b^7} \tag 2$$

Using $(1)$ and $(2)$, we get $$|z|=|w|=1$$

Now, let $z=e^{i \theta} \quad ; \;  w=e^{i \phi}$ and proceed.


Torsion subgroup of $SL(n,\mathbb Z)$ Let $G$ be subgroup of $SL(n,Z)$ such that for any $g\in G$ there exists integer $m\geq1$ $g^m=1$.

Show that there exists $N\geq1$ such that for any $g\in G$ , $g^N=1$

I know $m$-th root of unity is the eigenvalue of elements, any element is diagonalizable matrix over complex number but I don't know how to use facts?
any suggestion?

I think I've got it (but check it, it won't be the first time I produce a wrong proof!).

First step: Let $\mathcal P$ the set of monic polynomials of degree $n$, with coefficients lying in $\mathbb Z$, and the roots in the unit circle of the complex plane. Then $\mathcal P$ is finite. Indeed, fix $0\leq k\leq n-1$ and for $P\in\mathcal P$, $P=X^n+\sum_{j=0}^{n-1}a_jX^j$, with roots $\lambda_1,\ldots,\lambda_n$, we have
$$a_j=(-1)^j\sum_{J\subset\{1,\ldots,n\},|J|=j}\prod_{k\in J}\lambda_k$$
so $|a_j|\leq \binom nj$ and since $a_j$ is an integer it can take only a finite number of values.
Second step: For each $g\in G$, the characteristic polynomial of $g$, $p_g$, is an element of $\mathcal P$, so the set of all eigenvalues of the elements of $G$ is finite, and is contained in $\bigcup_{n\geq 1}\mathbb U_n$, where $\mathbb U_n$ is the sets of $n$-th roots of unity. So in fact the eigenvalues are contained in $\bigcup_{j=1}^{n_0}\mathbb U_{k_j}$, where $k_j$ are natural numbers $\geq 1$. Taking $N:=\operatorname{ppcm}(k_j,1\leq j\leq n_0)$, we get the wanted result.

Lemma A2 in the appendix of Swinnerton-Dyer's "Brief guide to Algebraic Number Theory" that might help solving your question. I am really sorry for giving this reference this way. I think this Lemma (or a similar version) has a commonly known name, but I just can not remember it. It states

Let $G$ be a f.g. abelian and torsion free group, and let $H$ be a subgroup. Then there exists a minimal base $x_1, \dots, x_n$ of $G$ and integers $m_1, \dots m_r$, $r≤n$, such that $m_{i+1}$ divides $m_{i}$ and $m_1 x_1, \dots, m_r x_r$ are a bases for $H$.

maybe the condition "abelian" can be withdrawn


What is the definition of function in ZF/ZFC? In ZF there is axiom schema of replacement, which can be stated as

  the image of a set under any definable function will also fall inside a
  set

Is there a definition of the concept of function in ZF/ZFC? What is it? I mean set-theoretically speaking. That is, in naïve set theory function can be understood as a set of pairs (triples, etc.), but what about ZF/ZFC?

There are two different notions which are both called "function". A function internally to ZFC is a set of pairs, where the first element of the pair is understood to be mapped to the second by the function. For example, the successor function $S :\mathbb N \to \mathbb N$ is a function internally in ZFC, and it is given by
$$
S = \{(n,m) \in \mathbb N \times \mathbb N \mid m = n + 1\}.
$$
However, the function from the axiom schema of replacement refers to a function on the universe given by a formula. Slightly simplified, if $\phi(x,y)$ is a formula with two free variables such that ZFC proves that $\forall x \exists y \phi(x,y)$ and $\forall x \forall y \forall y'(\phi(x,y) \land \phi(x,y') \to y = y')$, then there is an instance of the schema axiom of replacement which states
$$
\forall X \exists Y(\forall x\forall y(\phi(x,y) \land x \in X \to y \in Y)).
$$

There are:

functions and
operators.

Functions are values in the formal theory (in ZF values are usually called "sets"). Operators don't exist within ZF--they are formulas, so as entities they are present in the metatheory, but not as values in the theory.

Kunen explains the distinction clearly in Sec. I.7.2 on pages 28--30 of "The Foundations of Mathematics". He notes that operators are simply abbreviations for formulas, and they correspond to formulas that can be regarded as "pseudorelations", in the sense that they aren't values in the formal theory.

Another name for operator is class function, because their value is specified for more values that how many values fit in a set. Unfortunately, operators are usually called "functions", causing confusion.

Another issue is how functions are defined in mathematics. Typically in ad hoc ways that don't tell you what $f[x]$ means for $x$ outside of the domain of function $f$.

Traditional presentations of set theory introduce the notion of relation first, as a set whose each element is a set with two elements, usually structured so that we can tell their order (e.g., Def. I.7.5 on page 25 of Kunen's "The Foundations of Mathematics"). They then define functions as syntax for relations. But they almost never talk about what $f[x]$ means for arbitrary $x$.

Whether we are allowed to write $f[x]$ for $x$ outside $\mathrm{DOMAIN}\ f$ or not is a matter of the theory's syntax rules. A typed logic may disallow this, but ZF is untyped, so $f[x]$ should be some value even when $x \notin \mathrm{DOMAIN}\ f$.

So it remains to decide what value $f[x]$ is in that case. One option is to use a default value (as for example on page 15 in Kunen's 2013 "Set Theory"). Such a choice is a little arbitrary. It is simpler to let $f[x]$ be unspecified, in that it is some value (maybe different for each $x \notin \mathrm{DOMAIN}\ f$), but we assume nothing about which value it is.

TLA+

This simple approach is taken in TLA+, the Temporal Logic of Actions + ZF, introduced by Leslie Lamport. Chapter 6 of the book "Specifying Systems" explains these issues clearly and with examples, especially the distinction between operators and functions (the book is available online). This thread discusses this distinction.

TLA+ axiomatizes functions directly, with the function constructor syntax

$$[x \in S \mapsto \mathit{SomeExpression}(x)]$$

Not any value is a function. Only those values $f$ that satisfy the formula:

$$IsAFunction(f) \triangleq f = [x \in \mathrm{DOMAIN}\ f \mapsto f[x]]$$

In doing so, TLA+ does not mention any structure of $f$. A function $f$ could happen to also be a relation that is the set of pairs

$$\{\mathit{KuratowskiPair}(x, f[x]): \quad x \in \mathrm{DOMAIN}\ f\}$$

or not (where $\mathit{KuratowskiPair}$ refers to Kuratowski's construction of ordered pairs). Contrast this approach with the traditional one, where functions necessarily are sets with this relation structure, which is a somewhat secondary to what the notion of mapping stands for. The notion of mapping is distilled by the axiomatization of functions in TLA+, without irrelevant structure.

It is also worth distinguishing undefined from unspecified. Undefined may mean that writing $f[x]$ for $x \notin \mathrm{DOMAIN}\ f$ is nonsensical, as happens in typed formalisms (see also Kunen's comment about "partial functions" on p.15 in "Set theory"). In untyped logic though this has to be some value. Kunen specifies which value this is, whereas TLA+ does not. Lamport cites "Avoiding the undefined by underspecification", which is quite relevant to these issues. Good reading about untypeness:

"Types considered harmful"
"Types are not harmless"
"Should your specification language be typed?"

Extensions by definitions

In more detail, any new symbol that we introduce actually changes the formal system that we are working in. So an identifier that names a function or an operator is introduced by a definition, which means the creation of an inessential extension of the formal system by the addition of a symbol (the identifier in question), together with an axiom about this identifier. Extensions are discussed in Sec. II.15 of Kunen's "The Foundations of Mathematics", as well as in an appendix of Kleene's "Introduction to Metamathematics".


How to solve the following differential equation $B'(t)=1100\exp({\frac{\ln{0.5}}{5}t})+\frac{\ln{0.5}}{6}B(t)$? I have constructed this differential equation $B'(t)=1100\exp\left(\frac{\ln{0.5}}{5}t\right)+\frac{\ln{0.5}}{6}B(t)$

I have constructed this equation when i asked this question here,
but i'm unable to solve this equation from methods that i know.

I'm unable to  separate it, and it's not of the form $y'+p(t)y=q(t)$.

What should be done here?

The equation is of type $y'+p(t)y=q(t)$.

The solution for $B(t)$ will be $B(t)=\frac{\int{\mu(t)q(t)dt +c}}{\mu(t)}$,$\mu(t)=e^{\int{}p(t)dt}$.


Contraposition of an implication with quantifiers I am trying to prove a theorem, and a method is by using contraposition. What is the contraposition of the phrase:

$\exists x$ satisfying P $\Rightarrow$ $\forall y$ satisfy P

I thought it as

$\exists y$ that does not satisfy P $\Rightarrow$ $\forall x$ do not satisfy P.

Is this correct?

You are correct. $\forall$ turns into $\exists$ and each logical expression gets negated.

The contraposition of: $\exists x P(x) \Rightarrow \forall y P(y) $ is $ \exists x \lnot P(x)\Rightarrow \forall y \lnot P(y) $

(the two other answers are wrong)

Proof:

$\exists x P(x) \Rightarrow \forall y P(y) $
$ \lnot \forall y P(y) \Rightarrow \lnot \exists x P(x) $  Modus tolens
$ \lnot \lnot \exists y \lnot P(y) \Rightarrow \lnot \exists x P(x) $ Replace  $\forall y $ with $ \lnot \exists y  \lnot $
$ \exists y \lnot P(y) \Rightarrow \lnot \exists x P(x) $ Double negation elimination
$ \exists y \lnot P(y) \Rightarrow \lnot \lnot \forall x  \lnot P(x) $ Replace  $\exists x $ with $ \lnot \forall y  \lnot $
$ \exists y \lnot  P(y) \Rightarrow \forall x  \lnot P(x) $ Double negation elimination
$ \exists x \lnot  P(x) \Rightarrow \forall y  \lnot P(y) $ Relettering.


Find the radius in an ellipse from its angle Basically, I want to know the length of the radius of an ellipse, based on the angle this radius makes with either of the 2 main radius.

Is that possible to do?

The equation of an ellipse is $(\frac xa)^2+(\frac yb)^2=1$.  If you know the angle $\theta$ from the $x$ axis, you have $y= x \tan (\theta)$.  Now substitute in to get $x^2(\frac 1{a^2}+\frac {\tan^2 \theta}{b^2})=1$  This gives you $x$, then you can find $y$, then $r=\sqrt {x^2+y^2}$

$$\left(\frac{x}{a}\right)^2+\left(\frac{y}{b}\right)^2=r^2$$
$$x=acos(t),y=bsin(t)$$
$$r=\sqrt{x^2+y^2}=\sqrt{a^2cos^2(t)+b^2sin^2(t)}\text{, where "t" is the angle from }0\text{ to }2\pi.$$
If the angle from the minor axis is $\phi$ and the angle from the major axis is $\psi$, then $\phi=\frac{\pi}{2}-t$ and $\psi=\pi-t$.
$$r=\sqrt{a^2cos^2(\pi-\psi)+b^2sin^2(\frac{\pi}{2}-\phi)}$$


Prove that every internal angles of a convex polygon is less than $ 180 $ degrees It's not clear to me why a geometrical proof is so hard to find. The definition says a polygon is convex if we can connect any pair of two points of the polygon with a line that's contained in that polygon. In most sources, for unknown reason, it is treated as an obvious fact.

This is the proof I've found - page 2. Could you verify whether it is correct? I have doubts with regard to this proof - there's a contradiction if we allow angles $> 180$, but how do we know if we can connect two points inside the polygon with a line inside the polygon, if it has angles $<180$? Maybe we would arrive at contradiction if we assumed angles $>170$. We should prove that all angles $< 180$ are okay here.

Let $A$ be any vertex of the polygon. Let $B$, $C$ be the vertices adjacent to $A$.

Angle $BAC$ (the internal angle) is inside the non-degenerate triangle $BAC$, and hence is less than $180^{\circ}$.

Definitions:

$1$. A convex polygon is defined as a polygon with all its interior angles less than $180°$.

$2$. A simple polygon is concave iff at least one of its internal angles is greater than $180°$ .

Let's say an internal angle in a convex polygon is more than $180°$, but it is a contradiction to the definition of a convex polygon.


Indefinite integral from floor of $x$ I want to calculate $\displaystyle \int [x] dx$ where $[]$ is floor function.

I don't know if it is just $kx+C$ for $x \in [k, k+1)$ and $(k+1)x+C$ for $x =k+1$ or I'm missing something


How is the linear combination of Normal Distribution also normal? X ~ N(μ, σ2)
z-square = (X-μ)/σ ~ N (0,1)

If Y = (X - α) / β
X = α + βY
Y ~ N((μ - α) / β, (1 / β^2) * σ2)

How can we derive from above two that linear combination of normal distribution is also normal ?

The $\text{pdf}$ of the sum $s$ of two r.v. $x,y$ can be obtained as the convolution product of the originating distributions, which is an integral, and
$$\text{pdf}(s)\propto\int_{-\infty}^\infty\exp\left(-\frac{(s-t-\mu_x)^2}{2\sigma_x^2}\right)\exp\left(-\frac{(t-\mu_y)^2}{2\sigma_y^2}\right)dt
\\=\int_{-\infty}^\infty\exp\left(-\frac{(s-t-\mu_x)^2}{2\sigma_x^2}-\frac{(t-\mu_y)^2}{2\sigma_y^2}\right)dt.$$
As the exponent is a quadratic polynomial in $t,s$, the value of the integral is the exponential of a quadratic polynomial in $s$, i.e. a Gaussian function.


Equivalence of $\|x\|_1\|x\|_{\infty}$ and $\|x\|_2^2$ Let $x$ be any complex $n$-vector and let $\|\cdot\|_p$ denote the usual $p$-norm.
It is easy to show that $\|x\|_2^2\leq\|x\|_1\|x\|_{\infty}$ (Hölder's inequality). What I am rather interested in is the reversed inequality: finding a $c$ ($c>1$) such that
$$\tag{1}
\|x\|_1\|x\|_\infty\leq c\|x\|_2^2\quad\text{for all $x$.}
$$
Obviously, $\|x\|_1\leq\sqrt{n}\|x\|_2$ and $\|x\|_\infty\leq\|x\|_2$, so an easy candidate is $c_\mathrm{naive}:=\sqrt{n}$. However, it seems that a better constant is about a half of the naive one: $c_\mathrm{better}:=(1+\sqrt{n})/2$. I was wondering about a proof for this better $c$, that is, how to prove that

  $$\tag{2}\|x\|_1\|x\|_\infty\leq\frac{1+\sqrt{n}}{2}\|x\|_2^2\quad\text{for all $x\in\mathbb{C}^n$.}$$

WLOG we can assume that $x:=[1,y^T]^T$, where $\|y\|_\infty\leq 1$, so the quest for the optimal $c$ in (1) is equivalent to finding (or bounding from above)
$$\tag{3}
c_\mathrm{optimal}:=\max_{\|y\|_\infty\leq 1}\frac{1+\|y\|_1}{1+\|y\|_2^2}\;.
$$
By some experimentation, it seems that actually (2) is sharp, that is, $c_\mathrm{optimal}=c_\mathrm{better}$, and the bound in (2) is attained by $x=[1,\alpha,\ldots,\alpha]^T$, where $\alpha=1/(\sqrt{n}+1)$.

Since this is a problem in an early chapter of Matrix Computations by Golub and Van Loan, I suppose its prove might be not overly complicated and, since a hint is missing, it should actually be quite easy. Any input will be highly appretiated; a hint if possible :-)

Let $x$ be a vector in $\mathbb R^n$ with non-negative entries. Assume $x_1$ is the largest of them. Then we have to prove
$$
x_1 \cdot \sum_{i=1}^n x_i \le c \sum_{i=1}^n x_i^2.
$$
My idea is to estimate for $i\ne 1$ with $a>0$
$$
x_1 x_i \le \frac1{2a}x_1^2 + \frac a2 x_i^2.
$$
In order to obtain a balanced estimate,
$$
1+(n-1)\frac1{2a} = \frac a2
$$
is required. Setting $a= 1+\sqrt n$ gives $c=\frac{1+\sqrt n}2$.

When all the coordinates are equal you have   $\|x\|_2^2\leq\|x\|_1\|x\|_{\infty}$ (with equality indeed but I don't know to write this with TeX Commands). Consequently you cannot have c > 1 as the constant you expected. (I think I was a little confused!)


How to write $5 \over 2-i$ in standard form I am having problems with writing the problem $5 \over 2-i$ in standard form and my book doesn't really show how to do a problem like this with only a number and letter on the bottom.

Take the denominator and flip the sign of the $i$.

$$2-i\implies2+i$$

Now, multiply by $1$.

$$\frac5{2-i}=\frac5{2-i}\color{#034da3}{\underline{\times1}}$$

Any number divided by itself?

$$\color{#034da3}{1=\frac{2+i}{2+i}}$$

$$\frac5{2-i}=\frac5{2-i}\color{#034da3}{\underline{\times\frac{2+i}{2+i}}}$$

$$\text{Numerator}=5\times(2+i)\\\ \\\text{Denominator}=\underbrace{(2-i)(2+i)=4-i^2=5}_{\large\text{Foil, then remember that $i^2=-1$}}$$

$$\frac5{2-i}=\frac{\text{Numerator}}{\text{Denominator}}=\frac{5\times(2+i)}5=2+i$$

hint - multiply the expression with $$\frac{2+i}{2+i}$$


Combination of smartphones' pattern password Have you ever seen this interface?

Nowadays, it is used for locking smartphones.

If you haven't, here is a short video on it.

The rules for creating a pattern is as follows.

We must use four nodes or more to make a pattern at least.
Once a node is visited, then the node can't be visited anymore.
You can start at any node.
A pattern has to be connected.
Cycle is not allowed.

How many distinct patterns are possible?

I believe the answer can be found in OEIS.  You have to add the paths of length $4$ through $9$ on a $3\times3$ grid, so $80+104+128+112+112+40=576$

I have validated the $80$, $4$ number paths.  If we number the grid $$\begin{array}{ccc}1&2&3\\4&5&6\\7&8&9 \end{array}$$

The paths starting $12$ are
$1236, 1254, 1258, 1256$
and there were $8$ choices of corner/direction, so $32$ paths start at a corner.
Starting at $2$, there are
$2145,2147,2369,2365,2541,2547,2587,2589,2563,2569$ for $10$ and there are $4$ edge cells, so $40$ start at an edge.
Starting at $5$, there are $8$ paths-four choices of first direction and two choices of which way to turn

Added per user3123's comment that cycles are allowed:  unfortunately in OEIS there are a huge number of series titled "Number of n-step walks on square lattice" and "Number of walks on square lattice", and there is no specific definition to tell one from another.  For $4$ steps, it adds $32$ more paths-four squares to go around, four places to start in each square, and two directions to cycle.  So the $4$ step count goes up to $112$.  For longer paths, the increase will be larger.  But there still will not be too many.

Multiply the amount of nodes(9) by the number of rows and columns (9) and then multiply that by the amount of starts(9).

It would look like this: $9\times 9=81$, then, $81\times 9=729$, so it would be 729 possible answers that some one could use. Wait!, but you have to use 4 at a minimum so you multiply that by 4 like this:  $729\times 4=2916$

$2,916$ possible answers!


Identifying unordered set of complex data as originating from a particular Mandelbrot process? Here is an old question which probably originated back in my high school days.

When iterating the Mandelbrot

$$z_{i+1} = {z_i}^2+c$$

we get a sequence of complex numbers. If we plot these in the complex plane, we can get lots of different looks:

Now if we do not have ordered sequence, like a "time series" of these $z_k$ : $\{z_k,z_{k+1},\cdots
,z_n\}$ but instead just a plot like this with a unordered set of positions, can we calculate "backwards" what the original $c$ is?

You are drawing critical orbit = forward orbit of a critical point.

You ask : can we read/approximate the parameter c from the graph/image of critical orbit ?

I think that it is possible to some extent:

first image: c is probably from interior of Mandelbrot set main cardioid (=  internal radius < 1), with internal angle smaller then  n/8 ( 8 arms , turning clockwise), for example c = 0.345805039440922  +0.097755675960631 i
last image looks like a periodic orbit with period = 14 , so it maybe center of hyperbolic component with period 14, like for example c = 0.295453572980359  +0.020451548527456 i
middle image looks like Siegel disc

But remember that because of slow dynamics and numerical errors first n-points may look different then images with more points.

The next questions could be :

how critical orbit is changing when c is moving on the parameter plane?
how to move on the parameter plane ?

HTH


Find the equation of a line which is perpendicular to a given vector and passing through a known point There is given a vector $2 \vec i + \vec j - 3 \vec k$ and now I want to find the equation of a line that is perpendicular to the given vector and passing through a known point $(1,1,1)$. How can I solve this?

So, you are given the vector $(2,1,-3)$. Let $(2k,k,-3k)$ be the orthogonal projection of $(1,1,1)$ on $(2,1,-3)$. Then, $(2k-1,k-1,-3k-1)$ and $(2,1,-3)$ are orthogonal, giving:
$4k-2+k-1+9k+3=0$ i.e. $k=0$. So, $(0,0,0)$, the origin is the projection. Hence, the line contains the points $(0,0,0)$ and $(1,1,1)$, so its equation is $x=y=z$, if my calculations are correct!

ai + b j + ck is the linear combination notation for a point in 3-space..It is meaningless to speak of a line being "perpendicular" to a point.
...What you want is the line perpendicular to the line L  through (2 , 1 , -3) and the origin.
The direction vector of L is (2,1,-3)..a vector orthogonal to that is (3,O 2)..so the formula of the line you want is of the form (1,1,1) + k(3,O,2)..k a real number.....which you may rewrite in cartesian notation