What should the high school math curriculum consist of? "Life is open book."

With the advent of widely accessible, inexpensive (or even free) computational tools and Computer Algebra Systems (TI-89, Wolfram|Alpha, etc.), much of what traditionally comprises a high school math curriculum can now easily be done by almost everyone.  Factoring polynomials, solving inequalities, graphing linear equations, differentiation and integration -- these are the types of skills high school math students spend most of their time learning, and yet all of it can be done for free by anyone with a web browser.

What does this mean for the high school math curriculum?  On the one hand, we could leave it more-or-less the same, insisting that today's student learn what we learned decades ago, while banning or carefully regulating the use of these new tools.  On the other hand, we could embrace the tools and the opportunities they create to spend more math class time on different topics and skills, perhaps focusing more on analytic and synthetic problem solving and less on mechanical symbolic manipulation -- but at the risk of students never learning some basic foundations.

So how about it?  Binomial coefficients?  The angle-addition formulas for trig functions?  The conditions under which a function has an inverse?  Basic computer programming?  Keeping in mind that the vast majority of high school students do not go on to become professional mathematicians, what should the high school math curriculum consist of?

Btw, I post this question (inspired by this discussion) here because this is a community of thoughtful mathematicians.  I recognize this discussion may belong in a different forum, but I don't what/where that forum is.  Any suggestions are welcome.

I strongly believe that even if something can be done by calculator, a high school student should understand some nuts and bolts of how it's being done.

I spent some time doing volunteer tutoring at CRLS (Cambridge Rindge and Latin School). I still remember the girl at 8th or 9th grade who was studying inequalities, yet she couldn't compute $2-1$ without the help of calculator. The most frustrating case was the kid in 9th or 10th grade who didn't know multiplication tables, he couldn't compute, say, 3 times 7 in his head. I was supposed to help him with square roots. Well, how do you explain that $\sqrt{8} = 2\sqrt{2}$? First of, you have to realize that $8 = 2 \times 2 \times 2$, and that's exactly what he couldn't do. I ended up spending some extra time with him, afterward been told that he passed the test or exam and was very happy with my help - but I wasn't! I felt we were wasting lots of time and just because he didn't know multiplication tables, he couldn't break down numbers into factors, and calculator wasn't really help.

The bottom line: I think in school students still should learn basic arithmetic before moving to more advanced stuff. I think it's a pure idiocy to introduce the kids to set theory while having them relying on their calculators to compute $1 + 1$. Honestly, the advanced stuff can wait till college.

I am surprised people advocate the white box approach to learning math. In computing, it is imperative from programmers of lower layers(operating system, compilers) to hide their code internals to higher layers programmers. I don't see anything wrong with hiding low-level math from kids through the use of CAS(computer algebra system) and mathematical programming languages. In fact it need be such low level "algorithms" can be taught using such CAS eg "Write an algorithm that performs long division". Math assimilation has been regressive because of old methods of teaching which were clearly paper-based before the advent of computers. Einstein had to hire an "assistant" who acted basically as a computer to grind the numbers. My argument is we have computers now and let us incorporate them in learning "high" math which matters. In fact, low-level math has no applications in the real world which makes sense to relegate it to the computer while kids are taught how to use math as professionals do.

My ideal syllabus for high school, assuming they have been introduced to computer earlier on, especially programming lessons.

discrete mathematics (binary, Boolean algebra, logic)
recursion theory (theory of functions, classifications of functions, graphing using computer)
history of mathematics
calculus (allowed to use computer)
mathematical modeling.
computer programming.
linear algebra (matrices)


Equation with derivative on the left side I have a differential equation with derivative on the left side:

$y'=x^2e^x$

My theory is, that the solution to this equation is a simple integral $\int x^2 e^x dx$.

Is my theory correct?

Thanks

Yes, you are right. You only have to calculate the antiderivative of the RHS

This is the simplest case of an ODE.

$$y'=f(x)$$ or $$dy=f(x)\,dx$$ which you integrate as

$$y=\int f(x)\,dx+c=F(x)+c.$$

Another simple case is that of the separable equation,

$$g(y)\,y'=f(x),$$

$$\int g(y)\,dy=\int f(x)\,dx+c$$

or

$$G(y)=F(x)+c,$$

$$y=G^{-1}(F(x)+c).$$


Probability: is it raining? You're about to get on a plane to Seattle. You want to know if you should bring an umbrella. You call 3 random friends of yours who live there and ask each independently if it's raining. Each of your friends has a 2/3 chance of telling you the truth and a 1/3 chance of messing with you by lying. All 3 friends tell you that "Yes" it is raining. What is the probability that it's actually raining in Seattle?

Attempt:

To put it a bit more formally... Let $p_r$ be the prior probability for rain ($p_n=1-p_r$). Then the probability of rain given 3 "yes" replies $(y,y,y)$

$$P\{\text{rain}|y,y,y\}=\frac{P\{\text{rain}\bigcap (y,y,y)\}}{P\{y,y,y\}}$$
$$=\frac{P\{y,y,y|\text{rain}\}\cdot p_r}{P\{y,y,y|\text{rain}\}\cdot p_r+P\{y,y,y|\text{no rain}\}\cdot p_n}$$

Next, if we assume conditional independence of friends' replies the last formula becomes

$$=\frac{(2/3)^3\cdot p_r}{(2/3)^3\cdot p_r+(1/3)^3\cdot p_n}=\frac{p_r}{p_r+ p_n/8}$$

This answer is  duplicate from the following link
Facebook Question (Data Science)

Suppose it rains, then 3 yes answers would have been heard with probability $\frac{8}{27}$ if it does not rain, we'd hear those answers with probability $\frac{1}{27}$. We know we've heard them, so we're in one of two worlds, and one is 8 times more likely. So the intuitive answer is $\frac{8}{9}$, I'd say.


If $x, y \in \mathbb{N^{*}}$, such that $\frac{x}{y}+\frac{y}{x} \in \mathbb{N}$, show that $x=y$. If $x, y \in \mathbb{N^{*}}$, such that $\frac{x}{y}+\frac{y}{x} \in \mathbb{N}$, show that $x=y$.

My try: If $x$ is a multiple of $y$, such that $x \neq y$, $\frac{x}{y}$ would be greater than $1$, and natural, while $\frac{y}{x}$ would be less than $1$, so not a natural number. Same if we swap $x$ with $y$. So, in those two cases, the given sum can't be natural.

I don't know how to continue it from here. Can you help me, please? Thanks!

Let $q=\frac{x}{y}$, we want $q+\frac{1}{q}=n$ for some natural number $n$, or in other words $q$ is a rational root of $p(x)=x^2-nx+1$. Now by Rational root theorem, only possible values are $q=\pm 1$. Now it cannot be $-1$ since originally $x,y>0$. So we have $q=1$ and so $x=y$.

$$\frac xy +\frac yx \to \frac{x^2+y^2}{xy}$$ which is only an integer when $x=y$


How can I solve the improper integral $\int_{1}^\infty {dx \over {(x+1)(x+2)}}$ $$\int_{1}^\infty {dx \over {(x+1)(x+2)}}$$

I have the indefinite integral solved for:

$$\ln(x+1)-\ln(x+2) + C$$

But I don't know how to finish with $[1, \infty]$.

$\ln(x+1)-\ln(x+2) + C = \ln(\frac{x+1}{x+2}) + C$ evaluated at 1 and $\infty$ gives $\ln(\frac{\infty}{\infty}) - \ln\frac{2}{3}=\ln\frac{3}{2}$


Question on polar coordinates and cartesian coordinates I know the conversion between polar coordinates and cartesian coordinates. Nevertheless, I cannot understand why $r=2a\cos\theta$ represents a circle of radius $a$ and center $(a,0)$.
Can anyone explain it?

The graph hopefully makes clear angle subtended at origin is half that at center inside semi-circle and placed that way.

$ r = 2 a \cos \theta $

where the radius vector $r$ is a projection of diameter $ 2 a. $

The polar equation of all circles through the origin, rotated by $\alpha $ is:

$ r = 2 a \cos (\theta + \alpha) $

I suggest you draw out the graph with the circle because that's how I understand it. You could try and put it a few values for $\theta$ to see how the shape of the circle comes out.


prove that, for some $p$ & $q, a_p, a_p+a_{p+1} + \cdots$ all are positive Let $ a_1,a_2,\ldots ,a_{100}$ be real numbers, each less than one, satisfy
 $ a_1+a_2+\cdots+a_{100} > 1$

Show that there exist two integers $p$ and $q$ , $p<q$, such that the numbers

$$a_q, a_q+a_{q-1}, \ldots, a_q+\cdots+a_p,$$

$$a_p, a_p+a_{p+1},\ldots,a_p+\cdots+a_q$$

are all positive.

I proved that if $n$ is the smallest integer such that
$ a_1+a_2+\cdots+a_n>1$
then all the sums $a_n,a_n+a_{n-1},\ldots,a_n+\cdots+a_1$ are positive.
Will this help to prove?

source: Test of Math at 10+2 level( A collection of old ISI B.stat & B.math entrance exam question papers)

[I found this solution collaboratively with someone else offline.]
$\def\nn{\mathbb{N}}$
$\def\rr{\mathbb{R}}$

Let $T(n) = ( \text{The theorem is true for any length-$n$ sequence from $\rr$} )$, for any $n \in \nn$.

If $T(n)$ is false for some $n \in \nn$:

  Let $m \in \nn$ be the minimum such that $T(m)$ is false [by well-ordering].

  Let $a_{1..m}$ be a sequence that does not satisfy the theorem.

  For any $p \in [1..m]$:

    If $\sum_{k=1}^p a_k \le 0$:

      $\sum_{k=p+1}^m a_k \ge \sum_{k=1}^m a_k > 1$.

      Also $a_{p+1..m}$ satisfies the theorem [by minimality of $m$].

      Thus some segment of $a_{p+1..m}$ has initial and terminal segments all with positive sum.

      But any segment of $a_{p+1..m}$ is also a segment of $a_{1..m}$.

      Thus $a_{1..m}$ satisfies the theorem, which gives a contradiction.

    Therefore $\sum_{k=1}^p a_k > 0$.

    Similarly $\sum_{k=p}^m a_k > 0$.

  Therefore $a_{1..m}$ has initial and terminal segments all with positive sum.

  Thus $a_{1..m}$ satisfies the theorem, which gives a contradiction.

Therefore $T(n)$ is true for any $n \in \nn$.

If the sum  is positive, at least one element is positive. Pick that one as "sequence" (of length 1).


Why does $(1+x)^np(x)$ has at least $n+1$ terms? $p(x)$ is a polynomial. Assume $p(x)\ne0$.
How to prove that $(1+x)^np(x)$ has at least $n+1$ terms?

Hint: Induction with differentiation to get to smaller step.

If p(x) is non-zero then it  contains at least one term in it. How many terms are in $(1+x)^n$? The binomial expansion will help here.


Zero divisor in $R[x]$ Let $R$ be commutative ring with no (nonzero) nilpotents. If $f(x) = a_0+a_1x+\cdots+a_nx^n$ is a zero divisor in $R[x]$, how do I show there's an element $b \ne 0$ in $R$ such that $ba_0=ba_1=\cdots=ba_n=0$?

It is  true over any commutative ring, and is sometimes called McCoy's theorem. Below is a proof sketch
from my sci.math post on May 4, 2004:

Theorem $\ $ Let $ \,F \in R[X]$ be a polynomial over a commutative ring $ \,R.\,$
If $ \,F\,$ is a zero-divisor then $ \,rF = 0\,$ for some nonzero $ \,r \in R.$

Proof $\ $  Suppose not. Choose $ \,G \ne 0\,$ of min degree with $ \,FG = 0.\,$

Write $ \,F =\, a +\,\cdots\,+ f\ X^k +\,\cdots\,+ c\ X^m\ $

and $ \ \ \ \ G = b +\,\cdots\,+ g\ X^n,\,$ where $ \,g \ne 0,\,$ and $ \,f\,$ is the highest deg coef of $ \,F\,$ with $ \,fG \ne 0\,$ (note that such an $ \,f\,$ exists else $ \,Fg = 0\,$ contra supposition).

Then $ \,FG = (a +\,\cdots\,+ f\ X^k)\ (b +\,\cdots\,+ g\ X^n) = 0.$

Thus $\ \,fg = 0\ $ so $\: \deg(fG) < n\,$ and $ \, FfG = 0,\,$ contra minimality of $ \,G.\ \ $ QED

Alternatively it follows by Gauss's Lemma
(Dedekind-Mertens form) or related results.

Let f be a polynomial in the commutative ring R. Suppose fg is 0 where g is nonzero. Adjoining the coefficients of f and g to the prime subring we can assume the ring is Noetherian via the Hilbert Basis Theorem. Take a reduced primary decomposition of O in R. Extending each primary ideal to R[X] gives a primary decomposition for 0 in the polynomial ring. So f being a zerodivisor is contained in some P[X] where P is an associated prime of 0 in R. But P is killed by some nonzero c of R, c so r kills f.


How to convert the probability P/Q to P⋅Q−1 where Q is co-prime with mod I was dealing with probability in programming but i was stuck on the final answer part.

Below is statement in which format i have to give the answer

Can you find the probabilities It can be proved that for each of these values, the probability can be expressed as a fraction PQ, where P and Q are integers (P≥0, Q>0) and Q is co-prime with 998,244,353. You should compute P⋅Q−1 modulo 998,244,353 for each of these values.

Below is probability that can be calculated on paper and 2nd line is for what i have to print can any1 explain how should calculate P.Q-1.

For 1st Input
Calculated Probability = 1/4
Answer : 748683265
For 2nd Input
Calculated Probability was = 1/16 , 3/16 , 3/16 , 9/16
Answer that was given = 436731905 935854081 811073537 811073537

If anything is unclear then pls comment as iam new to community I am not very good at asking questions.
Thank you for your reply in advance.

$$\frac{p}{q} \equiv p \cdot q^{-1} \mod 998244353$$

Since $q$ is coprime with $998244353$, $q^{-1}$ always exist. It can be found using extended euclidean algorithm, shown here.

For example, $\frac{1}{4} \equiv 4^{-1} \mod 998244353$.

You can check that $4 \cdot 748683265 = 2994733060 \equiv 1 \mod 998244353$,

so $4^{-1} \equiv 748683265 \mod 998244353$.

This can be solved using Extended Euclidean Algorithm. You can visit the following link for further info and code solutions:

https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

Also there is a same question on overflow for this.


a regular graph has 15 edges, how many vertices does it have? I want to compute $|V|$ for a regular graph with 15 edges. According to this lemma:

$\sum_{v \in V} deg(v)=2|E|$

Whatever $|V|$ is, it should satisfy the above lemma. Based on that fact that in a regular graph, all vertices have the same degree, and that $|V|$ is an integer:

$\sum k = 2*15=30$

The only way for it to be correct is that $k=2,3,5$, which results in $|V|=6,10,15$. For example, if all vertices have a degree of $5$, then:

$\sum 5 = 30$

$5 |V| = 30$

So,

$|V|=\frac{30}{5}=6$

This was my solution, but I saw another solution which looks a little odd to me. It is based on the assumption that:

  In a regular graph, $deg(v)=|V|-1$.

which I think is not true. But anyway, this solution uses the above assumption to obtain:

$\sum (|V|-1)=30 \Rightarrow |V| ( |V| -1) =30$

$|V|^2 - |V| =30$

$(|V|-6)\cdot(|V|+5)=0$

Then it accepts $|V|=6$, because, the number of vertices can't be a negative number.

Now my question is: is that assumption "in a regular graph, $deg(v)=|V|-1$" correct? Which answer is correct?

It's not true that in a regular graph, the degree is $|V| - 1$. The degree can be 1 (a bunch of isolated edges) or 2 (any cycle) etc. In a complete graph, the degree of each vertex is $|V| - 1$.

Your argument is correct, assuming you are dealing with connected simple graphs (no multiple edges.) If they need not be connected, you miss the case $k=1$ with 30 vertices.

Number of edges $=|E|=15$
Number of vertices$=|V|=n=?$
$$
\begin{split}
|E|&=n\cdot\frac{k}{26} \\
2\cdot|E|&=n\cdot k\\
2\cdot 15&=n\cdot k\\
n&=\frac{30}{k}
\end{split}
\qquad\text{ where }k=2,3,5,\ldots
$$
At $k=1$ graph will be disconnected.


Which one is preferred: $r2^m$ or $2^m r$? Which is preferable to write: $r2^m$ or $2^m r$?

I think $r2^m$ is usually used, because if we write r at the end it is sometimes confused with $2^{mr}$


Probability of rolling X successes with differently sized dice I'm trying out different systems for a board game, and my (weak) probability skills are failing me.

The basic mechanic is as follows: you roll a number of six-sided dice (d6). Any die showing 5 or more is a success.
A specific bonus can "upgrade" part of your pool to a larger die (let's say a 10-sided dice, or d10).

So for example:
regular roll: roll 7d6; any die showing 5 or more is one success.
same roll with bonus: roll 4d6 and 3d10; any die showing 5 or more is one success.

I'd like to learn how to calculate the chance of getting X successes with the mixed pool (either "X" successes or "X or more" successes).

this thread thaught me how to find the probability for the homogenous pool, but I have no idea how to change the formula to accomodate the differently-sized dice.

I would like to learn the general formula, to be adjusted for different size of dice (such as d8 and d12) and for a larger or smaller pool of mixed dice as well.

Thanks in advance, sorry for any English mistake I may have made.

I jump directly to the second question:

  same roll with bonus: roll $4d6$ and $3d10$; any die showing 5 or more
  is one success.

4d6: The probability that one die show a 5 or a 6 is $\frac26=\frac13$. Now you can use the binomial distribution to calculate that x dice out of $4$ have an success.

$$P(X=x)=\binom{4}{x} \left( \frac{1}{3} \right)^x\cdot \left( \frac{2}{3} \right)^{4-x}$$

Similar for $3d10$

$$P(Y=y)=\binom{3}{y} \left( \frac{6}{10} \right)^y\cdot \left( \frac{4}{10} \right)^{3-y}$$

Let´s  denote $s$ as the number successes. We have to calculate the sum of the successes and fails to get the probability for $S=x+y$ successes and $3+4-x-y=7-s$ fails.  At maximum we can have $7$ successes. Thus

$P(S\geq s)=P(S=s)+P(S=s+1)+\ldots+P(S=7)$

As an example I show how to calculate $P(S=5)$. For this purpose I made a table for the combination of the successes for $x$ and $y$

$\begin{array}{|c|c|}\hline x&y \\ \hline 2&3 \\ \hline 3&2 \\ \hline 4&1 \\ \hline\end{array}$

Note that $x=1$ is not possible since $y\leq 3$. This shows why there is no "simple" formula. The random variables  $X$ and $Y$ are independent. Thus $P(X\cap Y)=P(X)\cdot P(Y)$. The single probabilities are

$$P(X=2,Y=3)=\binom{4}{2} \cdot \left( \frac{1}{3} \right)^2\cdot \left( \frac{2}{3} \right)^{4-2}\cdot \binom{3}{3} \cdot  \left( \frac{6}{10} \right)^3\cdot \left( \frac{4}{10} \right)^{3-3}$$

$$P(X=3,Y=2)=\binom{4}{3} \cdot \left( \frac{1}{3} \right)^3\cdot \left( \frac{2}{3} \right)^{4-3}\cdot \binom{3}{2} \cdot  \left( \frac{6}{10} \right)^2\cdot \left( \frac{4}{10} \right)^{3-2}$$

$$P(X=4,Y=1)=\binom{4}{4} \cdot \left( \frac{1}{3} \right)^4\cdot \left( \frac{2}{3} \right)^{4-4}\cdot \binom{3}{1} \cdot  \left( \frac{6}{10} \right)^1\cdot \left( \frac{4}{10} \right)^{3-1}$$

Finally the single probabilities have to be summed up to get $P(S=5)$.

"regular roll: roll 7d6; any die showing 5 or more is one success."
  With 6 sides, the probability of success, a single die showing "5 or more", i.e. 5 or 6, is 2/6= 1/3. The probability of no success is 2/3. The probability of exactly n dice showing 5 or more, the other 7- n not, is $\begin{pmatrix}7 \\ n\end{pmatrix}(1/3)^n(2/3)^{7- n}$ where $\begin{pmatrix}7 \\ n\end{pmatrix}$ is the "binomial coefficient", $\frac{7!}{n!(7- n)!}.

"same roll with bonus: roll 4d6 and 3d10; any die showing 5 or more is one success."
  The probability of "success" on the six sided die is, as before, 1/3.  The probability of "success" on the 10 sided die is 5/10= 1/2.  To find the probability of n successes, look at all the ways two non-negative integers can add to n: i= 1 to n, j= n- i.  Calculate the probability of i successes in 4 rolls of a 6 sided die, as above. Calculate the probability of n- i successes in 3 rolls of the 10 sided die as above except that the probability of success is 5/10= 1/2 and the probability of non-success is 1/2.  Multiply them together and then add for i going from 1 to n.


Mean number of replacements in a uniform random permutation I'm having a trouble understanding the logic behind the derivation of probability for a certain event. I'll state my question and explain the part which's bothering me:

"In a permutation of an ordered numbers set $(1,2,3,....,n) \:, n>=2$, each event in which two numbers $i$ and $j$,  $i\neq j$, swap places ($i\longleftrightarrow j$) is called a replacement. For example, in the permutation $(7,5,6,3,2,4,1)$ of the ordered numbers set $(1,2,3,4,5,6,7)$, there are two replacements: $1\longleftrightarrow 7$ and $2\longleftrightarrow 5$.

What is the expectation of the number of replacements in a uniform and randomly given permutation of the ordered numbers set $(1,2,3,4,5,6,7)$?

Ps.: By uniform, it means that all the permutations have the same probabilities."

My solution: There are $\frac {42}{2}=21$ couples of numbers which can participate in a replacement, so I defined the following indicator:

$$\forall i\neq j, \:\:\:\:\:\mathcal{X}_{i,j}=\begin{cases} 1,& i,j \:are \:swapped\:\\ 0,& otherwise\end{cases}$$

Hence, the number of replacements in a given permutation is:

$$X=\sum\limits_{1\le i<j\le 7} \mathcal{X}_{i,j}$$

But I'm having a trouble calculating the probability that two numbers $i,\: j$ are a replacement. My first instinct tells me it's $\frac {2}{42}=\frac {1}{21}$, for out of 42 couples it can be picked twice. However, that means that $E[\mathcal{X}]=1$ which is wrong... the answer in the book is $E[\mathcal{X}]=\frac{1}{2}$ but I cannot understand why. Thanks in advance for any help!

If I  interpret this  problem correctly we  are counting  the expected
number of two-cycles in a random permutation. This gives the species

$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z})
+ \mathcal{V}\mathfrak{C}_{=2}(\mathcal{Z})
+ \mathfrak{C}_{=3}(\mathcal{Z})
+ \mathfrak{C}_{=4}(\mathcal{Z})
+ \cdots).$$

This gives the generating function
$$G(z, v) =
\exp\left(z + v\frac{z^2}{2} +
\frac{z^3}{3} +
\frac{z^4}{4} +
\frac{z^5}{5} + \cdots\right)$$
which is
$$G(z, v) =
\exp\left((v-1)\frac{z^2}{2} + \log\frac{1}{1-z}\right)
= \frac{1}{1-z}\exp\left((v-1)\frac{z^2}{2}\right).$$

As this is an EGF to get the OGF of the average number of replacements
we must differentiate with respect to $v$, computing
$$\left.\frac{\partial}{\partial v}
G(z, v)\right|_{v=1}.$$

This is
$$\left.\frac{1}{1-z}\exp\left((v-1)\frac{z^2}{2}\right)
\frac{z^2}{2}\right|_{v=1}
= \frac{1}{1-z} \frac{z^2}{2}.$$

This gives for the average number of replacements
$$[z^n] \frac{1}{1-z} \frac{z^2}{2}
= \frac{1}{2} [z^{n-2}] \frac{1}{1-z} = \frac{1}{2}$$
when $n\ge 2$ and zero when $n=1.$

Corollary. We see that the expected number of $m$-cycles is $1/m$ and hence the expected total number of cycles is $$\sum_{m=1}^n \frac{1}{m} = H_n\sim\log n.$$

The probability that $X_{i,j}=1$ is by symmetry exactly the same as the one that $X_{i,j}=0$. To see why, pick a permutation $\pi$ where $(i,j)$ is a replacement. Then $\pi\circ[i,j]$ is another permutation, where $(i,j)$ is not; you therefore have exactly the same number of permutations where $(i,j)$ is a replacement than of permutations where it is not, since
$$
\phi\colon \pi \mapsto \pi\circ[i,j]
$$
is a bijection. This implies $\mathbb{E} X_{i,j} = \mathbb{P}\{X_{i,j}=1\} = \mathbb{P}\{X_{i,j}=0\}.$

Now, the number of permutations $\pi$ where $\{i,j\} = \{\pi(i),\pi(j)\}$ is $2\cdot 5!$: indeed, this is leaving only $5$ elements out of $7$ (the remaining ones to permute) to choose, times the two choices (swapping $i$ and $j$ or not), leading to $2\cdot 5!$ permutations. In particular, such a permutation $\pi$ is picked with probability $\frac{2\cdot 5!}{7!} = \frac{1}{21}$.

Thus, $\mathbb{E} X_{i,j} = \frac{1}{2}\frac{1}{21}.$ But you have $\binom{7}{2}=2$ pairs $(i,j)$, so overall the sum is $$\mathbb{E} X  = 21\cdot \frac{1}{2}\cdot\frac{1}{21} = \frac{1}{2}.$$


prove that any two isomorphic structures are elementarily equivalent Imagine we have two L-structures $M$ and $N$.
For each L-sentence $\phi$ , $M$ models $\phi$ iff $N$ models $\phi$. We call $M$ and $N$ two elementary equivalent L-structures.

We say $M$ and $N$ are isomorphic if there exists a function from $U_M$ to $U_N$ which is 1 to 1 and onto and preserves symbols.  ( i mean an embedding which is also onto )

Now i want to prove that if two structures are isomorphic, then they are elementary equivalent.

Note : When we speak about L-formulas, we prove these kind of questions by induction on the complexity of the formulas. but in this case, we have sentences not formulas.

Choose an isomorphism $f$. Prove the more general statement: for any formula $\phi$, if we consider any assignment of values in $M$ to the variables, and the corresponding (via $f$) assignment in $N$, the formula $\phi$ will be satisfied by the one assignment if and only if it is satisfied by the other.

The structures (2Z, 0,+) and (Z,0,+) are isomorphic in the language of gropus but are not elementary equivalent. E.g. the closed formula "There exists v such that (v+v=2)" is not satisfied in the first but is satisfied in the second.


Prove that $\{1^n,2^n,3^n,\ldots,(p-1)^n\}$ is a reduced residue system modulo $p$ I'm currently looking at the following problem.

  Let $p$ be a prime number. If $n$ is a positive integer with
  $(n,p-1)=1$, prove that $$\{1^n,2^n,3^n,\ldots,(p-1)^n\}$$ is a
  reduced residue system modulo $p$.

So we need to show that none of the elements in the above set are congruent modulo $p$ and that they are all relatively prime to $p$, knowing that $(n,p-1)=1$.

Since $p$ is a prime, we know that a primitive root modulo $m$ exists. Then the integer $a$ is an $n$th power residue modulo $p$ if and only if $$a^{(p-1)/d} \equiv 1 \pmod p$$ where $d=(n,p-1)$. But we know that $(n,p-1)=1$, so that $a$ is an $n$th power residue if and only if $a^{p-1}\equiv 1 \pmod p$.

How can we use this information?

Hint: if $(n, p-1)=1$ then you can find $a, b$ such that $an+(p-1)b=1$. Then for any $x$ invertible mod $p$,

$$(x^n)^a = x^{an} = x^{an+(p-1)b} = x.$$

(I used that $x^{p-1}=1$.)

Therefore the map $x \mapsto x^n$ has a double sided inverse given by $y \mapsto y^a$...

How can two of your elements be congruent mod $p?$ How can one of them NOT be relatively prime to $p?$


An integer $k$ is a generator of group $\mathbb{Z_n}$ if and only if $\gcd(k, n)=1$ An integer $k$ is a generator of the group $\mathbb{Z_n}$ if and only if $\gcd(k, n)=1$.
So $\langle k\rangle=\mathbb{Z_n}$ iff $\gcd(k,n) = 1$.
Is there any general way to prove this?
I see that it's so obvious but can't find a general way to prove it.

By Bezout, the integer has an inverse $\bmod n$ precisely when $(n,k)=1$.
But, $1$ generates $\Bbb Z_n$.  So once you can get $1$ it's all over.

If $\gcd(n,k)=d > 1$, then $k/d$ is an integer, so
$$n . \frac{k}{d} = 0 \in \mathbb{Z}_n$$
so the order of $k$ is less than $n/d$, so it is striclty less than $n$, so $k$ does not generate $\mathbb{Z}_n$.
If $\gcd(n,k)=1$, then there exists $a,b$ such that $ak+bn=1$, so
$$ak=1 \in \mathbb{Z}_n$$
so the subgroup generated by $k$ contains $1$, which generates $\mathbb{Z}_n$, so it contains $\mathbb{Z}_n$, so it is $\mathbb{Z}_n$.


How many Hamiltonian cycles are there in a complete graph $K_n$ ($n\geq 3$) Why? It seems to me like the answer should be $n!$. Since you can first select the first vertex, then select each remaining vertex until you've got them all in a permutation.

My textbook, however, says that the answer is $(1/2)(n-1)!$

Unfortunately, it doesn't explain why this is. Why is it?

The answer really depends on how we think that two Hamiltonian cycles are equal. Take $K_3$ as example. Let's call its vertices $1$, $2$ and $3$. Then do we consider $1\to2\to3\to1$ same as $2\to3\to1\to 2$? If yes,  $1\to2\to3\to1$ is the same as $2\to3\to1\to 2$, which is the same as $3\to1\to2\to 3$ in $K_3$. Then we will have two Hamiltonian cycles $1\to 2\to3\to1$ and $1\to 3\to 2\to1$. Moreover, if we consider $1\to 2\to3\to1$ and $1\to 3\to 2\to1$ being the same because the second one is obtained by reversing direction the first one, then we have only one Hamiltonian cycle in $K_3$.

For general $K_n$, it's the same. $1\to2\to\cdots\to n\to1$ is the same as $2\to\cdots\to n\to1\to 2$ is the same as.... $n\to1\to 2\to\cdots \to n$. And the $1\to 2\to\cdots\to n\to1$ and $1\to n\to\cdots\to2\to1$ being the same because the second one is obtained by reversing direction the first one. So we have altogether $\frac{1}{2}(n-1)!$ Hamiltonian cycles in $K_n$.

Easiest way to see this is to draw all possible Hamiltonians as figures - fairly easy to do for K4 say. You will then notice that of the 8 drawn, some are actually duplicated.. there are only 3.

I guess if you did this for K5 etc you would get a pattern to which 1/2(n-1)! is the answer


Combinatorics problem with bit-strings When only three types of bit strings 0, 10,11 are available, how many valid $7$-bit strings can be represented? For example, the bit string 0101110, which is composed of 0, 10, 11, 10, is a valid bit string, but 1100101 is invalid.

Define $f(n)$ as the number of valid $n$-bit strings and define the empty string as valid.  So $f(0)=f(1)=1$.  We can create a valid string of length $n$ by taking a string of length $n-1$ and appending "$0$" or by taking a string of length $n-2$ and appending either "$10$" or "$11$".  So, we have $f(n)=f(n-1)+2f(n-2)$.  From here, we get

$$f(2)=f(1)+2f(0)=1+2=3$$
$$f(3)=f(2)+2f(1)=3+2=5$$
$$f(4)=f(3)+2f(2)=5+6=11$$
$$f(5)=f(4)+2f(3)=11+10=21$$
$$f(6)=f(5)+2f(4)=21+22=43$$
$$f(7)=f(6)+2f(5)=43+42=85$$

The numbers 11 and 10 have 2 digits(2 bits) and 0 has a single digit(1 bit).
The 7 bits can be formed in 4 cases:  1) three 2 bits and one 1 bit
                                      2) two 2 bits and three 1 bits
                                      3) one 2 bit and five 1 bits
                                      4) zero 2 bits and seven 1 bits.

Case 1:
_ _ _ 0   the first three blanks can be filled in 8 ways(2 ways for 1st blank{because it
                can be filled by 10 or 11}, 2 ways in 2nd and the same goes for the 3rd).

so by product rule 2*2*2=8 ways

Case 2:
_ _ 0 0 0  the first two blanks can be filled in 4 ways( 2 ways for 1st and in two for
                                                                                2nd).

so by product rule we have 2*2 = 4.

Case 3:
_ 0 0 0 0 0   the first blank can be filled in 2 ways(with 10 or 11).

so this equals 2.

Case 4:
0 0 0 0 0 0 0   this is applicable in only one way.

(i didn't have the need to choose the one bit because it is 0 for sure)

now to obtain the final answer add all the cases.

which equals 8 + 4 + 2 + 1 = 15.

therefore there 15 strings.

I am happy to receive any corrections if this is wrong :)


How can we better understand multiplicative inverse modulo something? How can we intuitively understand modulo multiplicative inverse?

Suppose we have an ring $\mathbb{Z}_{13}= \{0, 1, 2, 3, \ldots, 12\}$.

Each element except zero has corresponding multiplicative inverse.

Below is the mapping of inverse.

1 $\rightarrow$ 1

2 $\rightarrow$ 7

3 $\rightarrow$ 9

4 $\rightarrow$ 10

5 $\rightarrow$ 8

6 $\rightarrow$ 11

7 $\rightarrow$ 2

8 $\rightarrow$ 5

9 $\rightarrow$ 3

10 $\rightarrow$ 4

11 $\rightarrow$ 6

12 $\rightarrow$ 12

Now, I want to consider division by 2, which here means that multiplication by 7.
However, some integer multiplied 7 becomes acutally the same result as division by 2 over real number field.
For example, the following holds.

4 * 7 = 28 = 2 mod 13;
6 * 7 = 42 = 3 mod 13;
etc.

On the other hand, other values do not produce the same result over real number fields.

For example,
5 * 7 = 35 = 9 mod 13 (I want this value to be 2 or 3 since 5/2 = 2.5)

7 * 7 = 49 = 10 mod 13 (I want this value to be 3 or 4 since 7/2 = 3.5).

Why some values produce the same result as over the real number field, and the others do not??

Operations mod $n$ aren't guaranteed to preserve the order inherited from the reals.

So the fact that in $\mathbb{R}$, we have
$$2 < {\small{\frac{5}{2}}} < 3$$
doesn't imply
$$2 < ({\small{\frac{5}{2}}}\;\text{mod}\;13) < 3$$
However what is true is that, working mod $13$, we have
$$
{\small{\frac{5}{2}}} = 2+{\small{\frac{1}{2}}} = 2+7 = 9
\qquad\;\;\;
$$
and also
$${\small{\frac{5}{2}}} = 3-{\small{\frac{1}{2}}} = 3-7 = -4 = 9$$

What you seek is generally impossible. Suppose that $\,b\,$ is invertible $\!\bmod n,\,$ i.e. $\,\gcd(b,n)=1\,$ and let's calculate the fraction $\,a/b = ab^{-1}\pmod{\! n},\,$ where $\, 0 < a,b < n$.

By division $\,a = q\,b+r\ $ thus $\bmod n\!:\,\ a/b\equiv ab^{-1} \equiv (qb+r)b^{-1}\equiv q + \color{#c00}{rb^{-1}}$

When $\,r = 0\,$ we get $\!\bmod n\!:\ (qb)/b\equiv q,\,$ same as in $\Bbb R,\,$ when $\,a/b\in\Bbb Z\,$ is an exact quotient.

Else $\,\color{#0a0}{0<r<b}\,$ and you want $\,\color{#c00}{rb^{-1}}\equiv 0\,\ {\rm  or}\,\ 1\, \Longrightarrow\, \color{#0a0}{r\equiv  0\,\ {\rm or}\,\ b},\,$  contradiction.

Note $ $ It can be true for fractions with $\,a,b > n\,$ if they reduce to exact quotients $(r= 0),\,$ e.g.

$$\bmod 13\!:\ \ \dfrac{13}{27}\equiv \dfrac{0}1 = \left\lfloor \dfrac{13}{27}\right\rfloor,\ \ \dfrac{14}{27}\equiv \dfrac{1}1 = \left\lceil \dfrac{14}{27} \right\rceil\qquad\qquad\qquad $$


Linear algebra find a parallel to the same plane Find ''$a$'' for which all three vectors $(1,2,3)$,$(1,2+a,6)$ and $(1,10,a-1)$
are parallel to the same plane.

I am more or less sure about the process of doing this.
Iam thinking about doing dot the product of each vector and solve for $a$.

Any hints on this?

Since the tag is "linear algebra":  If the 3 vectors lie in the same plane, then they are linearly dependent.  So the $3\times 3$ matrix whose rows are the vectors needs to have determinant $0$.  If you set up the determinant, you can subtract the top row from the other two rows and the determinant is equal to $a^2-4a-24=0$ which has solutions $a=2\pm 2\sqrt{7}.$

Say the plane is $\;Ax+By+Cz+D=0\;$ . Any vector parallel to this plane must be perpendicular to the plane's normal, which is $\;(A,B,C)\;$ , so then it must be:

$$\begin{cases}&I&(1,2,3)(A,B,C)=0\implies &A+2B+3C=0\\{}\\
&II&(1,a+2,6)(A,B,C)=0\implies&A+(a+2)B+6C=0\\{}\\
&III&(1,10,a-1)(A,B,C)=0\implies&A+10B+(a-1)C=0\end{cases}$$

Observe that, for example:

$$\begin{cases}
&II-I :\;\;&aB+3C=0\\{}\\
&III-II:\;\;&(a+8)B+(a-7)C=0\end{cases}$$

Solving this linear system, you get:

$$(II-I)\;\;C=-\frac a3B\stackrel{III-II}\implies (a+8)B+(a-7)\left(-\frac a3B\right)=0\stackrel{\text{assume}\; B\neq0}\implies$$

$$a+8-\frac{a^2}3+\frac73a=0\implies a^2-10a-24=0\iff(a-12)(a+2)=0$$

Take it from here (what if $\;B=0\;$ , say?)


Exponent of a direct product of groups Prove that if the group $G=\prod_{i=1}^nH_i$, where each $H_i$ is a finite group, then the exponent of $G$ which is

$\exp(G)=\min\{n \in \mathbb{N}:g^n=e, \forall g \in G\}$ is equal with $\operatorname{lcm}(\exp(H_1),\ldots,\exp(H_n))=M$

I proved that $\exp(G) \leqslant M$

Can someone help me with the other direction ?

Thank you in advance!

Since this problem is a little subtler than I (and others) assumed at first glance, let me provide a detailed answer as penance.

Suppose that $p$ is a prime and $p^a$ is the largest power of $p$ dividing $M$.  I claim there is an element of $G$ with (positive) exponent divisible by $p^a$.  From this it follows that $p^a$ divides the exponent of $G$.  Applying this to all primes $p$ dividing $M$, we see that $M$ must divide the exponent of $G$; in particular, the exponent of $G$ is at least $M$.

Since $p^a$ divides $M$ and $M$ is the lcm of some numbers, $p^a$ divides one of these numbers, say the exponent of $H_i$.  Then there is some element $h \in H_i$ whose exponent is divisible by $p^a$.  It follows that $(1, \ldots, 1, h, 1, \ldots, 1) \in G$ has exponent divisible by $p^a$, so $G$ itself has exponent divisible by $p^a$.

You show the other direction by identifying an element of the product which has order M.  Hint: Find a tuple that maximizes each coordinate.


How much bigger is 3↑↑↑↑3 compared to 3↑↑↑3? 3↑↑↑3 is already mind-bogglingly large, but how much larger is 3↑↑↑↑3? Is it so large that it is simply around 3↑↑↑↑3 times larger than 3↑↑↑3? Or is there another way to express its magnitude in terms of 3↑↑↑3?

By definition, $3\uparrow\uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow(3\uparrow\uparrow\uparrow 3))$.
\begin{matrix}
   3\uparrow\uparrow\uparrow 3= & \underbrace{3^{3^{3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}}}} \\
   & \mbox{7,625,597,484,987 copies of 3}
  \end{matrix}

which should make it a little clearer how much bigger $3\uparrow\uparrow\uparrow\uparrow 3$ is than $3\uparrow\uparrow\uparrow 3$. It's hard to even give a more concrete answer because the numbers of powers of $3$ get unreasonably large to compute or type.

3^^^3 is equal to 3^^3^^3 which is equal to 3^^(3^3^3)
3^^(3^3^3)= 3^^(3^27)= 3^^(7.6 trillion)= 3^3^3^3... 7.6 trillion times.
Let's represent this mind boggling number as x.

3^^^^3 is equal to 3^^^3^^^3 which is equal to 3^^^(x)
which is equal to 3^^3^^3^^3...(with x ^^3's)
Two threes: 3^^3 is around 7.6 trillion
Three threes: 3^^3^^3= x
Four threes: 3^^3^^3^^3= 3^3^3...(with x ^3's)
At five threes I can't even list out the exponentiation.

You get how if there were, say, a googleplex threes all tetrated, it would be completely absurd.

But we know that x is far far far (and I can not stress this enough) far far larger than a googleplex, or even a number with a googleplex digits.

In conclusion:
3^^^^3= 3^^^3^^^3
=3^^3^^3^^3...(with x 3's)
And because at even just 3^^3^^3^^3^^3 I can't list out the exponentiation, it is impossible to do so with x 3's.

So yes, 3^^^^3 is so large it is simply around just 3^^^^3 times larger than 3^^^3.

(although it really is just 3^^^3^^^3.)


Showing Linear Independence of $\, \{e^x, \, e^{-x}\} $ We examine the equation

$$ae^x + be^{-x} = 0$$

My book say manipulate to get

$$ae^{2x} = -b$$

and "The two members are identical for all $x$ only if

$$a =b = 0 \, \text{ "}$$

[Therefore the set in the title is L.I.]

My confusion is that I can easily choose $a = 2, b = -3$ and find an $x$ where the equation is satisfied. I can repeat this process for every $x \in \mathbb{R}$.

The definition my book uses for L.I. is

  A set of functions  \begin{equation}  \{y_1, y_2, \dots, y_n\}
 \end{equation} defined on $(a,b)$ is linearly independent if the
   linear combination for the set  \begin{equation} c_1y_1+c_2y_2 +
 \cdots + c_ny_n = 0 \end{equation} implies that for all $x$ the only solution is
   \begin{equation} c_1= c_2=\cdots =c_n = 0 \end{equation}

I'm guessing that means the $c_i$ must be fixed, and that's where I'm wrong. I don't see anything in the definition saying that $c_i$ must be fixed, nor anywhere I look; is it implied? The nature of the definition hints that there might be more than one solution depending on the function set (making the set L.D.), which to me means that the set of constants does not have to be fixed.

The $c_i$ do have to be fixed: since we're talking about linear independence of the set of functions, we're looking for a linear combination of functions that add to the zero function, i.e., the function which returns zero for all $x$. This function is fixed by fixed constants $c_i$. I agree that the definition you posted is a bit unclear on this point.

Take natural logarithm from both sides of equality $ae^x=-be^{-x}$, then you can see that $x$ should be $\frac{ln(a)+ln(-b)}{2}$.


What is the digit sum of $C(n)$? The number $C(n)$ , where $n$ is a positive integer is defined as follows : Write the numbers $j$ from $1$ to $n$ $j$ times. The resulting number is $C(n)$. The letter $C$ comes from the name I invented for these numbers : "Crazy Numbers"

Two examples ($C(8)$ and $C(10)$) including the PARI-routine calculating $C(n)$ :

? s=0;n=8;for(j=1,n,for(k=1,j,s=s*10^length(digits(j))+j));print(s)
122333444455555666666777777788888888
? s=0;n=10;for(j=1,n,for(k=1,j,s=s*10^length(digits(j))+j));print(s)
12233344445555566666677777778888888899999999910101010101010101010
?

Here :

How many digits does $C(n)$ have?

I asked for the number of digits of $C(n)$ (for the definition of $C(n)$, see the link in the linked question), which I finally found out. Another user asked for the digit sum of $C(n)$, and I only can say, if we denote $d(n)$ to be the digit sum of $n$, the digit sum of $C(n)$ is given by $$\sum_{j=1}^n j\cdot d(j)$$

If there would be a formula for $$\sum_{j=1}^n d(j)$$ we could derive the desired digit sum from that.

  Does anyone know a concrete formula for $$\sum_{j=1}^n d(j)$$ where $d(n)$ is the digit sum of $n$ ?

Consider the digit sum of $C(8) = 122333444455555666666777777788888888$.

We add one copy of $1$ to two copies of $2$ to three copies of $3$ and so on. . . .

In other words $1 + 2^2 + 3^2 + 4^2 + \ldots + 8^2 = \displaystyle \sum_{m=1}^8 m^2$.

In general $C(n)$ has digit sum $\displaystyle \sum_{m=1}^n m^2$.

And there's a formula for that.

The digit sum of $C(n)$ is equal to $\displaystyle \frac{n(n+1)(2n+1)}{6}$


I want to Find $3^{2x} + 7^{\frac{1}{x}}$ when $7^{x+1} = 21^{x}$ I figured that
\begin{align*}7^{x+1} &= 21^{x}\\
7^{x+1} &= 3^{x} \times 7^{x} \\
7 &= 3^{x}
\end{align*}
 but I can't go further at the moment.

Square both sides to reveal that

$$3^{2x}=49$$

$x$ root both sides to reveal that

$$7^{1/x}=3$$

Thus,

$$3^{2x}+7^{1/x}=52$$


If $y =\sin \log (x^2+2x+1)$ then $(x+1)^2 y^{(n+2)}+(2n+1)(x+1)y^{(n+1)}+(x^2+4)y^{(n)}=0$ How to prove this?

  If $y =\sin \log (x^2+2x+1)$, and $y'=y^{(1)}$, $y''=y^{(2)}$, and so on, prove that $(x+1)^2 y^{(n+2)}+(2n+1)(x+1)y^{(n+1)}+(x^2+4)y^{(n)}=0 $

Finding $y'$ is simple, but $y''$ and other higher terms seems difficult. Any short solution for this approach?

$y=\sin 2\log(x+1)
=2\sin\log(x+1)\cos\log(x+1)$.

Apply Leibnitz's formula for the n-th derivative of a product and look term-by-term.


Differential equation for harmonic functions. Show that a harmonic function satisfies the formal differential equation: $$\frac{\partial^2u}{\partial z \partial \overline{z}}=0$$

Question

How is $\frac{\partial u}{\partial z}$ even defined when $u$ isn't constant. It is clear that for any non-constant complex variabled, real valued, analytic function $u$ we have that $\frac{\partial u}{\partial z}$ is not defined. This comes from Cauchy-Riemann equations. So how does this question make sense?

Using the notation that Robert Israel mentioned you can restate the equation as

$$\dfrac{\partial^2u}{\partial z \partial \bar{z}}=\frac{1}{4}\left[\frac{\partial}{\partial x}-i\dfrac{\partial}{\partial y} \right]\left[\frac{\partial u}{\partial x}+i\dfrac{\partial u}{\partial y} \right]=\frac{1}{4}\left[\dfrac{\partial^2u}{\partial x^2}-i\dfrac{\partial^2u}{\partial y\partial x}+i\dfrac{\partial^2u}{\partial x\partial y}+\dfrac{\partial^2u}{\partial y^2}\right].$$

Can you complete it from here?


Generalisation of Euler's Theorem I have no idea how to start thinking about this. Any hints are welcome:

Prove that

$a^{m} \equiv  a^{m-\phi{(m)}} (mod\ m)$ for any integer m

I only know how to do it for $\gcd(a,m)=1$.

First method : elementary number theory.

By the factorization theorem let $m=p^kq^l$ and $a$ an integer not divided by $p^k q^l$ ($p,q$ two distinct prime numbers and $k,l$ integers $\ge 1$). We can also generalize to $m=p_1^{b_1}...p_n^{b_n}$ but it will be the same method but longer.

The first thing is to prove that  $\gcd(p,q)=1 \Rightarrow \gcd(p^k,q^l)=1$ ? All the powers
 of $p$ and $q$ are divided respectively by $p$ and $q$ which are
 difference, is that enough ? Probably (here).
 But here's a more formal proof with a weaker hypothesis ($p,q$ not
 necessarily prime numbers). Supposing $\gcd(p,q)=1$, so there exists $u,v\in
\mathbb{Z}$ such that $up+vq=1$. Multiplying by itself it gives :
 $1=u^2p^2+2uvpq+v^2q^2=(u^2p+2uvq)p+v^2q^2=1\Rightarrow
 \gcd(p,q^2)=1$. Again, traducing the new hypothesis by Bachet-Bézout
 theorem and by multiplying by $(up+vq=1)$ it gives that
 $\gcd(p,q^3)=1$. We repeat this $l-2$ times and it gives
 $\gcd(p,q^l)=1$.

It implies that there exists $u,v\in\mathbb{Z}$ such that $up+vq^l=1$.
 Multiplying by itself it gives $\gcd(p^2,q^l)=1$. This time we repeat
 the operation $k-1$ times and it gives $\gcd(p^k,q^l)=1$.

We can start the second step :

First thing is to prove with an induction on $k\ge 1$ that $a^{p^{k-1}(p-1)}\equiv 1 \pmod {p^k} $.

Initialisation : for $k=1$ we found Fermat little theorem so it's true.

Heredity : for $k=k+1$ we want to prove that : $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.

$a^{p^{k}(p-1)}= a^{p^{k-1}p(p-1)}=(a^{p^{k-1}(p-1)})^p=(up^{k}+1)^p=\sum \limits_{l=0}^{p}\binom{p}{l}(up^k)^l=1+up^{k+1}+"..."$, where $"..."$ is divided by $p^{k+1}$. So $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.

We deduce the same thing for all $l\ge 1$.

Then we have : $K=a^{p^{k-1}(p-1)q^{l-1}(q-1)}= (a^{p^{k-1}(p-1)})^{q^{l-1}(q-1)}\equiv 1 \pmod{p^k}$ and also  $K=a^{q^{l-1}(q-1)p^{k-1}(p-1)}=(a^{q^{l-1}(q-1)})^{p^{k-1}(p-1)}\equiv 1 \pmod{q^l}$

So now, we can say that there exists $\nu$ and $\mu$ $\in \mathbb{Z}$ such that : $K=\nu p^k +1=\mu q^l +1$

Then $\nu p^k=\mu q^l$. With the fact that $\gcd(p^k,q^l)=1$ we have by Gauss lemma $p^l$ which divides $\mu$. So there exists $\epsilon \in \mathbb{Z}$ such that $\mu=\epsilon p^k$ and finally $K=\epsilon p^kq^l+1$.
Then $a^{p^{k-1}(p-1)q^{l-1}(q-1)}\equiv 1\ \pmod{p^kq^l=m}$.

The last step consists in proving that $\phi(m)=\phi(p^kq^l)=p^{k-1}(p-1)q^{l-1}(q-1)$. To do this you consider for instance the group of units of $(\mathbb{Z}/p^k\mathbb{Z})^{\times}$ i.e the number of inverse elements in this groups (i.e the set of $x$ such that $\gcd(x,p^k)=1$). We list the elements of the group $(\mathbb{Z}/p^k\mathbb{Z})=\{0,1,...,p,...,2p,...,pp=p^2,...,p^{k}-1\}$. Now, between $0$ and $p$ we have $(p-1)$ coprime numbers with $p$ and we deduce that for each list of length $p$ we have $(p-1)$ coprime numbers with $p$ and we have $p^{k-1}$ lists. So the formula is right. It is the same for $q^l$.

Finally $a^{\phi(m)}\equiv 1 \pmod{m}$.

Second method : group theory.

We still consider $m=p^kq^l$ (by factorization theorem). Then by the form of the CRT with the ring isomorphism we have an isomorphism between $(\mathbb{Z}/m\mathbb{Z})$ and $(\mathbb{Z}/p^k\mathbb{Z})\times(\mathbb{Z}/q^l\mathbb{Z})$. Which means that for the group of units : $\vert(\mathbb{Z}/p^k\mathbb{Z})^{\times}\vert\times\vert(\mathbb{Z}/q^l\mathbb{Z})^{\times}\vert =\vert (\mathbb{Z}/m\mathbb{Z})^{\times}\vert=\phi(m)=p^{k-1}(p-1)q^{l-1}(q-1)$ (as previously).

Let $a\in (\mathbb{Z}/m\mathbb{Z})^{\times}$ a generator (the group is cyclic in our case), the order of $a$ divides $\phi(m)$. Let $y$ the order of $a$ so there exists $z\in \mathbb{Z}$ such that $yz=\phi(m)$. We have $a^y\equiv 1 \pmod m\Rightarrow (a^y)^z=a^{\phi(m)}\equiv 1 \pmod m$. It works because $\gcd(p^k,q^l)=1$ !


Multiples and decimal expansion... If $d \in \{1;\cdots;9\}$ and $x \in \mathbb{N^*}$, $N_d(x)$ denotes the number of digits equal to $d$ in the decimal expansion of $x$.

If $n$ and $m$ are in $\mathbb{N^*}$, is there $a$ in $\mathbb{N}^*$ such that : $\forall d \in \{1;\cdots;9\}$ , $N_d(an)=N_d(am)$ ?

Not completely rigorous, but let $m$ be the concatenation of to copies of $n$.  Then (ignoring carries at the joint) there will be twice as many of each digit in $am$ as there are in $an$

Generally no. For example $N_0(a \times 1) < N_0(a \times 1000)$ for  $a \in \mathbb N^* $.
But this is not counterexample.


Condition for zeros of a polynomial in Unit Disk Consider a polynomial in $\mathbb{C}$ with complex coefficients, $\lambda^2+p\lambda+q$ where both $p$ and $q$ are complex numbers.

I am looking a for a condition of $p$ and $q$ such that the zeros of this polynomial would lie in the unit open disk. In other words the modulus of the zeros is strictly less than $1$.

If $p\in\mathbb{R}$ then the roots of $z^2+p z+q$ lie in the open unit disc if and only if $$ |p| < \frac{1-|q|^2}{|1-q|}.$$

Note that for $q\in\mathbb{R}$ this criterion becomes $|q|<1$ and $|p|<1+q$.  If $p=|p|\omega$ for some $\omega$ on the unit circle then the criterion for real $p$ can be extended to
$$|p| < \frac{1-|q|^2}{|\omega^2-q|}$$
which is valid also for complex $p$.

The denominator is bounded above by $1+|q|$.  In other words $|p|+|q|<1$ will always imply that the roots will lie in the open unit disc.  This latter bound also guarantees that $z^2$ and $z^2+pz+q$ have the same number of roots in the open unit disc by Rouche's theorem.

I found the answer in the fantastic article written by Rahaman et.al. On the Eneström-Kakeya theorem. Tohoku Mathematical Journal, $Vol. 20 (2)$, $(1968)$, $126-136$.

Thanks to Q. I. Rahaman.


Finding values of a, b, c of a matrix Find for which values of $a, b, c$ the following matrix is orthogonal

$$A=
  \left( {\begin{array}{ccc}
   \sqrt{\frac{1}{2}} & a & \frac{1}{2} \\
    \sqrt{\frac{1}{2}} & b & \frac{1}{2} \\
    0 & c & \sqrt{\frac{1}{2}}  \\
  \end{array} } \right)$$

I was thinking of doing this: Need to find $u_1 \cdot u_2 = u_1 \cdot u_3 = u_2 \cdot u_3=0$ and that $u_4 \cdot u_4= 1$ which should form the orthogonal basis vectors but then I got stuck when I found $u_1 \cdot u_3 \neq 0$. Am I right or this is not the way to do this? Please help.

hint: $A$ is orthogonal iff $A\cdot A^{T} = I$. You can work out the equations.


For what values of a intersects $y = ax$, $y = \sin x$ just one time? As the title says, for what values of a intersects $y = ax$, $y = \sin x$ just one time?

I am not able to solve this problem, and I really want to know the answer.

Sketch $y = \sin x$ and imagine a vertical line through the origin, which initially has only one intersection point at the origin. Notice that we can rotate it clockwise until it is tangent to $y = \sin x$ at some point $x = k_1$, where $k_1 \in (-\pi/2, \pi/2)$. Likewise, notice that we can rotate it counterclockwise until it is tangent to $y = \sin x$ at some point $x = k_2$, where $k_2 \in (-2\pi, -\pi)$.

To solve for $k_1$ and $k_2$, we need to know when the tangent line of $y = \sin x$ at $x = k$ has a slope that is equal to the slope of the line passing through the points $(k, \sin k)$ and $(0, 0)$. That is, we must solve:
$$
\cos k = \frac{\sin k - 0}{k - 0} \iff \tan k = k
$$
Solving this equation with Wolfram|Alpha, we see that $k_1 = 0$ and $k_2 = 4.4934\ldots$. Taking their slopes, we have $\cos k_1 = 1$ and $\cos k_2 = -0.2172\ldots$ so that:
$$
a \in (-\infty, -0.2172) \cup (1, \infty)
$$

One intercept is at $x=0$.
Next, $ax=\sin x$, taking derivative of both sides wrt $x$, we get $a=cos x$.
Then, $x=\cos^{-1} a$ is another intercept. So $x=0$ will be the only intercept if $\cos^{-1}a$ does not exist, or $\cos^{-1}a=  0$, which will be the case if $a>=1$ or $a<-1$.


Decreasing sequence of non-negative integers Let $ a_n , \ n=0, 1, 2, \dots\ $ be a strictly monotonically decreasing sequence consisting of non-negative integers. The sequence also has a lower bound C such that $ a_n \ge C >-\infty.$
Intuitively, we know, that $a_n$ has to have finite amount of entries, but can this be proven exactly?

Well, this seems kind of obvious, but let's do it anyway. We know three things:
1: The sequence is strictly decreasing, i.e, $a_{n+1}<a_n.$
2: $a_n \in \mathbb{Z} ~~\forall n.$
3: $a_n\geq 0 ~\forall n$.
Condition (1) implies that all of the terms of $a_n$ are distinct, i.e, $\nexists m,n\in\mathbb{N}:a_m=a_n$. Now using condition (2), let $a_0=N$, some positive integer. We know, using condition (1), that all subsequent terms are $<N$, and using condition (3), are all $\geq0.$  Now suppose $a_n$ had infinitely many terms. That would imply that there are infinitely many integers in the range $[0,N]$, which is clearly false. Thus $a_n$ can only have finitely many terms.

Can we ever have this kind of sequence ? As it is strictly monotonically decreasing so we have $a_1 \geq a_n \geq 0$ for all $  n\geq 2 $  but there are only finitely many non negative integers satisfying this .so the sequence is eventually constant which contradicts the fact it is  strictly monotonically decreasing.


What proportion of the natural numbers satisfies the following inequality? Solving this problem might be too ambitious, but I will ask it here nonetheless, because I do not know of an answer currently.

Let $\sigma(x)$ denote the sum of the divisors of $x \in \mathbb{N}$, and let $\gcd(y,z)$ denote the greatest common divisor of the positive integers $y$ and $z$.

Here is my question:

  What proportion of the natural numbers satisfies $\gcd(n, \sigma(n)) > c\sqrt{n}$, where $c$ is a constant that does not depend on $n$?

MY ATTEMPT

I was able to get hold of Pollack's paper titled On the Greatest Common Divisor of a Number and Its Sum of Divisors, and while it does seem that my exact question is covered there, I am unable to parse my way through and thereby get an answer for my question here.

Let us calculate it for some values of $n$
$n=2,sum=3$
$n=3,sum=4$
$n=4,sum=7$
$n=5,sum=6$
Now there GCD is 1 thus we can be sure that no $n$ satisfies the relation.


Techniques for removing removable singularities (without resorting to series expansion)? Suppose $f: \mathbb{C} \supset U \to \mathbb{C}$ is a meromorphic function with a removable singularity at the point $z_0 \in U$.  Then $f$ can be extended to a holomorphic function over all of $U$.  However, the material I've encountered does not provide much in the way of practical techniques for explicitly computing the holomorphic extension.

The only technique I've encountered thus far is to simply write out the power series.  For instance, suppose we start with the function

$$ f(z) = \frac{e^z-1}{z}, $$

which has a removable singularity at $z=0$.  The corresponding power series is

$$ \frac{1}{z}\left( -1 + \sum_{n=0}^\infty \frac{z^n}{n!} \right) = \sum_{n=1}^\infty \frac{z^{n-1}}{n!}.$$

This series is certainly convergent (it is termwise smaller than the series for $e^z$), and is well-defined at $z=0$.  However, it leaves something to be desired: we started out with a nice, finite algebraic expression, and ended up with a nasty infinite sum.

One reason I call this sum "nasty" is that it does not lend itself well to numerical evaluation at an arbitrary point $z$.  Away from the origin, the original function $f(z)$ can be evaluated using a small number of standard numerical routines (exponentiation, division, etc.).  In contrast, to evaluate the sum to within machine precision, we likely have to evaluate a large number of terms (how many?), and we also have to be careful about things like catastrophic cancellation while accumulating the sum, especially near the origin.  What a mess!

  Question: Are there other techniques for explicitly constructing the holomorphic extension of a removable singularity, that do not
  result in series expansions?

(Note that in general I am interested in functions that are considerably more complicated than the example given above.)

The extension across the removable singularity simply coincides with the original function outside the singularitites (that's the very point!). At the removable singularity, the value of the extended function is just $\lim_{z\to a} f(z)$. In your particular case, we have that
$$
\lim_{z\to 0} \frac{e^z-1}{z} = 1,
$$
so the extended function is
$$
f(z) = \begin{cases} \frac{e^z-1}{z}, & z \neq 0 \\ 1, & z = 0 \end{cases}.
$$


How to apply Implicit function theorem in multivariable calculus? I probably know that I have to use implicit function theorem in this problem but don't know how.  The following is the problem:

  The system of equations
  $3x+y-z+u^2 = 0$,
  $x-y+2z+u=0$,
  $2x+2y-3z+2u=0$
  can be solved for $x, y,u$ in terms of $z$. Prove this.

Consider $$f(x,y,u,z) = \begin{bmatrix}
3x + y - z + u^2 \\
x - y + 2z + u\\
2x + 2y - 3z + 2u
\end{bmatrix}$$

The Jacobian is $$\left | \frac{\partial f}{\partial (x,y,u)} \right | = 2(4u-6).$$

So this is locally solvable in terms of $z$ as long as $u \neq 3/2.$

Start by adding the second and third equations, subtracting the sum from the first equation.  This yields $u^2$ - $u$ = 0, so $u$ = 0 or $u$ = 1 (or if you prefer, $u(z)$ = 0 or $u(z)$ = 1).  For each value of $u$, substitute back into the equations and solve the resulting linear system.  If you find one of these to be inconsistent, that lets you choose which $u$.


How to see if $\sum_{n=1}^\infty\frac{\sqrt{n+1}-\sqrt{n}}{n}$ converges I want to see if $$\sum_{n=1}^\infty\frac{\sqrt{n+1}-\sqrt{n}}{n}$$
converges or not.

I start with $$α_{n}=\frac{\sqrt{n+1}-\sqrt{n}}{n}=$$
$$\frac{(\sqrt{n+1}-\sqrt{n})(\sqrt{n+1}+\sqrt{n})}{n(\sqrt{n+1}+\sqrt{n})}=$$
$$\frac{n+1-n}{n(\sqrt{n+1}+\sqrt{n})}=$$
$$\frac{1}{n(\sqrt{n+1}+\sqrt{n})}.$$

And here I am stuck. How can I tell if $α_{n}$ converges or not?

In my textbook, it says that the last equation is $\leq\frac{1}{2n^{\frac{3}{2}}} $

But I cannot understand how or why it gets to that result.

We have

$$\frac{1}{n(\sqrt{n+1}+\sqrt{n})}\le \frac{1}{n(\sqrt{n}+\sqrt{n})}=\frac1{2n^{3/2}}$$
so apparently there is a typo in your textbook.

Because $\sqrt{n+1}>\sqrt n$ in the range of $n$, $\sqrt{n+1}+\sqrt n > 2\sqrt n$
and therefore the ratio is $\le \frac{1}{2n^{3/2}} = \zeta(3/2)/2$, where the
Riemann zeta function has a pole at 1 but is converging for larger values.


What is the use of moments in statistics? Can anyone give me a simple explanation (i.e. without too many equations) of what is the use of moments in statistics? Why do we need moments? What can we learn from them?

The central question in statistics is that given a set of data, we would like to recover the random process that produced the data (that is, the probability law of the population).  This question is extremely difficult in general and in the absence of strong assumptions on the underlying random process you really can't get very far (those who work in nonparametric statistics may disagree with me on this).  A natural way to approach this problem would be to look for simple objects that do identify the population distribution if we do make some reasonable assumptions.

The question then becomes what type of objects should we search for.  The best arguments I know about why we should look at the Laplace (or Fourier; I'll show you what this is in a second if you don't know) transform of the probability measure are a bit complicated, but naively we can draw a good heuristic from elementary calculus: given all the derivatives of an analytic function evaluated at zero we know everything there is to know about the function through its Taylor series.

Suppose for a moment that the function $f(t) = E[e^{tX}]$ exists and is well behaved in a neighborhood of zero.  It is a theorem that this function (when it exists and behaves nicely) uniquely identifies the probability law of the random variable $X$.  If we do a Taylor expansion of what is inside the expectation, this becomes a power series in the moments of $X$: $f(t) = \sum_{k=0}^\infty \frac{1}{k!} t^k E[X^k]$ and so to completely identify the law of $X$ we just need to know the population moments.  In effect we reduce the question above "identify the population law of $X$" to the question "identify the population moments of $X$".

It turns out that (from other statistics) population moments are extremely well estimated by sample moments when they exist, and you can even get a good feel on how far off from the true moments it is possible to be under some often realistic assumptions.  Of course, we can never get infinitely many moments with any degree of accuracy from a sample, so now we would really want to do another round of approximations, but that is the general idea.  For "nice" random variables, moments are sufficient to estimate the sample law.

I should mention that what I have said above is all heuristic and doesn't work in most interesting modern examples.  In truth, I think the right answer to your question is that we don't need moments because for many relevant applications (particularly in economics) it seems unlikely that all moments even exist.  The thing is that when you get rid of moment assumptions you lose an enormous amount of information and power: without at least two, the Central Limit Theorem fails and with it go most of the elementary statistical tests.  If you do not want to work with moments, there is a whole theory of nonparametric statistics that make no assumptions at all on the random process.

The normal distribution is determined by the first two moments.  Other families of distribution can be determined by their moments.  One method for estimating parameters is to equate moments (called the method of moments).


Is there a rule for integrating $f(x) f(f(x))$? I am looking through rules/tricks for integration, and there are a lot... but I can't seem to find one specifically applicable to the general form
$$\int_a^b f(x)\,f(f(x)) \,\mathrm dx$$

Is there a nice rule or trick that would generally apply in this situation?

No, but there is a rule for integrating $f'(x)\,f'(f(x))$.

I suggest integration by parts where $u=f(x)$ and $dv=f(f(x))dx$

$du=f'(x)dx$ and $v=\int f(f(x))dx$ , this integral we may evaluate as $v=\int f(x)dx \int f(x)dx$


Can I move a constant function out of an integral? I have the following integral:
$$\int\exp(2\pi i \Omega t)\beta(\omega_0)d\Omega$$
while $\Omega$ is defined as
$$\Omega = \omega - \omega_0$$.
$\omega_0$ is handled as a constant value, while $\omega$ is a variable. Now I am not sure if I can move $\beta(\omega_0)$ out of the integral.

Reason for moving it out: It is a const. value, and never changes.
Reason for doubt: $\omega_0$ is also used in the integration variable $\Omega$.

Is there a reason not to move $\beta$ out?

Use
$d\Omega=d\omega$ and write the integral explicitly as

$$
I(\omega_0)=\int d\omega e^{-2\pi i\omega_0 t} e^{2\pi i\omega t}\beta(\omega_0)
$$

now it should be obvious which factors can be pulled out of the integral.

If $ \beta ( \omega_0 )$ is a function of constant $\omega_0$ alone, it can be pulled out of the integral sign.  $ d \omega = d \Omega $ ,  $\omega ,\Omega $ are variables.


Compound interest formula and continuously compounded interest formula derivation My textbook gives the formula for compound interest as:

$A\left( t\right) =P\left( 1+\dfrac {r}{n}\right) ^{nt}$

Where:
P = The principal, r=the annual rate of interest, n= the frequency of compounding, t=Time in years and A is the total interest accrued over time.

It then goes onto show how if we compound £1 continuously at a rate of 100% for 1 year, for greater and greater values of $n$ we get:

$\left( 1+\dfrac {1}{n}\right) ^{n}\rightarrow e$

And then uses this to derive the formula for continuously compounded interest:

$A\left( t\right) =Pe^{rt}$

The book says it uses "a little calculus and the definition of e" to derive this, but how exactly does it do this?

Let's see. The limit claim is pretty widely discussed on MSE, so I'm assuming you're willing to believe that the limit does approach $e$. Once you have that, you can look at the formula
$$
A_n(t) = P \left(1+ \frac{r}{n}\right)^{nt}
$$
and do a little fiddling. Let $m = \dfrac{n}{r}$, so that $n = rm$. Then rewrite:
$$
A_n(t) = P \left(1+ \frac{r}{n}\right)^{nt} = P \left(1 + \frac{1}{m}\right)^{mrt}= P \left(\left(1 + \frac{1}{m}\right)^m \right)^{rt}
$$

Now as $n \to \infty$, the thing inside the large parentheses approaches $e$, so you get

$$
A(t) = Pe^{rt}.
$$

As for the main limit, the usual approach is to say you want to find
$$
L = \lim_{n \to \infty} \left(1 + \frac{1}{n} \right)^n
$$
but instead, you compute
\begin{align}
\ln L
&= \lim_{n \to \infty} \ln \left(1 + \frac{1}{n} \right)^n \\
&= \lim_{n \to \infty}  n \ln \left(1 + \frac{1}{n} \right) \\
&= \lim_{n \to \infty}  \frac{\ln \left(1 + \frac{1}{n} \right)}{1/n},
\end{align}
which you can evaluate with L'hopital's rule (take derivative of top and bottom, since both
go towards 0):
\begin{align}
\ln L
&= \lim_{n \to \infty}  \frac{\ln \left(1 + \frac{1}{n} \right)}{1/n} \\
&= \lim_{n \to \infty}  \frac{\frac{1}{1 + \frac{1}{n}}\left(\frac{-1}{n^2}\right)} {\frac{-1}{n^2}}\\
&= \lim_{n \to \infty}  \frac{1}{1 + \frac{1}{n}}\\
&= 1.
\end{align}
Since the natural log of your limit is $1$, the limit itself must be $e$.$$$$$$

There is an easier way to derive (without Calculus), using $(1 + \frac 1 m)^m = {\rm e }$.

If $A = P (1 + \frac r n)^{nt}$, then $A = P \left( 1 + \frac 1 {\frac n r} \right)^{nt}$ (we basically just took the reciprocal of $\frac r n$ and put a $1$ on top again to make it equivalent.)

Now set $\frac n r = m$ and substitute: $A = P (1 + \frac 1 m)^{nt}$. It seems pretty close now, doesn't it!

Let's reform the $\frac n r = m$ statement, shall we? We can change that into $n = mr$; substitute that back into the $nt$ exponent part for $n$, and you will get $A = P (1 + \frac 1 m)^{mrt}$ (hey, that looks kind of familiar, doesn't it!).

Substitute back in from the beginning formula $(1 + \frac 1 m)^m = {\rm e}$ and you get $A = P({\rm e})^{rt}$.


Computing $\sum_{i=1}^k{i\cdot c^i}$ I would like to compute the following sum :
  $$\sum_{i=1}^k{i\cdot c^i}$$
  where $k$ and $c$ are any real numbers.

I know how to compute $i$ and $c^i$ separately but I don't know how to do it when they are multiplied together.

Thanks a lot for the help!

Hint:

Do some analysis:
$$\sum_{i=1}^k ic^i=c\sum_{i=1}^kic^{i-1}=c\Bigl(\sum_{i=0}^k c^i\Bigr)'. $$

Hint: Let $a,q$ be real numbers with $q\ne 1$:
$$a + aq + aq^2 + \ldots +aq^{n-1} = a\frac{q^n-1}{q-1}.$$


What is the usage of Permuation and Combination in the real life or Computer Programming world? I have never understood the application of P & C, even in the software programming. I know, the principle behind P&C is counting. So, basically it makes the counting quicker. However, I could never apply it while programming,real life, etc? The only application I could find was very trivial - how many 2 digit binary numbers are possible? The answer is 00, 01, 10, 11. Since the numbers can repeat here - the answer is 2*2, which is 4. Apart from this, I couldn't find its application? Can someone please help me on it? This way, I can appreciate this topic in mathematics.

As per the people comments - this question is quite vague. Thus, I am rewording it to - suffice it's need in programming world like - Embedded, Graphics, Business, etc

At least in my experience, the usual reason for wanting to count something is to compute a probability. If, for example, you are playing a card game  (I'm thinking of the standard 52 card deck here) in which the cards are shuffled, and you want to know the probability of some event, then you need to know the total number of possible orderings of the cards, which is a (fairly straightforward!) permutation problem.

In that example, all the cards are distinct, but maybe you don't care about suits (or maybe you're playing an entirely different card game in which there really are multiple copies of some cards), so there are four copies of each card - now you have a combination problem to work out the total number of shuffles.

I'm sure there are many more interesting examples of counting problems that reduce to counting permutations or combinations of some set of objects - maybe people who spend more time computing probabilities than me have some examples.

Use of combinations in application development.
Travel application
Flight booking engine : Had to generate combinations for Multistop trip(based on timings, airline etc).
Hotel booking engine : Generate room combination for occupancy in a hotel(based on room type, room category etc).
In some cases we had to count the possible output(P&C) to check the usability of the solution and switch to different approach. For instance consider currency conversion. There are 180 current currencies across the world. It is not good practice to generate all the combination and store them. So in similar situation, it is easier to explain the difficulty or understand difficulty by calculating the P&C rather than implementing the solution and facing difficuities.


Formal proof for A subset of the real numbers, well ordered with the normal order of $\mathbb R$, is at most $\aleph_0$ I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$.

Any suggestions?

Thanks.

Now that your question has been answered, let me point out that it may be interesting to observe furthermore that all the countable well-orderings are in fact represented by suborders of $\langle\mathbb{R},\lt\rangle$, and even of $\langle\mathbb{Q},\lt\rangle$. Let me give two proofs.

The first proof is an elementary exercise in transfinite induction. One shows that every countable ordinal $\alpha$ embeds into $\mathbb{Q}$. Note that $0$ embeds trivially. If an ordinal $\alpha$ embeds, then by composing with an isomorphism of $\mathbb{Q}$ with an interval in $\mathbb{Q}$, we may suppose the embedding is bounded above, and thereby extend it to an embedding of $\alpha+1$. If $\lambda$ is a countable limit ordinal, with $\lambda=\text{sup}_n\alpha_n$, then by induction we may map $\alpha_n$ into $\mathbb{Q}\cap (n,n+1)$, and this is an embedding of an ordinal at least as large as $\lambda$. QED

The second proof is simply to argue that $\langle\mathbb{Q},\lt\rangle$ is universal for countable linear orders: every countable linear order embeds into $\mathbb{Q}$. This is proved by using just the "forth" part of Cantor's famous back-and-forth argument, namely, given a linear order $L=\langle\{p_n\mid n\in\mathbb{N}\},\lt_L\rangle$, then map $p_n$ to a rational $q_n$ so that one has a order-preserving map at each finite stage. The next element $p_{n+1}$ relates to the previous elements either by being above them all, between two of them, or below them all, and we may choose a corresponding $q_{n+1}$ of the same type. So we get an order-preserving  map $L\to \mathbb{Q}$. Thus, in particular, every countable well-ordering embeds into $\mathbb{Q}$. QED

A sketch proof...

Consider $\mathbb{R}$ as the set of equivalence classes of Cauchy sequences of rationals. We define "the normal" partial order on $\mathbb{R}$ by $x \leq y$ iff $(x = y)$ OR $(\forall \langle x_{i} \rangle)(\forall \langle y_{i} \rangle)(\langle x_{i} \rangle \in x$ AND $\langle y_{i} \rangle \in y \rightarrow (\exists n)(n \in \mathbb{N} \rightarrow (\forall m)(m > n \rightarrow x_{m} < y_{m}))))$. For $A$ to be well-ordered under this partial order there can only be at most $\aleph_{0}$ distinct $n$ in the last part of the definition as they are drawn from $\mathbb{N}$.


The limit points of an open interval (open set) I am not sure I understand why for the open set $(a,b)$, the limit points are $[a,b]$. Why are $a,b$ now included as limit points? Is this because we can somehow find a sequence in the open interval converging to these points?

Indeed we can find sequences that converge to those points.

Let $d = b-a$ and $\epsilon_n = \frac{d}{n}$. For each $n \in \mathbb{N}$ choose a point $x_n \in (a, a+\epsilon_n)$. Now we claim that that the sequence $\{x_n\}$ converges to $a$.

Let $\epsilon > 0$ then by construction we have

$$|x_n - a| < \epsilon_n = \frac{d}{n}$$

Thus we can let $N\in \mathbb{N}$ with $N > \frac{d}{\epsilon}$ so that for all $n \ge N$ we have

$$|x_n - a| < \epsilon_n = \frac{d}{n} < \epsilon$$

which means that $\lim x_n = a$. Thus $a$ is a limit point of $(a,b)$ and by similar approach (which I will leave to you), it is possible to show that $b$ is also a limit point.

$\boxtimes$

So what we have really done here is look at smaller and smaller intervals contained in $(a,b)$ that are close to $a$ and pick points from each of these intervals. These points form our sequence and the limit of this sequence is $a$. If you need help on constructing a sequence that converges to $b$, think about what intervals you would need to pick points from.

Suppose an open interval $(c, d)$ such that it contains only $a$, we can verify it is open in Euclidean topology (Topology Without Tears, definition 2.1.1), $(c, d)$ has no intersection with $(a, b)$, so, $a$ is not a limit point of $(a, b)$. Maybe I am wrong.


There are two integers whose sum and difference are perfect squares Definition: A positive integer $m$ is said to be a perfect square if there exists an integer $n$ such that $m = n^2$.

  Write a detailed structured proof to prove that there exist two distinct positive integers whose sum and difference are both perfect squares.

How would I write this in logical notation?

We want to prove :

  $$\exists a \in \Bbb Z_+\; \exists b \in \Bbb Z_+\; \exists m \in \Bbb Z_+\;\exists n \in \Bbb Z_+\; \bigl((a-b=m^2) \land (a+b=n^2)\bigr).$$

Since all the quantifiers are existential, one adequate proof is to find $a,b,m,n$ that satisfy the desired equations.  If you start with $m,n$ of the same parity, with $m \lt n$ that is not hard.

hey I'm in the same class as you, and stuck on this as well.  This is what I have so far.
I'm going off the direct proof structure of the existential (chapter 3.7)

This is my general structure:

Let $a = 40$ and $b = 24$.

Then $a \in \Bbb Z_+$ and $b \in \Bbb Z_+$.

Then $$a+b=40+24=64=8^2 \tag a\label a$$
and
$$a-b=40-24=16=4^2 \tag b\label b,$$
so $$a \in \Bbb Z_+,\quad b \in \Bbb Z_+,\quad a+b=x^2,\quad a-b=y^2 \tag c\label c$$

I'm not really sure how to format it properly.  Also I'm not sure if line \eqref{a} and line \eqref{b} can/are supposed to be combined like what I did on line \eqref{c}.  I'm not even sure if line \eqref{c} is correct format wise...


Finding the lengths of the sides of a triangle given 3 angles only. If a right $\triangle ABC$ has $\angle A= 90^\circ$, $\angle B=45^\circ$, $\angle C=45^\circ$. Is there a way of finding the lengths of the sides $a$, $b$ & $c$ without knowing any of their lengths ? Normally we use $(\cos{x})^2+(\sin{x})^2=1$ as the hypotenuse.

I have an equation that says: $$(\sin {x}\times \sin {x}\times \cos {x})^2+(\cos {x}\times \cos {x}\times \sin {x})^2=(\sin {x}\times \cos {x})^2$$

$$\frac{(\sin {x}\times \sin {x}\times \cos {x})^2}{(\sin {x}\times \cos {x})^2}=(\sin{x})^2$$
$$\frac{(\cos {x}\times \cos {x}\times \sin {x})^2}{(\sin {x}\times \cos {x})^2}=(\cos{x})^2$$

Here's an interesting fact:

  If $A$, $B$, $C$ are angles with $A+B+C=180^\circ$, then $\sin A$, $\sin B$, $\sin C$ are the lengths of the sides of a (not the!) triangle with angles $A$, $B$, $C$.

Specifically, the "$\sin A$-$\sin B$-$\sin C$" triangle is the one inscribed in a circle of diameter $1$; you might consider it a fundamental representative of the family of triangles with angles $A$, $B$, $C$, but it is not the only triangle with those angles. You can get from the representative to any other member of the family by magnifying the side-lengths (and the circumdiameter) by some factor, $m$; conversely, any member of the family has side-lengths that are multiples of the side-lengths of the representative (since the family members are all similar).

  A triangle has angles $A$, $B$, $C$ if and only if its side-lengths are $m\sin A$, $m\sin B$, $m \sin C$ for some (positive) $m$.

This is, in fact, exactly what the Law of Sines tells you:
$$\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = m$$
where $m$ is that scale factor ... and also the diameter of the triangle's circumcircle.

In the case of a right triangle with hypotenuse $1$, recall Thales' Theorem:

  A right angle is inscribed in a semi-circle.

Thus, an hypotenuse-$1$ right triangle is inscribed in a circle whose diameter matches that hypotenuse: in other words,

  A unit-hypotenuse right triangle is the fundamental representative of the "$A$-$B$-$90^\circ$" family.

Such a triangle's sides are indeed $\sin A$, $\sin B$ (which we also call "$\cos A$", since $A$ and $B$ are complementary), and $\sin 90^\circ$ (which, of course, is $1$). Perhaps this is what you were getting-at in your comment to your question.

Proof:if x,y and z belong to real numbers and$x<y<z$  then

$(((\frac{\sqrt\frac{y}{z}}{(1-\frac{x}{z})\times\sqrt\frac{x+z}{z-x}})\times\frac{x}{z})+\sqrt\frac{z-y}{z})\times((1-\frac{x}{z})\times\sqrt\frac{(x+z)}{(z-x)})=\sin A  \tag{1}$

$(\frac{\sqrt\frac{y}{z}}{(1-\frac{x}{z})\times\sqrt\frac{x+z}{z-x}})-(((\frac{\sqrt\frac{y}{z}}{(1-\frac{x}{z})\times\sqrt\frac{x+z}{z-x}})\times\frac{x}{z})+\sqrt\frac{z-y}{z})\times(\frac{x}{z})=\cos A \tag{2}$

$\sqrt\frac{(z-y)}{z}=\cos B \tag{3}$

$\sqrt\frac{y}{z}=\sin B \tag{4}$

$\frac{x}{z}=\cos C \tag{5}$

$((1-\frac{x}{z})\times\sqrt\frac{(z+x)}{(z-x)})=\sin C \tag{6}$

$(\sqrt{\frac{y}{z}}\times\frac{x}{z})+\sqrt\frac{z-y}{z}\times((1-\frac{x}{z})\times\sqrt\frac{(z+x)}{(z-x)})=\sin A \tag{7}$

$(-\sqrt{\frac{z-y}{z}})\times\frac{x}{z})+\sqrt{\frac{y}{z}}\times((1-\frac{x}{z})\times\sqrt\frac{(z+x)}{(z-x)})=\cos A \tag{8}$

$((((\frac{\sin B}{\sin C})\cos C)+\cos B)\sin C)=\sin A \tag{9}$

$(\frac{\sin B}{\sin C})-((((\frac{\sin B}{\sin C})\cos C)+\cos B)\cos C)=\cos A \tag{10}$

$((((\frac{\sin A}{\sin C})\cos C)+\cos A)\sin C)=\sin B \tag{11}$

$(\frac{\sin A}{\sin C})-((((\frac{\sin A}{\sin C})\cos C)+\cos A)\cos C)=\cos B \tag{12}$

find $\cos C$ and $\sin C$ in terms of $\sin A, \cos A, \sin B, \cos B$ just like equations $(9)$ to $(12)$?

Notice  that the last four lines, equations $(9)$ to $(12)$, are symmetric with respect to $A,B,C.$ The missing equations are

$ ((((\frac{\sin B}{\sin A})\cos A)+\cos B)\sin A) = \sin C, \tag{13}$

$ (\frac{\sin B}{\sin A})-((((\frac{\sin B}{\sin A})\cos A)+\cos B)\cos A) = \cos C. \tag{14}$

The reason is that $\, A + B + C = \pi \,$ because they are angles of a triangle. As just one example, let $\, x=1, \, y=2, \, z=4. \,$ Then the angles are
 $\, A \approx 59.4775^\circ, \, B = 45^\circ, \, C \approx 75.5224^\circ. \,$
The unusual parametrization of the triangle, given $\, x,y,z \,$ and $\, R, \,$ the radius of the circumscribed circle, is
$$\, b = 2R \sin B.  \sin B=\sqrt{y/z}, \quad c = 2R \sin C. \sin C=\sqrt{1 - x^2/z^2},
 \quad a = 2R \sin A = b \cos C + c \cos B. \,$$

Assuming A,B,C form a triangle.

cos(A+B+C)=-1, cos(A+B)cos(C)-sin(A+B)sin(C)=-1.
sin(A+B+C)=0, sin(A+B)cos(C)+cos(A+B)sin(C)=0.
sin(A+B)=sin(A)cos(B)+cos(A)sin(B).
cos(A+B)=cos(A)cos(B)-sin(A)sin(B).

Knowing cos(A) etc., use 3. and 4. to get cos(A+B) and sin(A+B).
1. and 2. become simultaneous linear equations in cos(C) and sin(C) - readily solved.


The Name for $\mathbb{R}$, $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$ Exclusively Algebras? The Wikipedia page for Normed Division Algebras has been redirected to Normed Algebras and the explanation given is that $\mathbb{R}$, $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$ algebras are not the only normed division algebras.

What is the name for the class of algebras consisting of $\mathbb{R}$, $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$ exclusively?

Euclidean Hurwitz algebras

"Theorem. The only Euclidean Hurwitz algebras are the real numbers, the complex numbers, the quaternions and the octonions."

This list of algebras stems from the Frobenius theorem for finite division algebras over the real numbers. As one goes further down the list, properties of the real numbers are lost along the way.

Real numbers: totally ordered, commutative, associative
Complex numbers: commutative, associative
Quaternions: associative
Octonions: none of the above


Matrix derivative of $\mbox{Tr} (\mathbf{AXB})$ The Matrix Cookbook says that:

$\frac{\partial}{\partial\mathbf{X}} Tr\{\mathbf{A}\mathbf{X}\mathbf{B}\} = \mathbf{A^T}\mathbf{B^T}$

I can't seem to get this. I know that:

$\frac{\partial}{\partial\mathbf{X}} Tr\{F(\mathbf{X})\} = f(\mathbf{A}\mathbf{X}\mathbf{B})^T$

Where $f$ is the scalar derivative of $F$.

So when I apply the rule: $\partial \mathbf{XY} = \partial \mathbf{X} \mathbf{Y} + \mathbf{X} \partial \mathbf{Y}$

I do:

Let: $\mathbf{C} = \mathbf{X}\mathbf{B}$

Then: $\mathbf{A}\mathbf{X}\mathbf{B} = \mathbf{A}\mathbf{C}$.

$\frac{\partial}{\partial\mathbf{X}} \mathbf{A}\mathbf{C} = \frac{\partial}{\partial\mathbf{X}} \mathbf{A} \mathbf{XB} + \mathbf{A} \frac{\partial}{\partial\mathbf{X}}\mathbf{X}\mathbf{B} = \mathbf{AB}$

But then:

$(\mathbf{AB})^{T} = \mathbf{B^TA^T} \neq \mathbf{A^{T}B^{T}}$

Am I confusing the notion of scalar derivative and matrix derivative? How can I verify the Cookbook's claim?

The matrix inner product (denoted by a colon) is equivalent to the trace
$$A^T:B = {\rm tr}(AB)$$

Therefore
$$\eqalign{
 f &= {\rm tr}(AXB) \cr
   &= {\rm tr}(BAX) \cr
   &= (BA)^T:X \cr
   &= A^TB^T:X \cr
\cr
df &= A^TB^T:dX \cr
\cr
\frac{\partial f}{\partial X} &= A^TB^T \cr
}$$

I assume the domain is the space of $n\times n$-matrices $M(n,n)$. The function $f(X)=Tr(AXB)$ is a linear function $M(n,n)\rightarrow R$ since $f(X+Y)=Tr(A(X+Y)B)=Tr(AXB)+Tr(AYB)$. It is thus equal to its differential. To compute its matrix in the basis $e_{ij}$ where $e_{ij}$ is the matrix which has $1$ at the $(i,j)$-place ($i$ is the line and $j$ the column) and all other coefficients are zero.

$Tr(Ae_{ij}B)=Tr(ABe_{ij})$. The unique non zero coefficient on the diagonal of $ABe_{ij}$ is the $(j,j)$ coefficient  which is the coefficient $(j,i)$ of $AB$ which is $\sum_ka_{jk}b_{ki}$ and this is the coefficient $(i,j)$ of $(AB)^T=B^TA^T$.


Don't know how to solve inequality $x^4-2x^3+x^2 < 4$ Solve the inequality: $x^4-2x^3+x^2 < 4$

I'm simply not sure about how to go about solving this inequality - it looks rather different from what I'm used to. Any help would be greatly appreciated.

A strategy you can use in this case is:

Make $y=x^2$
Solve the inequality for $y$
Go back to the $x$ variable for each inequality you found as solution for $y$


limit n tends to infinity for arbitrary non negative real numbers I tried evaluating the limit taking log and afterwards i couldnt proceed further. I tried solving using numbers instead of variables and did not got any relation from that and help in this matter is appreciated

Let $A=\max\{a_1,a_2,\ldots,a_k\}$, then
\begin{align}
\lim_{n\to\infty}(a_1^n+a_2^n+\ldots+a_k^n)^{\frac{1}{n}}&=\lim_{n\to\infty} A\left[\left(\frac{a_1}{A}\right)^n+\left(\frac{a_2}{A}\right)^n+\ldots+\left(\frac{a_k}{A}\right)^n\right]^{\frac{1}{n}}\\
\end{align}
Since $$A\leq A\left[\left(\frac{a_1}{A}\right)^n+\left(\frac{a_2}{A}\right)^n+\ldots+\left(\frac{a_k}{A}\right)^n\right]^{\frac{1}{n}} \le Ak^{\frac{1}{n}}$$
And $$\lim_{n\to \infty} k^{1/n}=\exp\left(\lim_{n\to\infty}\frac{\ln k}{n}\right)=\exp(0)=1$$ It follows, from the sandwich theorem, that
\begin{align}
\lim_{n\to\infty}(a_1^n+a_2^n+\ldots+a_k^n)^{\frac{1}{n}}&=\lim_{n\to\infty} A\left[\left(\frac{a_1}{A}\right)^n+\left(\frac{a_2}{A}\right)^n+\ldots+\left(\frac{a_k}{A}\right)^n\right]^{\frac{1}{n}}=A\\
\end{align}

I would say that this limit goes to infinity. Under the condition that a least one of the $a_k > 1$. The dividing by $n$ is is nothing compared to a power of $n$.


Integration factor - First Order Nonlinear ODE I can't seem to find the proper integrating factor for this nonlinear first order ODE. I have even tried pulling a bunch of substitution and equation-manipulating tricks, but I can't seem to get a proper integrating factor.

$$\frac{1}{x}dx + \left(1+x^2y^2\right)dy = 0$$

EDIT: Due to MSE users complaining about my lack of proof of work, intent of conceptual understanding, etc, here is exactly why I am stuck.

To start off, this ODE is obviously inexact:

$$\frac{\partial}{\partial y}\left(\frac{1}{x}\right) \neq \frac{\partial}{\partial x}\left(1+x^2y^2\right)$$

And so in order to make this exact (if we choose to go down this route) we must (I'll stick to standard convention/notation) find a function $\mu$ such that if we multiply the entire original ODE by it, we will be able to integrate and solve using 'exact ODE' methods. This is shown as:

$$ \mu \left(\frac{1}{x}\right)dx + \mu \left(1+x^2y^2\right)dy = 0$$

$$ \frac{\partial}{\partial y} \left(\mu\left(\frac{1}{x}\right) \right) = \frac{\partial}{\partial x} \left(\mu \left(1+x^2y^2\right) \right)$$

Now expanding by chain rule, we get:

$$\mu_y \left(\frac{1}{x}\right) = \mu_x \left(1+x^2y^2\right) + \mu \left(2xy^2\right)$$

Now here is where I'm stuck. We want to avoid dealing with a PDE, so we try to stick to good old ODE techniques by assuming that $\mu$ is either a function of only x or only y.
Let's first assume that $\mu$ is only a function of y. The following will then be true.

$$ \mu_x = 0$$

$$ \mu_y \left(\frac{1}{x} \right) = \mu \left(2xy^2 \right)$$

$$ \frac{d\mu}{\mu} = 2x^2y^2 dy$$

By looking at the right hand side, we see that it just won't work - x and y are related, so we can't have that integral.

Now let's assume that $\mu$ is only a function of x. The following will then be true.

$$ \mu_y = 0$$

$$ \mu_x \left(1+x^2y^2\right) = -\mu \left(2xy^2\right)$$

$$ \frac{d\mu}{\mu} = \frac{-2xy^2}{1+x^2y^2} dx$$

And, once again, if you look at the right hand side, we have an integral that we can't immediately work out, just as in the previous case.

Assume you're looking for a solution $y(x)$, then mathematic gives:

$$ \frac{-1}{x + x^3 y^2} = \frac{ dy}{dx} \implies  \frac{\exp (-2 y)}{8 x^2} + \frac{ \exp (-2y) }{16} (2 y^2 +2y +1) = Const $$

It looks to me like we can't find an integrating factor which depends only on $x$ or only on $y$ (in general, $\mu$ will be a function of only one variable just in some special cases, so this is not entirely surprising).

For any equation of the form $p(x,y)dx + q(x,y)dy = 0$,
in order to be able to find $\mu := \mu(x)$ it must be the case that
\begin{equation}
\frac{\frac{\partial p}{\partial y} - \frac{\partial q}{\partial x}}{q}
\end{equation}
is a function of $x$ only. If it is, we can set
\begin{equation}
\mu(x) = \exp\left(\int\frac{\frac{\partial p}{\partial y} - \frac{\partial q}{\partial x}}{q}dx\right).
\end{equation}
Here I get
\begin{equation}
\frac{\frac{\partial p}{\partial y} - \frac{\partial q}{\partial x}}{q} =
\frac{-2xy^2}{1 + x^2y^2},
\end{equation}
which clearly depends on $y$. Then we can't have a $\mu$ which depends only on $x$. To have a $\mu$ which depends only on $y$, we must have
\begin{equation}
\frac{\frac{\partial q}{\partial x} - \frac{\partial p}{\partial y}}{p}
\end{equation}
be only a function of $y$. If that's the case, we can set
\begin{equation}
\mu(y) = \exp\left(\int \frac{\frac{\partial q}{\partial x} - \frac{\partial p}{\partial y}}{p} dy\right).
\end{equation}
Here I get
\begin{equation}
\frac{\frac{\partial q}{\partial x} - \frac{\partial p}{\partial y}}{p} = \frac{2xy^2}{\frac{1}{x}} = 2x^2y^2,
\end{equation}
which clearly depends on $x$. Then we can't have $\mu$ depend on $y$ only.

As a result, we must have $\mu$ depend on both $x$ and $y$.


Simplifying expression quartic x Is it possible to simplify the expression:

$3x^4-x^3+4x^2-5x-5$

by finding the different roots of x? I tried by the Rational Roots test, but couldn't find one easily.


Does the Squeeze Theorem apply to $\lim_{x\to\infty}\sin(\frac{\pi x}{2-3x})$? I was recently asked to find the limit of
$$\lim_{x\to\infty}\sin(\frac{\pi x}{2-3x}).$$
I eventually solved it by breaking the limit down to a composition of functions, but my first instinct was actually to invoke the Squeeze Theorem. My logic was that since
$$-1\leq \sin(x) \leq 1,$$
I can have $\lim_{x\to\infty}-1$ serve as the lower bound and $\lim_{x\to\infty}1$ serve as the upper bound to conclude that
$$\lim_{x\to\infty}-1=\lim_{x\to\infty}1=\lim_{x\to\infty}\sin(\frac{\pi x}{2-3x})=1.$$
Given that the second method I did yielded an answer of $-\frac{\sqrt{3}}{2}$, I'm not sure where I went wrong in my implementation of the Squeeze Theorem. My suspicion is that a) I was wrong in thinking $\frac{\pi x}{2-3x}$ would be akin to simply another $x$ if both were entered into $\sin(x)$, or b) I needed to break down the limit into compositions before invoking the Squeeze Theorem.

Here are some better bounds to use for your squeeze theorem ($x>2$):

$$-\frac{\sqrt3}2-\frac\pi{9x}<\sin\left(\frac{\pi x}{2-3x}\right)<-\frac{\sqrt3}2$$

As $x\to\infty$, we see that $\frac\pi{9x}\to0$, hence the limit is $-\frac{\sqrt3}2$.

These bounds were obtained by noting that:

$$0<x<\frac12\implies\frac{d^2}{dx^2}f(x)>0$$

Where $f(x)=\sin\left(\frac\pi{2x-3}\right)$ is your function after $x\mapsto1/x$.

As $f(x)$ is concave up, it follows that for $x>0$ and sufficiently close to $0$, we have

$$f(0)+f'(0)x<f(x)<f(0)$$

Whereupon I obtained the values $f(0)=-\frac{\sqrt3}2$ and $f'(0)=-\frac\pi9$.

I made a very simple mistake:
$$\lim_{x\to\infty}-1\stackrel{?}{=}\lim_{x\to\infty}1$$
$$-1\ne1$$
Therefore I can't use $-1$ and $1$ as my bounds for the Squeeze Theorem.

credits to thedilated for pointing this out to me in comments.


Marginal density over parameter This is from my textbook, I was wondering why the last equation hold?

I got
$$\begin{aligned}
p(y|M_i)& =\int p(y,\theta_i|M_i)d\theta_i\\
& =\int \frac{p(y,\theta_i,M_i)}{p(M_i)}d\theta_i\\
& =\int \frac{p(y,\theta_i,M_i)}{p(\theta_i,M_i)}\frac{p(\theta_i,M_i)}{p(M_i)}d\theta_i\\
&=\int p(y|\theta_i,M_i)p(\theta_i|M_i)d\theta_i
\end{aligned}$$

Many thanks~

The correct series of equations can be obtained in a more direct way.

\begin{equation}
\begin{aligned}
p(y \mid M_i)
& = \int p(y, \theta_i \mid M_i) d\theta \text{ by marginalizing} \\
& = \int p(p, \mid M_i, \theta_i) p(\theta_i \mid M_i) d\theta_i \text{ by factoring pdf} \\
\end{aligned}
\end{equation}

The last step is justified in general because $ p(x, y \mid z) = p(x \mid y, z)p(y \mid z) $, where $ x, y, z $ are allowed to be vectors (and in particular, $ z $ can be empty).


Proving that the period of $\cos^2x$ is half the period of $\cos x$ For example, I know that the period of $\cos^2x$ is simply
$$\frac{\text{period of }\cos x}{2}$$ That is: $\pi$. Could you provide me with both a visual intuitive explanation and an algebraic proof?

For all $x$ we have $\cos^2 (x+\pi)=$ $(\cos (x+\pi))^2=(-\cos x)^2=(\cos x)^2=$ $=\cos^2 x.$

If $k/\pi\not \in \Bbb Z$ then let $k=k'\pi +k''$ with $k'\in \Bbb Z$ and  $0<k''<\pi.$  Then  $\cos^2(0+k)=\cos^2k=\cos^2 k''\ne 1=\cos^2 0,$  so $k$ is not a period of $\cos^2 x.$

We want period of $cos^2 (x)$  we know that $\cos^2(X)=\frac12(1+\cos2x)$ now consider only $\cos2x$ as the remaining are constants then it is in the form $\cos(ax+b)$ that is $\cos(2x+0)$ we know that period of $\cos x=\frac{2\pi}{|a|}$ now substitute $2$ in place of $a$ that is $\frac{2\pi}2=\pi$.
Then the period of $\cos^2(x)=\pi$


How to apply Newton's method on Implicit methods for ODE systems I am writing a Fortran program to solve any ODE initial value problems. There is a subroutine called Jacobian matrix and for different problems it is required that we just make changes to the subroutine such that all types of problems can be solved. The first step is to transform any high order ODEs to the first order ODE system. The next step is to use the implicit method, e.g. backward Euler method, to solve it. The question I have is how to use Newton's method on the implicit method? Especially what the Jacobian matrix should be?
enter image description here
enter image description here
How to use Newton's method to solve this ODE system? Anyone can give a detailed example? I would really appreciate it!

In Backward Euler, the equation to be solved at each step is

$$x_{n+1}=x_n+(t_{n+1}-t_n)f(x_{n+1},t_{n+1}).$$

That is, you want to find roots of the function

$$g_n(x)=x-x_n-(t_{n+1}-t_n)f(x,t_{n+1})$$

where we interpret $x_n,t_{n+1},t_n$ as parameters. So in particular the Jacobian for Newton's method is $I-(t_{n+1}-t_n)D_x f(x,t_{n+1})$, where $D_x$ represents differentiation with respect to the $x$ variables.


N-point compactification of $\mathbb{R}$. Let $X = \mathbb{R} \cup \{\infty_1,..., \infty_n\} $ be a topological space in which the topology is: the neighborhood of $\infty_i$ are $A \cup \infty_i$ with $A^c$ a compact set in $\mathbb{R}$. The problem asks to find the fundamental group of X. I have no idea how to do this. Thanks in advance for every hint\answer.

Actually $\mathbb R$ does have an obvious 2-point Hausdorff compactification, (not for any larger n though), but the compactification defined in your problem is different and definitely not Hausdorff.

Think of it as bending $\mathbb R$ round into a circle with one point missing, but then putting n points into the gap. They are distinct but have the same neighbourhoods within $\mathbb R$. A path going round the circle can pass through different infinities, but only one on each circuit. A loop which goes through one infinity but then comes back through another will not be homotopic to the null loop so the fundamental group is not the same as that of a circle. See if you can work it out from there.

$\mathbb{R}$ only has a one-point and two-point compactfication (homeomorphic to $S^1$ resp. $[0,1]$)

$\mathbb{R}^n$ has just a one-point compactification, not an $m$-point one for $m>1$: consider the intersection of the complements of the open balls $B(0,n)$ in such a compactification: it's an intersection of compact and connected (!) sets hence compact and connected and so cannot be a finite $m$-point set.


If two different numbers are taken from the set {0,1,2,3, ......, 10} ... If two different numbers are taken from the set {0,1,2,3, ......, 10}  then what is the probability that their sum as well as absolute difference are both multiples of 4

Here is my work out

The sample space here is equal to 55.

Now to me the possible combinations are {0,4},{0,8},{2,6},{2,10},{4,8},{6,10}

so to me the answer is 6/55

Let's think what it means for two numbers $a, b$ to have sum and difference multiples of 4.

$a+b\equiv0 \pmod4$

$a-b\equiv0 \pmod4$

Adding them up, $2a\equiv0 \pmod4$, so it follows that $a\equiv0,2 \pmod4$

$a-b\equiv0 \pmod4$ states that $a\equiv b \pmod4$.

So, $a, b$ are $0, 2 \pmod4$ and are congruent to each other. This splits nicely into 2 cases, $0 \pmod4$ and $2 \pmod4$.

Under the case $0 \pmod4$, $a, b$ can be $0, 4, 8$. There are 3 ways to select 2 numbers from this set, and it is easy to verify that all 3 ways work.

Under the case $2 \pmod4$, $a, b$ can be $2, 6, 10$. There are 3 ways to select 2 numbers from this set, and it is easy to verify that all 3 ways work.

With $6$ satifying possibilities in total, and ${11\choose2}=55$ ways to choose 2 numbers, the probability of this event is $\frac{6}{55}$.

Assuming random selection-- To have both sum and absolute difference of different integers be a multiple of 4 there are 5 possible combination of integers.0 and 4 , 2 and 6, 4 and 8, 6 and 10, and 0 and 8, = 5 choices
Given that  choice of 2 numbers from 0 to 10 , that is 11 choices, and that they must be different, the total choices is 11x10 = 110.
The probability of the 5 combinations being chosen, remembering that we halve because there is no requirement for order, is 5 (times 2) divided by 110  = 1/11


Cl(A union B) = Cl(A) union Cl(B) counter example where Cl stands for closure? In my topology book I was asked to prove the above result but instead I think I found a counter example. Consider:

X = {a,b,c,d,e}

A = {a,b}   B = {c,d} and Basis BS = {(a,b,e) , (b,e) , (c,e) , (c,d,e)}, (It's easy to visualize if you draw the basis by writing a,b,e,c,d and making circles left and right accordingly).

It is a basis because every element is contained in some basis and their is a basis which lies inside intersection of any two basis ( in case of (a,b,e) and (b,e) its (b,e)).

Now I quote a theorem which says , x belongs to cl(Y) if every basis element containing x intersect Y.

Therefore Cl(A) = A (because some basis of e doesn't intersect A eg (e,c))

Similarly Cl(B) = B, Therefore Cl(A) union Cl(B) = {a,b,c,d}.

Now Cl(AUB) contain e where basis containing e alternatively intersects both A and B, hence Cl(AUB)={a,b,e,c,d}

Could anyone point any mistakes in my argument?

The mistake is that you don’t actually have a base for a topology: both $\{b,e\}$ and $\{c,e\}$ are open, so their intersection, $\{e\}$, must also be open. Thus, $\{e\}$ must also belong to the base. In particular, this means that $e\notin\operatorname{cl}(A\cup B)$.


Are equivalence classes closed under intersection? How do I prove whether the set of equivalence classes for some equivalence relation is closed under intersection; that is the intersection of equivalence classes is an equivalence class?

If you're asking why... I'm trying to prove that Every two equivalence classes $[x]$ and $[y]$ are either equal or disjoint but that problem I can solve. I just need to know whether countable intersection of equivalence classes is an equivalence class.

If they are either equal or disjoint, then that means the (2-ary) intersection is either one set or the nullset. It is easily shown that this is also true for a k-ary intersection.

If I understood correctly, yes, the intersection of classes is a class. It will either be empty if you are intersecting inequivalent classes or , if not, it will agree with the first class in your intersection, which will coincide, (intersection being non-empty) with all classes being intersected..