If $n,m \in \mathbb{N}$ then there are $c,d$ such that $cd = (m,n)$, $(c,d) = 1$ and $(m/c,n/d) = 1$. Suppose that $m,n \in \mathbb{N}$. Using the fundamental theorem of arithmetic it is easy to show that there exist $c,d \in \mathbb{N}$ such that $(c,d) = 1$, $cd = (m,n)$ and $(\frac{m}{c},\frac{n}{d}) = 1$.

Is there any quick way to prove this without using the prime factorizations of $m$ and $n$, i.e. only the basic properties of the gcd, lcm, etc.?

$c$  consists of all the prime powers in $(m,n)$ that have the same exponent as in $m$ ...

Yes, expensive factorization is not needed. We can compute $\,c\,$ efficiently by iterated gcds that cancel from $\,m\,$ all primes that occur to higher power than in  $\,(m,n).\,$ These are exactly the primes in $\,m' = m/(m,n)\,$ and we can cancel them from $m$ by repeatedly cancelling any gcd it has with $\,m',\,$ yielding the solution $\ c = {\rm gdc}(m, m'),\ \ d = (m,n)/c,\ $ where

$\begin{align}&{\rm gdc}(x,y)\ :=\qquad \text{// greatest divisor of $\,x\,$ that is coprime to $\,y$}\\
&\quad {\rm if}\ \, \gcd(x,y) = 1\ \ {\rm then}\ \ x\\
&\quad {\rm else}\ \, {\rm gdc}(x/{\rm gcd}(x,y),\,y)
\end{align}$

Let $d=(m,n)$ and $c=1$, so the statement is proved trivially


Convergence of $\sum \frac{(-1)^{n+1}}{n}z^n$ at $|z|=1$ I know that the power series $\sum \frac{(-1)^{n+1}}{n}z^n$ converges for $|z| \lt 1$ but I have been trying to determine what happens on $|z|=1$
Clearly the series converges at $z=1$ and diverges at $z=-1$.
I thought that a good approach would be to write $z^n = \cos n\theta + i\sin n\theta$ and use Dirichlet's test for the two real series $\sum \frac{(-1)^{n+1}}{n} \cos n\theta, \space \sum \frac{(-1)^{n+1}}{n} \sin n\theta$ but I can't really use it here because $\frac{(-1)^{n+1}}{n}$ is not monotonic.
Can someone give a hint with the right direction?

Let $z=e^{it}$, then the series becomes

$$-\sum_{n=1}^\infty\frac{(-1)^ne^{int}}{n}$$

Let $a_n=(-1)^ne^{int}$, then for $t\neq\pi$:
$$\left|\sum_{n=1}^Na_n\right|=\left|\frac{-e^{it}(1-(-1)^Ne^{iNt})}{1+e^{it}}\right|\leq\left|\frac{2}{1+e^{it}}\right|$$

Then apply Dirichlet test to $a_n$ and $b_n=\frac{1}{n}$, we conclude that $\sum_{n=1}^\infty a_nb_n$ converges, for $z=e^{it}, t\neq\pi$.

If $t=\pi$, then it becomes the harmonic series, which diverges.

Hint:

For $\lvert z\rvert = 1$, consider the series representation of
$$
\log(z) = \sum_{n=1}^{\infty}\frac{(-1)^{n+1}}{n}(z-1)^n.
$$
What happens for $z$ on the unit circle?


Factorizing the Sum of Two Fibonacci numbers The Fibonacci and Lucas numbers are defined for all integers $n$ by the recurrence relations
$$F_n=F_{n-1}+F_{n-2}\text{ where }F_1=1\text{ and }F_2=1,$$
$$L_n=L_{n-1}+L_{n-2}\text{ where }L_1=1\text{ and }L_2=3.$$
I would like to know for what values of $k\in\mathbb{N}$ can one write
$$F_{n+(2k+1)}\pm F_n=cP(k,n)$$
where $c\in\mathbb{N}$ and $P(k,n)$ is some product of Fibonacci or Lucas numbers. Note that it is easy to show that that:
\begin{align*}
F_{n+2k}+F_{n}=F_{n+k}L_k\text{ where $k$ is even,}\\
F_{n+2k}+F_{n}=L_{n+k}F_k\text{ where $k$ is odd.}\\
F_{n+2k}-F_{n}=F_{n+k}L_k\text{ where $k$ is even,}\\
F_{n+2k}-F_{n}=L_{n+k}F_k\text{ where $k$ is odd.}\\
\end{align*}
It is also easy to see that
\begin{align*}
F_{n+1}+F_{n}=F_{n+2}\\
F_{n+1}-F_{n}=F_{n-1}\\
F_{n+3}+F_{n}=2F_{n+2}\\
F_{n+3}-F_{n}=2F_{n+1}\\
\end{align*}
Are these the only such expressions?

Ideas tried: I've tried the Binet formula to see what insights this might provide, but I can't see anything. I've also tested small values of $n$ numerically but couldn't find any further examples than those four given.

It seems unlikely that there will be a simple factorization for $F_{n+5}\pm F_{n}$ because these numbers are prime for several values of $n$.

Primes of the form $F_{n+5}+F_{n}$ are listed in oeis/A091157.

Primes of the form $F_{n+5}-F_{n}$ are listed in oeis/A153892.

Among Lucas numbers $L_{n+1}^2-L_n^2=L_{n+2}L_{n-1}, n\ge 2$.  This is just a differeence of squares factorization together with applying the recursive relation.


Find the min value of $\frac{1}{x+\frac{1}{y+\frac{1}{z}}}$, if $x\ne y \ne z$ and $x,y,z\in {1,2,3,4,5}$ My answer is $\frac{5}{29}$, I just use logic to substitute numbers in the expression, but I can't prove my answer If this expression be minimum then the denominator should be the greatest, so I just let  x=5 and I need to let $\frac{1}{y+\frac{1}{z}}$ be the greatest so just need this denominator be smallest so y=1 and z=4, this is what I thought.

Note that with $x,y,z \gt 0$ you have $$x+\frac 1{y+\frac 1z}\lt x+1$$ so if $x\le 4$ the denominator will be smaller than if $x=5$ and the fraction larger. You can repeat this kind of argument to make a proof (you will want $y$ to be small and $z$ large for similar reasons), and generalise it too.


If $f$ is an affine map and $f(0) = 0$, then $f$ is a linear map. If $f$ is affine and $f(0) = 0$, then $f$ is a linear map.
  Define $f(x) = T(x) - T(0)$, where $T$ is an affine map from $R^n$ to $R^k$.

I see that I would have to show that $f(ax) = af(x)$, which means $T(ax) - T(0) = a[T(x)-T(0)]$, but how would I show this equality?

I see that $f(x + y) = f(x) + f(y)$ iff $T(0) = 0$, but I don't see how I would show $f(ax) = af(x)$ since $aT(x) \neq T(ax).$

The definition of an affine map:

  Let $\{p_0, .., p_n\} \subseteq R^n$ be affine independent and let $A$ denote the affine set is spans.  An affine map $T: A \rightarrow R^k$ (for some $k \gt 1)$ is a function satisfying $T(\sum t_ip_i) = \sum t_i T(p_i)$ whenever $\sum t_i = 1$.  The restriction to $[p_0, ..., p_n]$, which is the convex set spanned by $\{p_0, ..., p_n\}$, is also an affine map.

Your thoughts are conspicuously missing the key step of writing down what it means for $T$ to be an affine map.

What do you do, is only reading the first part of the chapter four of the book foundation of optimization by Osman Güler.
Definition 4.1 A nonempty subset A of a vector space E is called an aﬃne set if for points x and y in A, the line passing through x and y is contained
in A; in other words,
x, y ∈ A ⇒ ℓ := {x + t(y − x) = (1 − t)x + ty : t ∈ R} ⊆ A.
Let A and B be aﬃne sets in vector spaces E and F , respectively. A map
F : A → B is called an aﬃne map if
F ((1 − t)x + ty) = (1 − t)F (x) + tF(y) for all t ∈ R.
Theorem 4.4. If A ⊆ E is an aﬃne subset of E, and a ∈ A is an arbitrary
point, then L := A − a = {y − a : y ∈ A} is a linear subspace of E, which is independent of a ∈ A;consequently,
A = a + L, and L = A − A = {y − z : y, z ∈ A}.
Let F : A → B be a map between two aﬃne sets A and B. It is easy to
verify that F is an aﬃne map if and only if its graph
gr(F ) := {(x, F (x)) : x ∈ A} ⊆ A × B is an aﬃne set.
Since the gr(F) is an aﬃne set in A × B
Using Theorem 4.4. (0,0) = (a -a,F(a)- F(a) ) = ((a,F(a)) - (a,F(a)) is consequently a linear subspace of L := A × B - A × B providing F(x) is a linear map.


Is there a "largest function"? In one of my classes, the professor asked about what we think the largest function was. Many thought perhaps ${e^x}^{e^x}$, but I thought about $n!$

When I talk about a "largest function", I mean the function that increases the quickest.

The professor asked about a function larger than $n!$ to which I responded, $2n!$

Although snarky in nature, it is technically true.

So my question is this:

  What is the "largest function" if we define "largest" as being "increases the quickest". A parent function is what we need, as it prevents someone like myself from putting a larger coefficient before the function.

There are many large functions, e.g. $e^n$, $n!$ etc.

And you might know that $e^n$ grows faster than $n^k$ for any $k\geq 1$.

But there are other interesting functions, e.g. the Busy Beaver function. It asymtotically grows faster than any computable function. That means you cannot even write a computer program that produces a faster growing function.

The nice thing is: The busy beaver function is well-defined, but not computable:)! This function really gives an upper bound for the growth of computable functions (e.g., it grows much faster than any function that just contains hyperoperators or the TREE function).

edit: Of course, there are more and even faster growing functions.

I'm just saying, the function that I think is the LARGEST ar aka the one that increases the value of the number is, what I invented, is Pxn("number").That kinda makes in infifnite because how it works for example if I took $1$, it would give me $\pi$, but if I take $3$, that means take every single number of $\pi$ and multiply it by $3$ so $``3.14"$ would be $``6.312"$.
So there you go, bye (I wrote this and I'm 9yr old)


Probability. White and black sheeps Of these days I met an interesting theoretical probability problem.

There is a flock of sheep, which initially included one white and one black sheep. Every day, the following procedure: choose randomly one sheep from the flock, and remember its color. Then it returned to the flock and add there a new one black sheep.
If any of the selected days choosing one is a white sheep, and the previous day took place the same, it is decided to make it a barbecue.
So the quiestion is, what is the probability of such an event with an unlimited repetition of the procedure?

Added: make it a barbecue means that when white sheep comes two days in a row, the experiment is over.

(Edit: The first version of this answer, while correct, was incomplete.)

Denote by $b_n$ the probability that you reach a state with $n$ sheep whereby the last picked sheep was black, and by $w_n$ the probability that you reach a state with $n$ sheep whereby the last picked sheep was white. Then $b_2=1$, $w_2=0$, and we have the recursion
$$b_{n+1}={n-1\over n}(b_n+w_n),\quad w_{n+1}={1\over n}b_n\qquad(n\geq2)\ ,\tag{1}$$
in particular $b_3={1\over2}$. From $(1)$ we obtain by eliminating $w_n$ the recursion
$$b_{n+1}={n-1\over n}b_n+{1\over n}b_{n-1}\ .$$
The sequence $(c_n)_{n\geq2}$ defined by
$$b_n:={ c_n\over(n-1)!}\qquad(n\geq2)$$
then satisfies
$$c_2=1, \quad c_3=1,\qquad c_{n+1}=(n-1)(c_n+c_{n-1})\ ,\tag{2}$$
whence is a sequence of natural numbers. One computes $(c_n)_{n\geq2}=(1,1,4,15,76,455,\ldots)$. This sequence can be found in OEIS as A002467. It turns out that $c_n$, defined by $(2)$, can be combinatorially identified as the number of non-derangements (i.e. permutations having at least one fixed point) in the symmetric group ${\cal S}_{n-1}$. Now it is well known that for large $n$ the fraction ${1\over e}$ of all permutations in ${\cal S}_{n-1}$ are derangements. This implies that
$$\lim_{n\to\infty} b_n=\lim_{n\to\infty}{c_n\over(n-1)!}=1-{1\over e}\ .$$
It follows that with probability $1-{1\over e}$ the sheep picking will go on forever. From this we can conclude that with probability
$$p={1\over e}$$ we shall see a barbecue taking place.

The answer is the following addition which comes from considering every possible way of having 2 white sheeps in a row:

$\sum_{k=1}^{\infty} \frac{1}{k(k+1)(k+2)}$

Using the formula below, we can see that the summation is equal to $1/4$ (notice how fractions with same denominator cancel out).

$\frac{1}{x(x+1)(x+2)}=\frac{0.5}{x}-\frac{1}{x+1}+\frac{0.5}{x+2}$


If a CW Complex captures the topology of manifold, what captures its geometry? Context:
I work on a scientific computing code (mostly fluid mechanics) and I am trying to learn differential geometry, understand it and then mimic its basic structures into a numerical code.

My intuition is that the "mesh" used in numerical simulations is nothing but the discrete version of the manifold.

I understood that a manifold is a topological space and an atlas (at least for continuum mechanics applications).

I think about a CW Complex as the topological discretization of the mesh. It is a finite set of cell spaces (i.e., points, lines, surfaces and volumes) related to each other by means of its boundary maps (i.e., the incidence matrices). This can be coded easily.

Question:
If the CW Complex captures the topological nature of the manifold, which entity captures its "position"? (may we call this the "geometric nature" of the manifold?)

I guess I should "discretize the atlas" but, is there any structure that already does that?
Is there something I am missing?

Thank you! :)

If you build a mesh, then the different line segments also each have a length. A CW complex wouldn't know about that because that is part of the geometry. The CW complex only describes which line segments are attached to which nodes. You could make some line segments very short and others much longer. The object will look very different because the geometry is very different but the topology didn't change.


Asymptotics of two expressions involving logarithms (As I am new to algorithmic complexity so),

EDIT:

please give solutions for large x (means as x->infinity) !

You can subtitute $y=\ln x$ and apply logarithm laws,

$$\ln\left(\frac{y+1}{y^3}\right)=\ln\left(1+\tfrac1y\right)-2\ln(y)=O(1/y)+O(\ln(y)),$$
which is both smaller or contained in $O(y^{\frac12})$

After the Edit: first simplify your expression. Then it reads as

$$x\cdot\frac{0.2}{y}\cdot\frac{y+1}{y^3}$$

which is $O(x\ln(x)^{-3})$ which is contained in $o(x)$.

Use backslash for special functions like $\ln$.

You didn't specify whether $x \to 0$ or $x \to \infty$ or something else, so your question is not precise enough. But either way, the technique is always to look for the most significant term and "pull it out" in some way to get to some form with an asymptotic expansion. For example:

$\ln(x+1) - \ln(x-1) \\
 = \ln(x(1+\frac{1}{x})) - \ln(x(1-\frac{1}{x})) \\
 = ( \ln(x) + \ln(1+\frac{1}{x}) ) - ( \ln(x) + \ln(1-\frac{1}{x}) ) \\
 \approx ( \frac{1}{x} ) - ( - \frac{1}{x} ) \text{ as } x \to \infty \\
 = \frac{2}{x}$

The asymptotic expansion used here is the Taylor series.

[Edit: Now that the question has been clarified..]

Use the same technique, since the outer function is increasing, we need to identify the asymptotically greatest term inside and factor it out:

$\ln(\frac{\ln(x)+1}{\ln(x)^3}) \\
 = \ln(\frac{1}{\ln(x)^2}(...)) \\
 = -\ln(\ln(x)^2) + \ln(...) \\
 \approx -\ln(\ln(x)^2) + ... \text{ as } x \to \infty$

again using the Taylor series.


A version of Hardy's inequality involving reciprocals. How can one prove for any sequence of positive numbers $a_n, n\ge1,$ we have
$$\sum_{n=1}^\infty \frac{n}{a_1+a_2+a_3+\cdots+a_n}\le 2\sum_{n=1}^\infty \frac{1}{a_n}$$

Added later:

Apparently, this is a version of Hardy's inequality. The above is the case $p=-1$. (See the wiki for what $p$ is).

The case $p=2$ appears here: Proving $A: l_2 \to l_2$ is a bounded operator

Here is a proof.

We try using induction, but as usual, a direct approach seems to fail and we have to try and prove a stronger statement.

So we try and pick a positive function $f(n)$ such that

$$ \frac{f(n)}{a_1 + a_2 + \dots + a_n} + \sum_{k=1}^{n} \frac{k}{a_1 + a_2 + \dots + a_k} \le \sum_{j=1}^{n} \frac{2}{a_j}$$

Let $S = a_1 + a_2 + \dots + a_n$ and let $x = a_{n+1}$.

In order to prove that $n$ implies $n+1$ it would be sufficient to prove

$$\frac{2}{x} + \frac{f(n)}{S} \ge \frac{f(n+1) + n+1}{S+x}$$

This can be rearranged to

$$2S^2 + f(n) x^2 + (f(n) + 2) Sx \ge (f(n+1) + n+1) Sx$$

Since $$ 2S^2 + f(n) x^2 \ge 2 \sqrt{2 f(n)} Sx$$

it is sufficient to prove that $f(n)$ satisfies

$$ f(n) + 2 + 2\sqrt{2 f(n)} \ge f(n+1) + n + 1$$

Choosing $f(n) = \dfrac{n^2}{2}$ does the trick.

We can easily verify the base case for this choice of $f(n)$.

Thus we have:

$$ \frac{n^2}{2(a_1 + a_2 + \dots + a_n)} + \sum_{k=1}^{n} \frac{k}{a_1 + a_2 + \dots + a_k} \le \sum_{j=1}^{n} \frac{2}{a_j}$$

Forgive me as it is my first time on math exchange and I dont know how formatting is done for expressions.

first thing I feel is factor of 2 on right side is not necessary. It can be any number greater than or equal to 1. Equality can occur only when all a_i are identical and that factor on right side is 1.

lets call  expression on right side as RHS and on left side as LHS.

Define f(n) = RHS_n - LHS_n
then f(n+1) = RHS_{n+1} - LHS_{n+1}

it is easy to see that

f(n+1) - f(n)>0 for all n

(final expression will be quadratic in  a_{n+1} and X, where X = summation of a_i [i =1 to n]).

given inequality is obvious when n =1, so that f(1) >0. hence f(n) > 0 for all n.


Show that there exist $n$ such that $r$ divides $\binom{p^n}{q^n}$ Cross-posted to Math Overflow

Two positive integers $p,q$ and a prime $r$ are given, such that $r>p>q>1$.
I have to show that there exist $n$ such that
$$r\ \text{divides}\ \binom{p^n}{q^n}$$

Should I use Lucas' theorem? I can't solve it.

Notation:

$a\operatorname{mod} m$ is the residue of $a$ modulo $m$.
$v_r(a) = \max\{n\ge 0: r^n\mid a\}$,
$\mathrm{ord}_{m}(a) = \min\{n\ge 1: m\mid a^n-1\}$.

As it was already explained here, we need to show that for some $n$ and $l$   $$p^n \operatorname{mod} r^l < q^n \operatorname{mod} r^l. $$
Assume the contrary.

Let $$k = \mathrm{ord}_r p.$$ If $q^k\neq 1\pmod r$, then we are done with $n=k$, $l=1$. So we have $j:=\mathrm{ord}_r q\mid k$.

Denote $$m = v_r(q^k-1).$$ If $v_r(p^k-1)>m$, then $n=k, l=m+1$ works.

Case 1. $v_r(p^k-1)=m$.

By Hensell's lifting lemma for any $l\ge 1$
$$
\mathrm{ord}_{r^{l+m}} p = r^l k,\quad \mathrm{ord}_{r^{l+m}} q = r^l j,
$$
so
$$
\mathrm{ord}_{r^{l+m}} p^k = r^l,\quad \mathrm{ord}_{r^{l+m}} q^k = r^l.\tag{1}
$$

The group $\mathbb{Z}^*_{r^{l+m}}$ of invertible elements modulo $r^{l+m}$ is cyclic of order $r^{l+m-1}(r-1)$. Let $\varepsilon$ be its generator. Then it follows from $(1)$ that
$$
p^k = \varepsilon^{sr^m(r-1)} \operatorname{mod} r^{l+m}, \quad q^k = \varepsilon^{tr^m(r-1)} \operatorname{mod} r^{l+m},\tag{2}
$$
where $r\nmid st$. Now consider
$$
p^k, p^{2k}, \dots, p^{(r^{l}-1)k} \operatorname{mod} r^{l+m}
$$
and
$$
q^k, q^{2k}, \dots, q^{(r^{l}-1)k} \operatorname{mod} r^{l+m}.
$$
Because of $(2)$, both sequences contain $\varepsilon^{r^m(r-1)}, \varepsilon^{2r^m(r-1)},\dots, \varepsilon^{(r^{l}-1)r^m(r-1)}$ in some order. Since $p^{ik}\operatorname{mod} r^{l+m} \ge q^{ik}\operatorname{mod} r^{l+m}$ for all $i$, then $p^{k}\operatorname{mod} r^{l+m} = q^{k}\operatorname{mod} r^{l+m}$. However, this cannot happen for $l$ large enough (so that $r^{l+m}>p^k$). This finishes the proof for this case.

Case 2. $d:=v_r(p^k-1)<m$.

Consider
$$
p^{k-1}, p^{2k-1}, \dots, p^{rk-1} \operatorname{mod} r^{d+1}.
$$
From $q^{sk-1} = q^{k-1}\operatorname{mod} r^{d+1}$ it follows that $p^{sk-1}\operatorname{mod} r^{d+1} \ge q^{k-1} \operatorname{mod} r^{d+1}$. But $p^{sk-1}$ for $s=1\dots,r$ have different residues modulo $r^{d+1}$ and the same residue modulo $r^{d}$. Therefore, the residues modulo $r^{d+1}$ are equal to $$p^{k-1}\operatorname{mod} r^{d}, (p^{k-1}\operatorname{mod} r^{d}) + r^{d}, \dots, (p^{k-1}\operatorname{mod} r^{d}) + (r-1)r^{d}$$ in some order. In particular, we get $q^{k-1} \operatorname{mod} r^{d+1} \le p^{k-1}\operatorname{mod} r^{d}<r^{d}$. But then $$q^{k}\operatorname{mod} r^{d+1} = \big(q\cdot (q^{k-1} \operatorname{mod} r^{d+1})\big)\operatorname{mod} r^{d+1}$$ cannot be equal to $1$, since $q<r$. The proof is now complete.

I write again main expression, which need to be multiple of r :
$$
{{p^n!} \over {q^n(p^n-q^n)!}}
$$
Again i have deleted everything, because i found my error, but luckily i found another answer :
$$
(q^n \mod r) + ((p^n-q^n) \mod r) >= r
$$
I will explain a little bit this expression : $q^n$ will contain x times r, or multiples of r in his factorial. Anyway it will contain at least $\lfloor q^n/r\rfloor$ times r. It can be more, because if one factor is for example $r^2$ or multiple, then it will contain more times r. Anyway, because $p^n!$ is higher, it will contain every factor of $q^n!$. We only need one factor of r, and it will be enough. We will by sure have more factors of r in this dividend if a sum both divisors will contain less times r. And this we check with both remainder. Let us write last expression in a more easier form :
$$
r({q^n \over r} - \left \lfloor{q^n \over r}\right \rfloor) +
r({{p^n-q^n} \over r} - \left \lfloor{{p^n-q^n} \over r}\right \rfloor)
>=r
$$
$$
({q^n \over r} - \left \lfloor{q^n \over r}\right \rfloor) +
({{p^n-q^n} \over r} - \left \lfloor{{p^n-q^n} \over r}\right \rfloor)
>=1
$$
$$
{p^n \over r} - \left \lfloor{q^n \over r}\right \rfloor
- \left \lfloor{{p^n-q^n} \over r}\right \rfloor
>=1
$$
Another way to get to this result is :
First we define few functions :
$N_r(x)$="number of prime factors r in x!"
$Q_y(x)=\left \lfloor {x \over y} \right \rfloor$
Now note that :
$$
N_r(x)=\sum_{k=1}^{{\log(y) \over \log(r)}} Q_{r^k}(x)
$$
I explain this last step with a example. For example x=29 and r=3. Then
$$
x!= 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29
$$
Let us count only multiples of 3 :
$$
3^1*1,3^1*2,3^2*1,3^1*4,3^1*5,3^2*2,3^1*7,3^1*8,3^3
$$
How many times we have multiples of 3^1 disregarding if it is 3^2 or 3^3 ? We have exactly $Q_3(29)=9$ times. If we take of all this factors 3, we left with :
$3^1$ from $3^2*1$
$3^1$ from $3^2*2$ ,and
$3^2$ from $3^3$
Now we take of again all this factors 3 from $3^2$ places. Exactly $Q_{3^2}(29)$=$Q_{9}(29)=3$ times. We left only with
$3^1$ from $3^3$
So, factors 3 in total from 29! are :
$$
N_3(29)=Q_3(29)+Q_{3^2}(29)+Q_{3^3}(29)=9+3+1=10
$$
For a general proof refere to https://en.wikipedia.org/wiki/Legendre%27s_formula#Proof.
After this little explanation of formula $N_r(x)$, let us continue :Necessary and sufficient condition that our division is multiple of r is that :
$$
N_r(p^n)-N_r(q^n)-N_r(p^n-q^n)>=1
$$
$$
\sum_{k=1}^{\infty} Q_{r^k}(p^n)-\sum_{k=1}^{\infty} Q_{r^k}(q^n)-\sum_{k=1}^{\infty} Q_{r^k}(p^n-q^n)>=1
$$
$$
\sum_{k=1}^{\infty} {Q_{r^k}(p^n)-Q_{r^k}(q^n)-Q_{r^k}(p^n-q^n)}>=
Q_{r}(p^n)-Q_{r}(q^n)-Q_{r}(p^n-q^n)>=1
$$
$$
\left \lfloor {p^n \over r} \right \rfloor -
\left \lfloor {q^n \over r} \right \rfloor -
\left \lfloor {{p^n-q^n} \over r} \right \rfloor >=1
$$
In fact, this function is very similar to previous formula adding one more floor. This sume, in fact can be only 0 or 1.
Let us put this formula in a form of remainders :
$$
r\left \lfloor {p^n \over r} \right \rfloor -
r\left \lfloor {q^n \over r} \right \rfloor -
r\left \lfloor {{p^n-q^n} \over r} \right \rfloor >=r
$$
Add $-p^n+q^n+(p^n-q^n)=0$ and reorder
$$
-(p^n-r\left \lfloor {p^n \over r} \right \rfloor) +
(q^n-r\left \lfloor {q^n \over r} \right \rfloor)+
((p^n-q^n)-r\left \lfloor {{p^n-q^n} \over r} \right \rfloor)>=r
$$
Let us define $R_r(x)=x \mod r=x-r\left \lfloor {x \over r} \right \rfloor$ and simplfy this expression :
$$
-R_r(p^n)+R_r(q^n)+R_r(p^n-q^n)>=r
$$
Reorder this :
$$
R_r(q^n)+(R_r(p^n-q^n)-R_r(p^n))>=r
$$
We call $R_r(q^n)+R_r(p^n-q^n)-R_r(p^n)$ main residual expression.
Inside parenthesis $(R_r(p^n-q^n)-R_r(p^n))$ we have form $R(a-b)-R(a)$. Results from this can be only R(-b) or -R(b). In our equality we will need that parenthesis expression is bigger or same as 0 in order to get $R_r(-q^n)$.Note that $R_r(q^n)+R_r(-q^n)=r>=r$. Continue then with this expression :
$$
R_r(p^n-q^n)-R_r(p^n)>=0
$$
$$
R_r(p^n-q^n)>=R_r(p^n)
$$
In which case we will have a guaranty that this inequality is true ? In case
$$
R_r(p^n)=1
$$
Now, we have a important point : r is prime. So we can apply "little Fermat theorem" (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem). If
$$
n=r-1
$$
But just in this case, always will happen that also $R_r(q^n)=R_r(p^n)=1$ for a same reason and then in main expression we get :
$$
R_r(q^n)+R_r(p^n-q^n)-R_r(p^n)=1+R_r(p^n-q^n)-1=R_r(p^n-q^n)<r
$$
when n=r-1.
Easier is to work with next (abstracted) condition :
$$
R_r(q^n)-R_r(p^n)>0
$$
or
$$
R_r(q^n)>R_r(p^n)
$$
This is a necessary condition in order to get a n for resolve main residual expression.
Greatings. Daniel


Is there a formal name for an equation that has no solution? I was wondering if there is a formal name for the equations which don't have any solution?

For example consider this equation in $m$ :

$$ -2(3-m)+15=6m-4(m-20)$$

If we do the algebra we will get $2m-6m+4m=80-15+6 \Rightarrow
0=71$ which implies no solution of $m$.

It seems that unsolvable, insolvable and insoluble are all used in this sense.  Personally I'd prefer either of the first two, to avoid confusion with the alternative meaning of insoluble in physics and chemistry.

The term that the textbook that we use for Algebra 1 is "contradiction" and the term used for an equation that has infinite solutions (4x + 2 =4x + 2) is called "identity"


In $\mathbb Z[x_1,x_2,\ldots,x_n]$, show $x_1 x_2\cdots x_n$ has $2^{n+1}-2$ non-constant polynomials dividing it This particular question is a part of an assignment which could not be discussed due to pandemic .

Question (a)  Consider the ring R of polynomials in n variables with integer coefficients . Prove that the polynomial $f(x_1 , x_2 ,\ldots, x_n) = x_1 x_2\cdots x_n $ has $2^{n+1}-2$ non-constant polynomials in R dividing it .

Attempt: (a) any polynomial in R dividing f would be of form ${x_{1}}^{i} ...{x_{n}}^{i}$ i=0 or 1.
So , there will be $2^{n}-1$ polynomials . But the answer is 2 times my answer.
Thanks!!

Note that if $x_i ...x_k $ divides f then - ($x_i ...x_k$) also divides f . So, correct answer is $2^{n+1}-2$.

In a) you forgot the coefficient: $-x_1$ divides $x_1x_2$. This gives $2^{n+1}-2$ divisors because the coefficient can be $1$ or $-1$.
b) The phrase "So, the elemets of order 11 is fixed" does not make sense.


Prove that if $p(x)$ is irreducible, then $\langle p(x) \rangle$ is a maximal ideal of $F[x]$ Problem:

Let $F$ be a field. Prove that if $p(x)$ is irreducible, then $\langle p(x) \rangle$ is a maximal ideal of $F[x]$.

Attempt:

Let $d(x),a(x),p(x) \in F[x]$ and suppose $\text{gcd}[a(x), p(x)] = d(x)$. Then $d(x) \mid p(x)$. So $p(x) = d(x)c(x)$ for some $c(x) \in F[x]$. Because $p(x)$ is irreducible, either $d(x)$ or $c(x)$ is a constant.

If $d(x)$ is a nonzero constant in $F$, then $\langle p(x) \rangle = F[x]$ by [previous proof]* and $\langle p(x) \rangle$ is not maximal because it generates all of $F[x]$.

If $c(x)$ is a nonzero constant, then:
\begin{align*}
    p(x) &= d(x)c(x) \\
    p(x) &= d(x)c && \text{$c(x) = c$ is a constant}\\
    p(x)c^{-1} &= d(x)cc^{-1} \\
    p(x)c^{-1} &= d(x) \\
    d(x) &= p(x)c^{-1}
\end{align*}

Since $d(x) \mid a(x)$, we have that $a(x) = d(x)e(x)$ for some $e(x) \in F[x]$. Then:
\begin{align*}
    a(x) &= d(x)e(x) \\
    a(x) &= p(x)c^{-1}e(x) && \text{substitution}\\
    a(x) &= p(x)e(x)c^{-1}
\end{align*}

This implies that $a(x)$ is a multiple of $p(x)$.

Questions:

My understanding is that if $d(x)$ is a nonzero constant, then $\langle p(x) \rangle$ cannot be maximal because it generates the entire ring. But it also seems to me that $c(x)$ being a constant presents a contradiction.

Does $a(x)$ being a multiple of $p(x)$ present a contradiction, because $a(x)$ and $p(x)$ are relatively prime?

If not, how can I use that $c(x)$ being constant shows that $\langle p(x) \rangle$ is maximal?

Second, guided attempt:

Let $J$ be an ideal containing $\langle p(x) \rangle$ that isn't equal to $\langle p(x) \rangle$. Then there must exist a polynomial $a(x)$ that is in $J$ but not in $\langle p(x) \rangle$. We'll show that $J = F[x]$ using that $p(x)$ and $a(x)$ are relatively prime.

Let $d(x),a(x),p(x) \in F[x]$ and suppose $\text{gcd}[a(x), p(x)] = d(x)$. Then $d(x) \mid p(x)$. So $p(x) = d(x)c(x)$ for some $c(x) \in F[x]$. Because $p(x)$ is irreducible, either $d(x)$ or $c(x)$ is a constant.

By [previous proof]*, if $d(x)$ is a nonzero constant in $F$, then $J=F[x]$ and we are done.

If, on the other hand, $c(x)$ is a nonzero constant, then:
\begin{align*}
    p(x) &= d(x)c(x) \\
    p(x) &= d(x)c && \text{$c(x) = c$ is a constant}\\
    p(x)c^{-1} &= d(x)cc^{-1} \\
    p(x)c^{-1} &= d(x) \\
    d(x) &= p(x)c^{-1}
\end{align*}

Since $d(x) \mid a(x)$, we have that $a(x) = d(x)e(x)$ for some $e(x) \in F[x]$. Then:
\begin{align*}
    a(x) &= d(x)e(x) \\
    a(x) &= p(x)c^{-1}e(x) && \text{substitution}\\
    a(x) &= p(x)e(x)c^{-1}
\end{align*}

This implies that $a(x)$ is a multiple of $p(x)$, which is a contradiction, because $a(x)$ and $p(x)$ are relatively prime. Thus, $\langle p(x) \rangle$ is a maximal ideal of $F[x]$.

* Previous proof: If $J$ is an ideal of $A$ and $J$ contains an invertible element $a$ of $A$, then $J = A$.

Every ideal of $F[x]$ is principal.  If $\langle p(x)\rangle$ is not maximal, then $p(x)$ must have a non-constant factor with a lower degree, which is impossible.

Here is the proof, maybe that will settle your questions?

If $(p(x))$ is not maximal, then there is an ideal $I$ containing it. We'll show $I=F[x]$ or $I=(p(x)).

Since $F[x]$ is a principal ideal domain, we know $I=(f(x))$ for some polynomial $f(x)$. (This is probably where your argument involving $a(x)$, $d(x)$, and $c(x)$ comes in --- your $a(x)$ is my $f(x)$.)

Now the containment of ideals $(p(x))\subseteq (f(x))$ implies that $f(x)$ divides $p(x)$. But $p(x)$ is irreducible --- so this is only possible if $f(x)$ is a scalar multiple of $p(x)$, or if $f(x)$ is constant. These cases correspondingly imply $(f(x))=(p(x))$, or $(f(x))=F[x]$.


Series of numbers that are divided by 3 This is a logical problem and I can't solve it. The problem goes like this:

There is a series of numbers:
$$3, 2, 1, 5$$

There is four ways to add the consecutive terms to have a number that is divided by 3 without leaving remainder (3 1 5 is not consecutive so it doesn't count):

3, that sums up 3.
3 2 1, that sums up 6.
2 1, that sums up 3.
1 5, that sums up 6.

There is another series that is:
$$6, 1, 4, 124, 3, 6, 512, 3, 1, 33, 2, 2, 32, 100, 813, 4, 41, 1, 3, 8, 213, 5, 7, 61, 8, 42, 1, 4, 2, 20, 8$$

  How many ways are there to sum up consecutive numbers that are divided by three?

It's there some trick? Fastest way to solve it?

You can look at the partial sums reduced modulo 3.

Suppose the original sequence is $a_1\ldots a_n$, then define a new sequence $b_0\ldots b_n$ by $b_k = \sum_{i=0}^k a_i\pmod{3}$. So basically you make the sequence of $b$'s by starting with a $0$ and then adding the next $a$ and reducing modulo $3$. Now if $b_k=b_l$ for some $i\neq j$ then $ 0 = b_k-b_l=\sum_{i=k}^l a_i \pmod{3}$ and we have found a sequential sum that is divisible by three.

So in your first example $(a_i)_i = (3, 2, 1, 5)$ then $(b_i)_i = (0, 0, 2, 0, 2)$. Now we are looking for places in the $b$ sequence where both numbers are the same:

$b_0=b_1$ which corresponds to the sequence $3$.
$b_0=b_3$ which corresponds to $3,2,1$.
$b_1=b_3$ which corresponds to $2,1$.
$b_2=b_4$ which corresponts to $1,5$.

To find the total number of consecutive sequences that have a sum divisible by three it is enough to count all pairs of indicies $i,j$ such that $b_i = b_j$.
But this is simple with combinatorics. If $x$ is the number of zeros in the sequence $y$ the number of ones and $z$ the number of twos. Then the total number is ${x \choose 2} + {y\choose 2} + {z\choose 2}$.

Indeed in the example $x=3$, $y=0$ and $z=2$ and ${3\choose 2} + {0\choose 2} +{2\choose 2} = 3+0+1=4$

how isn't there an application that you can just enter a number and get a list of every divisible number up to a specified range, Like say you wanted to get every number divisible by 12 up to 40,000

anyone get what I'm saying?

like sure you can just enter the number on a calculator and add it to itself then keep hitting the equals key but that's a lot of tedious work


Proving a function is odd Here is the given question

  Show that
  $$ f(x) = \frac{1}{2} - \frac{1}{2^x+1}$$
  is an odd function

I do know that

  $ f(x) = f(-x)$ is a even function
  $ f(x) = -f(-x)$ is a odd function

But i cannot seem to simplify f(x) into -f(x) to prove that it is a odd function
-f(x) is $ -\frac{1}{2} + \frac{1}{2^x+1}$

So far i have been able to get

  $$\frac{\frac{1}{2}+2^x-2^{x+1}}{2+2^{x+1}}$$

and cannot find a way further to simplify


Why does the Cauchy-Schwarz inequality hold in any inner product space? I am working through linear algebra problems in Apostol's Calculus, and he has numerous problems that seem to imply that Cauchy-Schwarz holds no matter how the inner product is defined. Then, he has problems where the triangle inequality holds despite alternative definitions of vector norm. This got me thinking, since the proof of the triangle inequality in Apostol relies on Cauchy-Schwarz, that the triangle inequality would hold regardless of how the vector norm is defined (if it involves the dot product).

I then found this response to a question, which states what I was thinking.

Are there any proofs that the Cauchy-Schwarz inequality holds in any inner product space (I looked for some and found none and could not prove it myself)? I've had a semester of algebra (Artin) and some analysis, if there is a proof at such a level of understanding. Intuitive explanations are good, too.

Wikipedia has the one I've usually seen.

Cauchy-Schwarz Inequality

Nothing especially tricky about it, just a really clever setup.

Indeed it holds in any sesquilinear form in any vector space not even (necessarily) normed space. The proof is trivial.


A doubt on a proof of $\lim \frac{\sin x}{x}$ as $x\to 0$ provided in Simmons's Calculus with Analytic Geometry I'm having difficulty understanding a proof of $\lim_{x\to0}\frac{\sin{x}}{x}=1$ provided in Simmons's Calculus With Analytic Geometry, pg. 72. The proof goes as follows:

Let $P$ and $Q$ be two nearby points on a unit circle, and let $\overline{PQ}$ and $\widehat{PQ}$ denote the lengths of the chord and the arc connecting these points. Then the ratio of the chord length to the arc length evidently approaches 1 as the two points move together:

$\frac{\text{chord lenght}\overline{PQ}}{\text{arc lenght}\widehat{PQ}}\to1$ as $\widehat{PQ}\to0$

With the notion in the figure, this geometric statement is equivalent to

$\frac{2\sin{\theta}}{2\theta}=\frac{\sin{\theta}}{\theta}\to1$ as $\theta\to0$

My doubt is, doesn't this proof simply that $\lim_{x\to0}\frac{\sin{x}}{x}=\frac{0}{0}$? I mean, sure the ratio of $\text{chord lenght}\;\overline{PQ}$ to $\text{arc lenght}\;\widehat{PQ}$ approaches 1 as $\theta$ approaches $0$, but that's because both the numerator and the denominator approach the samue value, which is $0$. How is it any different from saying $\lim_{x\to0}\frac{\sin{x}}{x}=1$ because both $\sin{x}$ and $x$ approach the samue value $0$ as $x\to0$?

I think your problem is deeper than understanding this proof.

What makes calculus difficult is that it's hard (at first) to make sense of the ratio of two small quantities. Just because both "approach the same value $0$" doesn't mean the limit of the quotient is $1$.

For example
$$
\frac{2x}{x}
$$
clearly approaches $2$, since it's always exactly $2$ when $x$ is not $0$.

Also
$$
\frac{2h+h^2}{h} = 2 + h
$$
approaches $2$ as $h$ approaches $0$, even though it looks like $0/0$ when $h = 0$.
That is in fact just the limit you probably saw when finding the slope of a parabola (differentiating $y=x^2$ when $x=1$).

The moral of the story is that you have to pay attention to the relative rates at which the numerator and denominator approach $0$. In the question you ask, the rates are the same and the limit is $1$.

You can take comfort in the fact that this was a mathematical and philosophical difficulty when Newton and Leibniz were inventing calculus.

Note: this in an informal discussion. The formal definition of limits avoids words like "approaches". And @Bernard 's comment about the geometric argument for $\sin(x)/x$ correctly notes the informality there too.

One can interpret the proof in a more abstract, intuitive way. As arc length decreases, its "curviness" disappears (i.e. it becomes a straight line). We can say this as $sin(\theta) \to \theta $ as $ \theta \to 0$. Taking this into account:

$$\lim_{\theta \to 0}\frac{sin\theta}{\theta} = \lim_{\theta \to 0} \frac{\theta}{\theta} = \lim_{\theta \to 0} 1 = 1$$


Show $\int_0^\infty xe^{-ax^2}dx=\frac{1}{2a}$ I tried integrating by parts but I always arrive at an expression other than $\frac{1}{2a}$ which contains $\sqrt{\frac{\pi}{a}}$ from the Gaussian integral $\int_0^\infty e^{-ax^2}dx=\frac12 \sqrt{\frac{\pi}{a}}$. Is there some kind of trick to evaluating this integral?

This integral is very simple and can be explained and understood in a better way just using simple properties of Gamma function
Put $$ax^2 =z$$ then use the definition of Gamma function also $$\Gamma \frac{1}{2}=\sqrt{\pi}$$


Check if Cantor’s Theorem is applicable in the following examples. Also, find $\bigcap_{n\in\Bbb{N}} F_n$ in each case So we have to find whether Cantor's Theorem is applicable to the following
(i) $F_n = [n, \infty)$ (ii) $F_n = (0, \frac{1}{n})$ (iii) $F_n = [1 − \frac{1}{n} , 2 + \frac{1}{n}]$
Now I've tried doing these as

$F_n$ is non-empty and closed and $[n+1,\infty)\subset[n,\infty)$. But since $n\to\infty$, the length of $F_n$ does not tend to $0$. So not applicable
$F_n$ is an open interval so not applicable
$F_n$ is non-empty and closed. But as $n\to\infty$, $F_n\to [1,2]$ and length $[1,2]$ is not equal to $0$. So not applicable.

Is my method correct or am I doing something wrong??

Note that the exact statement of Cantor’s Intersection Theorem is the following:

The intersection of any decreasing sequence of non-empty nested compact sets is non-empty.

Thus, as you correctly stated, it is not applicable in cases a) and b). However, it is clearly applicable in case c), since that sequence satisfies all of the assumptions of Cantor’s Theorem.


A little game with rolling a fair dice You play the following game: you roll a fair dice then either you stop rolling and take the sum of the rolled numbers so far or you continue rolling the dice. Any time if a 1 is rolled you lose all your money, and has no option to continue the game. The strategy that you follow is that you wait until the cumulated price reaches a given level and then you stop. What should be this level in order to maximize the expected value of the prize?

My answer is 20...is it correct?

Let's say that $k$ points is the place where rolling again and stopping have the same expected value.  That means that $$k=\frac16(0)+\frac16(k+2)+\frac16(k+3)+\frac16(k+4)+\frac16(k+5)+\frac16(k+6)\\k=\frac56k+\frac{20}6\\\frac16k=\frac{20}6\\k=20$$

So you are correct.

Every time you don't lose you will win an average of 4. Total prize would be
$$ W_n = 4 \cdot n \rightarrow_n \infty $$
The probability of winning is 5/6 and after n turns, the probability of still winning something is:
$$ P_n = ( \frac{5}{6} )^n \rightarrow_n 0 $$

Total prize expectancy is
$$ W_n \cdot P_n = 4 \cdot n \cdot( \frac{5}{6} )^n $$

Which has two maxima at n equal to 5 and 6.
$$ W_5 \cdot P_5 = W_6 \cdot P_6 = \frac{4 \cdot 5^6 }{ 6^5 } \approx 8.04 $$

So my strategy would be to play for 5 or 6 turns what will maximize my earnings. Every time I win, I will earn an average of 20 or 24.

Nice game to play with friends. Game fee 10$ ;)


Basic Topology of R (Just want hints) I just want to know if I'm on to something for the following problem from intro to analysis. I laid out the problem, my scratchwork follows and finally, my questions are found under "Thoughts" in boldface. The topic is, as in the title, the basic topology of the reals under a section called "Perfect Sets." There's a subsection called "Cannected Sets." I already covered compact sets. Thanks a bunch in advance for any help I can get (again, not the solution please; I'm one of those).

$\textbf{Problem}$

Let $r_{1},r_{2},\ldots$ be an enumeration for the rational numbers (I guess the author means that these are all the rational numbers) and for each $n\in \mathbb{N}$, let $\epsilon_{n} = 1/2^{n}$. Set $O=\bigcup_{n=1}^{\infty}V_{\epsilon_{n}}(r_{n})$ and $F=O^{c}$ where $V_{\epsilon}(x)=(x-\epsilon,x+\epsilon)$ centered at $x$. Then $F\neq \emptyset$.

$\textbf{Scratchwork}$

I'm assuming that $[0,3]\subseteq O\Rightarrow \exists r_{n_{1}},\ldots r_{n_{k}}$ such that $[0,3]\subseteq \bigcup_{i=1}^{k}V_{\epsilon_{n_{i}}}(r_{n_{i}})$. But the length of $V_{\epsilon_{n}}(r_{n})$ is $1/2^{n-1}$ for each $n\Rightarrow$ the length of $O$ is $\sum_{n=1}^{\infty}1/2^{n-1}=\displaystyle \frac{1}{1-1/2}=2\Rightarrow $the length of

$\bigcup_{i=1}^{k}V_{\epsilon_{n_{i}}}(r_{n_{i}}) $

is at most $2$. But the length of $[0,3]$ is $3\Rightarrow
\bigcup_{i=1}^{k}V_{\epsilon_{n_{i}}}(r_{n_{i}})$ does not cover $[0,3]$

Remark: The problem does not mention $[0,3]$. My strategy to proving that $F\neq \emptyset$ is to consider $[0,3]$ and show that it cannot be covered by $O$.

$\textbf{Thoughts}$

Am I right with what I have ?(don't want the solution please). If so, can I just say it like that? (then the "scratchwork" is actually a proof). Is there a better strategy? And on a final note, I did not use any of the ideas provided in this section but This problem is just an indexed question so I'm not too worried about that.

So the essence of your proof is that $\mu(O)\le M$ for some constant $M$ (3 maybe) and so $O$ cannot be $\mathbb{R}$ which has infinite Lebesgue measure. The idea seems OK to me.


Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive zeros.

Any input on how to approach this is appreciated.

Let's compute $C(N,M,k)$ the number of sequences of length $N$, with $M$ zeros, and with all runs of zeros having length up to $k$. Say we have $\ell$ runs of zeroes: $z_1,z_2 \cdots z_\ell$ with $1\le z_i \le k$ , $\sum_{i=1}^\ell z_i=Z=N-M$, and $ \lceil Z/k \rceil \le \ell \le M+1$

Then $$C(N,M,k)=\sum_{\ell=\lceil M-N/k \rceil}^{M+1} c_r(M-N,\ell,k) \, c(M-\ell+1,\ell+1)$$

where $c(A,B)={A+B-1\choose B-1}$ is the number of weak compositions, and  $c_r(A,B,k)$ is the number of (strict) compositions restricted to a maximum size $k$. This later problem is solved here.

Assuming $1$s and $0$s appear independent of each other, for $M$ ones, the probability that a $1$ appears is simply $p=\frac{M}{N}$ and for $0$ is simply $1-p$. The PDF of run of $K$ consecutive $0$s can then be calculated as follows:

$$
r(K) = \left\{ \begin{array}{rl}
 p(1-p)^K &\mbox{  $0\leq K\leq N$} \\
 (1-p)^K &\mbox{ $K=N$}
       \end{array} \right.
$$


Representing $100001$ in floating point system There's an example in my textbook about cancellation error that I'm not totally getting. It says that with a $5$ digit decimal arithmetic, $100001$ cannot be represented.

I think that's because when you try to represent it you get $1*10^5$, which is $100000$. However it goes on to say that when $100001$ is represented in this floating point system (when it's either chopped or rounded) it comes to $100000$.

If what I said above is correct, does $100001$ go to $100000$ because of the fact that it can only be represented like $1*10^5$?

If I'm completely off the mark, clarification would be great.

Yes, you only have five decimal digits available.  $100001=1.00001*10^5$ but I have six digits in the mantissa.  Clearly it is closer to go to $1.0000$ than to $1.0001$, so that is what we will do.  So the numbers around here that can be represented are $99998, 99999, 100000, 100010, 100020,$ etc.

That is correct. You have what is called type overflow.  Want to be amused?  If you have a C compiler run this program

#include<stdio.h>
int main(void)
{
    int x = 1;
    while (x > 0)
    {
        x = x + 1;
    }
    printf("x = %d\n", x);
}

It's educational.  This is in integer-world so it's simpler than floating point numbers, but these have an analogous problem: loss of precision. I recommend Forman Acton's Real Computing Made Real for a discussion of this issue.


Can one tell based on the moments of the random variable if it is continuos or not Suppose we are given moments of a random variable $X$.
Can we determine based on this if the random variable is continuous or not?

We also assume that the moments of $X$ completely determine the distribution of $X$.

In other words, do moments of continuous random variable behave fundamentally differently than moments of say discrete random variable?

Thanks, looking forward to your ideas.

Edit:
It seems like there was some confusion with the questions. Let me demonstrate with an example what I have in mind.

Suppose, we are given moments of some random variable $X$
\begin{align}
E[ X^n]=\frac{1}{1+n},
\end{align}
for $n \ge 0$.

Can we determine if the distribution of $X$ is continuous or not?

In this example, I took $X$ to be continuous uniform on $(0,1)$.

Some Thoughts: Since we know the moments we can reconstruct the  characteristic function of $X$  (I think this can be done, right? If not let as assume this)
\begin{align}
\phi_X(t) =\sum_{n=0}^\infty \frac{i^n E[X^n]}{n!} t^n
\end{align}

We also know that $X$ has a pdf iff $\phi_X(t)  \in L_1$.

So it seems it is enough to show that
\begin{align}
\int_{-\infty}^\infty \left| \sum_{n=0}^\infty \frac{i^n E[X^n]}{n!} t^n \right| dt
\end{align}
is finite or not. However, I don't think the above approach would work, as we can not switch the integration and summation.

I doubt that there are some feasible universal conditions for two reasons:

If the moment problem is indeterminate, then there can be both discrete and continuous random variables with same moments. For example, it is known that there is an infinite family of discrete random variables having the same moments as the log-normal distribution (see e.g. Stoyanov Counterexamples in Probability).
One can approximate a continuous distribution with discrete ones and vice versa. So the moments of discrete distribution can be quite close to those of continuous distribution.

Of course, it is possible to formulate infinitely many sufficient conditions for a distribution to be discrete. Example: Let $\mu_n = \mathsf{E}[X^n]$. If $\mu_8 - 10\mu_6 + 33\mu_4 - 40\mu_2 + 16=0$, then $X$ is discrete (moreover, $X\in\{\pm1, \pm2\}$ a.s.).

It's not clear what this is asking, for if the moments determine the distribution, then you simply look at the resulting distribution and see whether it's continuous.

But of course, the moments don't determine the distribution: two distributions on the reals that differ at a single point have the same moments. And if one is continuous; the other will be discontinuous.

Maybe you're asking: "Given a set of moments for a distribution, is there a way to determine whether some other equivalent distribution (equivalent in the sense of having the same moments) is continuous everywhere?"


Stuck in Induction Inequality: $2^n>3n^2$ I am doing an inequality induction question that looks like this:

Prove that $2^n>3n^2$ for $n\geq 8$

So I have done Step $1,2$ but I can't finish step $3$

Step $1$: RTP: $n=8$

LHS=$2^8=256$

RHS=$3(8)^2=192$

Therefore  true for $n=8$

Step $2$: Ass $n=k$

$2^k>3k^2$

Step 3: RTP: $n=k+1$

$2^{k+1}>3(k+1)^2$

LHS=$2^k \cdot 2$

$>2 \cdot (3k^2)$

$=6k^2$

New aim-RTP: $6k^2>3 \cdot (k+1)^2$

$6k^2>3k^2+6k+3$

I am stuck here, how do I continue beyond this step?

Notice that $6k^2\ge3(k+1)^2\iff 2k^2\ge(k+1)^2\iff 2k^2\ge k^2+2k+1\iff k^2\ge2k+1$.

Now use your assumption that $k\ge8$, so $k^2\ge 8k$.

Why don't you consider the real function $f(x) = 3x^2 -6x - 3$ ?


How do I prove that the following is a presentation of $\mathbb{Z_{35}}$? Prove that $\mathbb{Z_{35}}$ is isomorphic to $G=\langle x, y \, | \, x^7 = y^5 = 1, xyx^{-1}y^{-1}=1\rangle$. I'm having a very difficult time with such problems and would be very thankful to anyone who would take the time to slowly explain how does one even begin to take a stab at answering such a question. Thank you for your help.

$35 =7\cdot5$ , the Chinese remainder theorem show that $\mathbb{Z}_{35}\simeq\mathbb{Z}_7\times \mathbb{Z}_5$. Take u = a generator of $\mathbb{Z}_7$ and v a generator of $\mathbb{Z}_5$ and set x=(u,0) and y =(0,v)

$x^7=1$ has 7 complex solutions that constitute a cyclic group. The Same reasoning can be used for $y^5=1$ (a cyclic group with 5 elements). Now, every finite cyclic group is isomorphic to $Zn$ (n is the number elements in the group). So, we have two groups (Z7 and Z5).A theorem says that the Cartesian product of groups is a group itself. If each group is cyclic and the greatest common divisor of the orders of every two of the groups is one, then the product group is cyclic. So, the product group is of the order 7*5=35 and as it is cyclic, it is isomorphic to Z35.


A three-way duel (probability puzzle) This puzzle is taken from Mathematical Puzzles: A Connoisseur's Collection [Peter Winkler]. I don't understand the solution.
Alice, Bob, and Carol arrange a three-way duel. Alice is a poor shot, hitting her target only 1/3 of the time on average. Bob is better, hitting his target 2/3 of the time. Carol is a sure shot. They take turns shooting, first Alice, then Bob, the Carol, then back to Alice, and so on until one is left. What is Alice's best course of action?

The solution is that Alice is better of missing than hitting Carol or Bob, so she should shoot into the air. Indeed, then Bob will shot Carol, and it can be shown that it gives the greatest probability of survival for Alice. But I wonder if Bob should not voluntary shoot into the air too, so that Carol will do the same, and no one be shot. If this is the case, Alice survival probability is 1. What do you think of it? What is Alice survival probability?

To maximise their chances the duellists prefer to be left with a weaker opponent. So Bob would not shoot at Alice in preference to Carol, and Carol will not shoot at Alice in preference to Bob. Therefore Alice will not be shot at until Bob or Carol is dead and she will either be left standing with Bob or Carol, with or without the shot.

Probability of Alice, with shot, surviving against Bob is given by:

p = Pr(A hits B) + Pr(A misses B) * Pr (B misses A) * p
p = 1/3 + 2/3 * 1/3 * p
p = 3/7

Probability of Alice, without shot, surviving against Bob is given by:

p = Pr(B misses A) * (Pr(A hits B) + Pr (A misses B) * p)
p = 1/3 * (1/3 + 2/3 * p)
p = 1/7

Probability of Alice, with shot, surviving against Carol is given by:

p = Pr(A hits C) + Pr(A misses C) * Pr (C misses A) * p
p = 1/3 + 2/3 * 0 * p
p = 1/3

Probability of Alice, without shot, surviving against Carol is given by:

p = Pr(C misses A) * (Pr(A hits C) + Pr (A misses C) * p)
p = 0 * (1/3 + 2/3 * p)
p = 0

So, her probability of surviving from each position is:

Bob, with shot: 3/7
Carol, with shot: 1/3
Bob, without shot: 1/7
Carol, without shot: 0

So Alice is best off not killing anyone since the advantage she gains by having the first shot exceeds any possible benefit of facing Bob rather than Carol. She should shoot into the air.

Given that Alice is neither going to shoot at them, or be shot at by them until one is dead, Bob and Carol are essentially in a two person duel, the winner to face Alice. They cannot improve their chances by forgoing a shot, so they shoot. Bob wins that 2/3 of the time, Carol 1/3.

Alice wins 2/3 * 3/7 + 1/3 * 1/3 = 25/63.
Bob wins 2/3 * 4/7 = 24/63.
Carol wins 1/3 * 2/3 = 14/63.

If Alice shoots in the air and under the assumption that Bob shoots Carol than Alice has a huge probability to survive the game.

BUT:
However if Bob shoots himself in the second round then Alice is basically death and Carol has a higher probability to win this game. So under the assumption that carol want to survive, she should shoot in the air. Under this thought I think your solution is much more justified.

If all the others shoot in the air and continue until infinity(I cannot see a restriction for bullets). Then thats her highest probability.


Grand Prix Race- Differential Equations Driver A has boon leading archrival B for a while by a steady 3 miles. Only 2 miles from the finish, driver A ran out of gas and decelerated thereafter at ta rate proportional to the square of his remaining speed. One mile later,driver A's speed was exactly halved.If driver B's speed remained constant,who won the race?

Let $A(t)$ be the distances from the finish of $A$ at time $t$ from when A runs out of gas, and the initialy velocity of $A$ and $B$ be $v$. Then $B$ takes a time of $\frac{5}{v}$ to reach the finish.

$A(0)=0 \ , \ A'(0)=-v$

$\frac{\mathrm{d}^2A}{\mathrm{d}t^2}=k(\frac{\mathrm{d}A}{\mathrm{d}t})^2\\$

Seperation of variables to find $\frac{\mathrm{d}A}{\mathrm{d}t}$ followed by integration gives $A(t)=c_1t+\frac{kt^4}{12}+c_2$.

From the boundary conditions, $c_2=2 \ \ c_1=-v$.

Where $A(t)=1, \ \frac{\mathrm{d}A}{\mathrm{d}t}=\frac{v}{2}$. Hence $v=\frac{2kt^3}{3}, \ t^4=\frac{12}{7k}$ and $k^4=0.534v$.

I cannot answer the question without knowing $v$, but the time taken by $a$ is just the solution to $A(t)=0$.

The real solution (long for dummies answer):

   Just to let the audience know, the answer to this exercise is "A wins" (as stated in the solutions page in the back of the book where this is taken from <not sure if I can place the name of the book here>).

By far a simple exercise (and no more information is needed), let's start by knowing a simple diagram to set the time and space starting points.

The starting point of the $x$ function is the point where car A (the blue car) runs out of gas.

For driver B (In green and white car):

Note: This is a long procedure to probe (the obvious) that car B will take $t=\frac{5}{V_I}$ to get to the finish line.

Acceleration of driver B is zero as it goes at a constant speed (let's call it $V_I$).

$a_B(t)=0$

$\frac{dv_B}{dt}=0$

After solving the differential equation:

$v_B(t)=V_I$

Also, we know that $v_B$ = $\frac{dx_B}{dt}$:

$\frac{dx_B}{dt}=V_I$

Solving the differential equation we have:

$x_B(t)=V_It+C_0$

We know that $x(0)=-3$ with $x$ in miles:

$-3=C_0$

Thus, the space expression for driver B is:

$x_B(t)=V_It-3$

And with this we have the expected situation, car B will take $t_{B_{finishes}}=\frac{5}{V_I}$ to get to the finish line.

For driver A (In blue car):

As "A ran out of gas and decelerated thereafter at a rate proportional to the square of his remaining speed":

$a_A(t)=\frac{dv_A}{dt}=-kv^2$

Solving the differential equation we have:

$\frac{1}{kv}=t+C\hspace{1cm}$       $\therefore$        $\hspace{1cm}v_A(t)=\frac{1}{kt+C_1}$ $\hspace{1cm}$where $C_1=kC$

And we can use a initial condition here $v_A(0)=V_I$:

$v_A(0)=V_I=\frac{1}{0k+C_1}\hspace{1cm}$ $\therefore$ $\hspace{1cm}C_1=\frac{1}{V_I}$

then:

$v_A(t)=\frac{1}{kt+\frac{1}{V_I}}\hspace{5cm}(1)$

But also we know (as with driver B, physics laws don't change here) that $\frac{dx_A}{dt}=v_A$, thus:

$\frac{dx_A}{dt}=\frac{1}{kt+\frac{1}{V_I}}$

Solving the differential equation (with x in miles, obviously):

$x_A(t)=\frac{\ln\left(kt+\frac{1}{V_I}\right)}{k}+C_2\hspace{1cm}$ or $\hspace{1cm}x_A(t)=\frac{\ln\left(kt+\frac{1}{V_I}\right)+C_3}{k}\hspace{1cm}$ where $\hspace{1cm}C_3=C_2k$

Now, we know that at $t=0$ the drive A is at $x=0$, so:

$0=\frac{\ln\left(\frac{1}{V_I}\right)+C_3}{k}$

And this give us that:

$C_3=-\ln\left(\frac{1}{V_I}\right)$

Then:

$x_A(t)=\frac{\ln\left(kt+\frac{1}{V_I}\right)-\ln\left(\frac{1}{V_I}\right)}{k}$

And finally, after some operations:

$x_A(t)=\frac{\ln(V_Ikt+1)}{k}\hspace{4.5cm}(2)$

At this point the problem is basically solved, we know that at $x_A=1$ the value of $v_A=\frac{V_I}{2}$, so ($t_b$ is the time at which driver A have driven one mile after he ran out of gas):

$1=\frac{\ln(V_Ikt_b+1)}{k}$

This expression in terms of $t_b$ is:

$t_b=\frac{e^k-1}{V_Ik}$

This is the time at which driver A will have halved the constant speed, so:

$\frac{V_I}{2}=\frac{1}{k\left(\frac{e^k-1}{V_Ik}+\frac{1}{V_I}\right)}$

A few operations lead to $e^k=2$ so $k\approx0.6931$, then:

$x_A(t)=\frac{ln(0.6931V_It+1)}{0.6931}$

Now time for $x_A=2$:

$2=\frac{ln(0.6931V_It_{A_{finishes}}+1)}{0.6931}$

And clearing $t$:

$t_{A_{finishes}}=\frac{4.327835}{V_I}$

And as $t_{A_{finishes}}<t_{B_{finishes}}$ then A wins.


the least value for $m\ge 2005$ such that $a_{m+1}-1\mid a^2_m-1$ If we assume that  $a_1=3$  and for every $n\ge1$  we assume that $a_{n+1}=(n+1)\cdot a_n-n$.How to find the least value for $m\ge 2005$ such that $a_{m+1}-1\mid a^2_m-1$

Note that
$$ a_{n+1}-1=(n+1)(a_n-1) $$
so the question becomes:

Find the least value $m \geq 2005 $ such that $m+1 | a_m+1$

With a small amount of effort, the first formula can give you an explicit formula for $a_n$.


What is mathematical logic? What does mathematical logic mean?

In the book Analysis 1 by Terence Tao, it says:

  The purpose of this appendix is to give a quick introduction to
  mathematical logic, which is the language one uses to conduct
  rigourous mathematical proofs.

Checking Wikipedia:

  Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory.

This seems like a completely different definition. Why, for example, is set theory considered part of logic?

Mathematical logic is a strange beast.

It is a perfectly ordinary branch of mathematics whose goal is ... to study mathematics itself.

Thus, the different branches of mathematical logic are devoted to the study of some basic building blocks of mathematical practice : language, model, proof, computation.

Modern mathematical logic is "mathematical" also in another sense: some branches of it are simply mathematical disciplines, like e.g. Computability theory and Constructive mathematics,


Box with chocolates probability I am given a box with 20 chocolates, all of them identical from the outside but 5 of them are with cherry filling, 7 with cream and 8 with nuts.
  I ate 10 at random. What is the probability I ate at least one of each kind?

My attempt: All different ways to select 10 chocolates out of 20 are
$C(20,10)$.
Then the required probability is
$1 - ( C(12,10)+C(13,10)+C(15,10) ) / C(20,10)$

I am getting about 98% but this doesn't seem correct to me...

Any ideas?

Let $A$ be the event that I did not eat any with cherry filling.

Let $B$ be the event that I did not eat any with cream.

Let $C$ be the event that I did not eat any with nuts.

Then with inclusion/exclusion we find:

$$P\left(A^{\complement}\cap B^{\complement}\cap C^{\complement}\right)=1-P\left(A\cup B\cup C\right)=$$$$1-P\left(A\right)-P\left(B\right)-P\left(C\right)+P\left(A\cap B\right)+P\left(A\cap C\right)+P\left(B\cap C\right)-P\left(A\cap B\cap C\right)$$

But the events that differ from $A,B,C$ are all empty so that we can
simplify:

$$P\left(A^{\complement}\cap B^{\complement}\cap C^{\complement}\right)=1-P\left(A\right)-P\left(B\right)-P\left(C\right)=\frac{\binom{20}{10}-\binom{15}{10}-\binom{13}{10}-\binom{12}{10}}{\binom{20}{10}}$$
showing that your solution is correct.

Yeah, you're right, in general case, you have to use inclusion-exclusion principle to account for situations where you take only one type of sweet for example but no worries here because there is no possibility to choose from only one type.

In general we have something like:

P(not all types taken) = P(taken only from 1 and 2) + P(taken only from 2 and 3) + P(taken only from 3 and 1) - P(taken only from 1) - P(taken only from 2) - P(taken only from 3).

And to feed your intuition, check expected value of each of chocolate type.


Proof of Bound for Growth of Divergent Trajectory in $3x+1$ Problem In this paper, Lagarias makes the following claim in section 2.7 (Do divergent trajectories exist?).

Context

$$T(x) = \left\{ \begin{array}{rl} \dfrac{3x + 1}{2}, & 2 \nmid x \\ \dfrac{x}{2}, & 2 \mid x \end{array} \right.$$

$$\begin{align*} \tag{2.30} \lim_{k \to \infty} |T^{(k)}(n_0)| = \infty \end{align*}$$

Claim

If a divergent trajectory $\{T^{(k)}(n_0) : 0 \leq k < \infty\}$ exists, it cannot be equidistributed $\pmod{2}$. Indeed if one defines

$N^*(k) = |\{j : j \leq k \mathrm{\ and\ } T^{(j)}(n_0) \equiv 1 \pmod{2}\}|$,

then it can be proved that the condition (2.30) implies that

$$\begin{align*} \tag{2.31} \liminf_{k \to \infty} \dfrac{N^*(k)}{k} \geq (\log_2 3)^{-1} \approx .63097 \end{align*}$$

Question

How can this statement be proved?

Difficulty

It seems like the author may be ignoring the $+1$ term under the assumption that the factors will dominate. (I've seen this assumption made often for heuristic arguments for the truth of the Collatz conjecture.) I don't see how such an assumption can be justified.

Given any length $n$ sequence of $n - k$ zeros and $k$ ones, we can find an $x \in \mathbb{N}$ such that

$$T^n(x) = \dfrac{3^k x + m}{2^n}$$

where

$$3^k - 2^k \leq m \leq 2^{n-k}(3^k - 2^k)$$

Now, suppose, for example, $n = 2k$. Then, we have the bound

$$T^n(x) \leq \dfrac{3^k x + 2^{n-k}(3^k - 2^k)}{2^n} = \left(\dfrac{3}{4}\right)^k x + \left(\dfrac{3}{2}\right)^k - 1$$

and the exponential "$+1$" term dominates for large $n$. Now, of course, $m$ won't always be as large as possible, but even if we look at "random" $m$, that only introduces a constant factor in front of the exponential.

Additional Questions

Is the proof of this statement difficult? Is that why the author doesn't include it? Is there a paper containing a proof?

I contacted the author, and he was kind enough to write up a proof for me. I have attempted to simplify his proof for presentation here. I also use some notation without explanation to reduce clutter; the meanings should be clear. The trick is to use an apparently well known result from lattice theory.
Proposition 1 (Lattice Theory rotation trick)
If $b_1, b_2, \ldots, b_\ell$ are real numbers such that
\begin{align*}
   b_1 + b_2 + \cdots + b_\ell = r \ell
  \end{align*}
($\ell \geq 2$) then the lattice path
\begin{align*}
   (0, 0), (1, b_1), (2, b_1 + b_2), \ldots, (\ell, b_1 + b_2 + \cdots + b_\ell) = (\ell, r \ell)
  \end{align*}
has a cyclic forward shift by some $k$ with $0 \leq k \leq \ell - 1$
\begin{align*}
   (0, 0), (1, b_{k+1}), (2, b_{k+1} + b_{k+2}), \ldots, (\ell, b_{k+1} + b_{k+2} + \cdots + b_\ell + b_1 + b_2 + \cdots + b_k) = (\ell, r \ell)
  \end{align*}
so that
\begin{align*}
   b_{\overline{k+1}} + b_{\overline{k+2}} + \cdots + b_{\overline{k+j}} \leq jr
  \end{align*}
for all $1 \leq j \leq \ell$, where $\overline{k+i} \equiv k + i \pmod{\ell}$ and $1 \leq \overline{k+i} \leq \ell$.
Proof
Let $k$ be the smallest index such that the point $(k, b_1 + b_2 + \cdots + b_k)$ is not above the line $y = rx$ and the distance between this point and the line is maximum. Notice that $k \leq \ell - 1$ by the extreme value theorem.
Corollary 2
If $n_1 < n_2 < \ldots < n_k$ and $r = n_k/k$, then there is some $\hat{k}$ with $1 \leq \hat{k} \leq k - 1$ such that
\begin{align*}
    n_{k-\hat{k}+1} - n_j \geq (k - \hat{k} + 1 - j) r
   \end{align*}
for all $1 \leq j \leq k - \hat{k}$.
Proof
Apply Propositon 1 to the sequence
\begin{align*}
   b_1 = n_k - n_{k-1}, b_2 = n_{k-1} - n_{k-2}, \ldots, b_{k-1} = n_2 - n_1, b_k = n_1
  \end{align*}
Lemma 3 (bound on additive term)
For odd $x \in \mathbb{N}$, suppose that
\begin{align*}
   T^n(x) = \dfrac{3^k}{2^n}x + e(x, k)\;\;\;\;\; e(x, k) = \sum_{i=0}^{k-1} \dfrac{3^i}{2^{n_k - n_{k-1-i}}}
  \end{align*}
where $r = n/k \geq \log_2 3$. Then there is a $1 \leq \hat{k} < k$ such that
\begin{align*}
   e(x,k-\hat{k}) \leq \dfrac{1}{2^r - 3}
  \end{align*}
Proof
Let $r = n/k = (\log_2 3)(1 + \delta)$, where $\delta > 0$, and apply Corollary 2 to $0 = n_0 < n_1 < \cdots < n_{k-1}$ to find an index $\hat{k}$ such that $1 \leq \hat{k} < k$ and
\begin{align*}
   n_{k-\hat{k}} - n_{j-1} \geq (k - \hat{k} - j + 1)r
  \end{align*}
for all $1 \leq j \leq k - \hat{k}$. Then,
\begin{align*}
   2^{n_{k-\hat{k}} - n_{i-1}} \geq 2^{(k-\hat{k}-i+1)r} = 3^{(k-\hat{k}-i+1)(1+\delta)}
  \end{align*}
and
\begin{align*}
   e(x, k - \hat{k}) & = \sum_{i=1}^{k-\hat{k}} \dfrac{3^{k-\hat{k}-i}}{2^{n_{k-\hat{k}}-n_{i-1}}} \\
    & \leq \sum_{i=1}^{k-\hat{k}} \dfrac{3^{k-\hat{k}-i}}{3^{(k-\hat{k}-i+1)(1 + \delta)}} \\
    & = \dfrac{1}{3} \sum_{i=1}^{k-\hat{k}} \dfrac{1}{3^{(k-\hat{k}-i+1)\delta}} \\
    & \leq \dfrac{1}{3^{1+\delta} - 3} \\
    & = \dfrac{1}{2^r - 3}
  \end{align*}
Remark
The key fact about Lemma 3 is that the bound is independent of both $x$ and $e(x,k)$, depending only on the value of $r = n/k$. It achieves this by making the choice $\hat{k}$ that depends on $x$ and showing that such a choice must exist for every $x$ with $r \geq \log_2 3$. This is the ``trick."
Theorem 4
If $x, T(x), T^2(x), \ldots$ is a divergent trajectory with
\begin{align*}
   k(x, n) = |\{T^j(x) \equiv 1 \pmod{2} : 0 \leq j < n\}|
  \end{align*}
then
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x, n)}{n} \geq \log_3 2
  \end{align*}
Proof
Since $x$ has a divergent trajectory, there must be a sequence $y_0 < y_1 < y_2 < \cdots$ such that $y_j = T^{n_j}(x)$, for some natural numbers $n_0 < n_1 < n_2 < \cdots$, and such that $T^n(y_j) > y_j$ for all $n \in \mathbb{N}$. For each (fixed) $y_j$, we have
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x, n)}{n} = \liminf_{n \to \infty} \dfrac{k(x, n) - k(x, n_j)}{n - n_j} = \liminf_{n \to \infty} \dfrac{k(y_j, n)}{n}
  \end{align*}
Now, suppose that
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x, n)}{n} < \log_3 2
  \end{align*}
Then, there is some constant $c$ such that
\begin{align*}
   \dfrac{k(x, n)}{n} \leq \dfrac{1}{c} < \log_3 2
  \end{align*}
infinitely often, and, in particular, for each $y_j$, there is always an $n$ such that
\begin{align*}
   \dfrac{k(y_j, n)}{n} \leq \dfrac{1}{c} < \log_3 2
  \end{align*}
Let $d = c - \log_2 3 > 0$. Then, $n \geq k(y_j, n)(\log_2 3 + d)$ implies
\begin{align*}
   2^n \geq 3^{k(y_j, n)} 2^{kd} \geq 3^{k(y_j, n)} 2^d \iff \dfrac{3^{k(y_j, n)}}{2^n} \leq 2^{-d}
  \end{align*}
Let $r = n/k(y_j, n) \geq c$. Applying Lemma 3, we have an $n^*$ such that
\begin{align*}
   T^{n^*}(y_j) \leq 2^{-d} y_j + \dfrac{1}{2^r - 3} \leq 2^{-d} y_j + \dfrac{1}{2^c - 3}
  \end{align*}
where the values $c$ and $d$ are constant across all the $y_j$ (i.e., for each $y_j$, there is an $n^*$ such that the bound holds). Since $2^{-d} < 1$ and $y_j$ grow unbounded, there is a
\begin{align*}
   y_j > \dfrac{1}{(2^c - 3)(1 - 2^{-d})}
  \end{align*}
at which point
\begin{align*}
   T^{n^*}(y_j) < y_j
  \end{align*}
contradicting our construction of the $y_j$ and proving
\begin{align*}
   \liminf_{n \to \infty} \dfrac{k(x,n)}{n} \geq \log_3 2
  \end{align*}
Remark
If you find any errors in the above, it is almost certainly from my attempt to simplify the proof I was given and not from the author.

The "+1" term is just included in the bound,
$$3^{N^*(k)}\leq\frac{T^{(k)}(n_0)}{n_0}2^{k}$$

see construction here: A possible way to prove non-cyclicity of eventual counterexamples of the Collatz conjecture?

If you start with this:

$$T^{(k)}(n_0) = \frac{3^{N^*(k)}}{2^{m_1+m_2+...+m_i}}\cdot n_0+\frac{3^{N^*(k)-1}}{2^{m_1+m_2+...+m_i}}+\frac{3^{N^*(k)-2}}{2^{m_1+m_2+...+m_{i-1}}}+...+\frac{3^0}{2^{m_1}}$$
see construction here: $(n_0) \to (n_i)$ and $(n_0+k\cdot2^j)\to(n_i+k\cdot3^i)$, same Glide?

This can be simplified to
$$T^{(k)}(n_0) = \frac{3^{N^*(k)}}{2^k}\cdot n_0+\alpha N^*(k)$$
where $\alpha < \frac{1}{3}$ as shown in this paper: https://arxiv.org/abs/1710.01525v1

$$2^k = 3^{N^*(k)}\frac{n_0}{T^{(k)}(n_0)-\alpha N^*(k)}$$
$$k = N^*(k)\log_23+\log_2(\frac{n_0}{T^{(k)}(n_0)-\alpha N^*(k)})$$

Now as long as $T^{(k)}(n_0)-\alpha N^*(k)>=n_0$

$$k \leq N^*(k)\log_2(3)$$
$$\frac{N^*(k)}{k} \geq \frac{1}{\log_23}$$

I didn't check Theorem F, but i guess this is linked to his remark "cannot go too slowly"


Showing Mahonian triangle numbers related to inversion probability From this OEIS page about Triangle of Mahonian numbers:

http://oeis.org/search?q=+A008302&language=english&go=Search

I know 2 things:

That the  $T(n,k)$ can be generated by the coefficients in expansion of $$\prod_{i=0..n-1} (1 + x + ... + x^i)$$, where $k$ ranges from $0$ to A000217(n-1).
$T(n,k) :=$ number of permutations of $\{1,\ldots,n\}$ with $k$ inversions.

But can you please connect these two distinct ideas, i.e. why would the coefficients of this product of polynomials give the number of inversions of a set of consecutive integers? How are these two things related?

When you multiply $$\prod _{i=0}^{n-1} \sum _{j=0}^i x^j=1(1+x)\cdots (1+x+\cdots +x^{n-1}),$$ what you get as coefficient of $x^k$ is $|\{(a_1,\cdots , a_n):a_i<i \wedge \sum a_i = k\}|$ because of Cauchy product(i.e., $$(\sum _{i=0}^n a_i x^i)(\sum _{i=0}^m a_i x^i)=\sum _{ i = 0}^{n+m}(\sum _{\substack{r+s=i\\ r\leq n\\ s\leq m}}a_rb_s)x^i$$)
Now take a permutation $\pi\in S_n$ with $k$ inversions and denote $A_i = |\{j:j<i \wedge \pi _i < \pi _j\}|,$ so $\sum A_i = k,$ because you are doing a partition of the inversion pairs and $A_i<i$ because $0\leq j<i.$

Hope it helps.

To give a more intuitive and less strict approach:
Claim: There is a bijection with permutations of length $n$ and $n$-tuples $(c[1], c[2], \dots, c[n])$, with $0 \le c[i] \le n - i$ for each $i$.
For each permutation $(p[1], p[2], \dots, p[n])$, let's assign
$(c[1], c[2], \dots, c[n])$, where $c[i] = \#\{j > i: p[i] > p[j]\}$. In other words, $c[i]$ counts number of inversions with $i$ being the first member of the pair. Note the property of this tuple: $c[i] \le n - i$ (as there are only $n-i$ other members to it's right). Let's call tuples that satisfy $0 \le c[i] \le n - i$ valid.
Crucial idea is that we can uniquely go in a reverse direction too: for a given valid n-tuple, there's a unique permutation that corresponds to it (easy to prove by construction recursively).
This means there's a bijection, and the number we're looking for is same as the number of valid tuples. Now let's use generating functions to count this: for each $i$, define $G[i](x) = \sum _ {j = 0}^{n - i} x^j$. Multiplying all $G[i]$'s with each other and finding coefficient of $x^k$ gives the desired quantity. (Note that after multiplying all $G[i]$ and rearranging terms, we get the same product as mentioned in the question above).


Holder condition for $x^\beta$ Let $f(x)=x^\beta$ (for some fixed $0<\beta<1$) be defined on $(0,1)$. It's not hard to see that $f$ is $\beta$-Holder.

  How can I prove that $x^\beta$ is not $\alpha$-Holder for $\beta<\alpha<1$?

It's enough to use a counter example, say $x_1 = 0$, $x_2 = 0.5$ then we have that

$$ |0^\beta -0.5^\beta| \leq |0.5|^\beta$$

but the LHS you will see equals to $0.5^\beta$. Then for any $\alpha >\beta$ you'll see that $0.5^\beta > 0.5^\alpha$, so it can't be $\alpha$ - Holder for $\beta < \alpha < 1$

Using the value of $0$ is ok because $x^\beta$ us also $\beta$ - continuous on $[0,1]$...

If you don't like that to see the argument still holds instead of $0$ use a small $\epsilon$ in it's place. Then if $f(x)$ is $\alpha$ - Holder then we would have

$$ |\epsilon^\beta - 0.5^\beta| \leq |\epsilon - 0.5|^\alpha.$$

Take the limit as $\epsilon \rightarrow 0$ then you have a contradiction.


Several algebras in conditional and join probabilities There are several cases in combining conditional and joint probabilities, I get confused to show them if there are correct:

Given $A, B, C$ are random variables, $P(A|B)$ denotes conditional probability and $P(B, C)$ denotes joint probability.

$P((A|B)|C) = P(A|(B, C))$

We have: $P((A|B)|C) = \frac{P((A|B), C)}{P(C)}$. This requires following

$P((A|B), C) = P(A|(B, C))P(C)$

If the equality holds, there would be no ambiguity with $P(A|B, C)$

We can to understand $\Bbb{P}(A \vert B) = \Bbb{E}[1_A |\sigma(1_B)](\omega)$ for any $\omega \in B$.

In that sense one would interpret $\Bbb{P}((A \vert B) \vert C) = \Bbb{E}\Bbb{E}[1_A |\sigma(1_B)] \vert \sigma(1_C)](\omega)$ for $\omega \in B \cap C$

$$\Bbb{P}((A \vert B) \vert C) = \Bbb{E}\Bbb{E}[1_A |\sigma(1_B)] \vert \sigma(1_C)](\omega) = \Bbb{E}\Bbb{E}[\Bbb{E}[1_A |\sigma(1_B, 1_C)] |\sigma(1_B)] \vert \sigma(1_C)](\omega) = \Bbb{E}\Bbb{E}[1_A |\sigma(1_B, 1_C)] \vert \sigma(1_C)](\omega) = \Bbb{E}[1_A |\sigma(1_B, 1_C)](\omega) = P(A \vert B,C)  $$

Note $\Bbb{E}[1_A\vert \sigma(1_B)]$ is a random variable
$$\Bbb{E}[1_A\vert \sigma(1_B)] = P(A\vert B) 1_B + P(A\vert B^c)1_{B^c} $$

The relation we used for conditional expectations was this one.

$$\mathcal{G} \subset \mathcal{F} \Rightarrow\Bbb{E}[\Bbb{E}[1_A |\mathcal{G}] |\mathcal{F}] = \Bbb{E}[\Bbb{E}[1_A |\mathcal{G}]$$

where $\mathcal{F},\mathcal{G}$ are sigma algebras.

Note that we are understanding $P(A\vert B,C) = \Bbb{E}[1_A |\sigma(1_B, 1_C)]$ wich is different than $\Bbb{E}[1_A |\sigma(1_B 1_C)]$ to finally get a number we write

$$\Bbb{E}[1_A |\sigma(1_B, 1_C)] = P(A\vert B \cap C)1_{B \cap C} + P(A\vert B^c \cap C)1_{B^c \cap C} + P(A\vert B \cap C^c)1_{B \cap C^c}+ P(A\vert B^c \cap C^c)1_{B^c \cap C^c}$$

So you define $P(A \vert B,C) = \Bbb{E}[1_A |\sigma(1_B, 1_C)] (\omega)$  for any $\omega \in B \cap C$

As you would have defined $P(A\vert B) = \Bbb{E}[1_A |\sigma(1_B)](\omega)$ for any $\omega \in B$


the meaning of the notation behind derivatives In Calculus, we are taught $\frac{dy}{dx}$ (first derivative), $\frac{d^2y}{dx^2}$ (second derivative), ..., $\frac{d^ny}{dx^n}$ ($n$-th derivative) respectively. Am wondering does the notion of a $\frac{d^my}{dx^n}$ ($m\neq n$) exist? what does that mean? any approachable, understandable reference you can cite for me (a non-mathematician, math hobbyist at best) to learn these concepts clearly from basic principles? Thank you.

The notation is reminiscent of that for differences. The thing is that the first difference of a function $\Delta f=f(x+\Delta x)-f(x)$ is typically of the same order of $\Delta x$ (it is so at points where $f$ is differentiable and $f'(x)\neq 0$. If you consider the second difference $\Delta^2f=\Delta f(x+\Delta x)-\Delta f(x)$ (a difference of differences) it is a smaller infinitesimal, typically of the order of $\Delta x^2$, etc. This is why the interesting limits are the limits of $\Delta f/\Delta x$, $\Delta^2f/\Delta x^2$, etc. which are precisely the corresponding derivatives. If you divide $\Delta^2f/\Delta x^3$ you get infinity in the limit, if you divide $\Delta^2f/\Delta x$ you get zero because the infinitesimals have different orders. This is why $d^nf/dx^m$ with $n\neq m$ is not an interesting object, unless.. at a critical point you have $f'(x)=0$ and $\Delta f$ happens to be typically quadratic. Then, it makes sense to look at $\lim \Delta f/\Delta x^2$ which is equal to $f''(x)/2$ (just do Taylor expansion).  At certain singular points such mixed objects are finite and make perfect sense.

Nowadays they teach you that $df/dx$ is just a symbol and not a fraction. This is really sad, since the connection to differences is lost, not to mention the intuition behind the concept. There are fashions in Math like in anything. $df/dx$ is not a fraction now, but it was a fraction for the Mathematicians who created all the fundamentals of infinitesimal calculus in the XVIII and XIX centuries.


how are $m^{**}(E)$ and $m^{***}(E)$ related to $m^{*}(E)$? Let $A$ be a set and define

$m^{**}(A) \in [0,\infty] $ by
$m^{**} (A)= \inf\{m^{*}(\mathcal{O}) \ | \ A \subset \mathcal{O}, \mathcal{O} \ \text{open}  \} $.

And

$m^{***}(A) = \sup \{m^*(F) \mid F \subset A, F$ is closed $\}$.

Show how are $m^{**}(E)$ and $m^{***}(E)$ related to $m^{*}(E)$?

References are from your textbook Real Analysis, Royden and Fitzpatrick, fourth edition.
$\mathcal O$ covers $A$ and, by Proposition 9 of Section 1.4, is the union $\bigcup_{k=1}^\infty I_k$ of a countable collection of open intervals. By Propositions 3 and 1, $m^*(\mathcal O)\le\sum_{k=1}^\infty\ell(I_k)$. Then the definitions of $m^{**}$ and $m^*$ coincide. Thus, $m^{**} = m^*$.
If $A$ is measurable, $m^{***}(A)\ge m^*(F) > m^*(A) -\epsilon$ where the first inequality comes from the definition of $m^{***}$, and the second from Theorem 11(iii), which guarantees the existence of such a set $F$. Because that compound inequality holds for each $\epsilon > 0$, it holds also for $\epsilon = 0$. Hence, $m^{***}(A)\ge m^*(A)$. By monotonicity and Problem 22, we also have $m^{***}(A)\le m^{**}(A) = m^*(A)$ because $F\subseteq A\subseteq\mathcal O$. Thus, $m^{***} = m^*$.
If $A$ is not measurable, then by the contrapositive of Problem 17, there is a $\delta > 0$ such that $m^*(\mathcal O \sim F)\ge\delta$ for all $F,\mathcal O$, that is, $m^*(F) +\delta\le m^*(\mathcal O)$. For $\epsilon_1,\epsilon_2 > 0$, there are particular $F,\mathcal O$ for which $F\subseteq A\subseteq\mathcal O$ and $m^{***}(A) +\epsilon_1\le m^*(F)$, $m^*(\mathcal O) < m^*(A) +\epsilon_2$ by the definitions of $m^{***},m^*$ (see the remark on page 43). Compound those last three inequalities to get $m^{***}(A) +\epsilon_1\le m^*(F) +\delta\le m^*(\mathcal O) < m^*(A) +\epsilon_2$. Because that holds for each $\epsilon_1,\epsilon_2 > 0$, it holds also for $\epsilon_1,\epsilon_2 = 0$. Thus, $m^{***} < m^*$.

Solution: Let $E \in B( \Bbb R)$ let $C$ be an arbitary closed set and $O$ be an arbitrary open set in $\Bbb R$ such that $C \subset E \subset O$. So $m^*(C) \leq m^*(E) \leq m^*(O).$

Since $C$ is arbitary, we have $m^*(E) \leq \inf\{m^{*}(O \ | \ E \subset O, O \ \text{open}  \}  = m^{**} (E)$.

And since $O$ is arbitrary we have, $m^{***}(E) = \sup \{m^*(C) \mid C \subset E, C \ \text{is closed } \} \leq m^*(E)$


Does there exist a polynomial $p(x)$ of degree $n$, with complex coefficients, such that $p(k)=1/k$ for each integer $k$ satisfying $1\le k\le n+2$? This is the problem I am trying to solve:

Does there exist a polynomial $p(x)$ of degree $n$, with complex coefficients, such that $p(k)=1/k$ for each integer $k$ satisfying $1\le k\le n+2$?

I have come to the conclusion that no such polynomial exists but I don't know how to prove it? Perhaps by contradiction?

Thank you.

We know that
$$p(z)-\frac{1}{z}=\frac{zp(z)-1}{z}$$
on $\mathbb{C}-\{0\}$. Now we see the polynomial $zp(z)-1$ of degree $n+1$ must have $n+2$ zeroes, namely $1,..,n+2$. This is only possible if $zp(z)-1=0$, so if $p(z)=\frac{1}{z}$, clearly a contradiction since any polynomial is continuous at $0$.

Proof by contradiction can certainly be an approach to this question. Here's one way to do it using Calculus. Assume such a polynomial $p$ exists, and define $\displaystyle F(x)=p(x)-\frac{1}{x}$. This function is continuous and differentiable on $\displaystyle \left[\frac{1}{n+2},1\right]$ and has $n+2$ roots on this interval because $F(1)=F(2)=\cdots=F(n+2)=0$ by assumption. By Rolle's Theorem, between each pair of roots there exists at least one point $c$ such that $F'(c)=0$. Thus we can conclude that

$$F'(x)=p'(x)+\frac{1}{x^2} \text{ has at least } n+1 \text{ roots on } \left[\frac{1}{n+2},1\right].$$

By the same token:

$F''(x)$ has at least $n$ roots in this interval;
$F'''(x)$ has at least $n-1$ roots in this interval;
…
$F^{(n+1)}(x)$ has at least $1$ root in this interval.

But since the $(n+1)$-st derivative of an $n$-th degree polynomial is identically zero, $\displaystyle F^{(n+1)}(x)=p^{(n+1)}(x)+\frac{d^{n+1}}{dx^{n+1}}\left(\frac{1}{x}\right)=\frac{(-1)^{n+1}(n+1)!}{x^{n+2}}$, and it does not have any roots — hence the contradiction.

I think a different proof can be constructed using Lagrange's interpolation formula, but I didn't work it out. The idea is that an $n$-th degree polynomial is completely determined by its values at $n+1$ distinct points. But here we've been prescribed $n+2$ values, which is one too many.


How to model and solve the variant of Monty Hall problem in which the host opens a door randomly? The Monty Hall problem (wiki) is described as follows:

  Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

In the analysis, it reads,

  Most people come to the conclusion that switching does not matter because there are two unopened doors and one car and that it is a 50/50 choice. This would be true if the host opens a door randomly, but that is not the case; the door opened depends on the player's initial choice, so the assumption of independence doesn't hold.

I am interested in the variant in which the host opens a door randomly and try to formalize it.

First, it is crucial to explicitly identify the assumptions for this variant:

$A_1:$ The host must always open a door that was not picked by the contestant.
$A_2:$ The host must always offer the chance to switch between the originally chosen door and the remaining closed door.
$A_3:$ The host does not know what lies behind the doors and opens one at random that happens not to reveal the car.

By Bayes' theorem, we can obtain that

\begin{align*}
    \Pr\{C_2 \mid H_3, Y_1\} = \frac{\Pr\{H_3 \mid C_2, Y_1\}}
      {\Pr\{H_3 \mid C_1, Y_1\} + \Pr\{H_3 \mid C_2, Y_1\} + \Pr\{H_3 \mid C_3, Y_1\}},
  \end{align*}

where, the event $C_i$ denotes that the car is behind the door $i$, $Y_1$ denotes that you pick door 1, and $H_3$ denotes that the host opens door 3 and happens to reveal a goat.

Therefore, the task is to assign probabilities to $\Pr\{H_3 \mid C_1, Y_1\}$, $\Pr\{H_3 \mid C_2, Y_1\}$, and $\Pr\{H_3 \mid C_3, Y_1\}$.

Questions:

Are the three assumptions correct and sufficient to characterize the situation where the host opens a door randomly?
Should the assumption $A_3$ enforce the requirement that "... happens not to reveal the car"? Similarly, should the event $H_3$ specify that "... happens to reveal a goat"?
How to assign probabilities to $\Pr\{H_3 \mid C_1, Y_1\}$, $\Pr\{H_3 \mid C_2, Y_1\}$, and $\Pr\{H_3 \mid C_3, Y_1\}$?

If the host opens a door without knowledge and behind that door a goat is found then the new situation is that you can choose from two doors that have equal probability (so both $0.5$) to hide a car.

To come to this conclusion plain thinking is enough and the rule of Bayes is not needed.

There is no profit in changing your original choice and no profit in keeping to it.

It does not matter if Monty knows where the prize is or not.

Trying to work what Monty knows or doesn’t know into the problem is a tempting (apparently) but needless distraction.

This is all there is to the Monty Hall problem:
What’s the probability the prize is behind the doors you didn’t pick? Does this probability depend upon whether those doors are opened simultaneously or in sequence? I think you might agree that it doesn’t. So as doors (say there are N doors to start with, not necessarily limited to 3) are opened, the probability that the prize is in the group of doors you didn’t pick remains the same. Which means that the probability it’s behind the door you did pick also remains the same. That’s all you need to know.


Quotient a group by a proper subgroup. If you have a group $G$ and a proper subgroup $H$ inside of the group. Then is $H$ a proper subgroup of the quotient group $G/H$?

In order to be a subgroup of a group, one must first be a subset. However, $H$ is not a subgroup of $G/H$ for any normal subgroup $H$ because $G/H$ contains as its elements cosets in $G$. For instance $H$ is the identity of $G/H$ because $H$ is the class of the identity $e\in G$. The identity in $H$ is $e$ though and so if it was a subgroup then it would share the same identity as $G/H$. This is not the case.

It is possible for $H$ to be isomorphic to a proper subgroup of $G/H$ and this is a more interesting question. The easiest example is if $H$ is the trivial subgroup generated by the identity. In this case $G/\langle e\rangle=\{\{g\}\mid g\in G\}$ and so the subgroup $\{\{e\}\}\in G/\langle e\rangle$ is isomorphic to the subgroup $\{e\}$ in $G$. (note the double brackets in the notation used for the trivial subgroup in $G/\langle e\rangle$. It's important).

You have the natural mapping:

$$v\colon G \rightarrow G/H$$

If H is a normal subgroup, then $G/H$ (set of cosets) is a group. There you can identify $H$ with the $0$ element.


Let R be a ring with unity and S be the set of all units in R I need to prove two things

(a) prove or disprove that $S$ is a subring of $R$

(b) prove or disprove that $S$ is a group with respect to multiplication in $R$

For (a) (1) it is clearly that $S$ is non empty since it contains the identity (The unity)

(2) let $a,b \cap S$ then $ab \in S$ because for $a$ we know there is an element $x$ such that $ax = e$ and for $b$ we know what there exists an element $y$ such that $by = e$ and so $ab(yx) = a(by)x = aex = ax = e$ and so $ab \in S$

$a - b \in S$ i am stuck here ! any suggestions

for (b) i think we already proved that it is closed under multiplication and have the identity and it is trivial to prove that all elements have inverses and are also associative , so yes it is a group under multiplication

For the case (a), you already mentioned that $S$ is non-empty as $1 \in S$. But $1 - 1 = 0$ does not belong to $S$, unless $1 = 0,$ i.e. unless $R$ is the trivial ring. So if $R$ is non-trivial then $S$ can not be a subring.

Since in any ring, the additive identity is not a unit, it can not belong to the set of units, which can therefore never be a subring.


Real Analysis (derivative) I am completely stuck in this question.
If  $r > 0$  is a rational number, let $f : \mathbb{R} \to \mathbb{R} $ be defined by $f (x)=x^r\sin (1/x)$ for $x \ne 0$, and $f (0)=0$. Determine those values of $r$ for which $f’(0)$
exists.

We look at the behaviour of the difference quotient as $h\to 0$ :

For $r>1$ $$-h^{r-1}\leq \frac{h^r  \sin(1/h)-0}{h} \leq h^{r-1}$$ goes to $ 0$ as $h\to 0 $ .
So, $f'(0)=0$ .

For $ r= 1 $ , the difference quotient oscillates between $-1$ and $1$.

And lastly for $0<r<1$ ,the difference quotient oscillates unboundedly as $h\to 0$ .

hint:-

$f'(x)=rx^{r-1}\sin \frac{1}{x}+x^{r-2} \cos\frac{1}{x}$

now $f'(0)$ exists when $\lim _{x \to 0}x^{r-2} \cos\frac{1}{x}$ exist


A coin is tossed $n$ times. What is the probability of getting odd number of heads? A coin is tossed $n$ times. What is the probability of getting odd number of heads?

I started this chapter sometimes ago and faced in front of a tough problem. At first I started considering cases. Case-I : The probability of getting 1 head.Case-II : The probability of getting 3 head and so on. But there are many cases. So how can I solved this . Please help me. Thank you!

Hint. Let $p_n$ be the probability of getting an odd number of heads tossing a coin $n$ times, then
$$p_{n+1}=(1-p_1)\cdot p_{n}+ p_1(1-p_{n})$$
where $p_1$ is the probability to obtain a head with one toss. So given $p_1$ (if the coin is fair then $p_1=1/2$), the above linear recursion allows us to evaluate $p_n$ for any positive integer $n$.

P.S. The recursion is explained as follows: at the $(n+1)$th toss we have an odd number of heads if and only if one of these disjoint cases occurs:

i) we have a tail and in the previous $n$ tosses there are an odd number of heads;

ii) we have a head and in the previous $n$ tosses there are an even number of heads.

If $X$ is the number of heads you have to calculate
$$P(X \text{ is odd})=\sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}P(X=2k+1).$$

As $X\sim Binomial(n,1/2)$, you can calculate that probability for each $k$. That is:
$$P(X \text{ is odd})=\sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}{n \choose 2k+1}\left(\frac12\right)^{2k+1} \left(\frac12\right)^{n-(2k+1)} =\left(\frac12\right)^n \sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}{n \choose 2k+1}.$$

Now, if $n$ is odd the last sum is
$${n \choose 1}+{n \choose 3}+\cdots+{n \choose n-2}+{n \choose n},$$
which by the symmetry of the binomial coefficients is equal to
$${n \choose n-1}+{n \choose n-3}+\cdots+{n \choose 2}+{n \choose 0}.$$

Since it is known that
$${n \choose 0}+{n \choose 1}+{n \choose 2}+\cdots+{n \choose n-1}+{n \choose n}=2^n,$$
then both previous sums add up to $\tfrac{2^n}2=2^{n-1}$.

On the other hand, if $n$ is even the sum is
$${n \choose 1}+{n \choose 3}+\cdots+{n \choose n-1}=$$
$$=\left[{n-1 \choose 0} + {n-1 \choose 1}\right] + \left[{n-1 \choose 2} + {n-1 \choose 3}\right]+\cdots+\left[{n-1 \choose n-2}+{n-1 \choose n-1}\right]=$$
$$=2^{n-1},$$
as in the '$n$ is odd' case.

So for every $n \in \mathbb{N}$
$$P(X \text{ is odd})=\left(\frac12\right)^n \cdot 2^{n-1}= \frac12.$$


How can I show a supremum of a set is also its limit point? It just seems like I can't wrap my head around this. For a set $A$ how can I show that the supremum of that set $\sup(A)$ is also a limit point of said set?
Can I just set
$$a=\sup(A)$$
$$b\le a \: \:  \forall \: b \in A$$
and then show that there's a point different from $a$ in any $\epsilon$-neighbourhood for any $\epsilon>0$? Or should I use a completely different approach?

The other answers to this question are incorrect.  It is not generally true that the supremum of a set $A$ in $\mathbb{R}$ is a limit point of that set.  For example, as pointed out in the comments by Daniel Fischer, for any $a \in \mathbb{R}$, we have $\sup\{a\} = a$, but $a$ is not a limit point of $\{a\}$.  To explain this, first recall the definition:

  Definition: Let $A \subseteq \mathbb{R}$.  A point $x\in\mathbb{R}$ is called a limit point of $A$ if for any $\varepsilon > 0$ there exists some $y\ne x$ such that $|y-x| < \varepsilon$ and $y\in A$.  In other words, every $\varepsilon$-neighborhood of $x$ contains a point of $A$ which is different from $x$.

If we take $A = \{a\}$ then, as noted above $\sup(A) = a$.  But no neighborhood of $a$ contains any point of $A$ other than $a$.  Hence, by the definition above, $a = \sup A$ is not a limit point of $A$.  Indeed, given any set $A$ such that $\sup(A) < \infty$, we can construct a set $A'$ by appending an extra point that is greater than the supremum.  For example, for any $\varepsilon > 0$, the set
$$A' = A \cup \{ \sup(A) + \varepsilon \} $$
satisfies the properties

$\sup(A') = \sup(A) + \varepsilon$, and
$\sup(A')$ is not a limit point of $A'$.

If, instead we ask "Is the supremum of a subset of $\mathbb{R}$ an adherent point of $A$?", then the answer is "Yes", subject to appropriate caveats.

  Definition:  Let $A \subseteq \mathbb{R}$.  A point $x\in\mathbb{R}$ is called an adherent point of $A$ if for any $\varepsilon > 0$ there exists some $y$ such that $|y-x| < \varepsilon$ and $y\in A$.  In other words, every $\varepsilon$-neighborhood of $x$ contains a point of $A$.

Note here that we do not require $y$ to differ from $x$.  Hence $a$ is an adherent point of $\{a\}$.  Note that every limit point of a set is also an adherent point of that set, and that all the points of $A$ are also adherent points.  To show that the supremum of a bounded-from-above set is an adherent point, we can argue as follows:

If $\sup(A) \in A$, then $\sup(A)$ is an adherent point of $A$, and we are done.
If $\sup(A) \not\in A$, then it follows from the definition of the supremum that for any $\varepsilon > 0$ there is a point
$$x_n \in (\sup(A)-\varepsilon, \sup(A)]. $$
In other words, for any $\varepsilon > 0$, we can find a point $x_n \in A$ such that $|x_n - \sup(A)| = \sup(A) - x_n < \varepsilon$.  This implies that $\sup(A)$ is an adherent point of $A$.

Note that the second case is (in every way that matters) the argument given by MPW, mookid, and Paul in their answers.

The assertion is only true for open sets in R. Any neighborhood of supA except itself intersects A must be nonempty otherwise there is a smaller upper bound in that region. Also supA is not in A.


Do intersections commute with direct sum? This is just a basic linear algebra question without that much context to it.  I'm wondering if the following identity holds for vector spaces:
$$ (A \oplus  B)  \cap C  = (A \oplus 0 )\cap C  + (0 \oplus B)\cap C. $$

My intuition tells me it's always true, but I could be wrong.

This is so wrong...

Let $A=Span(1,0), B=Span(0,1), C=Span(1,1)$.
Then
$$(A\oplus B)\cap C=\mathbb{R}^2\cap C=C$$ and
$$(A\cap C)\oplus (B\cap C)=0\oplus 0 = 0.$$

No, vector spaces don't verify that:
$$(A \oplus  B)  \cap C  = (A\cap C)  \oplus (B\cap C).$$
To prove it, we can find a counterexpample:
Consider the vector subspaces $\langle\begin{pmatrix} 1 \\ 0 \end{pmatrix}\rangle$, $\langle\begin{pmatrix} 0 \\ 1 \end{pmatrix}\rangle$ and $\langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle$. Notice that
$$\left(\langle\begin{pmatrix} 1 \\ 0 \end{pmatrix}\rangle\oplus \langle\begin{pmatrix} 0 \\ 1 \end{pmatrix}\rangle\right)\cap \langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle=\mathbb{R}^2\cap \langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle=\langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle,$$
but
$$\left(\langle\begin{pmatrix} 1 \\ 0 \end{pmatrix}\rangle  \cap \langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle\right)\oplus\left(\langle\begin{pmatrix} 0 \\ 1 \end{pmatrix}\rangle  \cap \langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle\right)=0\oplus 0=0,$$
and clearly $\langle\begin{pmatrix} 1 \\ 1 \end{pmatrix}\rangle\neq 0$.


Prove or disprove $|x+y+z|\ge\sqrt{3}$ Let $x,y,z\in R$, such $|x|\neq|y|\neq|z|$,and $|x|,|y|,|z|>1$ and $xy+yz+xz=-1$
prove or disprove
$$|x+y+z|\ge\sqrt{3}$$

I try

$$(x-y)^2+(y-z)^2+(z-x)^2\ge 0$$
so $$|x+y+z|^2\ge 3(xy+yz+xz)=-3$$
why?


Have I drawn this Venn diagram correctly? Does this look correct?

http://i.imgur.com/vmlpYD8.png

I'm trying to find out whether this syllogism is valid (I'm guessing it's not valid)

Many thanks

The following argument is invalid:

(P1): All Cacti are Plants. (P2): Some Plants are Green. Conclusion: Some Cacti are not Green.

It's just that the non-Green plants needn't have any Cacti among them. The Venn diagram below illustrates that. Note that the diagram satisfies both (P1) and (P2), as required.

Statement 1: All cacti are plants implies that the cacti circle is 'in' the plant circle.
Statement 2: Some plants are green implies that there exist plants which are green. This may include the possibility of all plants turning green but excluding the possibility of 'not even one' plant which is not green. So, plant circle interaction with the green circle is 'non-zero'.
Statement 3: Some cacti are not green. You can never conclude this statement from the above two because there is no imformation of interaction of the cacti circle with the green circle.


Formal notation for representing decimal numbers What is the formal mathematical notation for representing a decimal number using variables as it's digits?

I am honestly surprised that this has not been asked yet on MSE. Let me clarify a little using an example. Consider the $3$ digit decimal number $123$. Say I  have $3$ variables for each of the decimal places $a,b,c$ such that $$a=1$$ $$b=2$$ $$c=3$$
I know that I can represent the number using $$a\times 100+b\times 10 + c$$
But this is too tedious. All I want to know is if there is any shorthand notation developed specifically for this purpose.
I have faint memory of using some notation for this exactly ONCE in my life but I think my memory is playing tricks on me. Does anybody actually remember some notation?
Thanks

Note

Not to be misunderstood as asking for notations of summations, et cetera. I am asking for specific purpose notation only.

I have seen $\overline {abc}$ used by some people on this site.  Others will just write $abc$ and state that it means concatenating the digits instead of multiplication.  Usually it is clear what problems want it that way.

Alternatively, I have found another less convenient but formally correct symbol
$$100a+10b+c=a\|b\|c$$
This of course is also usable on numbers $$123=1\|2\|3$$
The "$\|$" (represented by \| in $L^AT_EX$) operation is called concatenation (as mentioned by @GitGud and @RossMillikan).
More can be read about this operation here


Is the ring of global functions on an integral scheme integral? Is the ring of global functions on an integral scheme an integral domain (if the scheme is affine then it is try by definition so we are interested in non-affine schemes)? It is necessarily a reduced ring (https://stacks.math.columbia.edu/tag/01OL) so the question is whether it is irreducible.

If $X$ is any reduced scheme and $U$ is a dense open subset, then the restriction map $\mathcal{O}_X(X)\to\mathcal{O}_X(U)$ is injective.  Indeed, an element of the kernel vanishes in the fiber at every point of $U$, but the set where a section of $\mathcal{O}_X$ vanishes in the fiber is closed, so it must vanish in the fiber everywhere.  Since $X$ is reduced, a function which vanishes in the fiber everywhere must be $0$.

In particular, if $X$ is integral, we can consider $\mathcal{O}_X(X)$ as a subring of the domain $\mathcal{O}_X(U)$ for any nonempty affine open $U$, and so $\mathcal{O}_X(X)$ is also a domain.

This is an alternative answer to your question.
Question:
"Q1. Is the ring of global functions on an integral scheme an integral domain (if the scheme is affine then it is try by definition so we are interested in non-affine schemes)?
Q2. It is necessarily a reduced ring?"
Answer: If you use the definition in Hartshorne (page 82) you define a scheme $(X,\mathcal{O}_X)$ to be "integral" iff for any open set $U\subseteq X$ it follows
$\mathcal{O}_X(U)$ is an integral domain. In particular, since $X$ is an open set, it follows $\Gamma(X,\mathcal{O}_X):=\mathcal{O}_X(X)$ is an integral domain. Hence it seems to me the answer to Q1 is "yes, this is true by definition". Since an integral domain is a reduced ring it follows $\mathcal{O}_X(X)$ is a reduced ring. Hence the answer to Q2 is also "yes".


Example of Three Polyhedrons in $\mathbb {R^2}$ where any Two Have Non-Empty Intersection, but Empty Intersection Amongst All Suppose we are in $\mathbb R^2$.
It is not true that the polyhedra $P_1, P_2$,...$P_K$ (where $K \geq 3$) in the plane have a point in common if every two of them have a point in common.

For example:
Let $P_1=\{(x,y) \in \mathbb R^2 \mid x=0\}$, $P_2=\{(x,y) \in \mathbb {R^2} \mid y=0 \}$, $P_3=\{(x,y) \in \mathbb {R^2} \mid y=x-1 \}$

Any two have a point in common but the intersection amongst all three is empty. This is an interesting and cool example.
I was wondering what some other possible examples of polyhedron were to illustrate this fact.

In fact, if you want bounded polygons, it suffices to "bend" in a suitable way the straight lines solution ; for example for $K=3$ :

This method is suitable in any dimension ; consider for example the case of $K=5$ unbounded regions delimited by $5$ straight lines :

Their boundaries can be "bended" into closed polygons, giving this solution:


Can all irrational numbers be written in the form $u + v\sqrt{2}$, with $u$ and $v$ rational? I am curious to know whether all irrational numbers can be written in the form $u + v\sqrt{2}$, with $u$ and $v$ rational.

(Almost similar to how all complex numbers can be written as $x + iy$, with $x$ and $y$ real.)

Let $\sqrt3=u+v\sqrt2$. Then by squaring, $3=u^2+2\sqrt2uv+2v^2$ and $\sqrt2=\dfrac{3-u^2-2v^2}{2uv}$ is a rational number !?

No. It is not possible.  For examples,

$$\pi, e, e^\pi, \pi^e$$