monotone function on open interval is continuous except possibly at a countable number of points Here is the proof from Royden's book.

  Assume $f$ is increasing. Furthermore, assume $(a,b)$ is bounded and
  $f$ is increasing on the closed interval $[a,b]$. Otherwise, express
  $(a,b)$ as the union of an ascending sequence of open, bounded
  intervals, the closures of which are contained in $(a,b)$, and take
  the union of the discontinuities in each of this countable collection
  of intervals. For each $x_0 \in (a,b)$, $f$ has a limit from the left
  and from the right at $x_0$. Define $$f(x_0^-) = \lim_{x \to x_0^-}
 f(x) = sup \{f(x)| a < x < x_0\}, $$ $$f(x_0^+) = \lim_{x \to x_0^+}
 f(x) = sup \{f(x)| x_0 < x < b\}. $$Since $f$ is increasing, $f(x_0^-)
 \leq f(x_0^+)$. The function $f$ fails to be continuous at $x_0$ if
  and only if $f(x_0^-) < f(x_0^+)$, in which case we define the open
  "jump" interval $J(x_0)$ by $$J(x_0) = \{y|f(x_0^-) < y <
 f(x_0^+)\}.$$ Each jump interval is contained in the bounded interval
  $[f(a), f(b)]$ and the collection of jump intervals is disjoint.
  Therefore, for each natural number $n$, there are only a finite number
  of jump intervals of length greater than $1/n$. Thus the set of points
  of discontinuity of $f$ is the union of a countable collection of
  finite sets and therefore is countable.

It seems the book is assuming that $[f(a), f(b)]$ being finite, then what if it is not finite? i.e., $[f(a), f(b)]$ is of the form $[f(a), \infty]$. Can I write $[f(a), \infty] = \bigcup_{k=1}^\infty [f(a), k]$ and say for each number n, there are only countably sum of finite jump intervals of length greater than $\frac{1}{n}$ in each $[f(a), k]$, thus there are countably many jump intervals in $[f(a), \infty]$.

But how come there is only a finite number of jump intervals, and that too of the length provided above. I didn't get that.


Special cases of the Rohrlich-Lang conjecture with Gamma function The Gamma function satisfies:
$$\Gamma(z + 1) = z\Gamma(z)$$
$$\Gamma(z)\Gamma(1 - z) = \frac{\pi}{\sin(\pi z)}$$
$$\prod_{k = 0}^{n-1}\Gamma\left(a+\frac{k}{n}\right) = (2\pi)^{(n-1)/2}n^{-na + 1/2}\Gamma(na)$$

The Rohrlich conjecture states:
Any multiplicative dependence relation of the form
$$\pi^{b/2}\prod_{a \in \mathbb{Q}}\Gamma(a)^{m_a} \in \bar{\mathbb{Q}}$$
is a consequence of the relations above.

Do we know special cases where this is valid? For instance, given rationals $a$ and $b$, do we know when $\dfrac{1}{\pi}\dfrac{\Gamma(a)\Gamma(b)}{\Gamma(a + b)}$ is algebraic? And for three rationals?

At least two of gamma(1/5), gamma(2/5) and pi are algebraically independent. ..


Why is $\left|e^{iat} e^{-st}\right| \le \left| e^{iat}\right| \left| e^{-st}\right| \le e^{-st}$ true? My text states:

  $\left|e^{iat} e^{-st}\right| \le \left| e^{iat}\right| \left| e^{-st}\right| \le e^{-st}$

  as $\left| e^{iat} \right|=1$
  where $a,s,t \in \mathbb{R}$

I thought the last part of the inequality should read:

  $\left| e^{iat}\right| \left| e^{-st}\right| = e^{-st}$

since $\left| e^{-st}\right|$ is always positive.

I am also not sure how the middle expression of the inequality is arrived at. I do know that:
$$ \begin{align} a,b \in \mathbb{R} \Rightarrow & \left|ab\right| = \left| a \right| \left|b\right|\end{align}$$
By the property of the absolute value function.

But in this case, the left hand side of the inequality is the modulus of a complex number so I am not sure if the above rule still applies.I'm also not able to come up with a geometric argument to justify why the inequality must be true.

Please help me see why the given inequality must be true especially why it has to be a weak inequality instead of an equality.

I think it's equal, since complex norm is also multiplicative!


Proof that a limit is a partial derivative I'm writing up several proofs for myself, all of which have a particular sticking point.

Essentially, I want to prove that for a function $f$ of two real variables, we have

$\lim_{h \to 0} \frac{f(x \;+\; h, \; y \;+\; h) \; - \; f(x, \; y \;+ \;h)}{h} = \frac{\partial f}{\partial x}$.

When I've seen this crop up in textbooks and lecture notes (say, in the context of proving the multivariable chain rule), it's generally just been taken for granted, rather than proven.

Intuitively, how can we be sure that the function is sufficiently well behaved that having $y + h$ instead of $y$ in the second argument doesn't 'mess things up' and not allow this limit to be the partial derivative? And moreover, how could I give a rigorous proof of this?

Thanks all!

A sufficient condition for the claim to be true is that $f'_x=\partial f/\partial x$ exists in a neighbourhood of $(x,y)$ and is continuous at $(x,y)$.

Proof. Since $f'_x$ exists, the mean value theorem for derivatives says that
$$
f(x+h,y+h) - f(x,y+h) = f'_x(x+\theta h, y+h) \cdot h
$$
for some $\theta \in [0,1]$ (which may depend on $h$).
So your quotient is
$$
\frac{f(x+h,y+h) - f(x,y+h)}{h} = f'_x(x+\theta h, y+h)
,
$$
which tends to $f'_x(x,y)$ as $h \to 0$, because of the assumption that $f'_x$ is continuous there.

There's no way anything could be messed up since the second coordinate is always fixed. It's only the first that's varying. That is, we're considering the change from the point $(x,y+h)$ to the point $(x+h,y+h).$ Throughout this change, the second coordinate is clearly fixed. Thus, it's not concerned with the limiting process at all. This is why we can be sure that the limit, if it exists, is indeed the derivative with respect to $x,$ fixing $y.$ Thus, there's nothing more to justify than in the usual derivative. Hence, what you noticed about the books.


How to prove $ \int_{-\infty}^{+\infty}\left|x\right|^ke^{-(x-3)^2/2}dx $ is finite? How to prove this integral as following is finite?

$$
\int_{-\infty}^{+\infty}\left|x\right|^ke^{-(x-3)^2/2}dx
$$

k is a positive integer

Fix $n \in \mathbb{N}$, and consider $f_n (x)= \chi_{[-n,n]}(x) |x|^k \exp( - (x-3)^2 /2)$.
Then we have that $f_n$ increases pointwise to $f$ and thus we have by MCT
$$\lim_{n \to \infty} \int_{-\infty}^\infty f_n(x) \textrm{d}x = \int_{-\infty}^\infty \lim_{n \to \infty} f_n(x) \textrm{d}x = \int_{-\infty}^\infty f(x) \textrm{d}x.$$
Furthermore, we can find $\int_{-\infty}^\infty f_n(x) \textrm{d}x $ by using the power series of $\exp(- (x-3)^2 /2)$, and denote $g_{n,m}$ to be the partial sum till the $m^{\text{th}}$ term on $[-n,n]$ and $0$ outside $[-n,n]$.
As the $g_{n,m}$ converges pointwise to $f_n$ and the series $g_{n,m}$ is bounded by the integrable function $g_n(x) = \Lambda_n \chi_{[-n,n]}(x)$ where $\Lambda_n$ is a finite upper bound of $\{g_{n,m} ,f_{n}\}$, we have by DCT
$$ \lim_{m \to \infty} \int_{-\infty}^\infty g_{n,m}(x) \textrm{d}x = \int_{- \infty}^\infty f_n(x) \textrm{d}x.$$
And thus
$$ \int_{-\infty}^\infty f(x) \textrm{d}x = \lim_{n \to \infty} \lim_{m \to \infty} \int_{-n}^n g_{n,m}(x) \textrm{d}x.$$

You can use Taylor series representation for exponential function. Then interchange integration and summation with Fubinis theorem.


find the limit of this function? Evaluate $$\lim_{n\to \infty}\frac{1}{(n!)^{1/n}}={?}$$

My try:
$$\lim_{n\to \infty}\frac{1}{(n!)^{1/n}}=\exp{\lim_{n\to \infty}\frac{-\ln(n!)}{n}}$$
$$=\exp{\lim_{n\to \infty}\frac{-\ln(1\times2\times3\ldots(n-1)\times n)}{n}}$$
$$=\exp{\lim_{n\to \infty}\frac{-(1+2+3+\ldots+(n-1)+n)}{n}}$$
$$=\exp{(-\lim_{n\to \infty}\left(\frac1n+\frac2n+\ldots+\frac{n-1}{n}+\frac nn\right)})$$
$$=\exp(-1)=\frac1e$$
I don't know if my answer is correct please correct me if i am wrong. thanks

Note that $e^x \geq \frac{x^n}{n!}$ for all $x\geq 0$. Setting $x=n$, we have $$ n! \geq \left( \frac{n}{e} \right)^n .$$
Thus $$(n!)^{1/n} \geq \frac{n}{e} \to \infty.$$

Stirling's approximation $$n!\approx\sqrt{2\pi n}\left(\dfrac ne\right)^n$$

$$\begin{align}L&=\lim_\limits{n\to\infty}\dfrac1{(n!)^{\frac1n}}\\&=\lim_\limits{n\to\infty}\dfrac1{(2\pi n)^{\frac 1{2n}}\cdot\dfrac ne}\\&=\lim_\limits{n\to\infty}\dfrac{e}{ne^{\frac{\ln(2\pi n)}{2n}}}\\&=\lim_\limits{n\to\infty}\dfrac e{ne^{\frac1{2n}}}\qquad\left[\text{Applying L' H}\hat{o}\text{pital's Rule on }\lim_\limits{n\to\infty}\dfrac{\ln(2\pi n)}{2n}\right]\\&=\lim_\limits{n\to\infty}\dfrac en\\&=0\end{align}$$


How Do I Figure Out Which Door to Choose From? A computer game involves a knight on a quest for treasure. At the end of the journey, the knight approaches two doors.

The left door has a sign saying "One of these doors leads to a ferocious dragon!" and the right door has a sign saying "Behind this door is treasure, and behind the other door is a ferocious dragon!"

A Servant informs the knight that one of the doors is true, and the other is false. Use Indirect Reasoning to determine which door the knight should choose. Explain your reasoning.

Where do I start? I'm confused on where to begin and the steps to figuring out the right door...

Suppose the second door is being truthful. Then the first door has a dragon behind it. So, there is a door with a dragon. So the first door is being truthful too. This contradicts the servant.

Hence the second door is lying, but the first door is telling the truth. Unfortunately, as the questions is set up, this means the statement "door 2 has treasure and door 1 has a dragon" is false. This could, however, be false if door 2 was safe, but there was no treasure. So it seems to me like there still could be a dragon behind door 1, provided there is no treasure behind door 2. Or it can be because there is a dragon behind door 2.

Another solution would be for both doors to lead to a dragon, which would make the left door true and the right door false.


Can we formally distinguish between actual and potential infinities? Actual infinity is the idea that numbers, or some other type of
  mathematical object, can form an actual, completed totality; namely, a
  set. Hence, in the philosophy of mathematics, the abstraction of
  actual infinity involves the acceptance of infinite entities, such as
  the set of all natural numbers or an infinite sequence of rational
  numbers, as given objects. This is contrasted with potential infinity,
  in which a non-terminating process (such as "add 1 to the previous
  number") produces an unending "infinite" sequence of results, but each
  individual result is finite and is achieved in a finite number of
  steps.

Source: "Actual Infinity," Wikipedia

From another source:

  Potential infinity refers to a procedure that gets closer and closer
  to, but never quite reaches, an infinite end. For instance, the
  sequence of numbers 1, 2, 3, 4, ...

  Completed infinity, or actual infinity, is an infinity that one
  actually reaches; the process is already done. For instance, let's put
  braces around that sequence mentioned earlier: { 1, 2, 3, 4, ... }

Source: Eric Schechter, "Potential versus Completed Infinity",2009

EDIT: How can we talk about an infinite sequence of natural numbers without having already established the existence of the set of all natural numbers using Peano's Axioms or some equivalent?

It all seems a bit hand-wavy and circular to me.  Can we formally distinguish both kinds of infinities?

The distinction here is really philosophical rather than mathematical, but I wouldn't say it's hand-wavy at all. In any case, here's my best attempt at an answer.

Suppose we want to make a mathematical distinction between an actual infinitude and a potential infinitude, where by 'mathematical distinction' I mean a negation of an equation between two mathematical objects which is provable from a conventionally accepted system of axioms (e.g. ZFC).

The closest I can think to putting your question into words mathematically is: define sets $\mathbb{N}_a$ and $\mathbb{N}_p$ by

$\mathbb{N}_a$ is the card-carrying, honest-to-god, set of everything that self-identifies as a natural number;
$\mathbb{N}_p$ is the set of everything obtainable from $0$ by iterating the successor operator finitely many times.

...but in any conventional axiomatic system, these sets are equal: mathematics only pays attention to extensional equality between sets, even if they aren't intensionally equal. That is, sets may have different descriptions, but if they have the same elements then they're declared equal. As such, these two sets are mathematically indistinguishable.

from "Infinity and the Mind" by Rudy Rucker, page 89:
"Conway [..] even gets a definition of the traditional symbol $\infty$, for potential infinity. $\infty$ is defined as the gap between the finitely large and the infinitely large surreal numbers, and Conway derives the weird equation

$$
\infty = \sqrt[\Omega]{ \omega }
$$

which magically ties together potential infinity $\infty$, the simplest actual infinity $\omega$, and the Absolute Infinity $\Omega$."


Let $n$ be a positive integer and $p=4n+1$, a prime number. Show that $(\frac{p-1}2)!$ is a root of $x^2+1=0$ in $\mathbb Z_p$ I have to prove the following part, but I can not. Please help me.

Let $n$ be a positive integer and $p=4n+1$, a prime number.
Show that:

$((p-1)/2)!$ is a root of $x^2+1=0$ equation over $\mathbb{Z}_p$.

We will use the following lemma.

Lemma (Wilson's Theorem): Let $p$ be a prime number. Then $(p-1)! \equiv -1 $ (mod $p$).

Proof: There are several proofs on the "Wilson's Theorem" Wikipedia page, and many available elsewhere online. I'd encourage you to try to prove it yourself before looking them up, though!

$$\tag*{$\blacksquare$}$$

Now observe that, for each $i$, we have (working in $\mathbb{Z}_p$)

$$
\frac{p-i}{2} = \frac{p-i}{2} - p = \frac{-p - i}{2} = -\frac{p+i}{2}
$$

It follows from this that

\begin{align}
(p-1)! &= (1)(2)\ldots(\frac{p-1}{2})(\frac{p+1}{2})\ldots(p-2)(p-1)
\\
&= (1)(2)\ldots(\frac{p-1}{2})(-\frac{p-1}{2})\ldots(-2)(-1)
\\
&= (-1)^{\frac{p-1}{2}}\Big((\frac{p-1}{2})!\Big)^2
\end{align}
Now, since $p = 4n+1$, we have that $(p-1)/2 = 2n$ is even, which means that $(-1)^\frac{p-1}{2} = 1$. Finally then, applying Wilson's Theorem, we obtain

$$
\Big((\frac{p-1}{2})!\Big)^2 = (p-1)! = -1
$$
and the result follows.

Wilsons Theorem says $(p-1)! \equiv -1 \pmod p$.

And for any $k$ consecutive numbers, $m+1, m+2,.....,m+k$ we know that $k!$ divides $\prod (m+k)$.

So $\frac{p-1}{2}!$ will divide $1*2.....*\frac{p-1}2$ and $\frac {p-1}{2}!$ will divide $(\frac{p-1}2+1)*(\frac {p-1}2 +2)*.....*(p-1)$.

SO $(\frac{p-1}2)!^2$ will divide $1*2*...... *(p-1)=(p-1)!$.

So $(\frac{p-1}2)!^2 \equiv (p-1)! \equiv -1 \pmod p$ ad $(\frac{p-1}2)!^2 + 1 \equiv 0 \pmod p$.


Where have fractals gone since Mandelbrot? What are some examples of cutting-edge research involving fractals or self-similar structures?

Who's actively contributing high-quality research in this field?

As pointed out in the comments, this is a tremendously broad area and there are many people doing a lot of very good research, so I can only say a little bit about the small part of it that I'm familiar with.  When dealing with "chaotic" dynamical systems (a notion which can be made precise in a few different ways), one often finds that the chaotic behaviour of the dynamics is intimately connected to the presence of various geometric structures in the phase space that are best characterised as fractals -- the Julia sets found in complex dynamics are examples of this.

To study these structures, one uses various dimensional quantities, such as Hausdorff dimension.  It turns out that some fundamental dynamical quantities such as topological entropy can also be defined as "dimensions" of a sort, so that there are deep connections between fractal geometry and chaotic dynamics.  One of the standard (advanced) references on this is "Dimension Theory in Dynamical Systems", by Yakov Pesin.  A more introductory exposition (with apologies for self-advertising) is "Lectures on Fractal Geometry and Dynamical Systems", by Pesin and Climenhaga.

As an example of the sort of thing that occurs, suppose you have a dynamical system with phase space $X$ and an observable function $\phi\colon X\to \mathbb{R}$.  You take measurements of $\phi$ as time goes along, and calculate its average value as time goes to infinity.  This average value is a function of your starting position $x\in X$.  Let $K_\alpha$ denote the set of points for which that average value is equal to $\alpha$; then typically speaking, there is a range of values of $\alpha$ for which $K_\alpha$ is a fractal with quite an intricate structure.  This is called a multifractal decomposition.  One can define a multifractal spectrum by $B(\alpha) = \dim_H(K_\alpha)$, and it turns out (somewhat miraculously) that the function $\alpha\mapsto B(\alpha)$ is actually concave and analytic in a great many (important) examples!  This multifractal analysis has deep connections to thermodynamic formalism and statistical properties of chaotic dynamical systems; a good reference is "Thermodynamics of Chaotic Systems", by Beck and Schlögl.

render 3D fractals based on the original 2D mandelbrot formula, such as mandelbox and mandelbulb + many more - using free open source software called "mandelbulber"


Discrete Math Proofs Are these steps for finding the solutions of $\sqrt{x + 3} = 3 − x$ correct?

$\sqrt{x + 3} = 3 − x$ is given;
$x + 3 = x^2 − 6x + 9$, obtained by squaring both sides of (1);
$0=x^2 −7x+6$, obtained by subtracting $x+3$ from both sides of (2);
$0 = (x − 1)(x − 6)$, obtained by factoring the right-hand side of (3);
$x = 1$ or $x = 6$, which follows from (4) because $ab = 0$ implies that $a=0$ or $b=0$.

Yes, all the steps are correct. You only need to check those value of $x$ if it satisfies the original equation or not.

Assume that $ab=0$. We want to show that either $a=0$ or $b=0$. If $a=0$ then we are done. Suppose that $a\neq 0$. Then $a^{-1}\in\Bbb R$. Thus, using field properties of $\Bbb R$ we get
$$b=1b=(a^{-1}a)b=a^{-1}(ab)=a^{-1}0=0.$$

It's only valid to square the equation when both sides are positive.

In your second line you need to have a condition $3-x\geq 0 $ which simplifies to $x\leq 3$.Also you must have your square root defined i.e $x+3\geq 0$ or $x\geq -3$.

Now that we've done that we can see that $x=6$ is not a solution to the equation,this can be easily verified by plugging $x=6$ or differently $\sqrt{6+3}\neq 3-6$


Using Lie theory to understand $U=e^{iHt}$ (Quantum Mechanics) Can we use the exponential map (lie theory) to understand how the Hamiltonian ($H$) gives rise to the unitary, and therefore compliments an essential property of the unitary operator (ie to preserve inner products)?

With fixed H, you are just doing a single one parameter group $U(t)$ sitting inside $U(n)$ for some $n$. Where it gets more interesting is if you have $H_1+\lambda H_2$. Then you will have to actually use some Lie brackets when doing the exponential.


Proof that the nth root of a rational s/t is irrational unless s and t are perfect nth powers with gcd(s,t)=1 A few months ago I asked for help with the above question (linked here Proof that the nth root of a rational s/t is irrational unless s and t are perfect nth powers) and I need a bit more help.

My lecturer has specifically said I need to use the uniqueness of prime factorisation, similar to that used in the proof that $\sqrt{2}$ is irrational via the uniqueness of prime factorisation seen below (taken from my project),

We can also think of a different proof for this as well. Taking $a$ and $b$ as before we end up with $2a^2 = b^2$. We shall now say that $a$ and $b$ have the following prime factor decomposition's,

$a = \alpha_1^{\beta_1}\cdot\alpha_2^{\beta_2}\cdot\alpha_3^{\beta_3}\cdot\dots\cdot\alpha_n^{\beta_n}$

and

$b = \gamma_1^{\delta_1}\cdot\gamma_2^{\delta_2}\cdot\gamma_3^{\delta_3}\cdot\dots\cdot\gamma_n^{\delta_n}$

we see that when we have $2a^2 = b^2$ we can rewrite this as

$2\cdot\alpha_1^{2\beta_1}\cdot\alpha_2^{2\beta_2}\cdot\alpha_3^{2\beta_3}\cdot\dots\cdot\alpha_n^{2\beta_n} = \gamma_1^{2\delta_1}\cdot\gamma_2^{2\delta_2}\cdot\gamma_3^{2\delta_3}\cdot\dots\cdot\gamma_n^{2\delta_n}$

from this we can see that the left hand side must have an odd power two when $2$ and $a$ are multiplied together and the right hand side will have an even power (or no power at all). If these two expressions are equal then this is impossible due to the uniqueness of prime factorisation and we can once again conclude that $\sqrt{2}$ is irrational.

I either need to refine some of the answers given or redo the proof completely.

Any help greatly appreciated

Assume you have $\sqrt[n]{\frac{s}{t}}={a\over b}$, where s and t share no common primefactor. This leads to

$$
t\cdot a^n=s\cdot b^n\space$$

Now since $s$ and $t$ are coprime, if you take any primefactor of $t$ it has to be a primefactor of $b$ and so occurs as a multiple of $n$ in the primefactorization of $t\cdot a^n$ and  hence also as a multiple of $n$ in the primefactorization of $t$. This shows that $t$ is a n-th power.

The same argument can be applied to show that $s$ is a n-th power.


Countability of set of binary strings of finite length So I was thinking about the countability of the set of binary strings of finite length.
I approached using two ways.
The worst thing is I am getting different answers in both approaches.
Here is the way I proceeded.

My Ideas.
If I am given a binary string whose left most digit is $0$ then truncate it. Remove the $0$. Do it untill you get a $1$ at the left most place.
This is simply an extension of the fact that $0334$ and $334$ are equal and the $0$ in the left of $3$ in $0334$ isn't necessary!

Now coming to the solution
Method 1.
Map each binary string to it corresponding decimal representation.
And map each Natural Number to the binary representation.
This is a bijection as both the mapping are $1-1$.

Hence our set is countable as its isomorphic to $\mathbb{N}$.

Method 2.
Consider the mapping from the set of Binary Strings to Power Set of $\mathbb{N}$.
If the binary string is $a_k a_{k-1} ...a_3 a_2 a_1$ then define the set $$X=\{k\in \mathbb{N} | a_k=1\}$$
This also gives a bijection which shows that the set of binary string is Uncountable!

Where is the Error?

Your mapping in "method 2" maps (finite) binary strings to finite subsets of $\mathbb N$.
The power set of $\mathbb N$ includes infinite subsets.  So this is not a bijection.

If the sets $C_1,C_2,...$ are countable (or finite, if one is being picky), then so is $C= \cup_k C_k$. This follows from the same way that one shows that $\mathbb{N}^2$ is countable.

In the above case, if $C_k$ is the set of binary strings of length $k$ then we see that
$|C_k| = 2^k$ which is finite. Hence the (countable) union is countable.


Convergence of random increment of two bins If bins A and B are initialized to 1, and then I continually increment one of them by 1 with a probability proportional to their values, would A/B ever converge?

To demonstrate

A=1 B=1 , select A or B with 50-50 -> A chosen
A=2 B=1 , select A or B with 66-33 -> A chosen
A=3 B=1 , etc

For A=1 and B=1 it seems to diverge most of the time. But if I start from larger numbers A=100 B=100 it seems that it will converge to 50-50 after many iterations. And If I start from A=100 B=200 it would converge to 33-66 etc. So the initial value is important.

What is the mathematical explanation for this behavior? Maybe the initial value  is a function of the increment (1 in this case) in some way to be able to ensure convergence.

The problem can be formulated as a special random walk.

Let $X_n$ ($n\ge 1)$ be a set of Bernoulli variables, taking values on $\{1,-1\}$, and let $Y_n=\sum_{i=1}^n X_n$ be our random walk. Making the event $X_n=1$ correspond to incrementing $A_n$, we have:

$$ (A_n-A_0)-(B_n-B_0) = Y_n$$
$$ (A_n-A_0)+(B_n-B_0) = n$$

Hence $A_n = A_0 + (Y_n+n)/2$ and $A_n + B_n = n+A_0+B_0$

Then

$$p_n= P(X_n=1) = \frac{A_{n-1}}{A_{n-1}+B_{n-1}} = \frac{1}{2}\frac{Y_{n-1}+n-1+2A_0}{n-1+A_0+B_0}$$

Letting $\mu_n=E(X_n)$, conditioning on the past, and applying the tower expectation, we get (I spare the details) :

$$ \mu_n= \frac{\alpha +\sum_{i=1}^{n-1}\mu_i}{\beta +n} $$

where $\alpha=A_0-B_0$ and $\beta = A_0+B_0-1$. This has the constant solution: $\mu_n = \frac{\alpha}{\beta+1}=\frac{A_0-B_0}{A_0+B_0}$. Therefore

$$E(Y_n)=n \frac{A_0-B_0}{A_0+B_0}$$

and hence $A_n$ grows (in average) as $A_0 + n (\frac{A_0-B_0}{A_0+B_0}+\frac{1}{2})$

What remains is to compute the variance of $Y_n$, which requires to compute the correlations $E(X_n X_m)$. As a starting point, note that $\sigma_X^2=4 A_0 B_0 /(A_0+B_0)^2$. If $X_n$ were indepdent, $\sigma_Y^2= n \sigma_X^2$ . Because they have positive correlation, one would expect the variance to be larger - but not larger than $n^2 \sigma_X^2$.

Update: A straightforward but tedious computation [*] gives me: $$r=E(X_n X_m) = \frac{s+d^2}{  s(s+1)} \hskip{1cm} n\ne m, \;s=A_0+B_0, \; d=A_0-B_0$$

Then $E(Y_n^2)=n+n(n-1) r$ ; and, because  $E(Y_n)=n d/s$ then

$$ {\rm{Var}}(Y_n)=n\frac{s^2-d^2}{s(s+1)}\left(\frac{n}{s} +1\right) \approx n^2 \frac{s^2-d^2}{s^2(s+1)}$$

Going back to $A_n$, we see that its mean grows as

$$\overline{A_n} \approx n \left(\frac{1}{2}+\frac{d}{s}\right)$$

and the variance as

$$ {\rm Var}(A_n) \approx n^2 \frac{s^2-d^2}{4 s^2(s+1)}$$

In particular,  $A_0=B_0=1$ ($d=0$, $s=2$) we have

$$\overline{A_n} =1+\frac{n}{2} \hskip{1cm} {\rm Var}(A_n) \approx n^2 \frac{1}{12}$$

If instead $A_0=B_0=100$

$$\overline{A_n} =100+\frac{n}{2} \hskip{1cm} {\rm Var}(A_n) \approx n^2 \frac{1}{804}$$

That is, the behaviour is basically the same in the mean, but the variance is smaller.

[*] I've checked my results against simulations, they seem to agree. BTW, I confess I was surprised to find that both the mean and the correlation of $X_n$ are constants, perhaps I'm missing some basic insight and some simpler solution.

What you are seeing is called the Law of large numbers.

The greater the number of random choices you make the more closely the numbers will converge to their probabilities.

As this is a Binomial distribution and therefore has a finite first moment (mean) then it satisfies the criteria for strong convergence.

So for a probability of selecting $A$ of $p_a$ and an initial value of $A_0$ and $B_0$, after $n$ trials you will almost surely converge to:

$$A_n=np_a+A_0$$
$$B_n=n(1-p_a)+B_0$$

And, because we know the structure of Binomial distribution very well we can go further and state that they will have a mean of $np_a+A_0$ and $n(1-p_a)+B_0$ respectively with a variance of $np_a(1-p_a)$.

Now, for sufficiently large $n$, $A_0$ and $B_0$ are insignificant. So the initial values are irrelevant. How irrelevant you can quantify from the variance.


A Limit Question of 0/0 Uncertainty This questions of mine, I couldn't solve whatever I did. Please do not use L'hospital as it has not been taught to us and I don't think that kind of answer will be accepted in the exam.

$$\lim\limits_{x\to 0} \frac{3x + \sin^2x}{\sin2x - x^3}$$

Here is something to get you started:

To what is this limit evaluated:

$$\lim_{x\rightarrow 0} \frac{\sin x}{x}$$

You, probably, know the answer, that the above limit is $1$. Now, divide nominator and denominator by $x$. This should result in:

$$\lim_{x\rightarrow 0}\frac{3+ \frac{\sin^2 x}{x}}{\frac{\sin 2x}{x}- x^2}$$

Then , write that $\frac{\sin^2 x}{x}$ as $\frac{\sin x \cdot \sin x}{x}$ use the limit above I presented you with. At the denominator make a change of variable $u \mapsto 2x$ and make use of the limit I presented you with again.

I am pretty sure you can take it from here. :)

What you basically do when using l'Hospitals rule is to use Taylor expansions of the denominator and nominator. Your example would be

$${3x + \sin^2x\over\sin2x - x^3} = {3x + (x + O(x^3))^2\over2x + O(x^3) - x^3}$$

Then it's quite obvious that the limit will become $3/2$. Now the trick if you don't get to use l'Hospital is to only use the knowledge and do the same thing without showing that we in fact uses l'Hopsital. What happens in this fraction is that $(x+o(x^2))^2 = O(x^2)$ and $x^3 = O(x^3)$ and "disappears" under limit.

To formalize this:

We know that $\lim_{x\to0}x^{-1}\sin x=1$ so we can write $\sin(x) = x\phi(x)$ where $\lim_{x\to0}\phi(x)=1$. That will take care of the ordos:

$${3x+\sin^2x\over\sin2x-x^3} = {3x + x^2\phi(x)\over 2x\phi(2x) - x^3}={3\over2}{1+x\phi(x)/3\over\phi(2x)-x^2/2}\to3/2$$

Then it's just a matter of combining the limits of the parts, the limit of the nominator and denominator of the last ratio is $1$.

Then you only hand in the part after "To formalize this:" and your examiner can't complain that you're using "forbidden" techniques (even though you do).


Finding solutions to the diophantine equation $xy(x+y) = n$. I initially wanted to prove that there are no integer solutions for the equation $xy(x+y) = 4$, but I got intrigued by the general case as I noticed that there tends to be solutions when $n$ is in the form $2^a$. For example, $4 \times 4 \times(4+4)=2^7$. I have tried using the quadratic formula to solve for x in terms of y to reduce the original equation to a single-variable equation, but it gets far too messy:

$$ x = \frac{-y^2 \pm \sqrt{y^4 + 4ny}}{2y} \\
(-\frac{y^2}{2} \pm \frac1{2}\sqrt{y^4+4ny})(\frac{y}{2} \pm \frac1{2y}\sqrt{y^4+4ny})=n
$$

I also see that $xy(x+y)$ is a multiplication of three almost independent (since addition makes factoring hard) terms, so we would have to somehow split numbers into 3 divisions.

Are there any concise special cases for n? And how would you approach disproving the existence of solutions given a specific n?

This may help:
If $xy(x+y)=n$ then $(x+y)^3=3n+x^3+y^3$ which means $3n=(x+y)^3-x^3-y^3$ which shows that $3n$ is of a special kind, since we know that not every number is represented with $3$ cubes (with mixed sign).


Orthogonal projection of point onto line not through origin What is the orthogonal projection of the point $(8,3)$ onto the line $y = -2x - 3$?

Using basic analytical methods, I get the point $(-4/5,-7/5)$, but I want to obtain this point by seeing what happens to the standard basis vectors. But I always end up with the matrix
$$
\begin{bmatrix}-1&-\frac{8}{5}\\-1&\frac{1}{5}\end{bmatrix},
$$
and
$$
\begin{bmatrix}-1&-\frac{8}{5}\\-1&\frac{1}{5}\end{bmatrix}\begin{bmatrix}8\\3\end{bmatrix}
=\begin{bmatrix}-\frac{64}{5}\\-\frac{37}{5}\end{bmatrix}
\neq\begin{bmatrix}-\frac{4}{5}\\-\frac{7}{5}\end{bmatrix}.
$$
Can anyone tell me where I'm going wrong?

Projection onto a line that doesn’t pass through the origin is not a linear transformation, but it is an affine transformation. This means that it can be represented by a matrix, but you need to use a $3\times3$ matrix and homogeneous coordinates.

There are several ways to build this matrix. Since your approach of computing the projections of the basis vectors does work for a line through the origin, let’s take advantage of that method by adding a couple of translations: first translate so that the line passes through the origin, project onto the translated line, then translate back. Any point on the line will do for these translations, so we’ll use the $y$-intercept $\mathbf t=(0,-3)$ since it can be read directly from the equation of the line. Letting $P_2$ stand for the $2\times2$ matrix of the projection onto the translated line, the projection onto the original line is then (in block form): $$P=\left[\begin{array}{c|c}I_2 & \mathbf t \\ \hline \mathbf 0^T&1 \end{array}\right]\left[\begin{array}{c|c}P_2&0\\\hline\mathbf 0^T&1\end{array}\right]\left[\begin{array}{c|c}I_2&-\mathbf t \\\hline \mathbf 0^T&1\end{array}\right] = \left[\begin{array}{c|c} P_2 & \mathbf t-P_2\mathbf t \\\hline \mathbf 0^T&1\end{array}\right].$$ Here, $I_2$ stands for the $2\times2$ identity matrix. The columns of $P_2$ are the projections of $(1,0)$ and $(0,1)$, respectively, onto the translated line, giving $$P_2=\left[\begin{array}{rr}\frac15&-\frac25\\-\frac25&\frac45\end{array}\right]$$ and $\mathbf t-P_2\mathbf t=\left(-\frac65,-\frac35\right)$  (I’ll leave it to you to work out for yourself and verify these values), so the full projection matrix is $$P=\left[\begin{array}{rrr}\frac15&-\frac25&-\frac65 \\ -\frac25&\frac45&-\frac35 \\ 0&0&1\end{array}\right].$$ To use this matrix, you need to append a $1$ to the coordinates of the point being transformed and then drop that $1$ after you’ve found the product, e.g., $$\left[\begin{array}{rrr}\frac15&-\frac25&-\frac65 \\ -\frac25&\frac45&-\frac35 \\ 0&0&1\end{array}\right]\begin{bmatrix}8\\3\\1\end{bmatrix}=\begin{bmatrix}-\frac45\\-\frac75\\1\end{bmatrix}.$$ Since the last component of the product $P(x,y,1)^T$ is always going to be $1$, you can drop the last row of the matrix instead if you like. You can also verify that the projections of $(1,0)$ and $(0,1)$ computed with this matrix are the same as the values that you were getting “by hand.”

Observe that $\mathbf t-P_2\mathbf t$ is the orthogonal rejection of $\mathbf t$ from the translated line. In other words, it’s the component of $\mathbf t$ perpendicular to the line, but this is just the perpendicular displacement of the original line from the origin. (That’s why we could take any point on the line for $\mathbf t$). This shift perpendicular to the line is what was missing from your initial attempt.

$y = -2x-3$ is denoted by $<(1,-2)>$ named A

The orthogonal projection of point $<(8,3)>$  named $\bar x$ subtract (-3) from the y vector to obtain a new $\bar x$ to give you $<(8,6)>$ is given by

$ A(A^{T}A)^{-1}A^{T}\bar x$

$(1,-2)\left((1,-2).(1,-2)\right)^{-1}\times\left((1,-2).(8,6)\right) = (1,-2)(\frac{1}{5}\times -4)= \frac{-4}{5}<(1,-2)> = <(\frac{-4}{5},\frac{8}{5})>$ and now add -3 to y vector to get the projected point which will give you

$<(\frac{-4}{5},\frac{-7}{5})>$.


Unexpected use of polynomials in combinatorics Can someone please post some (relatively easy, say high school level) combinatorial problems which can be solved with polynomials but NOT generating functions.
Related to this post in ME.SE.

Problem:  Is it possible to weight two dice (possibly unequally) in such a way that every sum from $2$ to $12$ is equally probable?

The Answer is No.

Comment:  I set this problem for high school students a few years back. These were students who did well at competition style problems. They found this one difficult, but were able to make very good progress on it, and arrived at the first proof entirely on their own. They got the second after the basic idea was proposed to them. It's not intended to be an easy problem and it may well be more difficult than you were looking for.

Motivating Example:  to see that you can not do this with equally weighted dice, suppose you could and let $p_i$ be the probability a given die comes up $i$.  Then $p_1^2=p_6^2=\frac 1{11}\implies p_1=p_6=\sqrt {\frac 1{11}}$ But then the probability of getting a $7$ is at least $2p_1p_6=\frac 2{11}$, a contradiction.

Direct proof (no polynomials):  Say the probabilities for the first die are $p_i$ and for the second $q_i$.  Then $p_1q_1=\frac 1{11}=p_6q_6$.  But then we can get a lower bound on the probability of throwing a $7$ as $$\text {Prob}(Sum = 7)≥p_1q_6+p_6q_1=p_1\times \frac {1}{11p_6}+p_6\times \frac {1}{11p_1}=\frac 1{11}\times \left(\frac {p_1}{p_6}+\frac {p_6}{p_1}\right)≥\frac 2{11}$$ so we reach the same contradiction as in the equally weighted case.  Here, of course, we have used the fact that $x+\frac 1x≥2$.

Proof using polynomials:  Let the $p's$ and $q's$ be as above.  Define two polynomials $$P(x)=\sum_{i=1}^6p_ix^i\quad \&\quad Q(x)=\sum_{i=1}^6q_ix^i$$

Note that both $P(x), Q(x)$ are divisible by $x$ and that $P(1)=Q(1)=1$.

If the weightings were to work we'd have the product $$P(x)Q(x)=\frac 1{11}\sum_{i=2}^{12}x^i=\frac {x^2}{11}\frac {x^{11}-1}{x-1}$$

However, this is impossible.  Indeed, factoring out the factors of $x$ from $P(x),Q(x)$ we get two polynomials of degree $5$ each (noting that neither $p_6$ nor $q_6$ can be $0$).  As $5$ is odd, these must have at least one real root each...but $x^{11}-1$ has no real root other than $1$ (which is not a root of $P(x)$ nor $Q(x)$).

See Lucas's Theorem. There is one proof with groups and another with polynomials. Both are very nice. (There is a third by induction but it is pretty bad.)


Propositional logic meets diplomacy at the workplace This is just a funny little incident that made me think. Please don't take it too seriously or the wrong way. I would still like to hear your opinion on it, though.

I wrote an email to a colleague the other day, concerning some other colleagues who have certain data but are not very keen to share them. I wrote to her:

  If they don't give us those data, we can't calculate, etc.

She forwarded my email to one of them, but, first, very cleverly, she changed my sentence to

  If they give us those data, we can calculate, etc.

to make it sound more positive. At first, I thought "this means the same but it's nicer', but then I wondered if, strictly logically, the two sentences were really the same.

Let:

$a$ = "they give us the data"
$b$ = "we can calculate"

I first checked if the original statement implied the modified one.

$$(\bar a \to \bar b) \to (a \to b)$$

This worked out to:

$$\bar a \lor b$$

i.e.

$$a \to b$$

So it looks like the original statement implies the modified one only when the modified one is true. This is already very puzzling to me.

Then I tried this:

$$(\bar a \to \bar b) \leftrightarrow (a \to b)$$

which worked out to:

$$(\bar a \land \bar b) \lor (a \land b)$$

i.e., the original and modified statement are equivalent if $a$ and $b$ are both true or both false. And, apparently, this is the same as:

$$(a \lor \bar b) \land (\bar a \lor b)$$

i.e.:

$$(\bar a \to \bar b) \land (a \to b)$$

Does any of the above make sense?

And if so, is there any way to explain with an example that the original and modified statement don't mean the same?

Thanks!

"If they give us the data ... and we are still alive, and the data is legible, and ....  then we can calculate"

The point is:  your original statement made it clear that having the data is a necessary condition for being able to calculate ... but that is not the same as saying that having the data will be sufficient to be able to calculate the data, which is what your colleague's statement says.

$\neg A\implies \neg B$ is equivalent to $B\implies A$, not $A\implies B$ so you are correct in saying they are not logically equivalent.

In your case they are equivalent because you really have $A\iff B$, i.e. We can do the calculation if and only if we get the data.


Solve for $a,b,c$ given $1/a + 1/b = 1/c$ and a couple other constraints Suppose $a, b, c \in \{4, 5, \ldots, 21\}$ and satisfy $1/a + 1/b = 1/c$. Suppose also that $\gcd(b,c)=1$. Find $a, b, c$.

I tried this problem and I got the answer,
but I can't to understand how $\gcd(b-c,c^2)=\gcd(b,c)$. when gcd(b,c)=1

My attempt:
From question we can see that $b > c$. On
simplifying, we get $$a = c + \frac{c^2}{b-c}.$$

Obviously $b>c$. Multiply both sides by $abc$ to get$$bc+ac=ab$$It follows immediately that$$a=\frac{bc}{b-c}=\frac{bc-c^2+c^2}{b-c}=c+\frac{c^2}{b-c}$$So $b-c|c^2$, but $\gcd(b-c, c^2)=1$ since $\gcd(b, c)=1$. Hence we must have $b-c=1$, which in turn gives $a=c+c^2$.

From $c+c^2=a<22$ one gets $c<5$, so $c=4$ and thus the only solutions is$$(a, b, c)=(c+c^2, c+1, c)$$Where $c=4$.

As you say, $a,b \gt c$.  Presumably you demand $a \neq b$ or there would be many solutions with $a=b=c/2$.  We can demand $a \gt b$ and just try values for $b-c$.  If $b-c=1$, we have $a=c+c^2$ and the only value in range is $c=4, a=20, b=5$.  If $b-c=2,$ we must have $c$ even and $a=c+c^2/2$, which works with $c=4, a=12, b=6$, but $c=6$ makes $a$ too large.  $b-c=3$ gives $a=c+c^2/3$ and gives $c=6, b=9, a=18$.  $b-c=4$ fails because it either gives $c=4, a=8, b=8$ or $c=8, a=24$.  All higher $b-c$ also fail (you need to prove this), so we have three solutions.


Does the complex number $3 + i\sqrt3 $ have a purely imaginary power? I'm trying to find if this affirmation is true or false:

As $z= 3 + i\sqrt3 $ where $i$ is the imaginary unit

I would know if ∀$n$ $\in \mathbb{N} \neq 0$, $z^{3n}$ is a pure imaginary number.

I tried some weird calculations but nothing work... Could you help me?

If you are not familiar with polar coordinates yet, use induction.

Let $z = 3 + \sqrt{3}i$. We claim that $z^{3(2n+1)}$ is purely imaginary for $n \in \mathbb{N}_0$.

For $n=0$, we have
$$z^3 = 3^3 + 3 \cdot 3^2 \cdot \sqrt{3} i - 3 \cdot 3 \cdot 3 - 3 \sqrt{3}i,$$
which is clearly purely imaginary. Assume $z^{3(2n+1)}$ is purely imaginary for some $n \in \mathbb{N}_0$. Then,

$$z^{3(2n+3)} = z^{3(2n+1)+6} = z^{3(2n+1)} z^6.$$

Note that $z^6 =z^3 \cdot z^3$, which must be purely real since $z^3$ is purely imaginary. Therefore, $z^{3(2n+3)}$ is purely imaginary.

-

In polar coordinates,

$$z = 3 + \sqrt{3} i = \sqrt{12} e^{i \pi/6}.$$

Recall that $e^{i\pi (n + 1/2)}$ is purely imaginary for all $n \in \mathbb{Z}$.

$(3+i\sqrt 3)^n=(2\sqrt 3)^n (\sqrt 3 /2 +i/2))^n=(2\sqrt 3)^n (\cos 30^o+i\sin 30^o)^n.\quad$ Use DeMoivre's Theorem :$ (\cos A +i\sin A)^n=\cos (n A)+i\sin (n A).$ Observe that $\cos (30n)^o=0 $iff $n/3$ is an odd integer.


Plantinga's logical argument for mind-body dualism Some may feel this is not appropriate for the mathematics stack exchange, but it is a question in logic, and I feel it is entirely a good fit. The following argument has been put forth by the philosopher Alvin Plantinga in favor of mind-body dualism. I cannot see any logical error, but also have a hard time believing dualism has been demonstrated by a purely logical argument. If someone could please point out what is logically wrong with this, I would be appreciative.

The argument:

If A and B are identical then any statement of A is true of B and vice versa.
I can imagine existing without my body, for example in the body of a bird. I cannot imagine my body existing without my body.
By (2) we showed the existence of a statement that is true of (me) but not true of my (body).
By (1) my body and me are not identical.

End argument.

is true by definition. The first part of 2. is true by my experience -- I can imagine waking up in a bird's body, can you? The second part of 2. is true by my experience, and if I'm not mistaken it must be true of everybody's experience since one cannot imagine something logically invalid -- my body is my body by definition and cannot exist and not exist at the same time (P and $\not$ P cannot both be true). 3. and 4. are simply logical conclusions.

Has Plantinga rigorously proven an age old philosophical position defended by Descartes hundreds of years ago?

Update: Maybe this is better suited for the philosophy stack exchange? Could I please have it moved? Thank-you.

If A and B are identical then any statement of A is true of B and vice versa.
I think the unidentified serial killer is a horrible person. I do not think my son is a horrible person.
Therefore, my son is innocent.

Further reading: masked man fallacy.

Also, even if one accepts the argument as stated, the kind of mind-body dualism it supports is in any case an extremely mild one, of the same sort as the President/Obama dualism. (Replacing "me" and "my body" with "the President" and "Obama" in the posted argument is a fun exercise.) That doesn't mean that Obama is not the President, nor does it confer upon the office of the President some mysterious metaphysical status.

Are you sure what you've written is exactly Plantinga's argument? Perhaps there is some subtlety lost in your paraphrasing?

He is proving the wrong proposition for his purposes.  What he should establish is:

  my (body) cannot imagine existing without its body, for example, in the body of a bird.

If his (body) can imagine that, then we have not found something to differentiate his mind and his body.


The use of combination in statistics Why can't we use 0 in combination?
Like for example, count the probability of a person wins at least one prize if he buys 10 out of 1000 tickets in which 5 tickets will be drawn to be the winner. The solution shows that the P is 1- 5C990/5C1000.
Why cant I use 1 - 0C10/5C1000 instead? Thank you

Actually, the correct calculation is $$P=1-\frac{\binom{10}{0}\binom{990}{5}}{\binom{1000}{5}}$$
Representing that out of the $5$ cards picked from $1000$, $0$ winners are picked from the $10$ tickets that he bought, and  $5$ winners are picked from the $990$ he didn't
But $\binom{10}{0}=1$, so it is just left out of the solution.
For a calculation of the form $$\frac{\prod_{j\in\Bbb N}\binom{x_j}{y_j}}{\binom xy}$$ to be accurate in representing a probability we require that $\sum_{j\in \Bbb N} y_j= y$


Finding exact value(s) of x in $4\sin(x)\cos(x)-3\sin(x)=0$ One solution is $x = n\pi, n\in \mathbb{Z}$
The second one is $\cos(x) = \frac{3}{4}$
I do not know how to find an exact value for x in the second one.

$$\cos x=\frac34$$ naturally has the solution

$$x=\arccos\frac34.$$

As the cosine is an even function ($\cos x=\cos(-x)$) and has period $2\pi$, the solutions are

$$x=\pm\arccos\frac34+2k\pi.$$

so here i attach the graph of $y = \sin(x) \cos(x) - 3\cos(x)$ in the interval $[-4\pi,4\pi]$. There are 17 roots (intersection of $ y = 0 $ with $y = \sin(x) \cos(x) - 3\cos(x)$ ) in the interval  $[-4\pi,4\pi]$.

As you have said, you have roots of the form $n\pi$ (which are $-4\pi \ldots 4\pi)$. Those are 9 roots.

The other 8 are in the form of $\cos(x) = \frac{3}{4}$ also as you said. Also as @Mundron Schmidt suggests, the solutions of $\cos(x) = \frac{3}{4}$ are in the form of
\begin{equation}
x = \pm \arccos(\frac{3}{4}) + 2n \pi \qquad n \in \mathbb{Z}
  \end{equation}
which is the simplest form. And those are the 8 other roots in $[-4\pi,4\pi]$


What is a good text in intermediate set theory? I've been working my way through Enderton's Elements of Set Theory for a while, and I feel I have a decent grasp on some of the basics of elementary set theory. My question is, where should I look to next in set theory? What is a good book for set theory that may be considered 'the next step up'?

If it helps any, my background knowledge consists of some basic abstract algebra, general topology, linear algebra, etc., but I'm not sure how often they are used in real set theory. Thanks.

I have not read it myself, however I got a good recommendation from one of my teachers -

Azriel Levy's Basic Set Theory.

Jech's Set Theory is a great book but I think it is indeed slightly too advanced, he writes that the first part contains full proofs (I only read chapters from the second parts, in which proofs are many times sketched out and the details are left for the reader). Once you've got the basic theorems down, one might also check The Handbook Of Set Theory written by an ensemble of competent writers, for more specific topics.

Paul Halmos Naive Set Theory is an Excellent text


Change of variable problems in probability If $X$ is a continuous random variable with positive values,find it's Cumulative distribution function (CDF) and it's probability density function (PDF) for $$Y = \sqrt{X}$$

This was a detable question on another topic so I made it a seperate one.

Can someone explain how do we solve this problem to it's end? (putting some theory/ explanations in between would be appreciated. My goal is to understand the concepts that are behind this and be prepared for problems of equal difficulty). Thank you.

  Added by A.F. This was originally the "third pattern" of this question.  Possible solutions may exist on the linked question.

$$P(\sqrt{X}\leq t)=P(X\leq t^2)=F(t^2)$$
where $F$ is the cumulative distribution function of $X$. Therefore pdf of $Y$ is
$$\frac{dF(t^2)}{dt}=f(t^2)\times2t$$
where $f$ is the pdf of $X$.

See any elementary book on probability and statistics, for a better understanding of transformation of random variables.

$\newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\expo}{{\rm e}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert #1 \right\vert}$
$$
{\rm P}_{Y}\left(Y\right)\,{\rm d}Y
=
{\rm P}_{X}\left(X\right)\,{\rm d}X
\quad\imp\quad
\color{#ff0000}{{\rm P}_{Y}\left(Y\right)}
=
{\rm P}_{X}\left(X\right)\,{{\rm d}X \over {\rm d}Y}
=
{\rm P}_{X}\left(X\right)\,2Y
=
\color{#ff0000}{2{\rm P}_{X}\left(Y^{2}\right)Y}
$$


Can you compare sequences with information about their series? Let $a_n$ and $b_n$ be a sequence of non-negative, non-increasing numbers such that
$$A(x):=\sum_{n\leq x} a_n \leq \sum_{n\leq x} b_n := B(x)$$
for all $x$.

Can you conclude that $a_n \ll b_n$?

You need the non-negative condition because otherwise you could have $a_n$ going to negative infinity $b_n$ be some something that converges to a positive number.

You need the non-increasing condition because otherwise you can set $b_n=1$ and let $a_n$ be $0$ most places but then large in some places so that there is a subsequence of the $a_n$ that tends to infinity (i.e. $a_{10^n}=n$ but $a_n=0$ for $n$ not a power of $10$).

Are these the only conditions you need to conclude that $a_n\ll b_n$? If not, what other conditions do you need? Any solution or reference would be appreciated.

Take $a_n=b_n$, then you wont have $a_n<b_n$, so probably not $a_n<<b_n$ either


Quickest way to solve PDE with variation of parameters I have an exam question to solve the following PDE:
$$
  x^2y^{''}-4xy^{'}+6y=21x^{-4}
$$
This problem is supposed to be solved by the variation of parameter method(Wronskian). For finding the solution of the homogenous part I used the Euler cauchy method, but it turns out it gets very computationally intensive. What is the quickest way (and less prone to mistakes) to do this? (With the variation of parameters)

Assuming that the problem is $$x^2y''-4xy'+6y=21x^{-4}$$ For the homogeneous equation, assume $y=x^a$ and replace. This let you with $$(a-3) (a-2) x^a=0$$ So, you have $$y=c_1x^2+c_2x^3$$

After you find the solutions to the corresponding homogeneous ODE, you can find $y_p$ by variation of parameters, then the general solution to the original ODE is the sum of $y_p$ and a general linear combination of the $x^2$ and $x^3$.

Alternatively, you assume that the general solutions is something like $y=v*x^2$ ($x^2$ is a solution to the corresponding homogeneous ode, and $v$ is a function of $x$). Then, $y'=v'*x^2+2vx$ and $y''=v''*x^2+4v'x+2v$.
Substituting $y$ and its derivatives in the original ode, you end up with
$v"=21x^{-8}$

Integrate twice to get $v$, then multiply by $x^2$ to get $y$.

Hope this helps


How to prove the convergence of $\lambda_n = \frac{f_{n+1}}{f_n}$? A question about the fibonacci sequence.

I have a sequence:

$$\lambda_n = \frac{f_{n+1}}{f_n}$$

While $f_n$ is the fibonacci sequence.

I also have the equation: $$ 0 = x^2 - x -1$$
And i know that the two possible values for x are:

$$x= \frac {1\pm \sqrt{5}}{2}$$

(The famous golden ratio)

Let $\alpha$ be the positive solution for the above equation. Let $\beta$ be the negative one.

I want to show that $$\sigma_n = \frac {\lambda_n - \alpha}{\lambda_n - \beta}$$

converges (It does converge against 0 right? Because $\lambda_n$ converges against $\alpha$ But how would i go on proving it?).

I know about Cauchy's convergence criterion, and the definition for limits.. etc.
I don't get how to apply them here. For me, the coherence between the fibonacci sequence and the golden ratio is really hard to understand.

P.S: This is an exercise in analysis 1 (computer science), first term. I have seen questions like: Fibonacci and the algebraic expression $x^2-x-1$

But i can't understand these because i haven't ever seen most of the stuff they do there in our lectures.

To prove the convergence, I'll directly compare successive terms of $\lambda_n - \phi$ where $\phi$ is the golden mean (i.e. your $\alpha$). Notice

$$\frac{\lambda_n - \phi}{\lambda_{n-1} - \phi}
= \frac{F_{n+1} - \phi F_n}{F_n - \phi F_{n-1}}\frac{F_{n-1}}{F_n}
= \frac{(1-\phi)F_n + F_{n-1}}{F_n - \phi F_{n-1}}\frac{F_{n-1}}{F_n}\\
\stackrel{\color{blue}{[1]}}{=} \frac{(1-\phi)F_n - F_{n-1}\phi(1-\phi)}{F_n - \phi F_{n-1}}\frac{F_{n-1}}{F_n}
= (1-\phi)\frac{F_{n-1}}{F_n}
$$
Since $F_n$ is increasing, $\left|\frac{F_{n-1}}{F_n}\right| \le 1$. Together with $|1 - \phi| = \phi^{-1} < 1$, we get

$$\left|\frac{\lambda_n - \phi}{\lambda_{n-1} - \phi}\right| < \phi^{-1}
\quad\stackrel{\color{blue}{[2]}}{\implies}\quad
| \lambda_n - \phi | \le \phi^{-(n-1)} |\lambda_1 - \phi| = \phi^{-n}
\to 0\;\text{ as }\; n \to \infty
$$

As a result, $\lim\limits_{n\to\infty} \lambda_n = \phi$.

Update

As an alternate approach, one can compare the successive terms of $\sigma_n$. Notice

$$\begin{align}
\sigma_n &= \frac{\lambda_n - \alpha}{\lambda_n - \beta}
 = \frac{F_{n+1} - \alpha F_n}{F_{n+1} - \beta F_n}\\
&= \frac{(1-\alpha)F_n + F_{n-1}}{(1-\beta)F_n + F_{n-1}}
 = \frac{(1-\alpha)F_n - \alpha(1-\alpha)F_{n-1}}{(1-\beta)F_n - \beta(1-\beta)F_{n-1}}\\
&= \frac{1-\alpha}{1-\beta}\frac{\lambda_{n-1}-\alpha}{\lambda_{n-1}-\beta}\\
&= \frac{\beta}{\alpha}\sigma_{n-1}
\end{align}
$$
Since $\left|\frac{\beta}{\alpha}\right| < 1$, we find

$$\lim_{n\to\infty} \sigma_n \stackrel{\color{blue}{[2]}}{=} \lim_{n\to\infty} \left(\frac{\beta}{\alpha}\right)^{n-1} \sigma_1 = 0
\quad\implies\quad
\lim_{n\to\infty} \lambda_n = \lim_{n\to\infty} \frac{\alpha-\beta\sigma_n}{1-\sigma_n} = \frac{\alpha - \beta\cdot 0}{1-0} = \alpha$$

Notes

$\color{blue}{[1]}$ - We are using the identity $1 = -\phi(1-\phi)$ here.
$\color{blue}{[2]}$ - We are using the fact $|\lambda_n - \phi|$ is equal to
the product of $|\lambda_1 - \phi|$ with a telescoping products of ratios. More precisely,
$$|\lambda_n - \phi| =
\underbrace{\left|\frac{\lambda_n - \phi}{\lambda_{n-1} - \phi}\right|}_{ < \phi^{-1}}
\underbrace{\left|\frac{\lambda_{n-1} - \phi}{\lambda_{n-2} - \phi}\right|}_{ < \phi^{-1}}
\cdots
\underbrace{\left|\frac{\lambda_{2} - \phi}{\lambda_{1} - \phi}\right|}_{ < \phi^{-1}}
|\lambda_1 - \phi| < \phi^{-(n-1)}|\lambda_1 - \phi|$$
For the same sort of reasoning, we have $\sigma_n = \frac{\beta}{\alpha} \sigma_{n-1}$ for all $n > 1$ implies $\sigma_n = \left(\frac{\beta}{\alpha}\right)^{n-1}\sigma_1$.

$$
f_n = \frac{\alpha^n-\beta^n}{\sqrt{5}}
$$
where $\alpha = \frac{1 + \sqrt{5}}{2}$ and $\beta = \frac{1 - \sqrt{5}}{2} = -\frac{1}{\alpha}$.

A bit of algebra gives
$$
\lambda_n = \frac{\alpha^{n+1}-\beta^{n+1}}{\alpha^n-\beta^n}
$$
$$
\sigma_n =\frac{\alpha\beta^b-\beta^{n+1}}{\alpha^{n+1}-\beta\alpha^n}= \left(\frac{\beta}{\alpha}\right)^n=(-1)^n\alpha^{-2n}
$$
And since $|\alpha| > 1$ this converges to zero.


The limit of a function approaching infinity Suppose $f\in C(0,+\infty)$,and $\forall x \in (0,+\infty)$,we have
\begin{align}
\lim_{n\to \infty}f(nx)=0
\end{align}
where $n$ is positive integer.How to show that $\lim_{x\to\infty}f(x)=0$?

I have tried proof by contradiction, if not, $\exists \epsilon>0$, such that $\forall M>0$,$\exists y>M$, s.t. $|f(y)|>\epsilon$. But I got stuck here because I have no idea how to use the continuity to get contradiction.

Thanks for your attention.

By definition, we can rephrase $\lim_{n \to \infty} f(nx) = 0$ as "For all $x > 0$, for any $\epsilon > 0$, there exists $N \in \mathbb{N}$ such that for any $n \ge N$, $|f(nx)| < \epsilon$."

Consider the special case $x = 1$.  Then we have: for any $\epsilon > 0$, there exists $N \in \mathbb{N}$ such that for any $n \ge N$, $|f(n)| < \epsilon$.  By definition, this means that $\lim_{n \to \infty} f(n) = 0$.  Rename your variable $n$ as $x$ and we have $\lim_{x \to \infty} f(x) = 0$.


If $p_n = \frac {2}{n}+ (-1)^n$, compute sequence $P_n = sup\{p_m: m\ge n\}$ and find $\lim_{n\to 0}$sup $p_n$. If $p_n = \frac {2}{n}+ (-1)^n$, compute sequence $P_n = sup\{p_m: m\ge n\}$ and find $\lim_{n\to \infty}$sup $p_n$.

If n is even, $p_n = \frac{2}{n} + 1$ and $p_n \to 1$as $n\to \infty$

If n is odd, $p_n = \frac{2}{n} - 1$ and $p_n \to -1$as $n\to \infty$

Then $\lim_{n\to \infty}$sup $p_n = 1$

But $P_n =sup\{p_m: m\ge n\}=sup\{p_n, p_{n+1}, ...\} $

If $n=1$, then $P_1 = sup\{1,2,-\frac{1}{3}, \frac{3}{2}\,-\frac{3}{5}, \frac{4}{3}....\}$ ($P_1=2$, I think)

This is where I am having problem.

Note that the subsequence $\langle p_{2n}:n\in\Bbb Z^+\rangle$ is strictly decreasing, and that $p_{2n}>p_{2m-1}$ for all $m,n\in\Bbb Z^+$: every term with an even index is greater than $1$, and no term with an odd index is greater than $1$. Thus, $P_n$ is simply going to be $p_m$, where $m$ is the smallest even integer greater than or equal to $n$. That is,

$$P_n=\begin{cases}
p_n,&\text{if }n\text{ is even}\\
p_{n+1},&\text{if }n\text{ is odd}\;.
\end{cases}$$

From here I expect that you can easily find $\limsup\limits_{n\to\infty}p_n=\lim\limits_{n\to\infty}P_n$.

if $n = 2k-1$ is odd, $P_n = (k+1)/k$

if $n = 2k$ is even, $P_n = (k+1)/k$

and $\lim_{n \rightarrow \infty} \sup(p_n) = \infty$


Let $a_0=a_1=1$. Define $a_{n+1}=\frac{1+a_n+a_{n-1}^2}{4}$, does it converge? Let $a_0=a_1=1$. Define $a_{n+1}=\frac{1+a_n+a_{n-1}^2}{4}$. Does the sequence {$a_n$} converge to a finite limit as $n \to \infty$? Find this limit if it does?
Putting in successive value of n shows the value decreases as n increases, so it must converge. And then we can solve for $l=\frac{1+l+l^2}{4}$, to get the limit. Now I don't know how to formally prove that it converges.

Hint: show by induction that the sequence is nonincreasing and positive.


Recurrence $T(n)=2T([n/2]+17)+n$ and induction. Show that the solution to
$$T(n) = 2T\left(\biggl\lfloor \frac n 2 \biggr\rfloor+17\right)+n$$
is $\Theta(n \log n)$?

So the induction hypothesis is
$$ T \left( \frac n 2 \right) = c\cdot \frac n2 \cdot \log \frac n2.$$
Hence,
$$ T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n $$

but how do I continue from here?

Hint:  Now you want to prove that the right side is less than $cn \log n$.  The $2$'s cancel nicely.  Now write $\log \frac n2 = \log n - \log 2$.  If $c$ is large enough you can take care of the $n$ term, and if $n$ is large enough the $17$ won't matter.

Write it as:  $$T(n)=2\cdot T\bigg(\frac{n+34}{2}\bigg)+n$$
Alternative form: if we continue, we get:
$$\frac1{2} \bigg(-34+n\bigg) c+\frac1{2} \bigg(-34+n\bigg) \bigg(68 \bigg(1-\frac1{-34+n}\bigg)+\frac{(2 \log(-34+n))}{\log2}\bigg)$$


Proof the Existence and Uniqueness of Factorization Form of Polynomial with Complex Coefficient If $p\in P(\Bbb{C})$ is a nonconstant polynomial, then $p$ has a
  unique factorization (except for the order of the factors) of the form

  $$p(z)=c(z-\lambda_1)....(z-\lambda_m)$$

  where $c,\lambda_1,....\lambda_m \in \Bbb{C}$

I know how to prove the existence of the form. However, I don't know how to do it with the uniqueness of the form.

I know that $c$ must be unique, because $c$ equals the coefficient of $z^m$ in $p$. But how to prove that each $\lambda_j$ is unique?

And I also don't understand why the coefficient must be $\Bbb{C}$, but why doesn't this apply to $\Bbb{R}$?

You can show that in $\mathbb{C}$, all linear functions are prime, and there do not exist primes which are not linear.

Lemma 1: If $p$ is prime and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. Let $p$ not divide $a$. Then as $p$ is relatively prime to $a$, $gcd(p,a) = 1$ and so $\exists x,y \in F$ such that $xp + ya = 1$. Multiplying by $b$, we have that $bxp + yab = b$. And we know that $p$ divides $ab$ so $ab = mp$. Thus we have that $bxp + ymp = b$ and so $p(bx + ym) = b$ so $p$ divides b.

The Result: Now, let $f(x) = p_1 \cdot p_2 \cdot p_3 ... \cdot p_n$ where $p_1,.... p_n$ are prime factors. Suppose $f(x) = q_1 \cdot q_2 \cdot ... q_k$ where all $q_i$ are prime factors [We are trying a different factorisation]. Then, each $q_i$ must divide $f(x) = p_1 \cdot p_2 \cdot p_3 ... \cdot p_n$ and by Lemma 1, they must divide some $p_i$. But a prime is such that if $q_i$ divides $p_i$ then $q_i$ is an associate of $p_j$.  If we ignore the difference between a function and its associate, we can see that $q_i = p_j$ [effectively] and so we must have that each $q_i$ corresponds to a different $p_j$ and so we have that $n = k$ and the factorisation is unique.

Note: In $\mathbb{R}$, there can be quadratic equations which are prime as pointed out in the comment (They have complex factors only). Therein lies a fundamental difference.


A boat is to be manned by 8 men,of whom 2 can only row on bow side & 1 can only row on stroke side;in how many ways can the crew be arranged? I tried it by selecting 2 men out of 8 for bow side,and then arrange them in 2! ways.This can be done in$ \binom{8}{2}$*2! ways,and the stroke side can be crewed in 6 ways.So the required no. of ways are $\binom{8}{2}$*2!*6=336.
But,my answer is not matching.It's correct answer is 5760.

Please help me in pointing out my mistake.

You can select which two of the five who can row either side should row Bow in ${5\choose2}=10$ ways. That determines which four row Bow an which four row Stroke. Now you have $4!$ ways of arranging the Bow side and $4!$ ways of arranging the Stroke side. So total $10\cdot4!\cdot4!=5760$.

My answer is best as it is using basic principle
Consider 4 each on both sides
Then for 1st side we require 2 people so no. Of ways is 4(for 1st person)*3(for other one)
Then for 2nd side we require 1 person so he has 4 choice
Then for remaining 5 places we have 5*4*3*2*1 this (arrangement is of remaining people)


Is a finitely generated torsion group finite in general? This is not a duplicate of Can a finitely generated group have infinitely many torsion elements?

There he asks specifically about FC-groups.

Is a finitely generated torsion group finite in general?

Using Dietzmann's lemma allows you to prove this for FC-groups:
Dietzmann's lemma says:
Let G be a torsion group, and M a normal finite subset of G.
Then $\langle M \rangle $ (the subgroup generated by M) is finite.

Now for a finitely generated group G, we take M to be the set of generators.
Then it is finite, but is it normal?

If G is an FC-group then we know every generator in M has a finite conjugacy class (by definition of an "FC group").
And taking the union of the conjugacy classes of the generators gives us a finite union of finite sets, which is finite, and this set is normal because conjugating any element will take us to another element in its conjugacy class which is also in the set.

My question is if there is a way to prove this without the FC-group requirement.
Or better yet, specify what is the required and sufficient condition for G to be finite assuming G is finitely generated and a torsio group.

Some remarks:
In the question I linked to someone specifies that the infinite dihedral group represented by $\langle a,b : a^2 = b^2 = 1\rangle$ is finitely generated but not finite, $a$ and $b$ are torsion elements, but IMO the group is not a torsion group \ so this does not disprove what I am trying to prove.

EDIT:
A correct answer was provided but I will leave the question open a bit in case someone knows a necessary and sufficient condition on G for it to be finite.

No.  This is the General Burnside Problem -- must a finitely generated periodic (this is what you call "torsion": every element has finite order) group be finite? -- to which a negative answer was given by Golod and Shafarevich in 1964.  Please see the linked article for more information.

It is a classical question whether there exist finitely generated groups where every element is torsion. This is called Burnside's Problem. It was posed c1900, and Golod and Shafarevich proved in 1964 that there existed finitely->generated infinite p-groups (for some primes p), although the groups they constructed had unbounded order (for all n∈N there exists g∈G such that o(g)>pn). (from https://math.stackexchange.com/a/109582/491561)

Please see http://www.ijma.info/index.php/ijma/article/download/5635/3299 for a detailed proof of the Burnside problem: Every Finitely Generated Torsion Group is Finite.


How do you determine how many digits of pi are necessary? It is said that you only need to calculate pi to 62 decimal places, in order to calculate the circumference of the observable universe, from its diameter, to within one Planck length.

Most of us are probably dealing with more terrestrial things. Automobile tires, for example. And we can usually tolerate more sloppy calculations. Say, to within one micrometer.

Given a specified scale and/or desired precision, how can we figure out how many digits of pi we really need?

Using $\Delta$ for errors and usual notation otherwise for the circumference of a circle,

$$\Delta C = 2 R \Delta\pi + 2\pi\Delta R$$

If you want $\Delta C$ within some error margin, you usually have to worry first about minimizing measurement error for the radius $\Delta R$. But if that is no longer a constraint, then worry about $\Delta \pi$.

For example, suppose your target error $\Delta C = 1 \ \mu m$ but you can only measure $R$ within one $\mu m$. Then your error for $C$ is $2\pi \ \mu m$ before we even consider $\Delta \pi$. If you could measure $R$ within say $1/10 \ \mu m$, then we can begin to worry about solving for the required number the digits for $\Delta\pi$:

$$\text{ Target value of } \Delta \pi \leq \frac{\Delta C - 2\pi\Delta R}{2R}$$
a quantity that is now positive and meaningful. Suppose in our example that $R = 1 \ m$, then $\Delta \pi \leq 1.86 \times 10^{-7}$ and thus we would want $\pi$ accurate to at least $7$ decimal places.

Um, that depends on the amount of accuracy you need.  That's usually expressed as "significant digits".  If you need accuracy within .01% = 0.0001 margin of error, that is "four significant digits".  Everything, not just pi, can be estimated to four significant digits so it suffices to just use the first four digits of pi.  If you need higher accuracy you use more digits.


If $xR_1y$ if $x^2 + y^2$ is divisible by $5$, is the relation transitive? Been asked to prove if this is/isn't transitive. Not sure where to start on if it is transitive or not. Also by proving it is/isn't, do I simply need to give an example where it is/isn't true?

Thanks!

$R$ is transitive if, whenever $x R y$ and $y R z$, we have $x R z$.  Remembering what the relation means, the question you need to answer is: whenever $x^2 + y^2$ is divisible by 5 and $y^2 + z^2$ is divisible by 5, is $x^2 + z^2$ divisible by 5?

To prove the relationship is transitive, you need to show this is always true.  To prove it is not transitive, you need to find $x, y, z$ such that it's not true - that is, with $x^2 + y^2$ divisible by 5, $y^2 + z^2$ divisible by 5, and $x^2 + z^2$ not divisible by 5.

To prove it isn't true you need one example where it fails but to prove it you have to show it is true for all possible pairs, which means you need algebra.

Play around with some examples of xRy and yRz.


Show that $a_n=\frac{\sqrt{n^{2}+2021n+420}}{\sqrt{n^{3}+2022n+420}}$ is decreasing I need to show that the sequence $a_n=\frac{\sqrt{n^{2}+2021n+420}}{\sqrt{n^{3}+2022n+420}}$ is decreasing.
I tried showing $a_{n+1}\le a_n$ but it was too messy.
I did manage to do it by showing that $f'(x)$ will be negative at some point by taking the limit of the nominator of the derivative to infinity,  but this method was pretty exhausting. I wonder if there a simpler method I just didn't see, and i'd be happy to have it in my "toolbox".
thanks!


Count number of integer tuple I have $n$ integer constants $c_1, \ldots, c_n$ and $n$  integer variables $x_1, \ldots, x_n$ with following conditions:
$$
\begin{align}
& 0 \leq x_1 \leq c_1, \\
& \vdots  \\
& 0 \leq x_n \leq c_n;
\end{align}
$$
and
$$ x_1 \leq \cdots \leq x_n. $$

How to count the number of integer $n$-tuples $\left( x_1, \ldots, x_n \right)$ that satisfy all the above conditions?

I can use the for-loop in a programming language to count. But with some large values of $a$, $b$, $c$, it takes very long time to finish counting (For example $a = b = c = 1000000$).

Please help me to find a concrete formula for this problem.

Here is a sketch of a recursive approach.  It may not be the simplest.

We may as well assume $c_1 \le c_2 \le c_3 \le \ldots c_n$.  If not, reduce the earlier ones so it is true, because if $c_3 \gt c_4$ there are still no acceptable tuples with $x_3 \gt c_4$

Now if $x_2 \gt c_1$ we have $c_1+1$ choices for $x_1$ with the rest of the tuple, so solve the problem removing $x_1$ and subtracting $c_1+1$ from all the later $c$'s, then multiply the resulting answer by $c_1+1$.

If $x_2 \le c_1$ we have the same problem with $c_2$ replaced by $c_1$.  If $x_3\gt c_1$ we need the number of pairs less than $c_1$ for the first two times the number of tuples of length $n-2$ for the end.  Subtract $c_1+1$ from each of the last $n+2\ c$'s and solve the problem.

We have now reduced the problem to the number of increasing tuples of length $k$ with the same maximum $c_1$ for each entry.  We can use stars and bars to see there are $k-1 \choose m-1$ ways to choose the duplicate entries if there are $m$ distinct values.  There are $c_1 \choose m$ ways to choose the values, so there are $\sum_{m=1}^k{k-1 \choose m-1}{c_1 \choose m}$ solutions.


Is the empty graph connected? Is the empty graph always connected ? I've looked through some sources (for example Diestels "Graph theory") and this special case seems to be ommited. What is the general opinion for this case ?

As I could gather from reading Diestel Graph theory, the disconnected graphs and the trivial graph (meaning the one with just one vertex) are 0-connected. But the trivial graph is connected, since there always is a path from that node to itself. So isn't the terminology a bit misleading ? Because one could take "0-connected" to mean "disconnected", but in the case of the trivial graph this doesn't hold anymore, which seems to me to be - at the level of terminology - unaesthetic.

My opinion is that the empty graph ought to be regarded as disconnected, in the same way that $1$ ought to be regarded as not prime. The reason is that every graph should have a unique "prime factorization" into a disjoint union of connected graphs, and this theorem is false if you allow the empty graph to be connected.

The fact that the standard definition ("any two vertices can be connected by a path") is vacuously true for the empty graph is misleading. This is a phenomenon known on the nLab as too simple to be simple and it is caused by using definitions which don't work well for empty objects. Here is a better definition:

  A graph is connected if it has exactly one connected component.

Recall that a connected component is an equivalence class under the equivalence relation generated by the relation of adjacency; in particular I do not need to define the word "connected" to define what a connected component is. The empty graph has zero, rather than one, connected components.

A graph is connected if for all $x, y \in V(G)$ there exists a path from $x$ to $y$ using edges in $E(G)$. The null graph satisfies that criteria so it is connected. The term disconnected is the negation of connected; that is, there exists an $x, y \in V(G)$ for which there is no path from $x$ to $y$ using edges in $E(G)$. It is impossible to find such an $x$ and $y$ because the set is empty, therefore, the null graph cannot be disconnected.

We aren't allowed to change the standard definition to "A graph is connected if it has exactly one connected component". Moreover, it makes no sense to define "connected" using the term "connected component" because in order to talk about a connected component you'd already have to know what connected meant (as well as the term "component").

On a personal level, the definition of graph that I learned did not allow for the null graph. A graph consisted of a nonempty set V of vertices together with a (possibly empty) set of edges, E. It would seem prudent to define "graph" this way to keep the null graph from existing.


Find $\max_{0 < \beta < 1/2} \{\min \{\alpha - \beta, 1 - 2\beta, \beta \alpha\}\}$ Hello I'm looking for find $$ \max\limits_{0 < \beta < 1/2} \{\min \{\alpha - \beta, 1 - 2\beta, \beta \alpha\}\} $$
where $\alpha \in (0,1)$ is fixed and $\alpha > \beta$.

I don't know how to handle with an inequality contrainst like $0 < \beta < 1/2 $.

Two of them are decreasing with $\beta$, and the other is increasing.  So there are only five places to look: $\beta=0;\beta=1/2$; and where two of the formulas are equal.
A: If $\beta=0$, the numbers are $\alpha,1,0$, and the minimum is $0$.
B: If $\beta=1/2$, the minimum is either $\alpha-1/2$ or $0$.
C: If $\alpha-\beta=1-2\beta$, then $\beta=1-\alpha$ (if $\alpha>1/2$) and the minimum is either $2\alpha-1$ or $\alpha-\alpha^2$.
D,E: etc.

There is a switchover point, which is the $\alpha$ for which the three lines (functions of $\beta$) intersect in one point.  For that $\alpha$, the two options in C, in D and in E are equal.

$f(\alpha)= max_{0<β<1/2}(min(α−β,1−2β,βα))$

$\alpha$ in $Open(0)$ .. $ \frac {\sqrt 5}{2}-\frac{1}{2})$ :
$[\alpha, \beta, f(\alpha)] = [\alpha, \frac{\alpha}{1+\alpha}, \frac{\alpha^2}{1+\alpha}]$

$\alpha$ in $\frac{\sqrt 5}{2}-\frac{1}{2}$ .. $Open(1)$ :
$[\alpha, \beta, f(\alpha)] = [\alpha, \frac{1}{2+\alpha}, \frac{\alpha}{2+\alpha}]$


Any two of the subsequences $\{a_{2k}\}, \{a_{2k+1}\}, \{a_{3k}\}$ converge do not imply $\{a_k\}$ converges? If $\{a_k\}$ is a sequence, I have shown if the three subsequences $\{a_{2k}\}, \{a_{2k+1}\}, \{a_{3k}\}$ all converge, then the sequence converges.

I am asked whether the sequence converges if only two of them converge. Any help will be appreciated.

I first show the limits are the same. Let us assume $\lim a_{2k} = a, \lim a_{2k+1}=b, \lim a_{3k}=c$. Then $\lim_{6k} = a = c$ and $\lim_{6k +3} = b = c$. Now pick any $\varepsilon > 0$, there are $N_1, N_2$ such that
\begin{align*}
&|a_{2k} -a | < \varepsilon, \text{ if }2k \ge N_1, \\
&|a_{2k+1} -a | < \varepsilon, \text{ if }2k+1 \ge N_2.
\end{align*}
So if $n \ge \max(N_1, N_2)$, we get $|a_n -a| < \varepsilon$.

The answer is no. I remember I learned the example from my analysis class.

Take $a_n = (-1)^n$, then $\lim_{k \to \infty} a_{2k} =1$ and $\lim_{k \to \infty} a_{2k-1} = -1$.

If $$a_k = \begin{cases} 0, & \text{ if } n=2^k, k = 0, 1, \dots , \\
1 & \text{ otherwise. } \end{cases}$$ Then $\lim_{k \to \infty} a_{3k}  = 1 $ and $\lim_{k \to \infty} a_{2k+1} = 1$ but $\lim_{k \to \infty} a_{2k}$ does not exist.

Finally, if
$$ a_n = \begin{cases} 0 & \text{ if $n$ is prime }, \\ 1 & \text{ if $n$ is not prime.} \end{cases}$$
We can check $\lim_{k \to \infty} a_{3k} = 1$ and $\lim_{k \to \infty} a_{2k} =1 $ but $\lim_{k \to \infty} a_{2k+1}$ does not exist.

Let $a_{2k}\to a, a_{2k+1}\to b\ne a$. Now since $a_{6k}\to a$ and $a_{6k+3}\to b\ne a, a_{3k}$ is not convergent.

Since $a_{2k}\to a, \forall\varepsilon>0, \exists n_1\in\Bbb N$ such that $|a_{2k}-a|<\varepsilon, \forall2k\ge n_1$

Since $a_{2k+1}\to b,\exists n_2\in\Bbb N$ such that $|a_{2k+1}-b|<\varepsilon, \forall2k+1\ge n_2$

Let us assume $a_n$ converges. This means $a_n$ is Cauchy, or $\forall \varepsilon_1>0,\exists n_3\in\Bbb N$ such that $|x_n-x_m|<\varepsilon_1\forall n,m\ge n_3$.

Chose $n=m-1=2k\ge\max\{n_1,n_2,n_3\},\varepsilon=\varepsilon_1=\frac14|a-b|>0$

$|a_{2k}-a_{2k+1}|<\frac14|a-b|$ from the convergence of $a_n$, but

$a_{2k}\in(a-\varepsilon, a+\varepsilon), a_{2k+1}\in(b-\varepsilon,b+\varepsilon)\implies |a_{2k}-a_{2k+1}|>\varepsilon_1$

which is a contradiction.


Is non-standard analysis worth learning? As a former physics major, I did a lot of (seemingly sloppy) calculus using the notion of infinitesimals. Recently I heard that there is a branch of math called non-standard analysis that provides some formalism to this type of calculus.

So, do you guys think it is a subject worth learning? Is it a branch that is growing and becoming interconnected with other branches of math? Does it make calculus any easier?

I think this (interesting!) question is yet-another instance of the occasional mismatch of science (and human perception) and formal mathematics. For example, the arguments used by the questioner, and common throughout science and engineering, were also those used by Euler and other mathematicians for 150 years prior to Abel, Cauchy, Weierstrass, and others' "rigorization" of calculus. The point is that the extreme usefulness and power of calculus and differential equations was illustrated prior to epsilon-delta proofs!

Similarly, c. 1900 Heaviside's (and others') use of derivatives of not-differentiable functions, of the "Dirac delta" functions and its derivatives, and so on, brought considerable ridicule on him from the mathematics establishment, but his mathematics worked well enough to build the transatlantic telegraph cable. "Justification" was only provided by work of Sobolev (1930s) and Schwartz (1940s).

And I think there are still severe problems with Feynman diagrams, even tho' he and others could immediately use them to obtain correct answers to previously-thorny quantum computations.

One conclusion I have reached from such stories is that we have less obligation to fret, if we have a reasonable physical intuition, than undergrad textbooks would make us believe.

But, back to the actual question: depending on one's tastes, non-standard analysis can be pretty entertaining to study, especially if one does not worry about the "theoretical" underpinnings. However, to be "rigorous" in use of non-standard analysis requires considerable effort, perhaps more than that required by other approaches. For example, the requisite model theory itself, while quite interesting if one finds such things interesting, is non-trivial.
In the early 1970s, some results in functional analysis were obtained first by non-standard analysis, raising the possibility that such methods would, indeed, provide means otherwise unavailable. However, people found "standard" proofs soon after, and nothing comparable seems to have happened since, with regard to non-standard analysis.

With regard to model theory itself, the recent high-profile proof of the "fundamental lemma" in Langlands' program did make essential use of serious model theory... and there is no immediate prospect of replacing it. That's a much more complicated situation, tho'.

With regard to "intuitive analysis", my current impression is that learning an informal version of L. Schwartz' theory of distributions is more helpful. True, there are still issues of underlying technicalities, but, for someone in physics or mechanics or PDE... those underlying technicalities themselves have considerable physical sense, as opposed to purely mathematical content.

Strichartz' nice little book "A guide to distribution theory and Fourier transforms" captures the positive aspect of this, to my taste, altho' the Sobolev aspect is equally interesting. And, of course, beware the ponderous, lugubrious sources that'll make you sorry you ever asked... :)  That is, anything can be turned into an ugly, technical mess in the hands of someone who craves it! :)

So, in summary, I think some parts of "modern analysis" (done lightly) more effectively fulfill one's intuition about "infinitesimals" than does non-standard analysis.'

As a student of calculus that had the perennial trouble with epsilon-delta proofs and manipulations before trying my hand at non-standard calculus, perhaps I can provide a bit of perspective:

I still have trouble with epsilon-delta proofs of for derivative formulae. I think that arises from a lack of familiarity with the rigorous handling of intervals, neighborhoods, sequences and the like and I imagine that a more in-depth treatment of the subject would remedy this.

Infinitesimal calculus (as I have seen it so far) seems like a straightforward extension of the properties of "regular" numbers to "really small" numbers (infinitesimals) and "really big" numbers (infinites). The principles used for working with hyperreal numbers pretty much guarantee that an infinitesimal will behave in the same way you'd expect a "really small" real number to behave, while infinites behave as you'd expect "really big" real numbers to behave.
This makes the proofs of the basic differentiation formulae much easier both to understand and to read.

I also disagree with the complaint that one needs a good grasp of set theory and mathematical logic to be able to work with hyperreals. In this sense I think of hyperreals the same way I think of imaginary numbers, or sausages. While it can be illuminating to know how the sausage is made, one does not need to know that to find the sausage tasty. As a tutor of lower-level mathematics I can say that many, if not most of the students can handle imaginary numbers just fine without knowing how to construct the complex number system.

In short, I find non-standard calculus worth learning because it makes the arguments more understandable, easier to follow and more intuitive. However, if you are already comfortable with epsilon-delta calculus I don't know if you'd find it of much use.


Show a set it open but not closed Let $A = \{ z : |z| < 1 \} $ where $z \in \mathbb{C}$. Show that $A$ is open but not closed.
Try:
Let $\epsilon > 0$ be given. Pick any $z_0 \in A$ and choose $\epsilon = 1 - |z_0| $. We show $D(z_0,\epsilon) \subset A$. This will prove our set is open. Suppose $w \in D(z_0, \epsilon )$. this means that $|w-z_0| < \epsilon$. We must show that $w \in A$. Notice:
$$ |w| =|w - z_0 + z_0| \leq |w-z_0| + |z_0| < \epsilon + |z_0| < 1 - |z_0| + |z_0| = 1$$
and we have our conclusion. Is this a correct solution? Also, I am stuck on trying to show it is not closed. Can someone help me?

First of all, your wording for the proof that $A$ is open is faulty. There are two things you need to fix:

You first say "let $\epsilon$ be given", and then say "Choose $\epsilon = 1-|z_0|$". The two sentences are in contradiction to each other.
You then show that $D(z_0,\epsilon) \subseteq A$ with that poorly defined $\epsilon$ and say "we have our conclusion". But the conclusion referenced here is only of the subsets, not that $A$ is open. You need to improve your wording. Preferably, to something like

  $A$ is open if, for every something, this is true. Let $x$ be any something. Then, [...], therefore, this is true for $x$, and because $x$ is arbitrary, it is true for every something.

No, there are some mistakes.

Let $\epsilon > 0$ be given. Pick any $z_0 \in A$ and choose $\epsilon = 1 - |z_0| $. We show $D(z_0,\epsilon) \subset A$. This will prove our set is open. Suppose $w \in D(z_0, \epsilon )$. this means that $|w-z_0| < \epsilon$. We must show that $w \in A$. Notice:
$$ |w| =|w - z_0 + z_0| \leq |w-z_0| + |z_0| < \epsilon + |z_0| = 1 - |z_0| + |z_0| = 1$$

I has to be:

Let $z_0 \in A$ be given. Pick $\epsilon = 1 - |z_0|$. We show $D(z_0,\epsilon) \subset A$. This will prove our set is open. Suppose $w \in D(z_0, \epsilon )$. this means that $|w-z_0| < \epsilon$. We must show that $w \in A$. Notice:
$$ |w| =|w - z_0 + z_0| \leq |w-z_0| + |z_0| < \epsilon + |z_0| = 1 - |z_0| + |z_0| = 1$$

Why?
The (rather: one) definition is:
$A$ ist open $:\Leftrightarrow$
$$\forall z_0 \in A\exists  \epsilon >0:D(z_0,\epsilon) \subset A$$
So for any given $z_0$ you have then to find some $\epsilon$.
Show that A is not closed.
Ony way is to show that $B:=A^C=\mathbb{C}\setminus A$ ist not open.
(The topological defintion of closed is that the complement is open.)
Suppose $B$ is open.
$z_0=1$ is in $B$.
There has so exist some $\epsilon >0$ (w.l.o.g. $\epsilon < 2$) such that $D(z_0,\epsilon) \subset B$.
Since $A \ni 1-\frac{\epsilon}{2} = z_0-\frac{\epsilon}{2} \in D(z_0,\epsilon) \subset A^C$ we have a contradiction.
Therefore $B$ is not open, so $A$ is not closed.


Seating in a cinema hall There are $N$ numebered seats in a cinema hall. Each seat has been assigned to a specific spectator. However, the first $N-1$ spectators arrive early and occupy the seats completely randomly. The last spectator wishes to occupy her allotted seat though. So she goes to her allotted seat and then there are two cases

if the seat is vacant, occupies it
if the seat is occupied then asks the person sitting there to vacate it. The person asked to vacate follows the same pattern : goes to their allotted seat and either sits there if it is vacant or asks the person sitting there to move if occupied. This goes on till everyone is in their correct seats.

What is the expected number of displacements caused in this process?

Let $\mu_k$ denote the expected number of displacements if there are $k$ specators.

Then: $$\mu_k=\frac{k-1}k\cdot(1+\mu_{k-1})=\frac{k-1}k+\frac{k-1}k\mu_{k-1}$$

One step further we find:$$\mu_k=\frac{k-1}k+\frac{k-1}k\mu_{k-1}=\frac{k-1}k+\frac{k-1}k\left(\frac{k-2}{k-1}+\frac{k-2}{k-1}\mu_{k-2}\right)=\frac{k-1}k+\frac{k-2}{k}+\frac{k-2}{k}\mu_{k-2}$$This makes us suspect that for $n<k$:$$\mu_k=\frac1k\sum_{i-1}^n(k-i)+\frac{k-n}k\mu_{k-n}$$ and this can be verified by induction.

This leads to $$\mu_N=\frac1N((N-1)+\cdots+1)+\frac1N\mu_1=\frac12(N-1)+0=\frac12(N-1)$$

The expected number of displacements caused in this process are $\frac{N-1}{2}$ because no matter how many people are at the cinema hall, on the average,exactly one of them will select his own seat. So the expected number of displacements are $\frac{N-1}{2}$.

Letting $X$ denote the number of spectators that select their own seats, we can best compute $E[X]$ by noting that

$X=X_1+X_2+...+X_N$ where $X_i=\left\{{1,\mbox{if the ith spectator selects his own seat}\atop 0,\text{otherwise}}\right.$

Now, because the ith spectator is equally likely to select any of the N seats, it follows that

$P(X_i=1)$=P(ith spectator selects his own seat)=$\frac1N$

and so

$E[X_i]=1*P(X_i=1)+0*P(X_i=0)=\frac1N$

Hence,we obtain

$E[X]=E[X_1]+...+E[X_N]=(\frac1N)*N=1$. Hence, no matter, how many people are at the cinema hall, expected number of spectator who will select his own seat is exactly 1

So the expected number of displacements are $\frac{N-1}{2}$


Is the set of elementary functions which do not have elementary integrals bigger than set of elementary functions which have elementary integrals? It increasingly seems to me that the functions that have elementary integrals are quite rare in comparison to the ones that don't have them. Even raising an elementary function to a different power may result in it not having an elementary integral .

Ex. $\sqrt{\arctan (x)}$

Also many seemingly simple functions do not have elementary integrals.

Ex. $\frac {\sin (x)}{x}$ or $ \sin \left( \frac{1}{x} \right) $

So my question is that can we write a formal proof to prove/disprove that the set of elementary functions which do not have elementary integrals is bigger than set of elementary functions which have elementary integrals?

This might not answer your question precisely, but you might be interested by discussions around Liouville's theorem in differential algebra. Here is a link to the Wikipedia page of this theorem.

In a few words, the goal is to formalise the situation by saying that your "known" functions lie in some field $K$. For example, $K$ could be $\mathbb R(X)$ the field of rationnal fractions over $\mathbb R$. Then, adding some new functions like the logarithm is the same as looking at field extensions which have a certain property. I let you read that by yourself hoping that this might help you.

However I don't think this will answer your question fully, i.e. giving a way to take into account a comprehensive list of usual functions and then characterising perfectly those which integral is still some usual function.

They have the same cardinality

It is not clear whether all real/complex constants are allowed, or only integers. Let $K$ be the set of allowed constants.

Let $E_i$ and $E_{ni}$ be the sets of elementary functions that respectively do and don't have an elementary integral and let $E_a = E_i\ \cup\ E_{ni}$.

Lower bound on $E_i$ and $E_{ni}$

Since for every constant $c \in K$, there is a function $f(x) = c$, we have:
$$|E_i| \ge |K|$$
Also, for every constant $c \in K$, there is a function $f(x) = \sin(1/x)+c$, so:
$$|E_{ni}| \ge |K|$$

Upper bound on $E_a$ if $K = \mathbb{N}$

In this case every elementary function can be written using a text formula, for example sin(2*x)^(x/3). If there were more than countable infinite elementary functions, this wouldn't be possible, so:

$$|E_{a}| \le |K|$$

Upper bound on $E_a$ if $K = \mathbb{R}$

Let's say a form of an elementary function is an elementary function with the constants written as $c_i$. So for example $c_1\cdot x^{c_2}$. Just as in the previous section, we can write every form as a text formula, like for example c1*x^c2. This gives an upper bound of $|\mathbb{N}|$ on the number of forms.

Now to go from a form to an elementary function, we have to fill in the constants. Let's say some form has $n$ constants, then there are $|\mathbb{R}|^n$ ways to choose the constants. It is  well known that $|\mathbb{R}|^n = |\mathbb{R}|$.

To get an upper bound on $E_a$, we can multiply the number of forms by the number of ways to choose constants. So $|\mathbb{N}| \cdot |\mathbb{R}| = |\mathbb{R}|$ and we get:

$$|E_{a}| \le |K|$$

Upper and lower bound combined

If $K = \mathbb{N}$ or $K = \mathbb{R}$ we proved these formulas to be true:
$$
\begin{align}
|E_i| &\ge |K| \\
|E_{ni}| &\ge |K| \\
|E_a| &\le |K| \\
|E_a| &= |E_i| + |E_{ni}|
\end{align}
$$
It's not hard to see that it follows that:
$$|E_{a}| = |E_i| = |E_{ni}| = |K|$$


Infinite sum of matrix traces I am trying to work out the following sum where C is an n by n matrix:
$$S=\sum_{k=1}^\infty{\ln \left|e^{C^k} \right|}$$
The matrix $C$ has the property that $\operatorname{tr}(C^{2m-1})=0 $ when $m\in \mathbb{N}$ therefore I figured the sum should be equal to:
$$S=\sum_{k=1}^\infty{\ln \left|e^{C^{2k}} \right|}$$
Another property is that all the values in C are natural numbers and their sum is less than 2n.
From here I dont know where to go, but I tried the following:
$$S={\ln \left|\prod_{k=1}^{\infty} e^{C^{2k}} \right|}={\ln \left| e^{\sum_{k=1}^\infty{C^{2k}}} \right|}$$ Can I now treat the sum as a geometric series?

You will obtain
$$
S=\sum_{k=1}^\infty \ln|e^{C^k}|=\sum_{k=1}^\infty {\rm Tr}(C^k)
=\sum_{k=1}^\infty {\rm Tr}(C^{2k})=\sum_{k=1}^\infty \sum_{i=1}^N \lambda_i^{2k}
=\sum_{i=1}^N\frac{\lambda^2_i}{1-\lambda^2_i}
$$
and a property
$$\sum_{i=1}^N \lambda_i^{2k+1}=0$$
where $N$ is the dimension of the square matrix $C$ , $\lambda_i$ are its eigenvalues. Without any more conditions, you cannot simplify it further.


Prime numbers in Collatz sequences This question/request is twofold. First, if this is a stupid question or if it has been addressed before, please say so (bluntness is optional), and I will crawl back into my cave...

My question: is there always at least one prime number in a Collatz sequence? If so, why? If anyone more knowledgable in number theory can provide me with (a link to) a proof, I'd appreciate it.

I have been playing around with this idea and if we disregard the prime number 2 the sequence will always be "attracted" to the prime number 5, which will then provide the ending sequence 16, 8, 4, 2, 1.

I then tried a number of starting values, ran them through the Collatz algorithm to see how many prime numbers there are before the sequence hits 5. There is always at least one prime number, most of the time there are more. Starting the sequence with 363 I came up with 9 primes before hitting on 5. With 364 there are 18. Some other starting values:

363 - 9 primes, 364 - 18, 365 - 18, 366 - 16, 367 - 9, 368 - 2, 369 - 2, 370 - 11

Even if you disregard this as a silly question, thanks for reading it anyway.

John

We can produce an infinite family of counterexamples for the case where the starting value is odd.

Let $p\geq 7$ be an arbitrary prime. Then $p-1$ is even, so

$$2^{p-1}-1\equiv (-1)^{p-1} -1 \equiv 1-1 =0 \pmod 3$$

So $\frac{2^{p-1}-1}{3}\in\mathbb Z$ and this number is odd, because $2^{p-1}-1$ is odd. So, take it as starting value, the Collatz sequence is:
$$\left(\frac{2^{p-1}-1}{3},2^{p-2},2^{p-3},\dots,1\right)$$
By Fermat's little theorem:
$$2^{p-1}-1\equiv 0\pmod p$$
The condition on $p$ ensures, that $\frac{2^{p-1}-1}{3}>p$ holds. But $p\mid 2^{p-1}-1$ implies $p\mid\frac{2^{p-1}-1}{3}$ (because $p\neq 3$), so this number can not be prime. Hence, the sequence contains no primes (except $2$ of course).

You could always exclude this case. However, it seems like we could continue to produce other counter-examples using this very same "back-engineering" technique to produce a Collatz sequence with non-prime initial values, that leads to a power of $2$. This strongly suggests that a characterisation of such starting values is not easy.

Disregarding 2, this will not always be the case if we simply choose a power of 2 (128,64,32,16,8,4,2,1). This is known as the Martin counterexample.


What did Newton and Leibniz actually discover? Most popular sources credit Newton and Leibniz with the creation and the discovery of calculus. However there are many things that are normally regarded as a part of calculus (such as the notion of a limit with its $\epsilon$-$\delta$ definition) that seem to have been developed only much later (in this case in the late $18$th and early $19$th century).

Hence the question - what is it that Newton and Leibniz discovered?

To understand the relation between Leibniz's theory, on the one hand, and modern ϵ-δ definitions and constructions of the continuum, on the other, it is helpful to make the following distinction. The distinction is between the following two items.

(1) On the one hand, we have the procedures employed by Leibniz and other pioneers of the calculus, and their procedural moves in deriving various new results such as Leibniz's derivation of the product formula for differentiation, and Euler's various solutions of the Basel problem, to give some elementary examples. These procedures can be characterized as syntactic material because at this stage in the development of mathematics, its practitioners were not overly concerned with semantic issues (see below).

(2) On the other hand, we have the issue of the ontology of mathematical objects, i.e., what are the basic objects mathematics uses, how one axiomatizes their behavior and justifies their "existence" relative to appropriate foundational theories. These semantic issues only began to emerge starting around 1870, and resulted in the modern foundations for analysis in particular and much of modern mathematics in general.

To answer your question, I would say that the contributions of Leibniz and others would today be viewed as centering on the syntactic side of the mathematical endeavor.  They developed the calculus in the sense that they understood its procedures and syntax, which remain today largely as they have been developed by Leibniz, Euler, Lagrange, and others.

The semantic side of the story did not emerge until much later.  This observation is sometimes expressed by claiming that the pioneers of the calculus were not "rigorous" but this I believe is a misleading statement: Gauss and Dirichlet similarly did not have access to modern sematic theories and in this sense would also not be "rigorous", but in fact there are almost no errors in their work. For this reason it is more meaningful to acknowledge the syntactic contribution of the pioneers of the calculus than to apply the essentially anachronistic straitjacket of "mathematical rigor" in analyzing their work.

from my understanding, Newton's binomial said that the delta x should always have lim -> 0 because it's in the denominator, but once you got rid of it down there, delta x=0 is possible (and then you got rid of all the delta x in the numerator), thus, making the computation of derivatives systematic and easy.


Multiplication and modulo - Order of operations Simple question

I have $$a\cdot b\cdot c\;mod\;p$$

How do I interpret this? Do i read it as this $$(abc)\;mod\;p$$ or is it $$a\cdot b\cdot (c\;mod\;p)$$

Or do I completely misunderstand modular arithmetic?

Thanks!

Yes, it's $(a b c) \mod p$. In fact
$$
x \mod p =(x)\mod p \text{ for any expression } x
$$

You can see this as $a*b*c(mod p)$ or $a(mod\ p) *b(mod\ p)* c(mod\ p)$.


Evaluating $\lim_{x\to 0} (1-x)^{\frac 1x}$ How do you evaluate this limit?
$$\lim_{x\to 0} (1-x)^{\frac 1x}$$

I looked at it graphically (here is the graph), but it doesn't look like the limit is any nice number. Does anyone know how to find this?

One of the definitions of $e^y$ is $\lim_{n \to \infty}\left(1+\dfrac{y}n\right)^n$. In your case, replace $x$ by $1/n$, we then have
$$\lim_{x \to 0}\left(1-x\right)^{1/x} = \lim_{n \to \infty}\left(1-\dfrac1n\right)^n = e^{-1}$$

I'm pretty sure the limit is $e^{-1}$.  In fact $(1+\frac1n)^n\rightarrow e$.