How many combinations does Android pattern have? Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps

3) Once a dot is crossed, you can jump over it.

I think it's impossible to find it in a combinatory way, I used a recursive research to find it and it gave me the answer 487272. Under there is the c++ code. But a lot of sites posts a lesser answer, 389112. I'd like to see a more matematical way to solve this.

#include <iostream>
#include <stdlib.h>
using namespace std;

int combo;  //counter

void research(int Ipoints /*number of points already took*/, bool Icheck[9]/*points matrix*/,int Ilast/*last took point*/,
                   int Icomboval/*combination representation, only for printing purpose*/, int deep/*number of iteration, only for printing purpose*/)
{

    //  int numcall = 0;  //DEBUG

     for( int i=0; i<9; i++) //Controlling every free point in search of a valid way to contimue
          if( Icheck[i] == false )
          {
              //Just for security, coping every variable in a new variable. I don't know how c++ works but I will make it works
              int points = Ipoints;
              int last = Ilast;
              int comboval = Icomboval;
              bool check[9];
                   for( int j=0; j<9; j++)
                        check[j] = Icheck[j];

              int e1,e2;
              int middle = -1;
              e1=i; e2=last;  //Controlling duble jumps
              if( e1 == 0 && e2 == 2 ) middle = 1;
              if( e1 == 3 && e2 == 5 ) middle = 4;
              if( e1 == 6 && e2 == 8 ) middle = 7;
              if( e1 == 0 && e2 == 6 ) middle = 3;
              if( e1 == 1 && e2 == 7 ) middle = 4;
              if( e1 == 2 && e2 == 8 ) middle = 5;
              if( e1 == 0 && e2 == 8 ) middle = 4;
              if( e1 == 6 && e2 == 2 ) middle = 4;

              e2=i; e1=last;  // in both way
              if( e1 == 0 && e2 == 2 ) middle = 1;
              if( e1 == 3 && e2 == 5 ) middle = 4;
              if( e1 == 6 && e2 == 8 ) middle = 7;
              if( e1 == 0 && e2 == 6 ) middle = 3;
              if( e1 == 1 && e2 == 7 ) middle = 4;
              if( e1 == 2 && e2 == 8 ) middle = 5;
              if( e1 == 0 && e2 == 8 ) middle = 4;
              if( e1 == 6 && e2 == 2 ) middle = 4;

              if((middle != -1) && !(check[middle])) {
                        check[middle] = true;
                        points++;                      //adding middle points
                        comboval *= 10;
                        comboval += middle;
              }

              check[i] = true;
              points++;           // get the point

              comboval*=10;
              comboval += i+1;

              if(points > 3)
              {
                  combo++; // every iteration over tree points is a valid combo

                // If you want to see they all, beware because printing they all is truly slow:
                    // cout << "Combination n. " << combo << " found: " << comboval  << " , points " << points << " with " << deep << " iterations\n";
              }

              if(points > 9)   //Just for sure, emergency shutdown,
              { exit(1); }

              research(points,check,i,comboval,deep+1); /*Recursive, here is the true program!*/

              // numcall++; //DEBUG
          }

       //   cout << "Ended " << deep << " , with " << numcall << " subs called\n";   // Only for debug purposes,remove with all the //DEBUG thing

}

int main ()
{
    combo = 0; //no initial knows combo
    bool checkerboard[9];
    for( int i=0; i<9; i++) checkerboard[i]=false; //blank initial pattern

    research(0/*no point taken*/,checkerboard,-1/*just a useless value*/,0/*blank combo*/,1/*it's the firs iteration*/); //let's search!

    cout << "\n"  ;
    cout << "And the answer is ... " << combo << "\n"; //out

    char ans='\0';
    while(ans=='\0')
    {                   //just waiting
    cin >> ans;
    }

    return 0;
}

I try with combinatorics addition and multiplication principle. I just share my try. if there is any improvement, please suggest.


Can all math operations be reduced to a sufficiently complex algorithm? Say I could only perform one operation (addition) from addition I could derive subtraction by adding a negative number. Also, from addition I could derive multiplication, like $ a n $, just add $ a $ to itself $n$ times. The same for division but with negative numbers (how many times do I add a negative $a$ to itself to get to $0$. Exponenciation is glorified multiplication and there exist algorithms that use only division, addition, subtraction and multiplication to find square roots and logarithms. Sin can be expressed as a Taylor series only involving exponenciation and multiplication and addition. My question is, can every operation in mathematics (like differentiation, integration, etc.) be reduced in this way? Maybe allowing for multiplication, too, so that $i^2$ could still be -1.

It's a fundamental result in theoretical computer science that there exists a universal algorithm: a computable partial function $U$ with the property that for every computable function $f$ there is an $n$ such that
$$ \forall x:~ f(x)=U(n,x) $$
(Essentially, $n$ can be chosen as a program that computes the function, encoded as a number in some appropriate way, and $U$ is the function that tells how to execute programs in some programming language).

This gives at least a partial answer to the question in the title.

However, mathematics can also speak about functions that are not computable, and those are not realized by the usual universal algorithm. But if we want the case where $f$ is not computable to be handled, by fairness we should also allow $U$ to be noncomputable.

Exploring exactly how many functions we can cram into a single $U$ gets us into some twisty little foundational byways. However, it turns out that practically every function encountered in "ordinary" mathematics can be specified unambiguously by a logical formula built from addition and multiplication, the constants $0$ and $1$, and quantification over subsets of $\mathbb C^n$ and functions between such subsets. In this case  but we can say in standard mathematics that there is a (non-computable) $\bar U$ such that whenever $f$ is a function with such a specification, there is a number $m$ such that $f(x)=\bar U(m,x)$.

[It is not essential exactly which restrictions we put on the kind of formula that can be used to specify $f$, but we get into foundational trouble unless there are some such restrictions -- more technically there should be a predetermined repertoire of sets that the formula is allowed to quantify over. In fact a more restricted repertoire than the one outlined above can be used, at the cost of less natural specifications for many functions.]

In my college course of Numerical Analysis we did exactly this.  All was reduced to the simple truth table $0+0=0$, $1+0=1$, $0+1=1$ and $1+1=0$ carry $1$.

We did integration, differential equations, eigenvalue problems, matrix operations, Chebyshev polynomials, etc

I can't say ALL math could be done as I don't know ALL the math that exists.  But all the math that I have studied could be solved this way and we used just Fortran IV to do it.


Prove, by construction, that the elements of SO(2) and SO(3) do not have a unique inverse. I know the properties of the Matrix Group SO(n) are

• R ∈ SO(n)

• R^−1 ∈ SO(n)

• R^−1 = R^T

• The columns (and therefore the rows) of R are mutually orthogonal

• Each column (and therefore each row) of R is a unit vector

• det R = 1

How can I prove by construction, that the elements of SO(2) and SO(3) do not have a unique inverse?

Imagine a group $G$, and suppose there exist two different elements $h_1,h_2\in G$ that are inverse of the element $g\in G$, that is $gh_1 = e$, and $gh_2 = e$, with $e$ the identity element of $G$. You have then

$$
h_1 = h_1 e = h_1 (g h_2) = (h_1 g)h_2 = e h_2 = h_2
$$

that is, $h_1 = h_2$ which contradicts the assumption $h_1 \not= h_2$. We have just proved that the inverse is unique. As such, the inverse of any element in $SO(2)$ or $SO(3)$ is unique!

The groups SO(2) and SO(3) are the group of rotational matrices in 2-D and 3-D, respectively.
By definition a 3 by 3 matrix, $R$, belongs to SO(3) group if $R^T.R=I$ and $det(R)=1$. In other words, $R$ is a 3 by 3 orthogonal matrix with $det(R)=1$.

If $R∈SO(3)$ then $R^(-1)∈SO(3)$. Having said that, Equation 1 shows that if an object is rotated by an arbitrary angle $σ$, then the original object can be recovered either by rotating by $–σ$ or rotating by $2π-σ$.

$$(2π)k-σ, \quad  k∈{0,1,2,…,n}   \qquad (Equation 1)$$

If the rotational matrices of $$–σ$$ and the scalar multiples of $$2π-σ$$ are treated to be the same, the uniqueness of inverse matrices can be proved as follows:

Let $A$ has two inverses, denoted by $B$ and $C$, in the group SO(3) (or SO(2)).
By definition of inverse matrices,

$$AB=I \quad \textrm{and} \quad BA=I$$

Likewise,

$$AC=I \quad \textrm{and} \quad CA=I$$

Then,

$$B=BI$$

$$B=B(AC)$$

$$B=(BA)C$$

$$B=IC$$

$$B=C     \qquad  (Equation 2)$$

Equation 2 shows that $B$ and $C$ are equal hence there is only one inverse element of $A$, i.e. the matrix $A$ has a unique inverse.

If the rotational matrices of $–σ$ and the scalar multiples of $2π-σ$ are not treated to be the same then this proves that the matrix $A$ has multiple of inverses in the group SO(3).

Since the question states that "the elements of SO(2) and SO(3) DO NOT have a unique inverse." the second bullet point was chosen.


Sequence of vector of random variables I'm struggling a lot with below problem:

Let's take a sequence of independent two-dimmensional vectors of random variables $(A_n, B_n)_{n=1}^{\infty}$, where all vectors are uniformly distributed on square $[-2,2] \times [-2,2]$. Let $V_n=(S_n, T_n) = (\sum_{i=1}^n A_i, \sum_{i=1}^n B_i)$ and $|V_n| = \sqrt{(S_n)^2+(T_n)^2}$. Determine constant $c$ so that $lim_{n \to \infty} P(|V_n|<c\sqrt{n})=0,95$.

Any help is much appreciated.

Note that $\frac{1}{n}S_n$ and $\frac{1}{n}T_n$ each converge to a normal distribution with mean 0 and variance $\frac{4/3}{n}$ by Central Limit Theorem. Thus,
$$ \lim_{n\to\infty} {\left(\frac{S_n/n}{\sqrt{(4/3)/n}}\right)^2+\left(\frac{T_n/n}{\sqrt{(4/3)/n}}\right)^2} = \frac{3}{4n} (S_n^2+T_n^2) \quad\sim\quad \chi_2^2.$$

Let us write $Z=S_n^2+T_n^2$. Then,
$$ \mathrm{Prob}(\sqrt{Z} \leq c\sqrt{n}) = \mathrm{Prob}(Z \leq c^2 n) = \mathrm{Prob}(\frac{3}{4n} Z \leq \frac{3}{4}c^2). $$

All that remains is to solve $F(3c^2/4)=0.95$ for $c$, where $F(x)$ is the CDF for the chi-squared distribution with two degrees of freedom.

Using the fact that $S_n\ and\ T_n$ are independent and approximately normal,  you can write the joint density function approximately as a product of two normal densities.  Convert to polar coordinates and the function of r (after integrating out the angle) is the approximate density function for $|V_n|$.


Looking for 'elementary' approach that deals with Hom$_R(\oplus_{i \in I}M_i, N) \overset{\simeq}\to \Pi_{i \in I} \text{Hom}_R(M_i,N)$ I am trying to make this question as clear as possible. I will have to elaborate a bit though in order to do so.

I am in a first semester linear Algebra course (although people of a higher semster in my University claim that we're being taught Algebra rather than linear Algebra). This week I am struggling with the following problem:

  Current Problem Set (8th week): To show, for $(N,+,\cdot)$ being an R-Module  $$\text{Hom}_R(\oplus_{i \in I}M_i, N) \overset{\simeq}\to \Pi_{i \in I} \text{Hom}_R(M_i,N) \\ \hom_R(N, \Pi_{i \in I} M_i) \overset{\simeq}\to \Pi_{i \in I} \hom_R(N,M_i) $$

Which of course, as you can guess, I have no idea* on how to approach

To the Problem: Exhausting google just a little bit, one does find many relevant links addressing the above problem, for example on this math blog (crazy project) here. However  in the authors answer the person uses the universal property of the direct product. I have never been introduced to such a property in my course yet, which brings me to the word elementary that I have used in the title.

There are also related questions (I am not going to link them) on this website, the answers are of the caliber "trivial, indeed, it is easy to see that, it is clear that" by which I don't mean to mock the answerers - in fact they are in agreement to what my Professor would say to  this exercise.

No idea*: I fibbed there a little. On the level of definition I believe to know several things:

The direct sum $\oplus_{i \in I}M_i$ is a sub-module of the direct product $\prod_{i \in I}M_i$ and the direct sum is defined to be $m_i=0$ for almost all $ i \in I$ where $(m_i)_{i \in I}$ is a familiy of functions.
The direct product is nothing but a set $M= \prod_{i \in I} M_i$ with a component wise defined addition and scalar multiplication for $(m_i)_{i \in I} \in M$
An element $\varphi \in \hom_R(\oplus_{i \in I}M_i,N)$ would be a homomorphism with scalars in $R$ that maps from $\oplus_{i \in I}M_i$ to $N$. So to make this a bit more precise: $$\varphi \in \hom_R(\oplus_{i \in I} M_i, N) \implies \varphi : \begin{cases} \oplus_{i \in I}M_i & \longrightarrow N \\ (m_i)_{i \in I} & \longmapsto \varphi((m_i)_{i \in I}) \end{cases} $$
An element of the 'direct product over the index set $I$ of all homomorphisms with scalars in $R$ from $M_i$ to $N$' would be a 'family of mappings' of the like $$\omega_i: \begin{cases}M_i & \longrightarrow N \\ m_i & \mapsto \omega_i(m_i) \end{cases} $$

I am uncertain if all of the above is right. To quote my professor "all the exercises are trivial as soon as the definitions are clear". So I assume that I still lack understanding of the definition, because it feels hard for me to define an isomorphism as required in the exercise.

If someone could explain to me the taught-process on how to obtain the isomorphism or link to me relevant literature where the matter is explained I would appreciate it. Please note that I want to work with the definitions as 'purely' as possible and not use many theorems (chances are high that I don't know them).

Suppose you have
$$
\varphi\colon\bigoplus_{i\in I}M_i\to N
$$
For any $i\in I$, you can consider the map $\varphi_i\colon M_i\to N$ defined by composing with the “canonical embedding” of $M_i$ into the direct sum, let's call it $c_i$; thus $\varphi_i=\varphi\circ c_i$. Such morphisms define a family
$$
\check{\varphi}=(\varphi_i)_{i\in I}\in\prod_{i\in I}\operatorname{Hom}_R(M_i,N)
$$

Now, suppose you have
$$
f=(f_i)_{i\in I}\in\prod_{i\in I}\operatorname{Hom}_R(M_i,N)
$$
If $x=(x_i)_{i\in I}$ is an element in the direct sum, you can define
$$
\hat{f}(x)=\sum_{i\in I}f_i(x_i)\tag{*}
$$
Actually you should consider a finite subset $F\subseteq I$ such that $x_i=0$ whenever $i\notin F$ and set
$$
\hat{f}(x)=\sum_{i\in F}f_i(x_i)
$$
noting that this is independent of $F$ so long as it satisfies the condition above. This justifies the notation in (*).

It's just a matter of boring verifications to show that $\hat{f}$ is actually a morphism and that the two maps we built are inverse of one another.

The other situation is quite similar (and when you'll study some category theory you'll understand why). If
$$
\varphi\colon M\to\prod_{i\in I}N_i
$$
is a homomorphism, you can compose it with the “canonical projection”
$$p_i\colon\prod_{i\in I}N_i\to N_i$$
so getting a family
$$
\check{\varphi}\in\prod_{i\in I}\operatorname{Hom}_R(M,N_i)
$$
Conversely, given
$$
f=(f_i)_{i\in I}\in\prod_{i\in I}\operatorname{Hom}_R(M,N_i)
$$
you can define
$$
\hat{f}\colon M\to\prod_{i\in I}N_i
$$
by
$$
\hat{f}(x)=(f_i(x_i))_{i\in I}\in\prod_{i\in I}N_i
$$
Do the necessary verifications.

the first isomorphism is "slightly less trivial" than the second, which amounts to $f(n)_i \leftarrow\rightarrow f_i(n)$.

if $|I|$ is infinite then the direct sum of an $I$-indexed family of modules is a proper submodule of the direct product of the same family, so there is at least the appearance of something that requires proof. the fact that these two modules share the same homset is (waves hands) somewhat analogous to the compactness theorem in model theory.  what you wrote above captures the required idea.


In topology, intA ∪ A' =? here, A' denotes set of limit points of A

I know that A∪A' = closure of A

and

intA ∪ boundary of A = closure of A

then what about intA ∪ A' = ?

Let $f(A) = A^\circ \cup A'$. We have
$$ f(]0,1[ \cup ]1,2[) = [0,2] = (]0,1[ \cup ]1,2[)^-
$$
while
$$ f(\{0,1\}) = \emptyset
$$
so in general the result varies.

That will be all the interior points and the limit points.  If the set has isolated points they will not be in the union.  That union will be the closure minus the isolated points of A.


Cartesian product of Lebesgue measurable sets is Lebesgue measurable Let $A \subset \mathbb{R^m}$, $B \subset \mathbb{R^n}$ and $\lambda_n$ the Lebesgue measure on $\mathbb{R^n}$.

How to prove that if $A$ and $B$ are Lebesgue measurable sets then also $A \times B$ is Lebesgue measurable.

For showing that the cartesian product is Lebesgue measurable, I tried to use:

$A \times B$ is Lebesgue measurable if $\varepsilon>0$, and an open set $U$ and a closed set $V$ exist such that $V \subset A \times B \subset U$ and $\mathcal{L^{n+m}}(U$\ $V)<\varepsilon$.

I don't know how to continue from here and how to conclude that the cartesian product is also Lebesgue measurable.

As a prelude, let me first say that $A\times B$ is clearly in the product $\sigma$ algebra, since the product sigma algebra $\mathcal{F}\otimes \mathcal{G}$ of two measurable spaces is the sigma algebra generated by measurable 'rectangles'. i.e:

$\mathcal{F}\otimes \mathcal{G}= \sigma\Big( \{ E\times F: E\in \mathcal{F}, F\in \mathcal{G} \} \Big)$

Going by this definition, your set $A\times B$ is Lebesgue measurable in $\mathbb{R}^{n+m}$. However going by your criterion, recall first that for $A\in \mathcal{L}^n$ and $B\in \mathcal{L}^m$, we have:

$\lambda_n \otimes \lambda_m (A\times B)= \lambda_n(A)\times \lambda_m(B)$

Since $A,B$ are Lebesgue measurable, there exist $U_1,U_2$ open and $V_1,V_2$ closed such that:

$U_1\supseteq A \supseteq V_1$ , $U_2\supseteq B \supseteq V_2$ while $\lambda_n(U_1\setminus V_1)\leq \frac{1}{2} \tilde{\epsilon}$ and $\lambda_m(U_2\setminus V_2)\leq \frac{1}{2} \tilde{\epsilon}$

Notice that $U_1\times U_2\supseteq A\times B \supseteq V_1\times V_2$ while $U_1\times U_2$ is open and $V_1 \times V_2$ is closed. Since you can write:

$U_1\times U_2= \Big(  U_1\times V_2 \Big) \sqcup \Big( U_1 \times (U_2 \setminus V_2) \Big)=  \Big( V_1\times V_2 \Big) \sqcup \Big( (U_1\setminus V_1)\times V_2 \Big) \sqcup \Big( U_1 \times (U_2\setminus V_2) \Big) $

Then:

$\lambda_{n+m}\Big( (U_1\times U_2) \setminus (V_1 \times V_2) \Big)= \lambda_{n+m}\Big( (U_1\setminus V_1)\times V_2
 \Big) + \lambda_{n+m}\Big(  U_1 \times (U_2\setminus V_2)
 \Big)= $

$= \lambda_n(U_1 \setminus V_1)\cdot \lambda_m(V_2)+ \lambda_n(U)\cdot \lambda_m(U_2 \setminus V_2)$

If you assume $\lambda_n(U_1), \lambda_m(U_2)\leq M$, then for $\tilde{\epsilon}= \dfrac{\epsilon}{2M}$, you've shown that the difference is of measure less than $\epsilon$. Otherwise, there is a standard argument (which I will elaborate if you request) of going from the finite measured case to the $\sigma$-finite case.


Determining the number of ways a number can be written as sum of three squares I was going through Erich Friedman's "What's Special About This Number?" and there some numbers are classified based on the number of ways we can write them as sum of squares. I want to prove the following claim by Friedman:

  129 is the smallest number that can be written as the sum of 3 squares
  in 4 ways.

Indeed, as given in Wikipedia,
$$11^2+2^2+2^2 = 10^2+5^2+2^2 = 8^2+8^2+1^2 = 8^2+7^2+4^2 = 129$$
So what remains to prove is that this is the smallest such number.

  Is it possible to write a proof for this fact using some insights
  along with brute force/cases? How can we solve this problem using only
  brute-force?

Also, since I know the proof of Legendre's three-square theorem. I am also curious to know:

  How can we determine the number of ways we can write a non-negative
  integer which satisfies Legendre's three-square theorem as sum of
  three squares?

Edit1: Related discussions on MathOverflow:

Is there a simple way to compute the number of ways to write a positive integer as the sum of three squares?: Note that this is not answer of my question since $r_k(n)$ counts the number of representations of $n$ by $k$ squares, allowing zeros and distinguishing signs and order.
Efficient computation of integer representation as sum of three squares

Edit2: Related discussions on ComputerScience.SE

Listing integers as the sum of three squares $m=x^2+y^2+z^2$

Edit3: Related discussions on Mathematics.SE

When is a rational number a sum of three squares?
Why can't this number be written as a sum of three squares of rationals?
Sum of one, two, and three squares

Legendre gave the following answer, which he could not prove (Gauss gave the first proof of the 3-squares theorem). For the sake of simplicity I will only cover the case of numbers $c \equiv 5 \bmod 8$. In this case consider the equivalence classes of forms with discriminant $-4c$; like Legendre, we will consider equivalence with respect to the action of GL$_2({\mathbb Z})$. Let $P$ denote the form classes that represent primes $p \equiv 1 \bmod 4$, and $Q$ those that represent primes $q \equiv 3 \bmod 4$. Then the number of classes $P$ is equal to that of classes $Q$, and to the number of ways in which $c$ can be written as a sum of three squares.
If $c = 29$, the classes $P$ are $x^2 + 29y^2$ and $5x^2 + 2xy + 6y^2$, and these correspond to the two distinct ways of writing $29$ as a sum of three squares: $29 = 0^2 + 2^2 + 5^2 = 2^2 + 3^2 + 4^2$.
Legendre conjectured similar formulas for other values of $c$, which were later proved by Gauss, but using classes with respect to the action of SL$_2({\mathbb Z})$.


Maximum area of rectangle with fixed perimeter. How can you, with polynomial functions, determine the maximum area of a rectangle with a fixed perimeter.

Here's the exact problem—

  You have 28 feet of rabbit-proof fencing to install around your vegetable garden. What are the dimensions of the garden with the largest area?

I've looked around this Stack Exchange and haven't found an answer to this sort of problem (I have, oddly, found a similar one for concave pentagons).

If you can't give me the exact answer, any hints to get the correct answer would be much appreciated.

The result you need is that for a rectangle with a given perimeter the square has the largest area.  So with a perimeter of 28 feet, you can form a square with sides of 7 feet and area of 49 square feet.

This follows since given a positive number $A$ with $xy = A$ the sum $x + y$ is smallest when $x = y = \sqrt{A}$.

You have $2x + 2y = P \implies x + y = P/2$, and you want to find the maximum of the area, $A = xy$.

Since $x + y = P/2 \implies y = P/2 - x$, you substitute to get $A = x(P/2-x) = (P/2)x - x^2$.  In your example $P = 28$, so you want to find the maximum of $A = 14x - x^2$.

Put the perimeter into the vertex formula.

(Find the P=a+b equation and put it into the A=a*b equation.)

The answer is the maximum point.


If $f(x) = sin^3(x) + cos^3(x)$ prove that $f''(x)$ If $$f(x) = \sin^3(x) + \cos^3(x),$$ prove that $$f''(x) = \frac 32 [\sin(x) + \cos(x)] [3\sin(2x) - 2]$$
I had my go at this and I ended up with $$\frac32[\sin(x)+\cos(x)] [4\sin(2x) - 2]$$ which is a wrong answer.

Note that $\sin^3x+\cos^3x=( \sin x)^3+(\cos x)^3$ so you can use the chain rule to get $$f'(x)=3(\sin x)^2\cos x-3(\cos x )^2\sin x= 3\sin x \cos x(\sin x -\cos x).$$ Then use the product rule
$$f''(x)=3(\cos^2x-\sin^2x)(\sin x-\cos x)+3\sin x \cos x(\cos x+\sin x)$$ Which you can simplify however you want. One way would be to use the identity $2\sin x \cos x $ to write $3\sin x\cos x= \frac 32\sin(2x)$ and the identites $\cos^2x-\sin^2x=2\cos^2x-1=1-2\sin^2x$.

http://www.derivative-calculator.net/

This does it for you and also provides many many steps


Mathematics Combinatorics If I have 10 BALLS and 3 boxes, how many possible number of solutions are there with a maximum number of 9 and minimum number of 1? numbers cannot be repeated.

Mathematically, we are finding the number of solutions of $x_1+x_2+x_3=10$ where $1\leq x_1,x_2,x_3\leq9$ and $x_1,x_2,x_3$ are integers.

Straight enumeration is the way to go here, but you can simplify a little I think.    Since you don't allow repeats, this is the same as $6$ times the number of ways to write $x_1 + x_2 + x_3 = 10$ with $x_i$ strictly increasing and greater than or equal to $1$.  Subtracting $i$ from $x_i$, we see that's the same as counting the number of $x_1 + x_2 + x_3 = 4$ with the $x_i$ weakly increasing and greater than $0$.  It's pretty quick to enumerate these, there are only $4$ of them, $(0,0,4),(0,1,3),(0,2,2),(1,1,2)$.  So, there are $24$ ways to allocate the balls in your problem.

$\newcommand{\+}{^{\dagger}}%
 \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{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\fermi}{\,{\rm f}}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\half}{{1 \over 2}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
\begin{align}
?&=\sum_{x_{1} = 1}^{9}\sum_{x_{2} = 1}^{9}\sum_{x_{3} = 1}^{9}
\delta_{x_{1} + x_{2} + x_{3}, 10}
=\sum_{x_{1} = 1}^{9}\sum_{x_{2} = 1}^{9}\sum_{x_{3} = 1}^{9}\int_{\verts{z} = 1}
{1 \over z^{11 - x_{1} - x_{2} - x_{3}}}\,{\dd z \over 2\pi\ic}
\\[3mm]&=
\int_{\verts{z} = 1}\pars{\sum_{x = 1}^{9}z^{x}}^{3}{1 \over z^{11}}
\,{\dd z \over 2\pi\ic}
=
\int_{\verts{z} = 1}\bracks{z\pars{z^{9} - 1} \over z - 1}^{3}{1 \over z^{11}}
\,{\dd z \over 2\pi\ic}
=
\int_{\verts{z} = 1}{\pars{1 - z^{9}}^{3} \over \pars{1 - z}^{3}}{1 \over z^{8}}
\,{\dd z \over 2\pi\ic}
\\[3mm]&=
\int_{\verts{z} = 1}\sum_{\ell = 0}^{3}{3 \choose \ell}
\pars{-z^{9}}^{\ell}\sum_{\ell' = 0}^{\infty}{\ell' + 2 \choose 2}z^{\ell'}\,
{1 \over z^{8}}
\,{\dd z \over 2\pi\ic}
\\[3mm]&=
\sum_{\ell = 0}^{3}\sum_{\ell' = 0}^{\infty}\pars{-1}^{\ell}{3 \choose \ell}
{\ell' + 2 \choose 2}\delta_{9\ell + \ell',7}
=
\sum_{\ell = 0}^{3}\pars{-1}^{\ell}{3 \choose \ell}
\sum_{\ell' = 0}^{\infty}{\ell' + 2 \choose 2}\delta_{\ell',7 - 9\ell}
\\[3mm]&=
\sum_{\ell\ =\ 0 \atop {\vphantom{\LARGE A}\ell\ \leq\ 7/9}}^{3}\pars{-1}^{\ell}
{3 \choose \ell}{9 - 9\ell \choose 2} = {9 \choose 2} = \color{#0000ff}{\Large 36}
\end{align}


Showing Positive Definiteness In Inner Product Let $\mathcal{P}_2$ be the space of all polynomials of degree less or equal to $2$ for all $f,g\in \mathcal{P}_2$ we define:
$$\langle f,g \rangle=\int_0^\infty f(x)g(x)e^{-x} \,dx$$
Prove it is a inner product on $\mathcal{P}_2$

It is easy to show that $\langle f,g \rangle=\langle g,f \rangle$ and $\langle \alpha f+\beta g,h \rangle=\alpha\langle  f,h \rangle+\beta\langle g,h \rangle$
To show positive definiteness we take $\langle f,f \rangle=\int_0^\infty [f(x)]^2 e^{-x} \, dx$ but how can we be sure that $\langle f,f \rangle\geq 0$ and $\langle f,f \rangle=0\iff f=0$?

We know that $e^{-x}> 0$ and $(f(x))^2\geq 0$. Thus, $\displaystyle\int_{0}^{\infty} (f(x))^2 e^{-x}\geq 0$ and this function is the product of continuous functions, therefore, is continuous. Then, $\displaystyle\int_{0}^{\infty} (f(x))^2 e^{-x}=0$ if and only if $(f(x))^2 e^{-x}=0$ if and only if $(f(x))^2=0$ if and only if $f(x)=0$

You also have to show that the expression well-defined. To do this for given $f, g \in \mathcal{P}_2$, choose $M > 0$ such that for all $x \geq M$ we have $\lvert f(x) \cdot g(x)\rvert \leq x^5$ and $x^7 e^{-x}\leq 1$. Then we have
$$
\int_M^\infty\lvert f(x)g(x)e^{-x} \rvert \, dx \leq \int_M^\infty x^5e^{-x} \, dx = \int_M^\infty x^7e^{-x}x^{-2} \, dx \leq \int_M^\infty x^{-2} \, dx < \infty.
$$

It follows that
$$
\int_M^\infty f(x)g(x)e^{-x} \, dx <\infty.
$$


How to prove that both f(x) and its derivative decay to zero, as x grows to infinity, The problem statement is:

Prove: If $f(x)$ is differentiable for x>0 and

$$\lim_{x \to \infty}  (f(x)+\frac {df}{dx}(x)) =0$$

and if

$$\lim_{x \to \infty} f(x)$$ exists, then

$$\lim_{x \to \infty} f(x) = \lim_{x \to \infty} \frac{df}{dx}(x)=0$$

My work:

I don't see how the differentiability assumption on f can be used (or is even needed?), but I have that, for every $\epsilon$>0, there exists M = $max(M_1,M_2)$, such that x>M implies that

$$|f(x)+ \frac{df}{dx}(x)| < \epsilon$$
$$\implies-\epsilon < f(x) +  \frac{df}{dx}(x)  < \epsilon$$
$$\implies -\frac{df}{dx}(x) -\epsilon < f(x)   < -\frac{df}{dx}(x) +\epsilon$$

and since by assumption we know that the limit at infinity for f(x) exists, then the limit must be $-\frac{df}{dx}$, by the last inequality above.

Now I think the goal is to just show that the limit at infinity of $|\frac{df}{dx}|=0.$  Then we would have the desired equality, by the Squeeze Theorem.

But what can I say about the limit of $|\frac{df}{dx}|$?

Thanks,

With no loss of generality, suppose $\lim_{x \to \infty}f(x) > 0$; then by assumption we have $\lim_{x \to \infty}f'(x) < 0$; this implies that there are some $X \in \mathbb{R}$ and some $l < 0$ such that
$f'(x) < l$ for all $x \geq X$, which in turn implies that for every $x > X$ there is some $X < c < x$ such that
$$
f(x) - f(X) = (x-X)f'(c) < (x-X)l
$$
by the mean-value theorem;
this says that $\lim_{x \to \infty}f(x)$ does not exist, a contradiction.

If $f'(x) > M > 0$ for $x > N$, then what can you say about $f(x) = C + \int_N^x f'(x)dx$ as $x \to \infty$ ?


Convergence of a sequence involving the maximum of i.i.d. Gaussian random variables It's well known that, for a sequence of $n$ i.i.d. standard Gaussian random variables $X_1,\ldots,X_n$, where $X_\max=\max(X_1,\ldots,X_n)$, the following convergence result holds:

$$P\left(\lim_{n\rightarrow\infty}\frac{X_\max}{\sqrt{2\log n}}=1\right)=1$$

or, $\frac{X_\max}{\sqrt{2\log n}}\rightarrow1$ almost surely (for a proof of this convergence, see Example 4.4.1 in Galambos "Asymptotic Theory of Extreme Order Statistics").

I am wondering what happens to the following limit:

$$L=\lim_{n\rightarrow\infty}\left[\left(\frac{X_\max}{\sqrt{2\log n}}-1\right)f(n)\log(n)\right]$$
where $f(n)=o(1)$.

Is $L=0$ or infinite?  Does it depend of $f(n)$?  I am not sure how to deal with the indeterminate form here...

Let $M_n=\max\{X_k;1\leqslant k\leqslant n\}$ and let us first recall how the first order asymptotics of $M_n$ obtains. For every $x$,
$$
P[M_n\leqslant x]=P[X_1\leqslant x]^n,
$$
and standard estimates of the gaussian tail show that, when $x\to\infty$,
$$
P[X_1\gt x]=1/\theta(x),\qquad \theta(x)\sim x\sqrt{2\pi}\mathrm e^{x^2/2}.
$$
Thus, if $\theta(u_n)\ll n$, then $P[M_n\leqslant u_n]\to0$ while, if $\theta(v_n)\gg n$, then $P[M_n\leqslant v_n]\to1$. This holds with $u_n=(1-\varepsilon)\sqrt{2\log n}$ and $v_n=(1+\varepsilon)\sqrt{2\log n}$, for every positive $\varepsilon$, hence $M_n/\sqrt{2\log n}$ converges in probability  to $1$.

To go further, assume that $x_n=(1+z_n)\sqrt{2\log n}$, with $z_n\to0$. Then,
$$
n^{-1}\theta(x_n)\sim2\sqrt\pi\exp\left( (2z_n+z_n^2)\log n+\tfrac12\log\log n\right).
$$
In particular, if $2z_n\log n=t-\tfrac12\log\log n$ for some fixed $t$, then $n^{-1}\theta(x_n)\sim\sqrt{4\pi}\mathrm e^{t}$ hence $P[M_n\leqslant x_n]\to\exp(-\mathrm e^{-t}/\sqrt{4\pi})$. This means that
$$
T_n=2\log n\left(\frac{M_n}{\sqrt{2\log n}}-1\right)+\frac12\log\log n+\frac12\log(4\pi)
$$
converges in distribution to a random variable $T$ such that, for every $t$,
$$
P[T\leqslant t]=\exp(-\mathrm e^{-t}).
$$
In particular,
$$
U_n=\frac{\log n}{\log\log n}\left(\frac{M_n}{\sqrt{2\log n}}-1\right)\to-\frac14\ \text{in probability.}
$$
Edit: For every $n\geqslant2$, consider the random variable
$$
V_n=\frac{\log n}{\log\log n}\left(\frac{X_n}{\sqrt{2\log n}}-1\right).
$$
The asymptotics on the gaussian tail used above shows that, for every fixed $t$,
$$
P[V_n\geqslant t]\sim\frac1{2\sqrt\pi\cdot n\cdot(\log n)^{1/2+2t}}.
$$
If $t\lt1/4$, the series $\sum\limits_nP[V_n\geqslant t]$ diverges hence Borel-Cantelli lemma (difficult part) shows that, almost surely $V_n\geqslant t$ for infinitely many $n$. Since $U_n\geqslant V_n$, almost surely $U_n\geqslant t$ for infinitely many $n$.

If $t\gt1/4$, the series $\sum\limits_nP[V_n\geqslant t]$ converges hence Borel-Cantelli lemma (easy part) shows that, almost surely $V_n\leqslant t$ for every $n$ large enough. Thus, $V_n\leqslant t$ for every $n$ with positive probability, hence $U_n\leqslant t$ for every $n$ with positive probability. Since $M_n\to\infty$ almost surely, asymptotically $U_n$ does not depend on $(X_i)_{i\leqslant k}$, for every $k$. Thus, $\limsup U_n$ is an asymptotic random variable and $[\limsup U_n\leqslant t]$ has probability $0$ or $1$.

Finally,
$$
\limsup\limits_{n\to\infty}U_n=+\frac14\ \text{almost surely.}
$$

As in @Did's answer, we let $f(n)=(\log \log n)^{-1}$.  Also, for consistency with the existing literature (and Did's answer), let $M_n=\max\{X_k;1\leq k\leq n\}$.

Theorem: $P\left(\lim_{n\rightarrow\infty}\frac{\log n}{\log \log n}\left(\frac{M_n}{\sqrt{2\log n}}-1\right)\in\left[-\frac{1}{4},\frac{1}{4}\right]\right)=1$ if it exists.

First we state a couple of helpful lemmas for Embrechts, Klüppelberg and Mikosch's "Modeling Extremal Events".  The first follows from the Borel-Cantelli lemma; the sketch of the proof of the second is on page 170, with references to the full proof.

Lemma 1 (abridged Theorem 3.5.1 in Embrechts et al.): Suppose $(u_n)$ is non-decreasing. Then $\sum_{n=1}^\infty P(X_1>u_n)<\infty$ implies that $P(M_n>u_n~~\text{i.o.})=0$.

Lemma 2 (abridged Theorem 3.5.2 in Embrechts et al.): Suppose $(u_n)$ is non-decreasing and that the following conditions hold: $P(X_1\geq u_n)\rightarrow 0$ and $nP(X_1\geq u_n)\rightarrow \infty$. Then $\sum_{n=1}^\infty P(X_1>u_n)\exp[-nP(X_1>u_n)]<\infty$ implies that $P(M_n\leq u_n~~\text{i.o.})=0$.

(i.o. here means "infinitely often").

Proof: First we prove the upper bound; and then the lower bound.

For upper bound let $u^u_n=\sqrt{2\log n}+\frac{\sqrt{2}(\frac{1}{4}+\epsilon)\log\log n}{\sqrt{\log n}}$ where $\epsilon>0$. Using standard approximation for the distribution of the tail of a Gaussian random variable $P(X_1>x)\approx\frac{1}{\sqrt{2\pi}x}e^{-x^2/2}$, we obtain:
$$\begin{array}{rcl}P(X_1>u^u_n)&\approx&\frac{\exp\left[-\log n -2(\frac{1}{4}+\epsilon)\log\log n-\mathcal{O}\left(\frac{(\log\log n)^2}{\log n}\right)\right]}{\sqrt{2\pi}\left(\sqrt{2\log n}+\mathcal{O}\left(\frac{\log\log n}{\sqrt{\log n}}\right)\right)}\\
&=&\frac{1}{C_1n(\log n)^{\frac{1}{2}+2(\frac{1}{4}+\epsilon)}}
\end{array}$$
where $C_1=\mathcal{O}(1)$ captures the lower-order terms and the constants.
Using the Cauchy condensation test, one can easily check that:
$$\sum_{n=1}^\infty n^{-1}(\log n)^{-1-2\epsilon}<\infty$$
By Lemma 1, $P(M_n>u^u_n~~\text{i.o.})=0$. A few arithmetic manipulations yield that:
$$\tag{1}P\left(\frac{\log n}{\log \log n}\left(\frac{M_n}{\sqrt{2\log n}}-1\right)>\frac{1}{4}+\epsilon~~\text{i.o.}\right)=0$$

For the lower bound let $u^l_n=\sqrt{2\log n}-\frac{\sqrt{2}(\frac{1}{4}+\epsilon)\log\log n}{\sqrt{\log n}}$ where $\epsilon>0$. Again using the same approximation for the distribution of the tail of a Gaussian random variable, we obtain:
$$\begin{array}{rcl}P(X_1>u^l_n)&\approx&\frac{\exp\left[-\log n +2(\frac{1}{4}+\epsilon)\log\log n-\mathcal{O}\left(\frac{(\log\log n)^2}{\log n}\right)\right]}{\sqrt{2\pi}\left(\sqrt{2\log n}+\mathcal{O}\left(\frac{\log\log n}{\sqrt{\log n}}\right)\right)}\\
&=&\frac{(\log n)^\epsilon}{C_2n}
\end{array}$$
where $C_2=\mathcal{O}(1)$ captures the lower-order terms and the constants.
Clearly $P(X_1>u^l_n)\rightarrow 0$ and $nP(X_1>u^l_n)\rightarrow\infty$, so the conditions necessary for Lemma 2 are satisfied. Now,

$$P(X_1>u^l_n)\exp[-nP(X_1>u^l_n)]=\frac{(\log n)^\epsilon}{C_2 ne^{(\log n)^\epsilon/C_2}}$$

Again employing the Cauchy condensation test we can show that:
$$\sum_{n=1}^\infty \frac{(\log n)^\epsilon}{C_2 ne^{(\log n)^\epsilon/C_2}}<\infty$$
By Lemma 2, $P(M_n<u^l_n~~\text{i.o})=0$. A few arithmetic manipulations yield that:
$$\tag{2}P\left(\frac{\log n}{\log \log n}\left(\frac{M_n}{\sqrt{2\log n}}-1\right)<-\frac{1}{4}-\epsilon~~\text{i.o.}\right)=0$$
Combining (1) and (2) yields the desired result.

Remark: This demonstrates a bound on the limit if the limit exists (in fact, as Did points out, this shows $\limsup$ is $\leq 1/4$ and $\liminf$ is $\geq 1/4$).  I wonder if one can determine if the limit in fact converges to some fixed number $C\in\left[-\frac{1}{4},\frac{1}{4}\right]$ or "bounces around" (akin to a sine wave).  Perhaps Did's convergence in probability to $-\frac{1}{4}$ can somehow be leveraged here?


what does the "element of notation" means in big O statments? what does the following means?
$2^{\sqrt{x}} \in O(2^x)$
I have given the above statement to determine whether it is true or not but I do know the meaning of the $\in$ symbol

Notation $O(f),x \to x_0$ is set of functions:
$$O(f(x))=\{g: \exists U(x_0) \text{ set},\exists C>0, \forall x \in U(x_0), |f(x)| \leqslant C|g(x)|  \}  $$
so, $g \in O(f)$ mean that it satisfies above condition.
Also from above is clear, that without pointing $x_0$ set $O(f)$ have no sense.
For your example: if we take $x_0=0$, then your statement is not true, because for $x \in (0,1)$ we have $2^{\sqrt{x}}>2^x$. If we take any $x_0>1$, including $x_0=\infty$, then reverse is true for some $U(x_0)$ neigbourhood of $x_0$ and your statement is true. So, you cannot answer without $x_0$.

Hint: To show that $2^{\sqrt{x}} \in O(2^x)$, it suffices to show that
$$
\lim_{x \to \infty}\frac{2^{\sqrt{x}}}{2^x} = 0.
$$


Probability of rolling three dice without getting a 6 I am having trouble understanding how you get $91/216$ as the answer to this question.

  say a die is rolled three times

  what is the probability that at least one roll is 6?

Compute:

$1 - \left(\dfrac{5}{6}\right)^3\; \;$ to obtain the probability that at least one 6 is rolled in three tosses.

That is, we find the probability that at least one $6$ is rolled by subtracting from $1$ the probability that it does not appear on any of three rolls:

The probability that $6$ does not appear given one roll is $5/6.\;$  The probability that a $6$ does not appear on three roles of the die is given by $$\left(\frac 56\right)^3 = \dfrac{125}{216}$$

We use $1$ to represent certainty: that is 100 percent probability. It must be the case that P(Not rolling at least one 6 on three rolls) + P(rolling at least one 6 on three rolls)] =1$\implies 1 - $ (probability of not rolling at least one 6) = (probability of rolling at least one 6).

So the probability of obtaining a $6$ on at least one roll is:

$$1 - \dfrac{125}{216} \quad = \quad \dfrac{216}{216} - \dfrac{125}{216} \quad = \quad\dfrac{91}{216}$$

For rolling 3 dice without getting a six, to get the probability, pretend your 6-sided dice are 5-sided dice.  That can help you figure out the probability.  Therefore, the probability is 125/216.


Finding distance of mid-point $M$ of line-segment $PQ$ from origin In the figure, point $M$ is the midpoint of the line segment $PQ$. Show that $c = \frac12(a + b)$.

Hello, I couldn't figure out how to show it because I don't have vector points. And there are no vector angles. How should I go about it?

$\vec M=\frac12(\vec P+\vec Q)\implies\|\vec M\|=c=\frac12\sqrt{a^2+b^2+2ab\cos\theta}$ where $\theta$ is the angle between $\vec P,\vec Q$. Without knowing $\theta$, we can only find bounds on $c$:$$-1\le\cos\theta\le1\implies(a-b)^2\le a^2+b^2+2ab\cos\theta\le(a+b)^2\\\implies c\in\left[\frac12|a-b|,\frac12(a+b)\right]$$

Length $c$ is a half of their vector sum in a parallelogram resultant (half) computable by trig cosine rule.
$$ c=\frac12 \sqrt{a^2+b^2+ 2ab \cos POQ}$$
When vectors sense is (same, opposite) we have respectively half resultant
$$ c= ( \dfrac{a+b}{2}, \dfrac{a-b}{2})$$
(PM = MQ given lengths, marking error)
Question is misleading, true if they are vectors.


Intuition behind Matrix Multiplication If I multiply two numbers, say $3$ and $5$, I know it means add $3$ to itself $5$ times or add $5$ to itself $3$ times.

But If I multiply two matrices, what does it mean ?  I mean I can't think it in terms of repetitive addition.

  What is the intuitive way of thinking about multiplication of matrices?

Matrix ¨multiplication¨ is the composition of two linear functions. The composition of two linear functions is a linear function.

If a linear function is represented by A and another by B then AB is their composition. BA is the their reverse composition.

Thats one way of thinking of it. It explains why matrix multiplication is the way it is instead of piecewise multiplication.

This is the detailed and easiest explanation : https://nolaymanleftbehind.wordpress.com/2011/07/10/linear-algebra-what-matrices-actually-are/


Can we say that the matrix $\begin{bmatrix} A & A \\ 0 & A \end{bmatrix}$ is diagonalizable if and only if $A = 0$? Consider the block matrix

$$\begin{bmatrix} A & A \\ 0 & A \end{bmatrix}$$

where $A$ is a $n\times n$ complex matrix.

Can we say that this matrix is diagonalizable if and only if $A = 0$?

Let $m$ be the minimal polynomial of $A$ and $M=\begin{pmatrix}A&A\\0&A\end{pmatrix}$. Note that $m(M)=\begin{pmatrix}m(A)&Am'(A)\\0&m(A)\end{pmatrix}$.

Thus $m^2(M)=0$ and, since $M$ is diagonalizable, $m(M)=0$. Suppose that $m$ has multiple roots; then, there is a polynomial $p$ that strictly divides $m$ and satisfies $p(M)=0$; that implies $p(A)=0$, a contradiction.

Finally, $m$ has simple roots and $m(M)=0$ implies that $Am'(A)=0$; since $m'(A)$ is invertible, $A=0$.  $\square$

HINT: A matrix $B$ is diagonalizable if and only if $B$ is normal ($BB^*=B^*B$).


Pascals triangle pathways Hey Guys I really really need help with my data management problem. I've been racking my brain trying to figure out what to do. It deals with pascals triangle. The pegboard game is shown above. I really need help I genuinely do not know how to find the amount of paths, and because of that I can't move on. The questions is..

  Determine the total number of paths to the bottom of the game board (for each path). Include a separate game board for each starting slot (A-H)

If the numbers at the bottom don't mean anything and you just want the number of paths downward through the dotted squares, it is just like Pascal's triangle.  Starting from where you indicate there is one way to the neighboring cells on the top line and zero ways to all the other cells.  Now fill in the second line with each cell getting the sum of the two above.  It will exactly follow Pascal's triangle until the edges start to matter, when the numbers will be smaller.  Where are you stuck?


Proving that a function sequence converges uniformly to limit function I have the function sequence $f_n = n\sinh(x/n)$, $\forall n \in \mathbb{N}, \forall x \in [-1, 1]$ which I believe has the limit function $f = 1$ for $x = 1, f = 0$ for $x \in (-1,1)$ and $f = -1$ for $x = -1$.

How would I go about proving that $f_n$ converges to $f$ uniformly? I know that $f_n \rightarrow f$ iff $f_n \rightarrow f$ in the uniform topology. So I should somehow be able to use the metric that induces the uniform topology to prove that $f_n$ converges uniformly. Is it enough to show that the derivatives of the functions are bounded by some value not dependent on $x$?

$e^{t}=1+t+tg(t)$ where $g(t) \to 0$ as $t \to 0$ (and $g$ is continuous on $[0,1]$). [ To see this either use Taylor expansion to apply L'Hopital's Rule to $\frac {e^{t+-1-t}} t$].

Hence $n\frac {e^{x/n}-e^{-x/n}} 2 =x+\frac  x n [g(x/n)-g(-x/n)]$.

Note that $g(t)=\frac {e^{t}-1-t} t$ and $g(0)=0$ defines a continuous function on $[0,1]$ such that $e^{t}=1+t+tg(t)$ for all $t$. Being a continuous function $g$ is bounded Suppose $|g(t)| \leq M$ for all $t$. Then $|\frac  x n [g(x/n)-g(-x/n)]| \leq 2M \frac 1 n$ for all $x$. Hence $\sup_x  |\frac  x n [g(x/n)-g(-x/n)]|  \to 0$ proving uniform convergence.


If $n > 1$ and all $n$ positive integers $a, a + k, \cdots , a+ (n - 1)k$ are odd primes, show every prime $<n \mid k$. Background: This is from Rosen 5th edition, $3.2.15$ Number Theory.
This is an important proof because $3$ following problems require it to be correct.

If $i=0$, and $j=p$ then this proof is wrong and $p\mid (i-j)$ and $p$ may not divide $k$. Can this proof be modified so that it is correct or do I not understand it?

Assume that $p\nmid k$ for some prime $p<n.$ Then $kx\equiv-a\pmod p$ for some integer $0\leqslant x<p$ so $a+kx\equiv0\pmod p$ and since each of the numbers $a+ik,$ with $0\leqslant i<n,$ is a prime then $a+kx=p.$ Now notice that for each $1\leqslant i<n$ we have $\gcd(a,i)=1$ for otherwise the number $a+ik=\gcd(a,i)\left(\frac{a}{\gcd(a,i)}+\frac{i}{\gcd(a,i)}k\right)$ would not be a prime. Thus $a\geqslant n.$ Therefore we have $n\leqslant a\leqslant a+kx=p<n,$ which is a contradiction. Thus the primorial $(n-1)\#$ divides $k.$

If $i=0$, then $p$ would have to be equal to $-j$. This would be a contradiction since $i, j, p > 0$. WLOG, we can assume $i-j>0$.

Moreover, since $i \le p$ and $j \le p$, then the claim that $i-j < p$ holds, and the proof is true. Does that help?


Simplification for a double summation where the upper limit of the inner index depends on the value of the outer index? $$\sum_{x=1}^{N} \sum_{y=1}^{M(x)} (1 + a\cdot f\left(x\right))(1 + b \cdot f\left(y\right)) \tag{1}$$
where $N$, $a$, and $b$ are integer constants. $M$ is also an integer but changes for every value of x, which makes the index of the second summation dependent on the first. The problem is the relationship $M(x)$ is analytically difficult to define. Is there a way to simplify this expression?

I would evaluate this expression in the following way (in order):

Select the $x$ value (starting with $x=1$)
Then evaluate $M(x)$
Now you have a sum of the form, where now we have $M\equiv M(x),f\equiv f(x)$:

$$\tag{1}
\sum_{y=1}^{M} \left(1 + a\cdot f\right)(1 + b \cdot f\left(y\right))
$$

Proceed to the next value of $x$ (in this case it's $x=2$)
Go back to Step 2, 3, and 4, where the $M$ and $f$ can be slightly different (depending on the new value of $x$) from what you had before.

I'm certain that there's no way to "simplify" your expression without knowing the functional form of $M(x)$, for example is it $M(x)=\cos(x)$ or is it $M(x)=x^2 - \log(x) + \max(x,y,f(x),f(y),f(x)-f(y))$?

Not sure what you are looking for but you can change the order of integration as long as you include all cells in the yellow triangle.  For instance,
$\sum_{y=1}^{N} \sum_{x = M^{-1}(y)}^N (1 + a f(x))(1 + b(f(y))$
is the same.
If $M(x) = x$, the sum is over the yellow trangular region
You can also expand the product
$\sum_{x=1}^{N} \sum_{y = 1}^{M(x)} (1 + a f(x))(1 + b(f(y)) = \sum_{x=1}^{N} \sum_{y = 1}^{M(x)} 1 + a f(x) + bf(y) + abf(x)f(y)$


Striking applications of integration by parts What are your favorite applications of integration by parts?

(The answers can be as lowbrow or highbrow as you wish. I'd just like to get a bunch of these in one place!)

Thanks for your contributions, in advance!

I always liked the derivation of Taylor's formula with error term:

$$\begin{array}{rl}
f(x) &= f(0) + \int_0^x f'(x-t) \,dt\\
&= f(0) + xf'(0) + \int_0^x tf''(x-t)\,dt\\
&= f(0) + xf'(0) + \frac{x^2}2f''(0) + \int_0^x \frac{t^2}2 f'''(x-t)\,dt
\end{array}$$

and so on. Using the mean value theorem on the final term readily gives the Cauchy form for the remainder.

Integration by parts shows that (modulo a constant) the Fourier transform interchanges differentiation and multiplication by the variable:
$\begin{align*}
f'(x) \rightarrow \widehat{f'}(\xi) & = \int_{\mathbb{R}} f'(x)e^{-2 \pi i x \xi}dx\\
 & = f(x)e^{-2 \pi i x \xi}|_{-\infty}^{\infty} - \int_{\mathbb{R}} f(x) e^{-2 \pi i x \xi} (-2 \pi i \xi) dx \\
& = (2\pi i \xi) \widehat{f}(\xi)
\end{align*}$
where $f(x)e^{-2 \pi i x \xi}|_{-\infty}^{\infty}$ vanishes if $f$ decays fast.


What is $\dim(V^V)$? Where $V$ is a vector space and $V^V=\left\{ f\mid f\colon V\rightarrow V \right\}$.

I proved that $V^V$ is a vector space so $\dim\left(V^V\right)$ is well defined.

If $\dim V=0$, then one readily finds that $V^V$ is a singleton set, hence $\dim(V^V)=0$, too.

If $V$ is a vector space over a finite field $\Bbb F_q$ and of finite dimension $n$, then $V$ is a set of $q^n$ elements. Then one quickly finds that $V^V\cong V^{q^n}$ is of dimension $n^{q^n}$.

If $V$ is an infinite set (that is, either of infnite dimension over an arbitrary field, or of any positive dimension over in infinite field), then certainly $\dim(V^V)$ is infinite. If needed, you could still make more precise statements about the exact - infinite - cardinality, but I suppose yo do not want to go down that rabbit hole ...

If V has finite dimension n then $V^V$ has dimension $n^n$.  If V has countable dimension then $V^V$ has countable dimension.  If V has uncountable dimension then $V^V$ has uncountable dimension.


Prove that $f(x)=e^x\ln x$ attains every real number as its value exactly once how can I prove that the function
$f(x)=e^x\ln x$

attains every real number as its value exactly once. (by proving that it's a  monotonic continuous function)?

The function is defined for $x>0$; it should be easy to prove that
$$
\lim_{x\to0^+}f(x)=-\infty,\qquad
\lim_{x\to\infty}f(x)=\infty
$$
so the range of the function is $\mathbb{R}$ because…

The derivative is
$$
f'(x)=\frac{e^x}{x}(1+x\ln x)
$$

Consider $g(x)=1+x\ln x$; then
$$
g'(x)=1+\ln x
$$
that vanishes for $x=e^{-1}$ and $g(e^{-1})=1-e^{-1}>0$.

Can you conclude?

Take it's derivative: $f'(x)=e^x \ln x + \frac{e^x}{x}$ and note that it is always strictly greater than 0.

This shows that it is strictly increasing thus injective, so if every real number is reached, than also exactly once.

Now because $\lim_{x\rightarrow 0} f(x) = -\infty$ and $\lim_{x\rightarrow \infty} f(x) = \infty$, every real number is reached because of the mean value theorem.


Solution of given definite integral: $\int _0^a \frac1x \tan ^{-1} \left(\frac{x^2}{d^2+x^2} \right)dx$ Can following integral be solved in terms of elementary functions?

$$\int _{0}^{a} \frac{1}{x} \tan ^{-1} \bigg(\frac{x^2}{d^2+x^2} \bigg)dx$$

where $a,d \in R$

Could someone help me with this?

Could someone help me with this ?

Yes. I can. Here are two facts for future reference :

the presence of $\dfrac{{\bf d}x}x$ usually begs for a linear substitution, since, for $x=\alpha~t,$ we have $$\dfrac{{\bf d}x}x=\dfrac{{\bf d}(\alpha~t)}{\alpha~t}=\dfrac{\alpha~{\bf d}t}{\alpha~t}=\dfrac{{\bf d}t}t.$$
the presence of $1+x^2$ usually requires a trigonometric or hyperbolic substitution,  since, for $x=\tan(t),$ we have $1+x^2=1+\tan^2t=\sec^2t,$ and, for $x=\sinh(u),$ we can  write $1+x^2=1+\sinh^2u$ $=\cosh^2u.$

All in all, it would follow that we should employ the substitution $x=d\tan(t).$ Then, rewriting

$\sin^2t=\dfrac{1-\cos(2t)}2$ and $\sec(t)\csc(t)=\dfrac1{\sin(t)\cos(t)}=\dfrac2{\sin(2t)}=\dfrac1{\sqrt{1-\cos^2(2t)}},$ it only

feels natural to let $u=\cos(2t).$ Of course, this could all have been handled much more directly

by rewriting $\dfrac1x=\dfrac x{x^2}=\dfrac12\cdot\dfrac{{\bf d}(x^2)}{x^2},$ and then simply substituting $v=x^2,$ but where would

be the fun in that, right ? ;-$)$ Either way, the last and final steps involve yet another linear

substitution, $w=\dfrac{1-u}2,$ followed by factoring the integrand's new denominator using the

famous formula $A^2-B^2=(A-B)(A+B),$ and then employing some very basic partial  fraction decomposition, only to be left with a linear combination of integrals of the form

$\displaystyle\int\dfrac{\arctan(x)}x~dx$ and $\displaystyle\int\dfrac{\arctan(x)}{1-x}~dx,$ none of which are even remotely elementary.


Reducing Spaces: Characterization Given a Hilbert space $\mathcal{H}$.

Consider an operator:
$$T:\mathcal{D}(T)\to\mathcal{H}:\quad\mathcal{D}:=\mathcal{D}(T)$$

Regard a subspace:
$$\mathcal{S}\leq\mathcal{H}:\quad\mathcal{H}=\mathcal{S}\oplus\mathcal{S}^\perp$$

Then one has for reducibility:
$$PT\subseteq TP\iff T\mathcal{S}^{(\perp)}\subseteq\mathcal{S}^{(\perp)}\quad(P\mathcal{D}\subseteq\mathcal{D})$$

In general inclusion will be strict:
$$\mathcal{D}(PT)=\mathcal{D}\subsetneq P^{-1}\mathcal{D}=\mathcal{D}(TP)$$

How to prove this from scratch?

This answer is community wiki.

Preparation

Before it always holds:
$$\mathcal{D}\supseteq\mathcal{D}\cap\mathcal{S}+\mathcal{D}\cap\mathcal{S}^\perp$$

Especially one has:
$$P\mathcal{D}\subseteq\mathcal{D}\iff\mathcal{D}=\mathcal{D}\cap\mathcal{S}+\mathcal{D}\cap\mathcal{S}^\perp$$
(That will be crucial below!)

Characterization

On the one hand one has:
$$PT\subseteq TP\implies P\mathcal{D}\subseteq\mathcal{D}$$

Concluding that they're invariant as:
$$\varphi\in\mathcal{D}\cap\mathcal{S}:\quad T\varphi=TP\varphi=PT\varphi\in\mathcal{S}$$
$$\psi\in\mathcal{D}\cap\mathcal{S}^\perp:\quad T\psi=T(1-P)\psi=(1-P)T\psi\in\mathcal{S}^\perp$$

On the other hand one has:
$$P\mathcal{D}\subseteq\mathcal{D}\implies\mathcal{D}(PT)\subseteq\mathcal{D}(TP)$$

Concluding that they commute as:
$$\varphi\in\mathcal{D}:\quad PT\varphi=PT\varphi_\parallel+ PT\varphi_\perp=T\varphi_\parallel=TP\varphi$$
(Here equality above was crucial!)

Strictness

Consider an operator:
$$T:\mathcal{D}(T)\to\mathcal{H}:\quad\mathcal{D}(T)\subsetneq\mathcal{H}$$

Regard any closed subspace:
$$P^2=P=P^*:\quad\mathcal{R}(P)\subseteq\mathcal{D}(T)$$

Then extension will be strict:
$$\mathcal{D}(PT)=\mathcal{D}(T)\subsetneq\mathcal{H}=\mathcal{D}(TP)$$
(Note that happens in most cases!)


Higher order Jensen-like expansion upper bound If $Z$ is a random variable with fine moment generating function, what is a good way to upper bound $$|\log \mathbb{E}e^Z- \mathbb{E}Z- \frac{1}{2}\mathbb{E}Z^2|$$
This looks like a third offer Taylor series but cannot put finger on it.

If $M(t) = \mathbb E[e^{tZ}]$ is the moment generating function, $\mathbb E[e^Z] = M(1)$.
$|Z| \le (1+Z^2)/2$ so  $|Z + Z^2/2| \le  1/2 + Z^2 \le 2 \cosh(Z)$.  Thus
$$ \left| \log \mathbb E[e^Z] - \mathbb E[Z] - \frac{1}{2} \mathbb E [Z^2] \right| \le
  |\log M(1)| + M(1) + M(-1) $$


Fun logarithm question How would you go about solving $x^{2^{x}} = 2^{x}$? There should be a solution $1<x<2$, but I haven't found a way to derive the answer using the usual log laws, maybe there is an elegant way though...

We all agree on the fact that the solution of this equation is close to $e^{1/e}$. What I did was to write the solution as $x=e^{1/(e+y)}$ and I expanded the equation as a Taylor series around $y=0$. Limited to the first order, this leads to an expression of $y$ (I am physically unable to write it down) which only includes $2$, e and $\log 2$. Its numerical value is $2.53791*10^{-6}$. For this value of $x=1.444667364812765575108917$ (quite close to Umberto's), the function value is $5.48006*10^{-12}$.
Edit (6 years later)
Taking logarithms, consider that we look for the zero of function
$$f(x)=\log \left(x^{2^x}\right)-\log \left(2^x\right)=2^x\log(x)-x \log(2)$$ and perform one Newton iteration to get
$$x_0=e^{\frac{1}{e}}\implies x_1=x_0+
   \frac{{x_0} \left({x_0} \log (2)-2^{x_0} \log ({x_0})\right)}{2^{x_0}+2^{x_0} {x_0} \log (2) \log ({x_0})-{x_0} \log
   (2)}$$ which makes $x_1=1.44466736481181$ while the "exact" solution is
$x=1.44466736481170$.
Using one iteration of Halley method gives $21$ exact figures. Using one iteration of Householder method gives $27$ exact figures. The formulae are explicit but really too lengthy to be reported here.

Here is something very similar, and I think this YouTube video  may help. This is a video on how to solve equations of the type $$b^x =  x,$$ and the presenter solves for $x$ by taking the logarithm of both sides by doing:

$$ \ln(b^x) = \ln(x)$$
$$x \ln(b) = \ln(x)$$
$$x = \frac{ \ln(x)}{ \ln(b)}$$

In this case, the $b$ in the video is $1^{1/e}$. This problem seems very related - seeing as the solutions are the same, and the formulas seem similar when you substitute $x$ with $b$ and $2^x$ with $x$.


Question about "Approaching Zero and Limits" in the Intuitive Proof of the Derivative of Sine I'm a high school student hoping to self-study some introductory calculus over the summer. While studying, I came across this intuitive proof of the derivative of the sine function, using trig and the unit circle...

As in the picture, as dθ approaches zero, angles A and B will approach 90° -- allowing triangle ABC to be "approaching" similar to triangle BDE, but this would mean you would never get the exact angles for triangle ABC; thus, never the exact ratio of sine and cosine in order to complete the proof.

Is this small (even negligible) inaccuracy inherent to calculus, or is there a flaw in my understanding?

P.S. Please forgive me if this is a stupid/far-too-basic question.

The inaccuracy is of lower order than the main quantities of interest, and becomes fully accurate in the limit. The key to this question is understanding precisely what the limit means, and for this I direct you towards the rigorous meaning of a limit. Note that an initial course in calculus will include many such "hand-wavy" arguments that seem to be slightly inaccurate, and it is typically in a later course (often called "analysis" or "real analysis") following calculus where this rigorous definition is presented and results in calculus are put on a more solid footing.

For a more concrete instance of this, consider an expression like $x+x^2$ in the limit as $x$ tends to $0$. Now of course, $x+x^2$ does not equal $x$, but now if you imagine substituting a super tiny value for $x$, you will see that $x$ becomes a great approximation for $x(1+x)=x+x^2$. Note that this is stronger than saying that $x$ and $x+x^2$ have the same limit as $x$ goes to $0$, since $x^2$ also has this property - yet $x^2$ is a terrible approximation for $x+x^2$ in the limit when $x$ goes to $0$, since $x^2$ is much, much, much smaller than $x$. (I know this example is somewhat contrived, but it actually includes the main ideas in a particularly simple setting.)

If you look at the computer generated image below your drawing, the angle $\phi$ is equal to angle $\theta$. Which means that $\Delta\sin(\theta) = h \cos(\theta)$. Now if you let $\Delta\theta$ approach 0,  $\Delta\theta$ approaches $h$. So when you divide through, you get:
$$\Delta\sin(\theta)/\Delta\theta = \cos(\theta)$$
Hope this helps!


$12$ Identical balls can be placed into $3$ identical boxes, $12$ Identical balls can be placed into $3$ identical boxes, Then find probability that one of

the boxes contain exactly  $3$ balls.

$\bf{My\; Try::}$ First we select $1$ bag out of $3$ and then put

$3$ balls into that bag and then put remaining balls into $2$ bag.

Which can be done by $\displaystyle \binom {3}{1}\times 1 \times \binom{1}{1}\times 1 = 3$

bcz here balls are identical . So we can arrange by only one ways.

But my answer is wrong.

plz help me , How can I get correct answer.

Thanks

Take the simplest model: One after the other of the balls is thrown at random into one of the boxes $a$, $b$, $c$. There are $3^{12}$ different possible histories for that, all of them equiprobable. The number of histories leading to a particular final content $(r,s,t)$ of the three boxes is the coefficient of the term $a^r b^s c^t$ in the expansion of $(a+b+c)^{12}$, i.e., is given by ${12!\over r!\>s!\>t!}$.

There is the question whether "one of the boxes" means "at least one of the boxes", or "exactly one of the boxes". Since one sentence later they talk about "exactly three balls" my working hypothesis is that "at least one of the boxes" is meant.

For the probability in question we have to consider the contents
$$(3,9,0), (3,8,1), (3,7,2), (3,5,4)$$
each of them in six orders, and $(6,3,3)$ in three orders. The total number $N$ of "admissible" histories is therefore given by
$$N=6{12!\over3!}\left({1\over9!}+{1\over8!}+{1\over 7!\>2!}+{1\over 5!\>4!}\right)+3{12!\over 6!\>3!\>3!}=282\,480\ ,$$
and the required probability $P$ is $$P={N\over 3^{12}}\doteq0.531536\ .$$

Required probability
{(3c1*12c3*2 to the power 9) - (3c2*12c3*9c3)} ÷ (3 to the power 12)
this is the right answer


How can I divide $x \over x+1$ using long divison? $$x \over x+1 $$

I'm actually trying to integrate the above function, but I was told to first use long division to simplify it, which I'm not really sure how to do.

if you are trying to integrate $\frac{x}{x+1},$  you don't need to do long division; can be done with a change of variable. change of variable is a useful technique, and in particular for functions of the from $f(ax+b).$

here is it works in this case. $$u = x + 1, x = u-1$$ so $$\int \frac{x}{x+1}\, dx = \int\frac{u-1}{u}\, du = \int\left(1 - \frac 1u\right)\, du = u - \ln u+c = x - \ln|x-1| + c$$


convergenge of Hausdorff dimension for a sequence of compact sets Recall that

the Hausdorff distance (metric) is:

A metric in the space of subsets of a compact set $K$, defined as follows. Let $X,Y\subset K$ and let $D_{x,y}$ be the set of all numbers $\rho(x,Y)$ and $\rho(y,X)$ where $x\in X$, $y\in Y$ and $\rho$ is a metric in $K$. Then the Hausdorff metric $\operatorname{dist}(X,Y)$ is the least upper bound of the numbers in $D_{x,y}$.

the Hausdorff dimension is:
Let $(X,d)$ be a metric space. In what follows, for any subset $E\subset X$,
$\operatorname{diam}(E)$ will denote the diameter of $E$.

For any $E\subset X$, any $\delta \in ]0, \infty]$ and any $\alpha\in [0, \infty[$ we consider the outer measure
$$
\mathcal{H}^\alpha_\delta (E) :=
\inf \left\{ \sum_{i=1}^\infty (\operatorname{[diam}\, E_i)^\alpha :
E\subset \bigcup_i E_i \quad\text{and}\quad \operatorname{ diam}(E_i)< \delta\right\}.
$$
The map $\delta\mapsto \mathcal{H}^\alpha_\delta (E)$ is monotone nonincreasing and thus we can define the Hausdorff measure $\alpha$-dimensional measure of $E$ as
$$
\mathcal{H}^\alpha (E) := \lim_{\delta\downarrow 0} \mathcal{H}^\alpha_\delta (E)
$$
The map $\delta\mapsto \mathcal{H}^\alpha_\delta (E)$ is monotone nonincreasing and thus we can define the  Hausdorff α-dimensional
measure of E as
$$
\mathcal{H}^\alpha (E) := \lim_{\delta\downarrow 0} \mathcal{H}^\alpha_\delta (E).
$$

I wonder if the following is true:  If $A_n \to A$ in the Hausdorff distance, then $\operatorname{dim}_H A_n \to \operatorname{dim}_H A$, where $A$ is a compact subset of $[0,1]^2$.

Unfortunately this is not correct. Let us define
$$A_n:=\{\frac{k}{n}|\ k=0,1,\ldots n\}\subset [0,1].$$
Then $A_n$ converges in the Hausdorff sense to $[0,1]$. Let us proof this claim:
Let $x\in[0,1)$. Then for all $n\in\mathbb{N}$ exists a $k\in\{0,1,\ldots,n\}$ such that
$$\frac{k}{n}\leq x < \frac{k+1}{n}.$$
Hence
$$\rho(x,A_n)\leq \min(|x-\frac{k}{n}|,|x-\frac{k+1}{n}|)\leq |\frac{k+1}{n}-\frac{k}{n}|=\frac{1}{n}.$$
Therefore
$$dist_{\mathcal{H}}(A_n,A)\leq \frac{1}{n}\rightarrow 0\mbox{ for }n\rightarrow\infty.$$
The Hausdorffdimension of the $A_n$ is zero, because $A_n$ consists of finitely many points, while the Hausdorffdimension of $[0,1]$ is 1, because $\mathcal{H}^1([0,1])=\mathcal{L}^1([0,1])=1$ (Here $\mathcal{L}^1$ is the one dimensional Lebesgue mesaure).

The conjectured result does not hold.
For $j=1,2,$ define the maps $\varphi_j : [0,1] \to [0,1]$ by
$$\varphi_1(x) = \frac{1}{3}x \qquad\text{and}\qquad \varphi_2(x) = \frac{1}{3}x + \frac{2}{3}. $$  Let $A_0 = [0,1]$, and recursively define $A_n$ by
$$ A_n = \varphi_1(A_{n-1}) \cup \varphi_2(A_{n-1}). $$
Thus, working out the first few sets in the sequence:
\begin{align}
A_0 &= [0,1] \\
A_1 &= [0,1/3] \cup [2/3,1] \\
A_2 &= [0,1/9] \cup [2/9, 1/3] \cup [2/3,7/9] \cup [8/9,1],
\end{align}
and so on.  In general, the set $A_n$ will consist of $2^n$ closed intervals, each having length $3^{-n}$.  As each $A_n$ is a finite union of compact sets, each $A_n$ is, itself, compact.

Moreover, it can be shown that $A_n \to A$ in the Hausdorff metric, where $A$ is the usual two-thirds Cantor set (a proof of this follows by noting that the map of sets defined by $\Phi(E) = \varphi_1(E) \cup \varphi_2(E)$ is a contraction mapping on the space of compact subsets of $\mathbb{R}$ with respect to the Hausdorff distance; the claimed result then follows from the Banach fixed point theorem; see Hutchinson's 1981 paper for details).
Now, note that $\operatorname{dim}_H(A_n) = 1$ for each $n$ (where $\operatorname{dim}_H$ denotes the Hausdorff dimension)—that intervals are one-dimensional is a fairly standard result.  On the other hand, $\operatorname{dim}_H(A) = \log_3(2)$—again, I would refer you to Hutchinson's 1981 paper for a proof of this result, though, again, this is a fairly standard result.  Therefore
$$ A_n \overset{d_H}{\longrightarrow} A
\qquad\text{but}\qquad
1 = \operatorname{dim}_H(A_n) \not\to \operatorname{dim}(A) = \log_3(2). $$
Note: I am working with subsets of $[0,1]$.  However, we can regard these sets as subsets of $[0,1]^2$ with no modifications.  Alternatively, we might consider a similar setup with four maps $\varphi_j : [0,1]^2 \to [0,1]^2$ defined by
\begin{align}
\varphi_1(x) &= \frac{1}{3} x, &
\varphi_2(x) &= \frac{1}{3} x + \begin{pmatrix} \frac{2}{3} \\ 0 \end{pmatrix}, \\
\varphi_3(x) &= \frac{1}{3} x + \begin{pmatrix} 0 \\ \frac{2}{3}\end{pmatrix}, &
\varphi_4(x) &= \frac{1}{3} x + \begin{pmatrix} \frac{2}{3} \\ \frac{2}{3} \end{pmatrix}. \\
\end{align}
In this case, take $A_0 = [0,1]^2$ and
$$ A_n = \bigcup_{j=1}^{4} \varphi_j(A_{n-1}). $$
The approximating sets have Hausdorff dimension $2$, while the limiting set is a two-dimensional Cantor dust, which has Hausdorff dimension $\log_3(4)$.


Stability of difference equation $x_{n+1}=ax_ne^{-bx_n}$ Determine the conditions on $a$ and for which the nonzero equilibrium value of $b$ $x_{n+1}=ax_ne^{-bx_n}$ is stable, where $a$ and $b$ are positive constant.

I have learnt the condition of stability of system of difference equations, but I have no idea on this problem and I can not express $x_n$ in terms of n, could you please give me some hints? Thank you.

You've asked for some hints so I would start by considering different ranges for b (major clue: $b>0$ & $b<0$ due to the significance of the exponential sign in stability in infinite series)

Then consider what would happen if you kept calculating $x_n$ and what conditions you would have to apply for $a$ so that $|x_n|<\infty$


Find the number of elements of set $M$ having: $\forall A, B \in M$ there is $C \in M$ such that the triangle $ABC$ is equilateral Let $M$ a finite set of points in a plane such that $\forall A, B \in
 M$ there is $C \in M$ such that the triangle $ABC$ is equilateral.
   Find the possible number of $M$ elements.

My guess is the number is 3. It is easy to show there isn't such a set with, let's say, 4 elements, but I cannot cope with the general case.

Take the two points $A$ and $B$ farthest away in the set $M$, i.e. $|AB|=d$, the diameter of $M$. This is legit, since $M$ is a finite set, and thus there are two points achieving the diameter.

There must be some point $C$ such that $ABC$ is equilateral. Now, observe that since $AB=BC=CA=d$, the diameter of $M$, all points in $M$ must lie in the following figure $\Phi$ (I can't draw a diagram, but I can describe it explicitly).

$\Phi$ consists of the triangle $ABC$ together with three circular segments $s_A,s_B,s_C$, where $s_A$ is the segment of the circle centered at $A$ with radius $d$ bounded by the chord $BC$. $s_B,s_C$ are defined similarly.

Now suppose there's some other point $X$ in the set. First suppose $X$ is inside or on the sides of the triangle $ABC$. Split $ABC$ into three triangles by connecting the vertices to the center $O$, and suppose $X$ falls inside or on the sides of WLOG $ABO$. Then, there must be a point $Y\in\Phi$ such that $CXY$ is equilateral. Thus, $Y$ is inside the image of $ABO$ under rotation centered at $C$ by $60^\circ$. The two possible images of $ABO$ under such a rotation are two triangles that can be seen to lie outside of $\Phi$ except for the images of $A$ and $B$ under them, but we know $X\neq A,B$ by assumption. The key observation needed to see that is that the tangents to the circle centered at $C$ with radius $d$ at $A$ and $B$ respectively make $30^\circ$ angles with $AB$, and the image of $ABO$ is on one side of these tangents, while the segment $s_C$ is on the other. So, $X$ can't be inside $ABC$.

Similarly, suppose $X$ is WLOG in or on the boundary of $s_A$. Then there is some $Y\in\Phi$ such that $AXY$ is equilateral, i.e. $Y$ is in the image of $s_A$ under a rotation centered at $A$ with radius $d$. But again, it's easy to see that the two possible images intersect $\Phi$ only at $B$ and $C$, which are not allowed for $Y$.

So we conclude that there can be no other points in $M$, thus $|M|=3$.

We'll prove tham $|M|=3$
Suppose that $|M|\geq 4$ then say that points $A,B,C,E$ are different points in plane then:
$ABC$ is equilateral triangle.
Let D be such that CD is perpendicular to AB, then from equilateral triangle property we know that $CD$ is perpendicular bisector of $AB$, so also height of triangle $ABE$ should be also bisector of $AB$,since D is midpoint of AB then height of $ABE$ is ED, so ED will be the prependicular bisector of $AB$, which means that E should be on line CD.
Since $\angle{DAE}=60$ then either E=C or is symmetric point of C with respect to AB, but since E and C different then the second holds.
Referring to this figure then $ABE$ is equilateral but then $$\angle{CBE}=\angle{CBA}+\angle{ABE}=60+60=120$$
which means that triangle $CBE$ is not equilateral triangle.

So $|M|=3$

The idea of solution is that for any 2 points $X,Y$ and point $Z$, $XYZ$ make equilateral triangle if $Z$ lies in perpendicular bisector line of $XY$


Elementary proof that $2x^2+xy+3y^2$ represents infinitely many primes? We did in class $x^2+y^2$, which was easy, and we had for homework $2x^2+2xy+3y^2$, which I did (its values (if not square) must be divisible by form primes, or of the form $x^2+5y^2$, and clearly they can't all be the latter!).

Just to test my method I took the middle coefficient down by one - and ran into trouble...

This example morally comes from class field theory. It is just easy enough that I can do it using elementary algebraic number theory but not class field theory.

Write $\theta = (1+\sqrt{-23})/2$; it obeys $\theta^2-\theta+6=0$. Let $R$ be the ring $\mathbb{Z}[\theta]$. This is the ring of integers in the field $\mathbb{Q}(\sqrt{-23})$. It turns out that the class group of $R$ is $\mathbb{Z}/3$, representatives for the three ideal classes are:
$$I_0:= \langle 1 \rangle,\ I_1:=\langle 2, \theta -1 \rangle,\ I_2:=\langle 2, \theta \rangle.$$
I leave this for you to check from the standard Minkowski bounds. Note that $I_1 I_2 = \langle 4, 2(\theta-1), 2 \theta, 6 \rangle = \langle 2 \rangle$, so $I_1^{-1} = (1/2) I_2$ and vice versa. Note for future use that we are giving a $\mathbb{Z}$ basis for the latter two ideals, and that $\langle 1, \theta \rangle$ is a $\mathbb{Z}$-basis for $I_0$.

An arbitrary ideal equivalent to $I_0$ is of the form $\langle x+y\theta \rangle$, and we have $N(\langle x+y\theta \rangle) = x^2 - xy + 6 y^2$. An arbitrary ideal equivalent to $I_0$ is of the form $\langle x+y\theta \rangle$ in precisely two ways, because the unit group of $R$ is $\pm 1$. So
$$\# \{ I \subseteq R : \ I \sim I_0 \ \mbox{and} \ N(I) = n \} = \frac{1}{2} \# \{(x,y) : x^2 - xy + 6y^2 =n \}. \quad (1)$$

Similarly, an ideal equivalent to $I_1$ is of the form $\alpha I_1$, for $\alpha \in I_1^{-1} = (1/2) I_2$. This $\alpha$ looks like $(1/2) (2 x + y(\theta -1))$ for some integers $x$ and $y$ and we have $N(\alpha I_1) = N(\alpha) N(I_1) = (x^2 - xy +3 y^2/2) \cdot 2 = 2x^2 - 2xy + 3 y^2$ (exercise!). Running through the same argument as before:
$$\# \{ I \subseteq R : \ I \sim I_1 \ \mbox{and} \ N(I) = n \} = \frac{1}{2} \# \{(x,y) : 2 x^2 - xy + 3y^2 =n \}. \quad (2)$$
Similarly,
$$\# \{ I \subseteq R : \ I \sim I_2 \ \mbox{and} \ N(I) = n \} = \frac{1}{2} \# \{(x,y) : 2 x^2 + xy + 3y^2 =n \}. \quad (3)$$

Call these numbers $a_0(n)$, $a_1(n)$ and $a_2(n)$. We want to know that $a_2(p)$ is positive for infinitely many primes.

We have unique factorization into ideals in the ring $R$. So we have the analog of the Euler product
$$\sum_n \frac{a_0(n) + a_1(n) + a_2(n)}{n^s} = \prod_{p} \frac{1}{(1- p^{-s})^{a_0(p)+a_1(p)+a_2(p)}}.$$

Let $\omega$ be a primitive cube root of unity. Since the class group is $\mathbb{Z}/3$, with $[I_1]^2=[I_2]$ and $[I_1]^3=[I_0]$, we also have the identities:
$$\sum_n \frac{a_0(n) + \omega a_1(n) + \omega^2 a_2(n)}{n^s} = \prod_{p} \frac{1}{(1-p^{-s})^{a_0(p)}} \frac{1}{(1-\omega p^{-s})^{a_1(p)}} \frac{1}{(1-\omega^2 p^{-s})^{a_2(p)}}.$$
$$\sum_n \frac{a_0(n) + \omega^2 a_1(n) + \omega a_2(n)}{n^s} = \prod_{p} \frac{1}{(1-p^{-s})^{a_0(p)}} \frac{1}{(1-\omega^2 p^{-s})^{ a_1(p)}} \frac{1}{(1-\omega p^{-s})^{ a_2(p)}}.$$

Define these three sums to be $L_0(s)$, $L_1(s)$ and $L_2(s)$. Using equations $(1)$, $(2)$ and $(3)$, and approximating sums by integrals, we see that $L_0(s)$ has a simple pole at $s=1$ while $L_1(s)$ and $L_2(s)$ are bounded as $s \to 1$. Using explicit numerical computation, one can check that $L_1(s)$ and $L_2(s)$ do not vanish at $s=1$.

Now the end game is exactly like the proof of Dirichlet's theorem on primes in arithmetic progressions: take logs of the above equations to deduce that
$$\log \left( \frac{1}{s-1} \right) + O(1) = \sum \frac{a_0(p)+a_1(p)+a_2(p)}{p^s} + O(1)$$
$$O(1) = \sum \frac{a_0(p)+\omega a_1(p)+ \omega^2 a_2(p)}{p^s} + O(1)$$
$$O(1) = \sum \frac{a_0(p)+\omega^2 a_1(p)+ \omega a_2(p)}{p^s} + O(1)$$

We thus have
$$\sum \frac{a_2(p)}{p^s} = (1/3)\log \left( \frac{1}{s-1} \right) + O(1) \ \mbox{as}\ s \to 1^{+}$$
and, in particular, $a_2(p)$ is nonzero infinitely often.

So, where is the class field theory?  For $R$ the ring of integers of a number field, $H$ the class group of $R$, and $\chi: H \to \mathbb{C}^*$ a nontrivial character, define $L(\chi, s) = \sum_{I \subseteq R} \chi([I]) N(I)^{-s}$. If you wanted to generalize this proof to an arbitrary quadratic number field, you would want to know that $L(\chi, s) \neq 0$. For any particular $R$ and $\chi$, you can prove this by hand. In Dirichlet's theorem, the analogous result can be proved by looking at the zeta function of the cyclotomic field. In the general case, it can be proved by looking at the $\zeta$ function of the class field -- but only once you know this exists!

If you are willing to accept Dirichlet's Theorem on primes in arithmetic progression, then you can assume there are infinitely many primes of the form 4n + 3. Your form generates such numbers when y=1 and x is a multiple of 4.


Uniqueness of solution $u \in H^2(0, 1)$ to partial differential equation. Assume that $p \in C^1([0, 1])$ with $p(x) \ge \alpha > 0$ for all $x \in [0, 1]$ and $q \in C([0, 1])$ with $q(x) \ge 0$ for all $x \in [0, 1]$. Let $v_0 \in C^2([0, 1])$ be the unique solution of$$\begin{cases} -(pv_0')' + qv_0 = 0 & \text{on }[0, 1], \\ v_0(0) = 1,\,v_0(1) = 0.\end{cases}\tag*{$(*)$}$$Set $k_0 = v_0'(0)$. From some post elsewhere from MSE, we know that $k_0 \le -\alpha/p(0)$. We now investigate the problem$$\begin{cases} -(pu')' + qu = f & \text{on }(0, 1), \\ u'(0) = ku(0),\,u(1) = 0,\end{cases}\tag*{$(**)$}$$where $k \in \mathbb{R}$ is fixed and $f \in L^2(0, 1)$ is given. Assume $k = k_0$. We have that$$[(**) \text{ has a solution }u \in H^2(0, 1)] \iff \left[\int_0^1 fv_0 = 0\right].$$My question is, is there uniqueness of $u$?

No, $u$ is not unique.  Take any $u(t)$ that satisfies (**).  Then $u(t) + \theta v_0(t)$ is
also a solution for all $\theta \in \mathbb{R}$.  As the equations are linear, the only
thing to check is the condition:

$$ u’(0) + \theta v_0’(0) = ku(0) + \theta k = k u(0) + \theta k v_0(0) = k[u(0)+\theta v_0(0)] $$

which uses the fact that $k=k_0=v_0'(0)$ and $v_0(0)=1$.

The solution is unique if k is nonnegative.

Let $u, v $ be the solutions, consider w = u - v, then w solves
$$\begin{cases} -(pw')' + qw = 0 & \text{on }(0, 1), \\ w'(0) = kw(0),\,w(1) = 0,\end{cases}$$
Now
$$\int_0^1(-(pw')' + qw) w dx= 0$$
Integrating by parts
$$ -pw'w|_{x =0}^{x =1} + \int_0^1(pw'w' + qw^2) dx = 0$$
We know $-pw'w|_{x =0}^{x =1} = pw'(0)w(0) = pk(w(0))^2$

Therefore,
$$pk(w(0))^2 + \int_0^1(p(w')^2 + qw^2) dx = 0$$
So w = 0. Hence, the solution is unique.

If k is negative, it is not clear if it has a unique solution.


Intuitively explaining the difference between a combination and permutation I'm having a hard time trying to determine when to use combination and when to use permutation with a problem.  Can someone offer a clear and concise explanation or general rules to follow so I don't get tripped up on similar problems?

For example: How many ways are there to select five players from a 10-member tennis team.

My approach would be that there are 10 ways to choose the first spot, 9 for the second, 8 for the third... so the total is 10!/5!; but apparently this is a combination problem.

I'm just having a hard time telling the difference between the two.  Are there any questions I can ask myself before I begin to really solidify what the problem is asking for?

Thank you!

EDIT:

Here's another problem I'm confused with:

Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?

Why is the answer 9!/(3!6!) * 11!/(4!7!) rather than 9!/(3!6!) + 11!/(4!7!)?

Regular rule, Permutation is when order matters. You can memorize it with P ermutation-P osition. Combination on the other hand doesn't care in which order the elements are chosen.

As in your first example, you want to choose $5$ players, but no other information is given so you assume order isn't important.

Note that I the problem stated $5$ player to form a hockey team, then order could have mattered, for say center, Left and right wing, and left and right D player.

For your second example, note that for each subcomitee of $3$ members of math, there are $11!/(4!7!)$ subcomitee of members of CS so you have to multiply them

It is a matter of translation: In your problem if you have a collection (without order) then you asking how many sets can you form (combination). If you have an ordered collection (or chain, ranking, etc.) then you are asking about how many ordered sets you can form (permutation).


Derivatives problem - what am I doing wrong? The problem:

A shuttle lifts off vertically from a point $4$ miles from the command post.  For the first $20$ seconds of flight, its angle of elevation changes at a constant rate of $3$ degrees per second.  What is the velocity of the shuttle when the angle of elevation is $30$ degrees?

I made a right triangle picture and realized that $\tan \theta = \frac x4$.  This means that $ x=4\tan \theta$ which is the same as $ x=4\tan(3t)$ because $\theta=3t$ if the angle is changing at $3$ degrees per second.

The velocity will be $\frac {dx}{dt}$ so differentiating the equation gives $\frac {dx}{dt}=12\sec^2 (3t)$. Substituting back gives me $\frac {dx}{dt}=12\sec^2\theta$.

Finally, the problem asks for the velocity when the angle of elevation is $30$ degrees, which is $\frac \pi 6$, so evaluating my derivative gives $12\sec^2 \frac \pi 6$ which is $16$.

The text says the answer is supposed to be $\frac {4\pi} {45}$, and I can't see my error.  Please help.

community wiki answer so that the post can be closed.

To get the correct answer, you have to express the rate at which the angle is changing in radians per second.  Since $3^\circ$ is equivalent to $\pi/60$ radians,
$$x = 4\tan\left(\frac{\pi}{60}t\right)$$

{d(θ)/dt} = 3 degrees/second

θ = 30 degrees

tan θ = (x/4)

(dx/dt) = 4 sec^2 (θ) (dθ/dt)

(dx/dt) = 4 sec^2 (30 degrees) (3 degrees/sec)

(dx/dt) = 12 degrees/{cos^2(π/6) second --- change 30 degrees to radian = (π/6)
                                        --- change sec θ to (1/cos θ)

(dx/dt) = 12 degrees/(3/4)second

(dx/dt) = 16 degrees second

Then change 16 degrees to radian which is 16 degrees times (π/180 degrees)

Now for your final answer,

(dx/dt) = (4π/45) second


$ \lim_{x \to \infty} \frac{xe^{x-1}}{(x-1)e^x} $ $$ \lim_{x \to \infty} \frac{xe^{x-1}}{(x-1)e^x} $$

I don't know what to do. At all.

I've read the explanations in my book at least a thousand times, but they're over my head.

Oh, and I'm not allowed to use L'Hospital's rule. (I'm guessing it isn't needed for limits of this kind anyway. This one is supposedly simple - a beginners problem.) Most of the answers I've seen on the Internet simply says "use L'Hospital's rule".

Any help really appreciated. I'm so frustrated right now...

Multiply the fraction by $1$ in the carefully chosen disguise $\dfrac{e^{-x}}{e^{-x}}$ and do a bit of algebra:

$$\begin{align*}
\lim_{x \to \infty} \frac{xe^{x-1}}{(x-1)e^x}&=\lim_{x\to\infty}\left(\frac{xe^{x-1}}{(x-1)e^x}\cdot\frac{e^{-x}}{e^{-x}}\right)\\
&=\lim_{x\to\infty}\frac{xe^{-1}}{x-1}\\
&=\lim_{x\to\infty}\frac{x}{e(x-1)}\\
&=\frac1e\lim_{x\to\infty}\frac{x}{x-1}\\
&=\frac1e\lim_{x\to\infty}\frac{x-1+1}{x-1}\\
&=\frac1e\lim_{x\to\infty}\left(1+\frac1{x-1}\right)\;.
\end{align*}$$

That last limit really is easy.

You may wonder how I came up with some of the steps. The very first one was simply recognizing that if I divided numerator and denominator by $e^x$, the resulting fraction would be a lot simpler, in that all of the exponentials would be gone. Pulling constant factors outside the limit is usually useful and almost never hurts. The simplification of $\frac{x}{x-1}$ could also have been achieved by doing a straightforward polynomial long division of $x-1$ into $x$, but the trick of subtracting and adding the same amount (here $1$) in order to get an expression that can be split in some nice way is a pretty common one that’s worth remembering.

$$\lim_{x\to\infty}\frac{xe^{x-1}}{(x-1)e^x}=\lim_{x\to\infty}\frac{x}{x-1}\cdot\lim_{x\to\infty}\frac{e^{x-1}}{e^x}=1\cdot\frac{1}{e}=\frac{1}{e}$$

the first equality being justified by the fact that each of the right hand side limits exists finitely.


Partitioning Points Into Regions I have a list of points $p_1, p_2, ..., p_n$ in the plane where each point has a weight $w(p)$ and I want to partition the points into $k$ separate regions with the following constraints:

The convex hull of a region cannot contain any points from a different region.
Let $R_1, R_2, ..., R_k$ be the resulting regions. Let $$W(R_i) = \sum\limits_{p\in R_i} w(p)$$

Then, I wish to minimize the standard deviation of $\left\{{W(R_1), W(R_2), ..., W(R_k)}\right\}$ (So all regions should contain as close to the same total weight as possible.)

Does anyone know of any good algorithms that would allow me to compute $R_1, R_2, ..., R_k$? An optimal solution is not necessary for this problem. Also, n  ~ 10000 and k ~ 20. It seems like some sort of modified k-means clustering should work. Thanks in advance.

There is a growing literature in the area of computational geometry which deals with issues related to partitioning point sets into groups of approximately uniform size for some "secondary goal." This paper, http://cccg.ca/proceedings/2007/03a1.pdf while not directly dealing with your question may give you some useful ideas as well as having references to other approaches to point partition questions that have been developed by William Steiger (Rutgers) and others.

The methods described in this paper https://arxiv.org/pdf/1710.03358.pdf are sufficient for meeting the criteria posed in the original question.

The key to generating the desired region is given by the use of power diagrams, which assign points to centers based on the weighted squared distance measure. Then, this modification is paired with an iterative process to generate Voronoi cells, giving the final result. The authors also describe an optimization based on a min cost flow algorithm


Functions such that $xf''(x) + f'(x) > 0$ I'm struggling on how to approach this question:

Find functions $f$ such that $xf''(x) + f'(x) > 0$ with $x \in \mathbb{R}^+$

Any help?

Consider $g(x)=xf'(x)$; then $g'(x)=f'(x)+xf''(x)$, so you want to find the function $g$ so that it's increasing and $g(0)=0$. If $g$ is any differentiable function with $g(0)=0$ and $g'(x)>0$ for all $x$, then define
$$
F(x)=\begin{cases}
g'(0) & \text{if $x=0$}\\[3px]
\dfrac{g(x)}{x} & \text{if $x\ne0$}
\end{cases}
$$
and
$$
f(x)=\int_{0}^x F(t)\,dt
$$
will satisfy your requests, because
$$
f'(x)=F(x)
$$
and
$$
xf'(x)=g(x)
$$
for all $x$, so $g'(x)=xf'(x)+f''(x)>0$ by assumption.

Now it's only a matter of choosing a function $g$: if $g(x)=x$, you surely have $g'(x)>0$ and $g(0)=0$, so $F(x)=1$ and $f(x)=x$. But you can also choose
$$
g_1(x)=\arctan x,\qquad g_2(x)=e^x-1,\qquad g_3(x)=x^3+3x,\qquad \dots
$$

The LHS is equal to

$$\frac{d}{dt}\left(tf'(t)\right)>0$$

Integrating from $0$ to $x$:

$$\int_{0}^x  \frac{d}{dt}\left(tf'(t)\right) dt=xf'(x)-0\cdot f'(0)>0$$

How $x>0$

$$f'(x)>0$$

Then any function strictly inscreasing satisfy your equation.


Is induction something we take on faith? I understand that in mathematics and logic we can continue to reduce things to simpler axioms, principles, and so on, and we have to "stop" at some point otherwise we're just going on forever. We eventually say that some axiom or principle is good enough, so that we accept it to be valid, true, useful, sensible, and so on.

That being said, my question is whether mathematical induction is one of these "fundamental" concepts we just accept, or if it follows from some even deeper or simpler concept.

Sometimes I see people say that it works because of the well-ordering principle of the natural numbers, but this doesn't satisfy me. In Tao's Analysis Vol I, we say $m \leq n$ (for natural numbers $m$ and $n$) iff $m = n + a$ for some natural number $a$. But then if I wanted to prove that any arbitrary set of natural numbers has a "least element" (the definition of the well-ordering principle), I'd be resorting to induction, the very thing I'm trying to "prove."

Does this mean the concept of induction is just something we all accept as one of those sufficiently simple, intuitive things that require no further proof, that comes from no simpler means?

My viewpoint is the same as in Noah's first comment: for me, induction is part of the essence of what I mean when I talk about the natural numbers, so the thing I take on faith is not that induction is true but that the natural numbers "exist," whatever that means. Axioms don't tell you what to take on faith: they're a way for two people to agree that they're talking about the same thing.

Some people called ultrafinitists would in some sense deny that the natural numbers exist.

Here is a blog post which describes in detail the sense in which the Peano axioms are a way for two people to agree that they mean the same thing by "the natural numbers."

In the first several books of Aristotle you can find a discussion of different forms of "priority". Among them is a statement concerning priority of existence. In this account, Aristotle remarks that there must exist one individual if, in fact, two individuals are the subject of discussion. It is this account of relation which seems to ground the directionality of succession in natural numbers.

But, the situation is far more complicated. In the same discussion, Aristotle speaks of genera being prior to species. This is a motivation for arriving at the identity of indiscernibles -- a principle denied by first-order logic. Yet, it remains relevant in the guise of the principle of indiscernibility of non-existents from negative free logic. As Dana Scott has observed, this principle grounds Frege's definition of the number zero. Since Frege's definition is essentially that found in Zermelo-Fraenkel set theory, it serves as a condition of well-fomedness for the iterative hierarchy.

A good example in the literature can be found in Moschovakis' work on formal recursion theory where all meaningless syntactic forms are set equal to one another and denoted as the empty partial function.

The reason for mentioning the two directions (from below with succession and from above with "least" classes) is that this accounts for the difference between first-order and second-order notions of induction. The first-order account depends upon a well-formedness condition to assert the individuality of its base element. Note, however, that such a  claim is opaque to formalist accounts of foundations based on formal systems and interpretations.

At a much deeper level, there is the issue of discernibility within a logical domain. Hilbert acknowledges that well formed identity relations are a presupposition of formalist mathematics. So, it is difficult to find relevant discussion. One place to find such considerations is in Russell's "Principles of Mathematics". He distinguishes between being and existence. Then he makes the claim that all things with being can be counted. This is motivated by the logical problem of negative existentials. But it is also a well ordering principle.

In other words, Russell is suggesting that ordinal numbers may be  viewed as generic names for a consistent global labeling for any logical domain. This is implicit in his distinction between a logical class and a mathematical collection. And, it is very nearly explicit in the quote from Bolzano he uses to explain his account of numerical conjunction as the ground of logical domains. Bolzano is clear that each object be denoted uniquely.

Today one speaks of expanding a language with constants so that each object of the domain has a denotation. The procedure is attributed to Abraham Robinson. Such expansions are usually represented using ordinal subscripting.

If you wish to get a sense of how induction arises naturally in mathematical discourse, look at the first four chapters of Moschovakis' book, "Elementary Induction Over Abstract Structures".


What causes long sequences of consecutive 'collatz' paths to share the same length? I asked Longest known sequence of identical consecutive Collatz sequence lengths? some time ago, but I don't feel like it really got to the bottom of things.

See, in the answers lopsy find a sequence in the range of $596310 ... 596349$ and makes a heuristic argument:

  There's nothing special about these numbers, as far as I can see. In
  fact, there are probably arbitrary long sequences of consecutive
  numbers with identical Collatz lengths. Here's a heuristic argument:

  A number $n$ usually takes on the order of ~$\text{log}(n)$ Collatz
  steps to reach $1$.

  Suppose all of the numbers between $1$ and $n$ have random Collatz
  lengths between $1$ and ~$\text{log}(n)$. Then, if we choose a
  starting point at random, the probability that the next $X$
  consecutive numbers all have the same Collatz length is
  ~$\text{log}(n)^X$. There are ~$n$ possible starting points, so we
  want $X$ so that the probability is $\text{log}(n)^X \cong
> \frac{1}{n}$. Then I'd expect the longest sequence to have around $X$
  consecutive numbers.

  As it turns out, $X=\frac{\text{log}(n)}{\text{log}\text{log}(n)}$
  does the trick.

Except in the comments exchanged afterwards I point out that:

  log(596349)/log(log(596349)) ~ 7, not 40

(that should be log(596310)/log(log(596349)) but the comment holds)

So Heuristically we're expecting 33 fewer consecutive sequences of the same length, seem like a massive outlier.

So perhaps these sequences are special; what causes them to to arise?

If we look only at the occurences of two consecutive numbers $n,n+1$ with the same Collatz-trajectory-length $cl$ (I call this $cecl$ meaning "consecutive equal collatz lengthes", here $cecl=2$) then we can observe periodicity in $n$ with cycle-lengthes of perfect powers of $2$ and odd and even starting values. For instance, all numbers of the form $n=8k+4$ (with $k$) show a $cecl=2$ property. We might express this by an analytical formula. For the even number $n$ we look at the head of the trajectory
$$ n_0 \to n_1={n_0\over 4} \to n_2=3n_1+1 = 3{n_0 \over 4}  +1= {3 \over 4} n_0 +1 \tag 1$$ and for the odd number $m_0=n_0+1$ we get
$$ m_0=n_0+1 \to m_1 = 3m_0+1 \to m_2={m_1 \over 4}={3(n_0+1) +1\over 4}= {3 \over 4} n_0 +1 \tag 2$$
which result in equality $n_2=m_2$ and from there the same trailing trajectory follows. Because the leading trajectory $n_0 \to n_2$ is 1 "3n+1" step and 2 "/2" steps and accordingly for $m_0$ the two overall lengthes are equal.
Because in (1) we see, that $n_0$ must be divisible by $4$ but not by $8$ we can conclude, that for each number $n = 8k+4$ with some $k_{min}$ and $k \ge k_{min}$ we shall have a cecl of at least 2. The first occurence is $n_0=12,m_0=13$ which give $n_2=5=m_2$ and from that the trailing trajectory is equal. The next occurence is $n_0=20,m_0=21$ and we get $n_2=16$ and $m_2=16$ and from there equality of lenghtes.
For all residual classes modulo 8 we find such cyclic cecl=2 occurences, however with perfect powers of 2 as cycle-lengthes, so for instance $n_{0,k}=37+2^5k$ give $cecl=2$, as well as $45+2^6k$ and $29+2^7k$ and so on.
After we find, that a number $n_{0,k}=4+2^3k $ has a $cecl=2$ and $m_{0,j}=29+2^7j$ then if $k$ and $j$ are selected such that $m_{0,j}=n_{0,k}+1$ then the two $cecl$'s join to build a $cecl=3$.

Accordingly this can happen if three or more conditions/cycles meet at some $n_0,n_0+1,n_0+2,...$ - then we can have $cecl$'s of arbitrary lengthes.
The occurence of such longer $cecl$'s are thus themselves periodic, and result from some multiplicative expression of modular conditions with cycle-lengthes of $2^w$ and odd and even initial values, which meet at consecutive numbers $n_0,n_0+1,...$

In my other answer in the linked question I've given a picture/table which illustrates that joins of consecutive numbers with each $cecl=2$-property.

Here at $n_0=28,m_0=29$ and on $n_0=68,m_0=69$ (and so on) join two consecutive $cecl=2$s to make one of $cecl=3$.

The number really has to do with how many $2^k-1$ odds on the path.  27 is bad because it goes through 31.  You basically are growing and whittling – hence hailstone problem – I like Josephus with adding people!

You add $\frac{3n+1}2$ multiplicatively for the power of 2 closest to the odd number 27 is 3 so you increment up twice then eliminate even powers of 2.  Then you hit 31, then you increment 5 times before whittling the evens.  Any MAP of these shouldn't be by counting in the conventional sense, but by an alternate method of I3E3I5 until you get to 1.


Proving that a quotient space is Hausdorff This question is influenced by Quotient space of unit sphere is Hausdorff. I have slightly modified this to make it somewhat difficult.

 Let $S^1=\{e^{2\pi it}|r\in\mathbb{R}\}$ be the unit sphere. Define $\sim$ on $S^1$ where two points are identified if $t_1-t_2=\sqrt{2}k$, for some $k\in\mathbb{Z}$. It must be shown that $S^1/\sim$ is Hausdorff.

Define $f:S^1\times S^1\rightarrow S^1$ by $f(x,y)=xy^{-1}$. Clearly $f$ is continuous. Let $R=\{(x,y)\in S^1\times S^1|x \sim y \}=\{(e^{2\pi it_1},e^{2\pi it_2})\in S^1\times S^1|t_1-t_2=\sqrt{2}k,k \in\mathbb{Z}\}$. Also, let $A=\{ e^{2\sqrt{2}k\pi i}|k\in \mathbb{Z} \}$. Then $f^{-1}(A)=R$. $A$ being a countable set implies that $A$ is closed, therefore $R$ is closed since $f$ is continuous. Thus $S/\sim$ is Hausdorff. Is this proof correct? Thank you.

First, $S^1=\{e^{2\pi it}:t\in\mathbb{R}\}$ is a unit circle rather than a unit sphere.
Second, for $t_1,t_2\in\mathbb{R}$ we have $e^{2\pi it_1}=e^{2\pi it_2}$ if and only if $t_2-t_1\in\mathbb{Z}$, hence we can also write $S^1=\{e^{2\pi it}:t\in[0,1)\}$.
Third, in order to correctly define a binary relation $\sim$ on $S^1$ by identifying points $e^{2\pi it_1}$ and $e^{2\pi it_2}$ whenever $t_1,t_2$ satisfy a property $P(t_1,t_2)$, one has to ensure that the property $P$ has the same logical value for all pairs $(t_1,t_2)\in\mathbb{R}^2$ that yield the same pair of points $(e^{2\pi it_1},e^{2\pi it_2})$ on the circle.
Namely, that for any $t_1,t_2,t'_1,t'_2\in\mathbb{R}$, if $t'_1-t_1\in\mathbb{Z}$ and $t'_2-t_2\in\mathbb{Z}$, then $P(t_1,t_2)\equiv P(t'_1,t'_2)$.

Your property $P(t_1,t_2)\equiv(\exists k\in\mathbb{Z})(t_1-t_2=\sqrt{2}k)$ is not such.
Let $t_1=1+\sqrt{2}$, $t'_1=\sqrt{2}$, $t_2=t'_2=1$.
Then $t'_1-t_1$ and $t'_2-t_2$ are integers, $P(t_1,t_2)$ holds true since $t_1-t_2=\sqrt{2}$, but $P(t'_1,t'_2)$ is false since $t'_1-t'_2=\sqrt{2}-1$ and there is no $k\in\mathbb{Z}$ satisfying $\sqrt{2}k=\sqrt{2}-1$, as this would mean that $k=1-1/\sqrt{2}$. So your relation is not correctly defined and it has no sense to ask whether $S^1/\mathord{\sim}$ is Hausdorff.

The only way for points to be equivalent is for k=o so your equivalence relation is the identity (again ) . Try t_1-t_2 =k/2  which would identify antipodal points. Then I think  your argument will work . detail ? If t_1-t_2=2^(1/2)k then e^2(PI)i$\sqrt2$k =1 . Then $\sqrt2$k is an integer so the square root of 2 is rational ( impossible) unless k=0 So k=0 and the equivalence relation is the identity