What is the order of operations in a given formula? My question is probably very basic. It's related to the order of operations in the following simple formula:

$$\frac{A}{B\times C}.$$

My question arises when I want to write this formula in a single line. For instance: $150/1.5\times 0.33$.

Should I write $150/1.5\times 0.33$ or $150/(1.5\times 0.33)$. Is the answer equal to $300$ or $33.3$? I mean, it's obviously $300$ according to the original formula. But I am a bit confused with the single line formula.

I remember that the multiplication has a preference over the division. So, the parenthesis is not needed... But then the answer might be $33.3$, which is not correct. I get stuck with this quite simple thing.

The other answers here address the mathematics of "order of operations" - operator precendence in programming languages. They pretty much tell you to use the parentheses.

I want to address this point explicitly:

  My question arises when I want to write this formula in a single line.

You are asking here about communication. The important issue is to make your meaning unambiguously clear. So when writing inline you should use the parentheses in the denominator, even if they are unnecessary because your reader or your compiler "knows what you mean".

To understand this we must first explain what division means.

Division is multiplication by an inverse element. In a group or a field there is ensured to exist an inverse element such that if you multiply it it becomes 1 : $\frac{a}{a} = a^{-1}a= aa^{-1} = 1$. What is important is to specify which element should be inverted before multiplication. In many programming languages there is a convention that division has higher precedence. That is just to make sure one knows which number we should find the multiplicative inverse for before performing multiplication with it.

$$\frac{a}{bc} = a(bc)^{-1}, \frac{ab}{c} = ab(c)^{-1}$$
Where $(bc)^{-1}$ is the multiplicative inverse to $bc$ and $(c)^{-1}$ is the multiplicative inverse for $c$.

The horizontal division sign ____ only helps us explaining this for commutative algebras as we otherwise need to also decide from which side the division occurs. Or in other words from which side we should multiply with the multiplicative inverse.


Eigenvalues existence I know there are linear maps $f:\Bbb R^{n} \rightarrow \Bbb R^{n}$ where $\Bbb R^{n}$ is on $\Bbb R$ that do not have eigenvalues.

Can we find a linear map $f:V \rightarrow V$ where $V$ is a vector space on $\Bbb C$ such that $f$ does not have eigenvalues?

The answer is "yes" if $V$ is allowed to be infinite-dimensional, and "no" if $V$ is finite-dimensional.

For the example in infinite dimensions, simply consider $\mathbb C^\omega:=\{(x_1,x_2,\ldots):x_i\in\mathbb C\}$ and the linear function $f\colon\mathbb C^\omega\to \mathbb C^\omega$ defined by $f(x_1,x_2,\ldots)=(0,x_1,x_2,\ldots)$.
There is nothing special about $\mathbb C$ here; the same example works over any field

On the other hand, if $V$ is a finite-dimensional dimensional vector space over $\mathbb C$, suppose $\dim V=n$ and consider $L(V,V)$, the space of linear functions from $V$ to itself, which is also a vector space over $\mathbb C$ under pointwise addition and scalar multiplication and has dimension $n^2$.

For $f\in L(V,V)$, and a polynomial $p(t)=a_0+a_1t+\dots+a_kt^k\in\mathbb C[t]$, we can define $p(f)=a_0\text{id}_V+a_1f+a_2f^{\circ 2}+\dots+a_kf^{\circ k}$ where $\text{id}_V$ is the identity map on $V$ and $f^{\circ k}=f\circ f\circ\cdots\circ f$, $k$ times. Note that $p(f)\in L(V,V)$ as well, and that we can factor $p(f)$ (using $\circ$ as multiplication) in the same way as we would factor $p(t)\in\mathbb C[t]$.

Now, consider the set $\{\text{id}_V,f,f^{\circ 2},\dots,f^{\circ n^2}\}$; this is a set of $n^2+1$ vectors in $L(V,V)$, so there must be a non-trivial linear dependence $c_0\text{id}_V+c_1f+\dots+c_{n^2}f^{\circ n^2}=O_V$ where $O_V\in L(V,V)$ is the map which sends everything to $0$.
In other words, if $p(t)=c_0+c_1t+c_2t^2+\dots+c_{n^2}t^{n^2}$, then $p$ is a non-zero polynomial in $\mathbb C[t]$ with $p(f)=O_V$. Suppose that $k$ is the largest non-zero index with $c_k\neq 0$, so by dividing by $c_k$, we can suppose that $p(t)=c_0+c_1t+\dots+c_{k-1}t^{k-1}+t^k$.

Now, using the fundamental theorem of algebra, we can factor $p(t)=\prod_{i=1}^k(t-\lambda_i)$ where $\lambda_i\in\mathbb C$ and thus $O_V=p(f)=(f-\lambda_1\text{id}_V)\circ\cdots\circ(f-\lambda_k\text{id}_V)$. Now, $\ker p(f)=V\neq\{0\}$, but if it were the case that $\ker(f-\lambda_i\text{id}_V)=\{0\}$ for all $i$, then this could not happen, so there must be some $i\in[k]$ for which $\ker(f-\lambda_i\text{id}_V)\neq\{0\}$.
Hence, find $v\in\ker(f-\lambda_i\text{id}_V)\setminus\{0\}$, so $f(v)-\lambda_i\text{id}_V(v)=0\implies f(v)=\lambda_i v$, i.e. $v$ is an eigenvector for $f$ with eigenvalue $\lambda_i$.

we can find a map $T\colon v\mapsto v$ where $v$ is a vector space over $c$ such that
              $$T(f(x))=xf(x)$$
   Then $T$ has no Eigenvalue


Maximizing a product of factorials I would like to maximize $n_1! n_2! \cdots n_k!$ under the constraint $n_1 + n_2 + \cdots + n_k = N$ and $n_i > 0$ for all $i$. Intuitively, I think the maximum occurs when all $n_i$ are $1$ except for one of them: $$(1!)( 1!) \cdots (1!)( (N-(k-1))!)$$ but I am unsure how to show this because I can't take the derivative of this kind of function. Could someone point me in the right direction? Thanks!

Edit: perhaps induction on $k$ will work?

If $k=2$, it is a little easier to see that the maximum of $n_1!n_2!=n_1! (N-n_1)!$ is $N!$ (how to rigorously show this still escapes me). Then it follows by induction, I believe.

Increasing the largest $n_i$ by 1 and simultaneously decreasing the smallest $n_j$ by 1 respects the condition $n_1 + n_2 + \cdots + n_k = N$ and increases the product.  Therefore you can make all of the factors equal to 1 except the biggest one.

$\newcommand{\+}{^{\dagger}}%
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert #1 \right\vert}%
 \newcommand{\yy}{\Longleftrightarrow}$
$\ds{{\cal F} \equiv \sum_{\ell = 1}^{k}\ln\pars{\Gamma\pars{n_{\ell} + 1}} - \mu\pars{\sum_{\ell = 1}^{k}n_{\ell} - N}}$
$$
0 = \partiald{{\cal F}}{\tilde{n}_{\ell}} = \Psi\pars{\tilde{n}_{\ell} + 1} - \mu\,,
\quad\forall\ \ell\quad\imp\quad \tilde{n}_{\ell} = {N \over k}\,,\quad\forall\ \ell
$$


Surprising identities / equations What are some surprising equations/identities that you have seen, which you would not have expected?

This could be complex numbers, trigonometric identities, combinatorial results, algebraic results, etc.

I'd request to avoid 'standard' / well-known results like $ e^{i \pi} + 1 = 0$.

Please write a single identity (or group of identities) in each answer.

I found this list of Funny identities, in which there is some overlap.

This one by Ramanujan gives me the goosebumps:

$$
\frac{2\sqrt{2}}{9801} \sum_{k=0}^\infty \frac{ (4k)! (1103+26390k) }{ (k!)^4 396^{4k} } = \frac1{\pi}.
$$

P.S. Just to make this more intriguing, define the fundamental unit $U_{29} = \frac{5+\sqrt{29}}{2}$ and fundamental solutions to Pell equations,

$$\big(U_{29}\big)^3=70+13\sqrt{29},\quad \text{thus}\;\;\color{blue}{70}^2-29\cdot\color{blue}{13}^2=-1$$

$$\big(U_{29}\big)^6=9801+1820\sqrt{29},\quad \text{thus}\;\;\color{blue}{9801}^2-29\cdot1820^2=1$$

$$2^6\left(\big(U_{29}\big)^6+\big(U_{29}\big)^{-6}\right)^2 =\color{blue}{396^4}$$

then we can see those integers all over the formula as,

$$\frac{2 \sqrt 2}{\color{blue}{9801}} \sum_{k=0}^\infty \frac{(4k)!}{k!^4} \frac{29\cdot\color{blue}{70\cdot13}\,k+1103}{\color{blue}{(396^4)}^k} =  \frac{1}{\pi} $$

Nice, eh?

Jean Nicod's first single axiom DDpDqrDDtDttDDsqDDpsDps, where D stands for the Sheffer stroke ("NAND"), and we write in Polish notation.  Under the rule {D$\alpha$D$\beta$$\gamma$, $\alpha$} $\vdash$ $\gamma$, all tautologies (containing just "D" and variables) in classical logic can get derived.

CCCpqrCCrpCsp.  This is Lukasiewicz's 13 letter axiom which suffices as the only axiom, under detachment, to prove all formulas of the classical pure implicational calculus of propositions.

Meredith's 21 letter axiom CCCCCpqCNrNsrtCCtpCsp which suffices as the only axiom for C-N classical logic under detachment (it's not known if this is the shortest such axiom).

(x(y(((zz')(uy)')x))') = u.  This is a product and inverse single axiom for group theory.  There are no shorter product and inverse single axioms for group theory.

((x|z)|y)|((x|(x|y))|x)=y, (x|((y|x)|x))|(y|(z|x))=y, ((x|y)|z)|(x|((x|z)|x))=z, and  ((x|(z|x))|x)|(z|(y|x))=z are among the shortest possible single axiom for Boolean algebra in the Sheffer stroke.

XCB: EpEEEpqErqr was the last proved shortest single axiom and completes the set of shortest single axioms for equivalential calculus under the rule {E$\alpha$$\beta$\, $\alpha$ $\vdash$ $\beta$}.  The proof involved a computer program.

C$\delta$pC$\delta$Np$\delta$q, where $\delta$ comes as a functional variable of one argument, consists of a single axiom which under uniform substitution and detachment comes as sufficient to deduce all C-N-$\delta$ tautologies.

C$\delta$CpqCp$\delta$q suffices as a single axiom to prove a deduction theorem for a propositional calculus.

C$\delta$CpqC$\delta$p$\delta$q, from what I have read though I have not seen a proof, suffices as a single axiom for all C-$\delta$ propositions.

C$\delta$$\delta$0$\delta$p.  This 6 letter single axiom under detachment, substitution, and the rules for quantifiers, I have read, suffices for all theorems or axioms of classical propositional logic with functional variables, quantifiers of propositions, and quantifiers of functional variables.


Is there any commonality between the use of Parseval's Identity in two different contexts? In Fourier analysis, Parseval's Identity relates to "the summability of the Fourier series as a function."

In inner product space analysis, the "identity" works as a "Pythagorean theorem" relating the squared length of a vector to the sums of squares of its components.

How would the same theorem be central to two different applications? Or are they more or less connected because the "summability" of the Fourier Series, is somehow also based on a "Pythagorean" theorem?

The Fourier theorem is in a way a special case of Parseval's identity. Consider the following: If you look at the space $L^2$ with inner product

$$\left\langle f,g \right\rangle = \frac{1}{2\pi} \int_{0}^{2\pi} f(x)\overline{g(x)} dx$$

Then the functions $e^{ikx}, k\in\mathbb{Z}$ form an orthonormal basis, so Parseval tells you
$$\|f\|^2 = \sum_{k\in\mathbb{Z}} \left|\left\langle f,e^{ikx}\right\rangle\right|^2 $$

However $c_k = \left\langle f,e^{ikx}\right\rangle = \frac{1}{2\pi} \int_{0}^{2\pi} f(x)e^{-ikx} dx$ is exactly the $k$-th Fourier coefficient, so this is nothing other than Parseval's identity for Fourier series.

It all comes down to the fact, that taking the Fourier series of a function is nothing other then expressing this function in the basis given by $e^{ikx}$:
$$ f = \sum_{k\in\mathbb{Z}}  \left\langle f,e^{ikx}\right\rangle e^{ikx} = \sum_{k\in\mathbb{Z}} c_k e^{ikx} $$

(Your constants may vary depending on definitions)

NO, summability in Pythagorean has nothing to do with with Parseval's theorem.

It just says that energy of the "system" is always same no matter how you look at it! So you calculate the energy in time domain, OR, you transform your function to another domain (e.g. frequency), the energy remains the same.

One way to look at it is that the preservation of basic physical law. For instance, if you want to calculate the kinetic energy of a system: $\frac{1}{2}m||v||^2$. Now you calculate the velocity in Cartesian coordinate/polar coordinate/cylindrical coordinate, the energy would remain the same, now matter how you look at the system. The same logic applies here!

No matter how one mess around a system, the basic physical laws always conserves itself. It's just a matter of perspective.


Algorithm for calculating $A^n$ with as few multiplications as possible Is there an algorithm for working out the best way (i.e. fewest multiplications) of calculating $A^n$ in a structure where multiplication is associative?

For example, suppose $A$ is a square matrix. Matrix multiplication is associative, and I can compute $A^9$ with $4$ multiplications:

$$A^2 = A \cdot A$$

$$A^3 = A^2 \cdot A$$

$$ A^6 = A^3  \cdot A^3 $$
$$ A^9 = A^6 \cdot A^3 $$

One method which works is to compute $A^{2^i}$ and use the binary representation of $n$, but this is not always optimal, e.g. with $n=23$, we can do it in $6$ multiplications:

$$ A^2 = A \cdot A $$

$$ A^3 = A^2 \cdot A $$

$$ A^5 = A^3 \cdot A^2 $$

$$ A^{10} = A^5 \cdot A^5 $$

$$ A^{20} = A^{10} \cdot A^{10} $$

$$ A^{23} = A^{20} \cdot A^3 $$

rather than $7$:

$$ A^2 = A\cdot A $$
$$ A^4 = A^2 \cdot A^2 $$
$$ A^8 = A^4 \cdot A^4 $$
$$ A^{16} = A^8 \cdot A^8 $$
$$ A^{20} = A^{16} \cdot A^4 $$
$$ A^{22} = A^{20} \cdot A^2 $$
$$ A^{23} = A^{22} \cdot A $$

Is there an algorithm which gives the quickest way?

There seems to be no efficient algorithm for this. Quoting Wikipedia on Addition-chain exponentiation:

  … the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete.  Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.

On the same page, however, it does link to a reference* of some methods better than binary exponentiation.

One simple example is to use base-N number instead of base-2. e.g. for A510,

with binary:   2 = 1 + 1
               3 = 2 + 1
               6 = 3 + 3
               7 = 6 + 1
              14 = 7 + 7
              15 = 14 + 1
              30 = 15 + 15
              31 = 30 + 1
              62 = 31 + 31
              63 = 62 + 1
             126 = 63 + 63
             127 = 126 + 1
             254 = 127 + 127
             255 = 254 + 1
             510 = 255 + 255   (15 multiplications)

with base-8:   2 = 1 + 1
               3 = 2 + 1
               4 = 3 + 1
               5 = 4 + 1
               6 = 5 + 1
               7 = 6 + 1
              14 = 7 + 7
              28 = 14 + 14
              56 = 28 + 28
              63 = 56 + 7
             126 = 63 + 63
             252 = 126 + 126
             504 = 252 + 252
             510 = 504 + 6      (14 multiplications)

with base-4:   2 = 1 + 1
               3 = 2 + 1
               4 = 2 + 2
               7 = 4 + 3
              14 = 7 + 7
              28 = 14 + 14
              31 = 28 + 3
              62 = 31 + 31
             124 = 62 + 62
             127 = 124 + 3
             254 = 127 + 127
             508 = 254 + 254
             510 = 508 + 2      (13 multiplications)

(I don't know how to choose the optimal N.)

*: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), pp 129–146

[Edited:This is about solving the Project Euler problem, and not directly about your
question. ] Admittedly, I'm quite late but remember having worked out this problem myself. The quickest cut to the solution is to use this  OEIS page .

Add up the right hand entries for the first 200 rows, and you're done.As a general hint to Project Euler problems, when all this much theory is required, avoid writing your own programs and look it up somewhere.


How to find the perpendicular distance from B to AC? "Find the area of triangle $ABC$ with vertices $A(2, 1), B(12, 2) $and $C(12, 8)$. Hence or otherwise, find the perpendicular distance from $B$ to $AC$."

I found the area, which is 30 units by find the length:

$AB:\sqrt101$, $BC: 6$ and $AC: \sqrt149$

But I can't continue, how to find the perpendicular distance from B to AC?

Please help...give me some hint.

Hint: Choose “otherwise“: The distance from $BC$ to $A$ is $10$.  Draw a picture to see why.

area of the triangle is given by $bh/2$ where $b$ is the length of the base and $h$ the length of height. Draw a figure of the given triangle and you will see that $b=|AC|$ and $h$ is the length of the required perpendicular. Now put it into the formula for area.


Algebraic solution to the Broken Weight Problem Here is a problem I was sent, which it turns out was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems. The problem is as follows:

  A few years ago, a King's mathematics professor purchased a small farm, a place where he could unwind on the weekends and grow some fruit and vegetables. The farm came with all kinds of tools and various implements, including a large balance scale. Next to the scale was an old (pre-metric) 40 lbs stone with some initials carved into it: apparently, a previous owner had used it to weight 40 lbs of feed.

  One morning, while cleaning out his barn, the professor dropped the stone and it broke into four pieces.

  The professor was a bit sad about his carelessness, as he had liked that curious old stone. But he soon discovered something interesting: He could use the four pieces of the broken stone to weigh items on the balance scale - as long as these items were in one pound increments, between 1 and 40 pounds.

  How much did each of the four pieces weigh?

Note that since this was a 17th-century merchant, he of course used the balance scale to weigh things. So, for example, he could use a 1 lb weight and a 4 lb weight to weigh a 3 lb object, by placing the 3 lb object and 1 lb weight on one side of the scale, and the 4 lb weight on the other side.

I won't post the solution as maybe some of you would like to give this a go. For anyone reading this and wanting to try it themselves, DON'T SCROLL DOWN! People will be posting their solutions there.

I did this using an intuitive method but my question I am asking is in two parts:

1) Is there an algebraic solution to this without first solving it intuitively and then finding the logic

2) Is there therefore a general form you can take to solve any problem of this type?

Good luck!

If you can weigh $1,2,3,\ldots,40$, you can also automatically weigh $-1,-2,-3,\ldots,-40$ and trivially $0$. That is, you can determine $81=3^4$ different weights by putting each of the four weights into either of the pans or not use it. This means that the condition is "sharp" - any distinct distribution of pieces results in a distinct (integer) weight as difference between the two pans. If the pieces are $a\le b\le c\le d$, then the largest possible weights are $a+b+c+d=40$ (of course) and then $b+c+d$, which must be $39$, hence $a=1$. The next smallest weight is $b+c+d-a=38$, followed by $a+c+d$, which must be $37$, hence $b=3$. Then we already know that the sequence continues with $c+d=36$, $c+d-a=35$, $c+d-b+a=34$, $c+d-b=33$, $c+d-b-a=32$. Then the next smallest (i.e., the largest not having $+c$ and $+d$) is $a+b+d$ and must equal $31$, so that $c=9$ and finally $d=27$ (as we might have guessed meanwhile).


Is there a way of proving that $\mathbb{Z}[i]$ and $\mathbb{Z}[\sqrt{-2}]$ are UFD s without showing that they are euclidian domains? What are direct methods for proving that a ring is a UFD in general without proving that it's a PID/Euclidean domain/field and using the fact that all those things are UFDs?

As an example, we can take $\mathbb{Z}[i]$ or $\mathbb{Z}[\sqrt{-2}]$ or other rings you come up with.

Here are some thoughts:

Exsitence is easy to prove using induction on the norm.
Uniqueness is the hard part, especially since it fails for most rings of the form $\mathbb Z[\sqrt d]$. For the rings you've mentioned, it can be proved by knowing the units and exactly how primes in $\mathbb Z$ decompose in $\mathbb Z[\sqrt d]$. There are three possibilities for a prime $p$: it remains prime, it is product of two non associate primes, it is a square. For the rings you've mentioned, this can be decided in ad hoc ways.

In the general case of the ring of integers in quadratic fields $\mathbb{Q}(\sqrt{n})$, the answer is not simple but is fascinating, See the book Primes of the Form $x^2+ny^2$, by David Cox.

This would be extremely wasteful, and nobody would do it before showing they were Euclidean domains or PIDs, but you could show that they have class number 1 through some indirect means. $\mathbb Z[i]$ is a Dedekind domain so it is a UFD if and only if its class number is 1.


Showing that $n$ exponential functions are linearly independent. I have $n$ lambdas, which are all different real and positive numbers, where:
$\lambda_1 < \lambda_2 < \cdots < \lambda_n$.

I then have to show that these functions are linearly independent:

$$e^{\lambda_1 t}, e^{\lambda_2 t}, \ldots, e^{\lambda_n t}$$

So I guess what I want to show is that the only solution to this equations:

$$c_1 e^{\lambda_1 t} + c_2 e^{\lambda_2 t}+ \ldots +c_n e^{\lambda_n t}=0, \quad \text{for all } t$$

is that all constants are zero.
I am not entirely sure how to do this when it is for $n$ lambdas - I did it earlier for just 3 lambdas, where I differentiated the function, so I have tried to use the same approach.

I wanted to get $n$ equations with $n$ unknown, so I differentiated the function $n-1$ times, and then I chose to look at the case where $t = 0$, so I have something looking like this:

$$c_1+c_2+ \ldots +c_n = 0$$

$$c_1 \lambda_1+c_2 \lambda_2+ \ldots +c_n \lambda_n = 0$$

$$ \cdots $$

$$c_1 \lambda_1^{n-1}+c_2 \lambda_2^{n-1}+ \ldots +\lambda_n^{n-1} = 0$$

Then I put this into a matrix $Ac = 0$, and now I want to show that the $\det(A)$ doesn't equal zero, so that the only solution is c = 0, but I'm not quite sure how to do this, or whether there is an easier way to do it ?

Define $f_j \colon \mathbf{R} \to \mathbf{R}$ by
$$ f_j(t) = e^{\lambda_j t}.$$
Let $V$ denote the vector space of infinitely-differentiable functions from $\mathbf{R}$ to $\mathbf{R}$. Define $D \colon V \to V$ by $$Df = f'.$$
Note that $$Df_j = \lambda_j f_j$$ for $j = 1, \dots n$. Thus $f_1, \dots, f_n$ is a list of eigenvectors of $D$ corresponding to distinct eigenvalues. Now use the theorem that a list of eigenvectors corresponding to distinct eigenvalues is linearly independent, completing the proof that $f_1, \dots, f_n$ is a linearly independent list.

I'm not sure but this matrix looks like the transpose of the Vandermonde matrix


Find the sum of the First $50$ Natural Numbers starting from $11$. Is it from $11-50$ or $11-60$? This a simple question yet confusing for me, I found the answer as 1220 by taking sum from $11$ to $50$, by inferring the question as first 50 natural numbers {$1,2,3,4,5,6,7,8,9,10,11,...49,50$}

and sum starting from 11 which means sum $= 11+12+...+49+50$.
But my friend says otherwise, he took from 11 to 60 and says answer as 1775. Can anyone explain how to infer the word first in the context of maths.

I think there's a bit of ambiguity in the language, so either interpretation is justified. I also think it's just a poorly worded question. The only recourse is to ask whoever set the question or to just let it go - I don't think the intended meaning is really something you can figure out by yourself.

To clarify why I believe both interpretations are valid:

"The first $50$ natural numbers" means $1-50$. So then "The first $50$ natural numbers (starting from $11$)" could mean the same set $1-50$ but starting from $11$ and excluding $1-10$. So $11-50$.
"The natural numbers starting from $11$" means $11,12,\ldots$. So then "(The first $50$) natural numbers starting from $11$" could mean the first $50$ elements of this set. So $11-60$.

There's a high school formula for the sum of consecutive terms in an arithmetic sequence: it is equal to the number of terms, times the arithmetic mean of the first and last term.

Here the first term is $11$ and $50$th term  is $60$, so the sum is
$$50\times\frac{11+60}2=1775.$$


how to construct the addition function in terms of sets In set theory it is my understanding that all things are sets, for example, a relation can be viewed as a set of ordered pairs and a function is a special type of relation. I have seen how each natural is expressed as a set like so:

0 = {}
1 = 1∪{1}
...
n+1 = n∪{n}

However, how does one construct the addition function as a set? Similarly for multiplication. I have only seen recursive definitions like this here:

a+0=a and a+S(b) = S(a+b)

How does one define the addition function as a set?

(For simplicity I'm going to look just at addition of finite ordinals, i.e. natural numbers; addition of arbitrary ordinals is essentially the same, just more messy.)

This is where the recursion theorem comes in. The recursion theorem gives a way to convert a recursive description like

$$a+0=a, \quad a+S(b)=S(a+b)$$ into a genuine set-theoretic object. In fact, that's literally what it says - that recursive definitions are actually valid.

The recursion theorem is easiest to state for unary functions from $\omega$ to $\omega$:

  Suppose $n\in\omega$ and $I:\omega\rightarrow\omega$. Then there is a unique function $f_{I,n}:\omega\rightarrow\omega$ such that $f(0)=n$ and $f(k+1)=I(f(k))$ for all $k\in\omega$.

For example, fixing $a\in\omega$ we can get the "addition-by-$a$" function $add_a$ from this result by setting $n=a$ and $I:x\mapsto S(x)$.

We'll want the binary version of the recursion theorem here; it's more tedious to state and prove, but not substantially different.

It may help to be a bit more concrete. Intuitively, the definition of addition we get looks like:

  For $a,b,c\in\omega$ we have $a+b=c$ - that is, $\langle a,b,c\rangle\in GRAPH_{addition}$ - iff there is a finite sequence of finite ordinals $$\langle x_1,...,x_n\rangle$$ such that $(1)$ $x_1=a$, $(2)$ for each $i\in\{1,...,n-1\}$ we have $x_{i+1}=S(x_i)$, and $(3)$ $x_n=c$ and $n=b$.

This leans on a rigorous set-theoretic approach to sequences, and that has to be understood first. It is in the same spirit as the implementation of finite sequences in arithmetic.

Annoyingly, it's worth noting that there are multiple things called the recursion theorem.

You can construct the addition function as a set $A\subset N^3$ without using the heavy machinery of the recursion theorem as follows.
We start from Peano's Axioms:

$0\in N$
$\forall a\in N: S(a)\in N$
$\forall a, b\in N: [S(a)=S(b) \implies a=b]$
$\forall a\in N: S(a)\neq 0$
$\forall P\subset N: [0\in P \land \forall a\in P: S(a)\in P
    \implies P=N]$

Construct $N^3$. Then construct $A\subset N^3$ such that:

$\forall a,b,c: [(a,b,c)\in A \iff (a,b,c)\in N^3 $
$\land [\forall d\subset N^3:[\forall e\in N: (e,0,e)\in d $
$\land \forall e,f,g:[(e,f,g)\in d \implies (e,S(f),S(g))\in
 d]\implies (a,b,c)\in d]]]$

$A$ is just the "smallest" subset of $N^3$ such that:

For all $a\in N$, we have $(a,0,a)\in A$

For all $(a,b,c) \in A$, we also have $(a,S(b),S(c))\in A$

You would then have to prove that $A$ is function, and that it has the required properties.

$\forall a,b \in N:\exists c\in N:[(a,b,c)\in A \land \forall d\in
   >     N: [(a,b,d)\in A\implies d=c]]$

$\forall a\in N: (a,0,a)\in A$

$\forall a,b,c \in N: [(a,b,c)\in A\implies (a,S(b),S(c))\in A]$

A somewhat tedious, but straightforward exercise.
Similarly for multiplication, having constructed the addition function, we can construct $M\subset N^3$ such that:

$\forall a,b,c: [(a,b,c)\in M \iff (a,b,c)\in N^3 $
$\land [\forall d\subset N^3:[\forall e\in N: (e,0,0)\in d $
$\land \forall e,f,g:[(e,f,g)\in d \implies (e,f+1,g+e))\in
 d]\implies (a,b,c)\in d]]]$

You would then have to prove that $M$ is function, and that it has the required properties.


Prove $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\geq 1$ when $(x^2-1)(y^2-1)(z^2-1)=8^3$ Please help to prove this inequality.

Prove $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\geq 1$ when $(x^2-1)(y^2-1)(z^2-1)=8^3$ and each of $x,y,z$ is greater than 1.

Thanks.

By symmetry, the minimum value of the expression

$$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$$

under the constraint $(x^2-1)(y^2-1)(z^2-1)=8^3$ will occur when $x=y=z$.  From this, it follows that the minimum occurs when $x=y=z=3$, and the minimum is $1$.


Probability of getting a red ball when picking 5 from 10 in a bag There are 10 balls in the bag, 2 of them are red. We are picking randomly 5 balls from 10, what is the probability that at least one of picken 5 is red?
So far I found out that are $^{10}C_5 = 252 $ possibilties of picking 5 from 10.

It says to find the probability of picking at least $1$ red ball. So your total probability is simply,
$$P(X\geq1)=P(X=1) + P(X=2)$$
Now, this is a simply fancy notation for saying it is the sum of the probability that you pick $1$ red ball out of the $5$ and $2$ red balls out of the $5$. Then for $1$ red ball we get, $$P(X=1) = \frac{^2C_1}{^{10}C_5} \;\text{or} \;\frac{\binom21}{\binom {10}{5}}$$
And for $2$ red balls we get,
 $$P(X=2) =  \frac{^2C_2}{^{10}C_5}\;\text{or} \;\frac{\binom22}{\binom {10}{5}}$$ The sum of these two gives you your answer.


Can all naturals can be expressed as sums of prime powers of $\{3,5,7,13\}$? Define the set $$S=\left\{(p,k) \mid p\in\{3,5,7,13\} \land k \in\mathbb Z^{0+}\right\}.$$
The question is whether every natural number $n$ can be expressed as the sum of some subset $s\subseteq S$ of distinct pairs $(p,k)$ such that $$n=\sum_{(p,k)\in s}{p^k}.$$ To be clear, any pair in $S$ may be used at most once in the sum, though $k=0$ is allowed as an exponent. As an example, when using only the primes $\{3,5,7\}$, $24$ has two valid representations:
$$ 3^1+3^2+5^1+7^1 = 3^0+3^2+5^0+5^1+7^0+7^1 = 24. $$
Another way to describe the problem is to ask whether every natural can be described as the sum of four numbers, one each in bases 3, 5, 7, and 13, using only $0$ and $1$ digits. So equivalently, in that formulation, $$110_3+10_5+10_7=101_3+11_5+11_7=24.$$
Using $\{3,5,7,13\}$ gives 20 representations for $24$, which seemed a little spammy to include.
This post is a direct follow-up to this one, which posed the same question for $p\in\{3,5,7\}$. A nice proof was given that that set isn't sufficient to cover the naturals; the bottom line is that this arises because $$\frac{1}{3-1}+\frac{1}{5-1}+\frac{1}{7-1}=\frac{11}{12}<1.$$
This leaves open the interesting edge case of whether it would be possible for $\{3,5,7,13\}$, as $$\frac{1}{3-1}+\frac{1}{5-1}+\frac{1}{7-1}+\frac{1}{13-1}=1.$$

Note: To explain comments below, I originally thought I had a counterexample, but that was a rounding error. I'm leaving this question up as it seems like it still has merit. Clever arguments as to why $\{3,5,7,13\}$ should or should not work are also welcome.

Update
It actually seems like you may be able to limit this to proper prime powers after all, i.e. disallowing $p^0$ terms, for all $n\geq 113$. The only numbers I can find at first glance that require them are $\{1, 2, 4, 6, 11, 26, 31, 107, 112\}$ (though this is not proven!) So if you confine yourself to $n \geq 113$, each term $p^k$ in the sum must be distinct, no caveats required.
This seems like a cleaner formulation of the problem, but it's unclear to me which version would is more likely to be tractable or of greater interest. Input on this welcome.

I cannot confirm your counterexample. Here are the details so nobody else has to duplicate this effort. Following the method from Brian Moehring's answer, we want to find a value of $n$ such that $\log_5(3^n - 1), \log_7(3^n - 1), \log_{13}(3^n - 1)$ all have fractional parts close to $1$. If their integer parts are $n_5, n_7, n_{13}$, it then suffices to show that
$$\sum_{p = 3, 5, 7, 13} \left( \sum_{k=0}^{n_p} p^k \right) = \sum_{p = 3, 5, 7, 13} \frac{p^{n_p + 1} - 1}{p - 1} < 3^n - 1.$$
With $n = 338993010578$ we get (noting that $3^n$ is never a power of any other prime so $\lfloor \log_p(3^n - 1) \rfloor = \lfloor \log_p(3^n) \rfloor = \lfloor 3 \log_p n \rfloor$) we get (computations done in WolframAlpha)
$$n_3 = n - 1 = 338993010577$$
$$n_5 = \lfloor n \log_5 3 \rfloor = 231398728907$$
$$n_7 = \lfloor n \log_7 3 \rfloor = 191386990490$$
$$n_{13} = \lfloor n \log_{13} 3 \rfloor = 145196584918$$
and now it remains to show the desired inequality. If we try to compute the sums above directly we may run into rounding errors; we can do the following instead. First, since $\sum_{p = 3, 5, 7, 13} \frac{1}{p - 1} = 1$, we can add $1$ to both sides to convert the desired inequality into the slightly simpler form
$$\sum_{p= 3, 5, 7, 13} \frac{p^{n_p + 1}}{p - 1} < 3^n.$$
Second, we can divide both sides by $3^n$ to convert the inequality into the form
$$\sum_{p=3,5,7,13} \frac{3^{(n_p+1) \log_3 p - n}}{p - 1} < 1.$$
From here we see that to get the desired inequality it suffices (again using the fact that $\sum_{p=3,5,7, 13} \frac{1}{p-1} = 1$) that $3^{(n_p+1) \log_3 p - n} \le 1$ for each $p$ and that the inequality is strict for at least one $p$. Taking logs, equivalently we want $(n_p + 1) \log_3 p \le n$ or
$$n \log_p 3 \ge n_p + 1.$$
Unfortunately this is false for $p = 5, 7, 13$ since by definition we have $n \log_p 3 < n_p + 1$ (and we have equality for $p = 3$). So $3^{(n_p + 1) \log_3 p - n} > 1$ for $p = 5, 7, 13$ which implies that the inequality in Brian Moehring's answer cannot hold in this case for any value of $n$. The method can be salvaged if you show that one of the largest powers can't appear in the sum but this seems tricky.

Let $n_1, n_2, n_3, \dots$ be a nondecreasing sequence of integers $\geq 1$.
Let $s_0 = 0, s_k = s_{k-1} + n_k$ for $k \geq 1$.
Then every integer is the sum of a finite subsequence of the $n_k$ if and only if $n_k \geq s_{k-1} + 1$. Proof: if the condition is met then by induction over $k$ all $n \leq s_k$ are the sum of a subsequence of the first $k$ numbers. Otherwise if $k$ is the smallest $k$ such that the condition is not met, then $n_k - 1$ is not the sum of any subsequence.
If we sort the prime powers in non-descending order then $\frac{1}{p_1-1} + \dots + \frac{1}{p_4-1} \geq 1$ guarantees the condition above. If  the sum is less than $1$ then the condition above will fail if there are $4$ prime powers very closely together. A counter example can then be found by sorting the prime powers and calculating the sequence $n_k$ and $s_k$.
Proof: Assume we calculated up to $n_k$ and $s_k$, and the next $4$ powers are $a, b, c$ and $d$. Then $s_k = \frac{a-1}{2} + \frac{b-1}{4} + \frac{c-1}{6} + \frac{d-1}{12}$. Let $x$ be the smallest of $a, b, c, d$ then $s_k \geq \frac{x-1}{2} + \frac{x-1}{4} + \frac{x-1}{6} + \frac{x-1}{12} = x-1$, and $n_{k+1} = x \geq s_k +1$ as required.
There is no need for any or all of the numbers to be primes at all, as long as they are integers.


What is the geometric interpretation of a vector squared? I'm working through Introduction to Space Dynamics by William Tyrrell Thomson. I am having to do a lot of research to make it through even small parts, but I am unable to find information to make me confident enough to solve this question from the book:

  What is the geometric interpretation of $\left(\vec{a} + \vec{b}\right)^2$?

To start, I'm considering a simplified form: $\vec{c}^2, c = \vec{a} + \vec{b}$

This is where I get stuck, as I have not been able to find how to handle a vector multiplied by itself. Information one place states that a vector multiplied by itself is the same as the dot product of a vector with itself: $\vec{c}\cdot\vec{c}$. Other places I've found information which makes me think that multiplying a vector by another vector in the sense one would multiply a scalar by a scalar is not a valid operation to perform.

Which of these two is the case, or is it a third case I haven't considered?
Am I approaching the problem incorrectly?

$\vec{c}^2$ is an alternative notation for $\vec{c}\cdot\vec{c}=||\vec{c}||^2$

A motivation for this is that the formulas

$$||\vec{a}+\vec{b}||^2=||\vec{a}||^2+2\vec{a}\cdot\vec{b}+||\vec{b}||^2$$

$$||\vec{a}-\vec{b}||^2=||\vec{a}||^2-2\vec{a}\cdot\vec{b}+||\vec{b}||^2$$

and

$$(\vec{a}+\vec{b})\cdot(\vec{a}-\vec{b})=||\vec{a}||^2-||\vec{b}||^2$$

now becomes

$$(\vec{a}+\vec{b})^2=\vec{a}^2+2\vec{a}\cdot\vec{b}+\vec{b}^2$$

$$(\vec{a}-\vec{b})^2=\vec{a}^2-2\vec{a}\cdot\vec{b}+\vec{b}^2$$

and

$$(\vec{a}+\vec{b})\cdot(\vec{a}-\vec{b})=\vec{a}^2-\vec{b}^2$$

Similarities with the corresponding scalar identities make them easier to remember.

I think you are wise to focus on
$\vec{c} \cdot \vec{c}$, rather than $(\vec{a} + \vec{b})^2$.

Let $\vec{c}=(2,1)$. Then
$$\vec{c} \cdot \vec{c} = (2,1) \cdot (2,1) = 2 \cdot 2 + 1 \cdot 1 = 5 \;,$$
which is the square of the length of the vector $(2,1)$,
i.e., that vector has length $\sqrt{5}$.
The dot-product multiplication is "component-wise," i.e., product of $x$-coords,
plus product of $y$-coords.
So the geometric interpretation is: the square of the length of the vector.

(There is another prominent vector multiplication, the cross product.)


Let $M$ be a free module over a PID with finite rank, then any submodule $N \subset M$ is also free with finite rank I want to post the statement from Dummit and Foote (page460), but it is so long that I have to post a shorter one from another book.

Q2: I want to make sure I understand this. We apply induction on $t > 0$, so that means anything $<t$ is assumed to be true. Therefore $N \cap \ker g$ being a submodule of $N$ with rank $t -1 < t$ is assumed to be a free of finite rank $t-1.$ So what they are saying is to adjoin the one element $a_1x_1$ to the finite set of basis $B_{t-1}$ is a finite basis set. So I think this is actually strong induction? In this instance, we don't even need to prove the $t + 1$ case?
Q2: Again by reasoning above assume it is true for $r > 0$ and any all integers less than $r$, then $\ker g$ is a submodule of rank $r -1.$ Now what I don't get is it says
$\exists \{x_2, \dots,x_{r}\}$ basis (there is exactly $r-1$ in this set) for $\ker g$ such that $\{a_2x_2,\dots, a_rx_r\}$ basis for $N \cap \ker g$ such that $a_i | a_{i+1}.$
It feels like we somehow already know that elements of the form $a_ix_i$ with $a_i|a_{i+1}$ are going to be basis elements for $N\cap \ker g$ to make this induction. I feel like there is some circular logic going on. The induction feels like one big verification. I want to know how we know the submodule has to be generated by elements that look that in the first place.

Both of your questions are labelled as Q2. They have more to do with the principle of induction than with modules.
Anyhow, in the first instance you are quite right that this is a strong induction. This means that they assume that the statement is true for all numbers $\leq t-1$ and then have to prove it for $t$.
The strong induction could alternatively be phrased as follows: Assume that the statement is true for all numbers $\leq t$ and then they would need to prove it for $t+1$. Which version you choose is a matter of notation, not of the actual mathematical content.

The second issue is similar. At the stage that you say you don't get, the author is using the inductive hypothesis (remember, you are proving the statement for $r$ so you are allowed to use it for $r-1$). This is not circular, because there is extra work to be done to transfer from
a basis $\{a_2x_2, \dots ,a_rx_r\}$ for $N \cap \ker g$ such that $a_i|a_{i+1}$ (induction hypothesis = statement for $r-1$)
to
a basis $\{a_1x_1,a_2x_2, \dots ,a_rx_r\}$ for $N$ such that $a_i|a_{i+1}$ (your goal = statement for $r$).

Following the comment, I now see that you are interested in "how would one think about that in the first place" rather than in the details of the proof. The prototypical example I would have in mind is a free $\mathbb{Z}$-module $M=\mathbb{Z}^n$. Choose a standard basis $x_i = (0,\dots ,0,1,0, \dots, 0)$ for $i=1, \dots, n$. What do the submodules of $M$ look like? For example, there is a submodule $N_1 = \mathbb{Z}x_1$ spanned by $x_1$. This has a very nice form already. But there is also a submodule $N_2 = \mathbb{Z}(3x_5-2x_{10}) + \mathbb{Z}7x_9$ spanned by $3x_5-2x_{10}$ and $7x_9$, which you may think is ugly. But wait! It's only ugly with respect to this basis of $M$. The theorem says that there is another basis $y_1, \dots, y_n$ of $M$ such that $N_2$ is a nice direct sum of two multiples of basis vectors, ie $N$ has a basis $\{ a_1y_1, a_2y_2 \}$ for some $a_1, a_2$.

There are two inductions one is on $t=$rank($N$), one is on $r=$rank($M$).
Actually the induction on $t$ doesn't prove anything, that paragraph can be deleted.
induction on $r$ part need a result to obtain ker($g$) is free: submodule of a free $R$-module is free.
This induction is actually just repeat the process of how you get $a_1$ to get $a_2$ then $a_3$, ...


Prove that $C\exp(x)$ is the only set of functions for which $f(x) = f'(x)$ I was wondering on the following and I probably know the answer already: NO.
Is there another number with similar properties as $e$? So that the derivative of $\exp(x)$ is the same as the function itself.
I can guess that it's probably not, because otherwise $e$ wouldn't be that special, but is there any proof of it?

Of course $C e^x$ has the same property for any $C$ (including $C = 0$). But these are the only ones.

Proposition: Let $f : \mathbb{R} \to \mathbb{R}$ be a differentiable function such that $f(0) = 1$ and $f'(x) = f(x)$. Then it must be the case that $f = e^x$.

Proof. Let $g(x) = f(x) e^{-x}$. Then

$$g'(x) = -f(x) e^{-x} + f'(x) e^{-x} = (f'(x) - f(x)) e^{-x} = 0$$

by assumption, so $g$ is constant. But $g(0) = 1$, so $g(x) = 1$ identically.

N.B. Note that it is also true that $e^{x+c}$ has the same property for any $c$. Thus there exists a function $g(c)$ such that $e^{x+c} = g(c) e^x = e^c g(x)$, and setting $c = 0$, then $x = 0$, we conclude that $g(c) = e^c$, hence $e^{x+c} = e^x e^c$.

This observation generalizes to any differential equation with translation symmetry. Apply it to the differential equation $f''(x) + f(x) = 0$ and you get the angle addition formulas for sine and cosine.

Note that $e$ is defined by the following Limit: $e=\lim_{n \rightarrow \infty}(1+ \frac{1}{n})^n$. Then: $e^x=\lim_{n \rightarrow \infty}(1+ \frac{1}{n})^{nx}$. Applying the Definition of the derivative $f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h)-f(x)}{h}$ one obtains: $(e^x)'=\lim_{h \rightarrow 0} \frac{ \lim_{n \rightarrow \infty}((1+ \frac{1}{n})^{n(x+h)}-(1+ \frac{1}{n})^{nx})}{h} = \lim_{h \rightarrow 0}(  \lim_{n \rightarrow \infty}(1+\frac{1}{n})^{nx} \lim_{n \rightarrow \infty}(\frac{(1+\frac{1}{n})^{nh}-1}{h}))$

$= e^x \lim_{h \rightarrow 0} \lim_{n \rightarrow \infty}(\frac{(1+\frac{1}{n})^{nh}-1}{h})$.

Now one can replace $h$ by $n$ by the relation $h= \frac{C}{n}$ with a finite constant $C$, because if $n \rightarrow \infty$ then $h$ tends to Zero. Hence:

$\lim_{h \rightarrow 0} \lim_{n \rightarrow \infty}(\frac{(1+\frac{1}{n})^{nh}-1}{h}) = \lim_{h \rightarrow 0} (\frac{(1+\frac{h}{C})^{C}-1}{h}) = \lim_{h \rightarrow 0} (\frac{(1+C \frac{h}{C} + \frac{C(C-1)}{2}(\frac{h}{C})^2+O(h^3)-1}{h}) = \lim_{h \rightarrow 0} (1 + \frac{C(C-1)}{2}\frac{h}{C^2}+O(h^2)) = 1$

Therefore $(Ce^x)'=C(e^x)'=Ce^x$.

q.e.d.


Introductory Topology Book Recommendation for Economics Would you please share your 2 cent on book recommendation for introductory topology book to graduate student in Economics.

Have exposure to the first half of the yearlong analysis course in the following books:

Baby Rudin.

Understanding Analysis by Abbott.

The Way of Analysis by Strichartz.

Yet Another Introduction to Analysis by Bryant.

The main reason for searching a good introductory topology book is to gain formal exposure to concepts like connected spaces, metri, pseudo metric spaces, products/quotients, separation axiom, ordered sets, compactification, etc.

My friend recommended Real Analysis with Economic Applications by Ok and if anybody had exposure with his book, also please share your experience with the book.

Thanks.

I don't know what you're getting at by mentioning you're in economics, but if you have some first year analysis then Munkres' book is a fantastic introduction.

You may consult the following two books which are very fundamental & easy to understand;

1) Topology & Modern Analysis  by  G. F. Simmon
2) General Topology            by  Seymour Lipschutz


Find sum of product of all possible triplets in an array in O(n)? For example,
If array A = { 1, 2, 3 ,4 }

possible triplets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} and their products are 6, 8, 12, 24 respectively.

So final answer is 50.

I found a O(n) time code, but i can't understand how it is working.

Initially count1 array stores the original array and all other arrays has only 0 elements.

int sum = 0;

B[n-1] = count1[n];
for(i=n-2;i>=0;i--)
    B[i] = (B[i+1] + count1[i+1]);

for(i=1;i<n-1;i++)
    C[i] = (count1[i+1] * B[i+1]);

D[n-2] = C[n-2];
for(i=n-3;i>=1;i--)
    D[i] = (D[i+1] + C[i]);

for(i=0;i<n-2;i++)
    sum = (sum + count1[i+1] * D[i+1]);

If Someone wants to know how above code works,

read this thread :
https://www.quora.com/How-do-I-find-the-sum-of-products-of-all-possible-k-numbers-from-an-array-of-N-numbers-k-n

The code is a bit more tricky than it needs to be to achieve $O(n)$. Let $\sigma_k=\sum_ix_i^k$ (where the $x_i$ are the numbers). Then you basically want $\frac16\sigma_1^3$, but that counts some products with repeated factors. Products with one factor repeated twice are counted with weight $\frac12$, so we have to subtract $\frac12\sigma_1\sigma_2$, and then products with a single factor cubed are counted with weight $\frac16-\frac12=-\frac13$, so we have to add $\frac13\sigma_3$, for a total of $\frac16\left(\sigma_1^3-3\sigma_1\sigma_2+2\sigma_3\right)$. In your example, $\sigma_1=10$, $\sigma_2=30$ and $\sigma_3=100$, so the result is $\frac16\left(10^3-3\cdot10\cdot30+2\cdot100\right)=50$.

In  above shared Link, he used dynamic porgramming bottom up approach that difficult to think but easy to implement here i am sharing my top down approach of dp for this concept..

    /*
     * To change this license header, choose License Headers in Project Properties.
     * To change this template file, choose Tools | Templates
     * and open the template in the editor.
 */
package EasyProblems;

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author Hemant Dhanuka
 */
public class Sum_OfProduct_Ofall_K_numbers_From_Array {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();
        int a[] = new int[N];
        for (int l = 0; l < N; l++) {
            a[l] = s.nextInt();
        }
        int k = s.nextInt();

        long dp[][] = new long[N][k];
        for (long d[] : dp) {
            Arrays.fill(d, -1);

        }
        //System.out.println(dp[1][1]);
        long ans = sum(a.length - 1, k - 1, a, dp);
        System.out.println(ans);

    }

    static long sum(int n, int k, int a[], long dp[][]) {

        if (k == -1) {
            return 1;
        }

        if (n == -1) {
            return 0;
        }

        if (dp[n][k] != -1) {
            return dp[n][k];
        }
        //if picked
        long ans1 = ((long) a[n]) * sum(n - 1, k - 1, a, dp);

        //if not picked
        long ans2 = sum(n - 1, k, a, dp);
        dp[n][k] = ans1 + ans2;
        return ans1 + ans2;
    }
}


Find the edges in a Hypergraph I have 8 vertices. I need to form hyperedges such that each edge should contain exactly 4 vertices and each edge should intersect with every other edge at exactly 2 vertices. How many edges are there(maximum)? I believe the answer to be 7, but how?. I got the answer by listing down the possible combinations. Is there an algorithmic approach? I need to find a generalized approach for this. Any help would be much appreciated. Thank You
Maximum number of edges on a graph

The maximum is indeed $7$.
Upper bound
With each edge $e$ we associate $8$ triples ($3$-element sets) of vertices, namely, the $4$ triples contained in $e$ and the $4$ triples disjoint from $e$. No triple is associated with two different edges; this follows from the fact that the edges intersect in exactly two vertices. If we have $n$ edges then we have $8n$ distinct triples of vertices. Since there are just $8$ vertices, it follows that $\8n\le\binom83$, i.e., $n\le\binom83/8=7$.
Lower bound
In fact, on a set of just $7$ points, we can family a family of $7$ $4$-sets such that any two of them intersect in exactly two points. Note that the complements of the $4$-sets are $3$-sets, and two $4$-sets intersect in exactly two points if and only if their complements intersect in exactly one point. Thus an equivalent problem is to find a system of $7$ triples on $7$ points such that any two triples intersect in exactly one point. This is a well known construction; look up Steiner triple system or Fano plane.

I suppose when you say that the "answer is 7", you refer to the minimal number of hyperedges on your hypergraph for a valid solution.
Let's clarify things algebraically. You have a set $V = \{ v_i | i \in [[1, n]]\}$ of $n$ vertices, and a set $E$ of hyperedges over V (ie, $E \subset P(V)$). You are looking for the minimal number of hyperedges $m_e$ such that the condition "all hyperedges contains $m_v$ vertices, and the intersection of any two hyperedges contains $m_i$ vertices".
In this case, the solution is actually trivial: no hyperedges at all. But since this is a bit of a dumb problem (since the solution is always trivial), I suppose you might have the additional condition "all vertices must be covered by at least one hyperedge".
In this case we have $n = 8$, $m_v = 4$ and $m_i = 2$. We'll use an algorithmic approach. Since there is no distinctive factor between each vertex at this point, they are symmetrical, in the sense that any can be picked as our starting point. Our goal is thus to cover each vertex, while keeping the conditions $\forall e \in E, card(e) = m_v$ and $\forall e_1, e_2 \in E, card(e_1 \cap e_2) = m_i$.
So we start by covering a set of $m_v$ vertices with a first edge $e_1 = \{v_1, v_2, v_3, v_4\}$. Both conditions are still true (since there is no second edge to intersect with, the second is 'trivially true'). Note that here, symmetry is broken: some edges are covered by one hyperedge, others are covered by none. However, by symmetry among the hyperedges that are covered by none, we can pick any $m_v - m_i = 2$ extra vertices, and make an edge with those, and $m_i$ of vertices from the existing hyperedge. This will make it so our new hyperedge indeed has $m_v$ vertices. In our case, we pick the hyperedge $e_2 = \{v_1, v_2, v_5, v_6\}$. Both conditions are still true.
At this point we can notice that symmetry is broken again. Vertices $v_1$ and $v_2$ are covered by the 2 hyperedges; vertices $v_3$ and $v_4$ are covered by 1 hyperedge; vertices $v_5$ and $v_6$ are covered by another 1 hyperedge; and vertices $v_7$ and $v_8$ are not covered.
Our algorithm requires us to minimize the total number of hyperedges, while making a full cover, and respecting some conditions. So we'll start by trying to cover the uncovered vertices. This implies that our new hyperedge HAS to cover $m_v - m_i = 2$ "new" (uncovered) vertices, and intersect over $m_i = 2$ vertices, in a way that doesn't break the intersection condition for any of our previous hyperedges.
Such a hyperedge must then contain $v_7$ and $v_8$, and two other vertices. Among the vertices that are already covered, we have to take $m_i$ vertices such that the intersection condition is respected. The only set of $m_i$ extra vertices that respects this condition is the set $\{v_1, v_2\}$, thus resulting in the hyperedge $e_3 = \{v_1, v_2, v_7, v_8\}$. Additionally, our problem is solved at this point.
Precisely: $E = \{\{v_1, v_2, v_3, v_4\}, \{v_1, v_2, v_5, v_6\}, \{v_1, v_2, v_7, v_8\}\}$. As you can see, in this setup, all vertices are covered, and the 2-by-2 intersections of hyperedges only ever have 2 elements (the set $\{v_1, v_2\}$). Finally, $m_e = 3$, not $7$.
NB:

This is a naive algorithm I came up with on the spot. It'd take time and skills (which I'm not sure I really have) to prove it.
Consequently, I'm not sure how well it generalizes. For example, this algorithm would not find non-minimal solutions such as $E = \{\{v_1, v_2, v_3, v_4\}, \{v_3, v_4, v_5, v_6\}, \{v_5, v_6, v_7, v_8\}, \{v_7, v_8, v_1, v_2\}\}$.
My gut feeling is that symmetry arguments are important for this problem, and that group theory can play a role. I wouldn't know how to justify this gut feeling though.
Finding the set of all sets of hyperedges which are a solution to this restricted covering problem will require group theory, if only to handle counting all distinct valid re-labellings of vertices.
There is probably a way to define group theoretic equivalence classes of solutions and thus some form of hypergraph quotients based on this problem.

If anyone has some references on this problem, or hypergraphs in general: I'm interested as well.


Confused about modular notations I am little confused about the notations used in two articles at wikipedia.

According to the page on Fermat Primality test

$
a^{p-1}\equiv 1 \pmod{m}$ means that when $a^{p-1}$ is divided by $m$, the remainder is 1.

And according to the page on Modular Exponential

$c \equiv b^e \pmod{m}$ means that when $b^e$ is divided by $m$, the remainder is $c$.

Am I interpreting them wrong? or both of them are right? Can someone please clarify them to me?

Update: So given an equation say $x \equiv y \pmod{m}$, how do we interpret it? $y$ divided by $m$ gives $x$ as remainder or $x$ divided by $m$ gives $y$ as remainder?

They are both correct. The congruence sign is symmetric so c ≡ b^e is the same as b^e ≡ c.

However what it really means is this: a≡b (mod m) if and only if m|a-b (i.e. m divides a-b).

Mod, or modulas, is a binary operator, like '+'.  You write a mod b.  Writing a (mod b) is a bit like writing a (+ b).  That said, you might see a note in with your equations.  Just I might write time = money (minus taxes as previously discussed), that wordy chunk is part of my verbiage instead of my equation.

a mod b means that the remainder of dividing a by b.  For example, 27 mod 5 = 1 or (27 mod 5) + 2 = 3.

Neither of the equations listed makes any sense, because mod is binary.   You probably meant:

(a^(p-1)) mod m = 1

and

*c = (b^e) mod m


Is my proof that $(p \wedge \neg p) \Rightarrow q$ correct? I was asked by a professor a while ago to prove $(p \wedge \neg p)$ implies $q$.  Whether through laziness or cleverness, I came up with the following proof:

$p \wedge \neg p$ (by assumption).
Assume by way of contradiction $\neg q$.
$p \wedge \neg p$, therefore $p$ (I forget what this rule is called).
Similarly, $p \wedge \neg p$, therefore $\neg p$.
We have both $p$ and $\neg p$, a contradiction.
Therefore, our assumption, $\neg q$, must have been false, i.e., $q$ is true, the desired result.

Is this right?  I keep going either way about it to myself.  On the one hand, it definitely feels circular.  On the other hand, it seems contain all the correct elements of a contradiction proof.

EDIT: many commenters seem concerned about what I am allowed or not allowed to "use".  I am allowed to use whatever you feel mathematically is correct, and not allowed to use things that aren't.  The context of the exercise was not a course in logic, or even in mathematics.  It was a computer science class in algorithms.  I think the professer just wanted to get a feel for our understanding of logic, and also wanted to demonstrate why inconsistant assumptions can be used to prove anything.  I don't even remember if the assignment was graded, or if it was what I got.  I do remember that when I presented it on the board that it (obviously) wasn't quite what the professor was looking for.

Given the tools you have chosen to work with, you have a valid proof of $p\land \neg p\Rightarrow \neg\neg q$. Formally you would need an extra step where you point out that $\neg\neg q$ is the same as $q$, but that's not the real problem here.

The reason why it feels circular is that what you're being asked to prove is one of several possible logical axioms that can be used to justify proof by contradiction in the first place, so the difference between the rule you use and the conclusion is only very slight. It is then natural to wonder whether you're supposed to prove it from more primitive ingredients than proof by contradiction. However, what those particular ingredients might be varies considerably between formalizations of logic.

Basically one can choose any of quite a lot of possible logical foundations to use as axioms, and then prove that all of the other ones follow as logical consequences of the axioms we have chosen. (For pedants in the audience, this is assuming that the axiom sets in question are all for classical first-order logic, blah blah blah). In ordinary mathematical reasoning one tacitly allows all of those standard consequences as single proof steps that need no explanation because the reader is always expected to be able to formalize them in his own favorite logic if he wants to. However, that won't work here, because then there wouldn't be anything for you to prove! So it is necessary to be explicit about which proof steps one allows here, because otherwise your exercise just implodes.

If one happens to choose an axiom set that includes $p\land \neg p\Rightarrow q$ as an axiom, then there's nothing to prove -- a full and complete proof would consist of the words "it's an axiom". But if you choose not to make it an axiom, then what counts as a valid proof depends critically upon what you do consider axioms.

If you do not have a particular formal system you must do your proof in, then I suspect that the expected solution is simply by truth tables -- for each of the possible 4 combinations of whether $p$ and $q$ are true or false, show that $p\land \neg p\Rightarrow q$ evaluates to true.

Then you have proved "$p\land \neg p\Rightarrow q$ is always true" which is just a more convoluted way of saying that you have proved $p\land \neg p\Rightarrow q$ itself.

The answer is: yes, your proof is correct.

Instead of reductio ad absurdum, your can use the principle of explosion. Falsum $\bot$ follows from $p$ and $\neg p$, and ex falso sequitur quodlibet, so one can conclude $q$ directly from $\bot$. This is trivial though, whereas your proof shows the strength of double negation elimination.


Solving the equation $z^7=-1$ Solve the equation $z^7=-1$

My attempt:

$$z=x+yi$$

$$(x+yi)^7+1=0$$

$$(x^2+2yi-y^2)^3(x+yi)+1=0$$

but now it's start to look ugly.

I'm sure that there is a simple way

HINT:
Try using this,(one of the solution)

$$
z^7=e^{i\pi}
\\z=e^{i\frac{\pi}{7}}
$$


Criteria to determine if equation is solvable in radicals? Assume we have an equation:
$$\sum_{i=0}^p a_ix^i=0$$
where p is prime and the left side polynomial is irreducible. Is there a method or algorithm to determine if this equation is solvable in radicals?

EDITED

I mean is there a general method to determine if it is solvable in radicals without computing an appropriate Galois group.

There are in fact some criteria that allow you to determine if the polynomial is solvable by radicals (from here thereon solvable) in some special cases!

The plainest one is that if the degree is less than 5, the polynomial is solvable.

If your polynomial is of the form $f(T)=g(T^k)$ and $g$ is solvable, then $f$ is solvable.

A more exciting one: if $f$ is irreducible of prime odd degree (as it is the case), then $f$ is solvable iff its splitting field is generated by any two of its roots.

In particular, this means that if $f$ has at least two real roots and one complex root then it is NOT solvable.

If you want a truly general algorithm, I am afraid I have no better way than jumping through the hoop of Galois theory and determining if its Galois group is solvable.

EDIT: I did some digging, and S. Landau and G. Miller have you covered:

  A polynomial time algorithm is presented for the founding question of Galois theory: determining solvability by radicals of a monic irreducible polynomial over the integers.

Their approach passes through Galois theory though, but hey polynomial time!

I'm not sure why you are considering only prime $p $...

It is proved in Galois theory that polynomials of degree  $5$ and up are not solvable by radicals...  that is there is no closed form that works for all such polynomials...


Diffeomorphism with only hyperbolic periodic points has finitely many periodic points (Morse-Smale) Came across the following question during a course Chaotic Dynamical Systems:

  If a diffeomorphism $f:I\to I$ is Morse-Smale (i.e. has only hyperbolic periodic points), then it has finitely many periodic points. ($I:=[0,1]$)

I assume the prove is done by contradiction that a Morse-Smale diffeo can't have infinitely many periodic points for then it should have a non-hyperbolic fixed point; i.e. $\exists p\in I$ s.t. $|(f^n)'(p)|=1$ by the Mean Value Theorem (somehow). The chapter where this question is asked talks about structural stability in the sense of $C^r-\epsilon$-distance of two conjugate functions. So I expect the prove to contain some structural stability properties. I have no clue how to use this $C^r-$distance in proving this. Can anyone help me out?

Special note: $$d_{C^r}(f,g)=\sup_{x\in\mathbb{R}}\{|f-g|,|f^{(1)}-g^{(1)}|,...,|f^{(r)}-g^{(r)}|\}<\epsilon$$ for some $\epsilon>0$ must imply $f$~$g$. Also, I just discovered that a map near a hyperbolic fixed point is always locally topologically conjugate to it's derivative. Maybe this also holds for maps near hyperbolic periodic points?

I might as well answer my own question myself by now. To finish the prove, one must note that a diffeo is monotone increasing or if it's decreasing, then its second iterate will be increasing. So w.l.o.g. let $f$ be monotonely increasing. Since $f$ has infinitely many periodic points, it must have infinitely many fixed points for it should cross the line $y=x$ infinitely many times. Now, as I stated in the comments with some help of others, there must exist an infinite sequence of periodic points converging to some fixed point. But hyperbolic fixed points must have a neighbourhood such that this nbh does not contain any other periodic points. Hence, a contradiction since $f$ should only have hyperbolic periodic points by assumption. We conclude that Morse-Smale diffeos have only finitely many periodic points. $\Box$.


maximum of iid exponential random variables I have a sequence of iid r.v. $(X_n,n\geq 1), X_i\sim \mathcal{E}(1)$.

I am studying properties of the random variable $T_n = \max({X_1,\ldots,X_n})$.
Computing the cdf I get $$\mathbb{P}\left(\{T_n\leq t\}\right)= \prod_{i=1}^n\mathbb{P}(\{X_i\leq t\}) = F_X(t)^n = (1-e^{-t})^n$$

I was asked to study the convergence in distribution of $T_n-\log(n)$ I get that $$
\begin{split}
\mathbb{P}(\{T_n-\log n\leq t\})
  &=\mathbb{P}(\{T_n\leq t+\log n\}) \\
  &= \left(1-e^{-t-\log n}\right)^n \\
  &= \left(1+\frac{-e^{-t}}{n}\right)^n \to e^{((-e)^{-t})}, \quad n\to +\infty
\end{split}$$

But I was also asked to compute the expectation of $T_n$. Now, I know that since the $X_i$ are positive then the $T_n$ will also be positive and thus I can compute $$\mathbb{E}(T_n) = \int_{0}^{+\infty}\mathbb{P}(\{T_n>t\})dt$$

But $$\int_{0}^{+\infty}\mathbb{P}(\{T_n>t\})dt = \int_{0}^{+\infty}1-(1-e^{-t})^n dt = x\big|^{+\infty}_0 - \int_{0}^{+\infty}(1-e^{-t})^n dt$$ and I tried, for instance, to solve the last integral by substitution $y = (1-e^{-t})$ but I don't get something "easy" to compute, and wolfram alpha also does not provide me an answer. Am I on the wrong track?

Expand $(1-e^{-t})^{n}$ using Binomial theorem. you will be able to compute the integral easily.

Use 1-a^n = (1-a)(1+a+a^2+...+a^(n-1)) , change of variables from exp(-t) --> x  and then integrate to get required answer as 1+1/2+1/3+...+1/n (which varies as log n)


Providing initial conditions for differential equation? - Phase portrait I'm given the system of differential equations \begin{align*} \begin{cases} x'(t) &= y(1 + x^2 + y^2) \\ y'(t) &= x (1 + x^2 + y^2) \end{cases} \end{align*} I need to plot (with Maple) the phase portrait of this, and also the direction field. From this I need to determine the nature and stability of the critical point $(0, 0)$. Now, for this critical point we have the linearized system (which results when you set all the non-linear terms zero) \begin{align*} \begin{pmatrix} \tilde{x}'(t) \\ \tilde{y}'(t) \end{pmatrix}  = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} \tilde{x}(t) \\ \tilde{y}(t) \end{pmatrix}  \end{align*} I used $\tilde{x} $ notation to make clear this is an approximation and not the same system as the original one. The eigenvalues of this matrix are $\lambda = \pm 1$, which means this critical point is a saddle point, and this is always unstable.

Now, I was wondering if there some trick to provide 'nice' initial conditions, such that the phase portrait shows clearly the solution curves? I entered this in maple:

DEplot([diff(x(t), t) = y(t)*(1+x(t)^2+y(t)^2), diff(y(t), t) = x(t)*(1+x(t)^2+y(t)^2)],
    [x(t), y(t)], t = 0 .. 5, [[x(0) = -2, y(0) = -2], [x(0) = 3, y(0) = 0]],
    x = -3 .. 3, y = -5 .. 5, arrows = medium, stepsize = 0.05, linecolor = blue)

The result I got was:

But I'm not satisfied with this, because the solution curves are not nicely shown. How does one specify the initial conditions such that this happens? Is it just by trial and error?

Try and choose initial conditions "earlier" along the direction curves.

Eg: Something like $x(0)=-3$, $y(0)=2$ should get you a good picture of a solution curve on the left of the origin.

Are you after some visualisation  similar to the diagram below?


How to integrate $\int\frac{dx}{(A^2+x^2)^{3/2}}$ I have the following to integrate:

$$\int\frac{dx}{(A^2+x^2)^{3/2}}$$

Where, $A$ is a constant.

Not really sure what technique to use. Any hint would be helpful.

This is actually a simple integral. Use the substitution

$$x = A\tan (y) ~~~~~~~ \text{d}x = A\sec^2(y)\ \text{d}y$$

In this way

$$(A^2 + x^2)^{3/2} = (A^2\tan^2(y) + A^2)^{3/2} = A^3\sec^3(y)$$

and $y = \arctan(x/A)$

So your integration becomes

$$\frac{1}{A^2}\int\cos(y)\ \text{d}y$$

which is trivial.

Final answer:

$$\frac{\sin(\arctan(x/A))}{A^2}$$


Number of subsets when each pair of distinct elements is contained in exactly one subset Let $E$ be a set of cardinality $n$. Suppose $M_1, M_2, .. , M_m$ are
   distinct proper subsets of $E$ such that for each pair of distinct elements $x_1, x_2\in E$, there is exactly one $M_i\supseteq\{x_1,x_2\}$. Prove that $m \ge n$.

It's obvious $n$ has to be greater or equal to $3$. Also, for $n=3$, it's easy to prove it, but I have no idea how to extend it. I think a proof using induction by $n$ is possible.

Solution for general case

Let $E=\{1,2,\ldots, n\}$. Define column vectors $v_j=(v_{ij})^T$ with $v_{ij}= \mathbf{1}_{M_j}(i)$ which gives $1$ if $i\in M_j$ and $0$ otherwise. Then $M=(v_{ij})$ is an $n\times m$ matrix consisting of $0$, $1$ entries. Our goal is to prove that $\mathrm{rank}(M)=n$. We will show this by proving that the rows of $M$ are linearly independent. Then the columns $v_j$ form an spanning set for $\mathbb{R}^n$ and it will follow that $m\geq n$.

According to the assumptions, for each $i$,  there are at least two sets $M_{j_1}$ and $M_{j_2}$ such that $i\in M_{j_1}\cap M_{j_2}$. Otherwise, the pairs $\{i,1\}$, $\ldots$, $\{i,n\}$ are all included in one set $M_k$ which gives $M_k=E$. Thus, we see that any row of $M$ contains at least two $1$'s.

Consider a $n\times n$ matrix $MM^T$. If $MM^T$ is nonsingular then the rows of $M$ are linearly independent. For the proof, let $M^T x = 0$ for some $x\in\mathbb{R}^n$. Then $MM^T x = 0$. Since $MM^T$ is nonsingular, $x=0$. Write the rows of $M$ as $R_1, \ldots , R_n$. Then $MM^T = (b_{ij})$ with the dot product $b_{ij}=R_i\cdot R_j$.

Since any row has at least two $1$'s, we have $b_{ii}\geq 2$. Since any pair $\{i, j\}$ with $i \neq j$ is in exactly one $M_k$, we have $b_{ij}=1$ for $i\neq j$. Writing the determinant as a multlinear function on columns, we obtain that $$\det MM^T \geq 1+n.$$
Therefore we conclude that $MM^T$ is nonsingular, and we are done.

Proof of the determinant inequality

Let $A=(a_{ij})$ be a $n\times n$   matrix with $a_{ij} = 1$ for $i\neq j$, and $a_{ii}\geq 2$. Then $\det A \geq 1+n$. For the proof, let $J=(1, 1, \ldots, 1)^T$, and write the determinant as a multilinear function on columns:
$$
\begin{align}
\det A &= \det \left((a_{11}-1) e_1 + J, \ldots, (a_{nn}-1)e_n + J\right)\\
&=\det \left((a_{11}-1)e_1, \ldots, (a_{nn}-1)e_n \right) \\ &+ \sum_{j=1}^n \det \left((a_{11}-1)e_1, \ldots, J (j-\textrm{th column}), \ldots,  (a_{nn}-1)e_n \right)\\
&=\prod_{i=1}^n (a_{ii}-1) + \sum_{j=1}^n \frac{\prod_{i=1}^n (a_{ii}-1)}{a_{jj}-1}\geq 1 + n.
\end{align}$$

An Example for $n=4$

An example of such matrix $M$ is
$$
M=\begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\    1 & 0 & 0 & 0 & 1
\end{pmatrix},  \ \ \
MM^T=\begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}, \ \ \ \det MM^T = 16.$$

Possibility of $m=n$

Note that it is possible to have $n$ distinct subsets $M_1, \ldots, M_n$ satisfying the requirements. Let $M_1=\{2,3,\ldots, n \}$, $M_2=\{1,2\}$, $M_3=\{1,3\}$, $\ldots$, $M_n = \{1, n\}$.

Take $E = \{ x_1, x_2\}$.
There exist a set $M_{1,2}$ such that $x_1, x_2 \in M_{1,2}$.

But then $M_{1,2} = E$. This is a direct contradiction to the theorem.

Thus this doesn't work for $n<3$.


Stopping the "Will I need this for the test" question I am a college professor in the American education system and find that the major concern of my students is trying to determine the specific techniques or problems which I will ask on the exam. This is the typical "will this be on the test?" question.

I find this to be a major detraction from students education. Students seem to have the notion that they can discard a lot of ideas and just memorize a few specific problems in order to pass the class. Given the philosophy of some teachers to "teach to the test" when in a standardized testing environment, this does not surprise me.

This stressful approach to education seems to make student overlook major themes in each class and themes in the subject as a whole. Even worse, once they land in classes like calculus 3 and real analysis, the effects of this point of view rears its head in an ugly way.

My question is:

  How can we turn students away from this way of thinking?

The psychology of all this is quite simple, IMHO: no matter how much a student may WANT to learn mathematics, the fact is that she MUST earn acceptable grades, and success in the former doesn't always guarantee the latter. It's a basic hierarchy-of-needs issue. If a student strives wholeheartedly to learn the material with no specific thought given to exam results, the result is often a worse grade than if the student had striven solely to do as well as possible on exams. Any responsible student should and must ask endless questions about what's going to be on each exam, and is given no choice but to prioritize grades over learning, since a student's academic reputation, financial aid, and prospects for employment and/or admissions to successive levels of schooling all depend much more on GPA than on less tangible qualities like subject matter mastery. Of course, taking a long view, one easily understands how crucial such mastery will be in the long term, but students rarely have the luxury of adopting such a perspective when they know that a single red "73" scrawled at the top of the next exam may literally cost them thousands of dollars in the short term. The solution? There isn't one, practically speaking. Theoretically, we'd just have to scrap our entire model of education and replace it with something new.

"Will I need this for the test?”

Being a student myself, I know that the moment the teacher answers this question with a 'Yes/No' I am already in the mindset that I should only focus on learning the things that I know will be on the exam, whilst completely ignoring anything I don't need to know. Extra knowledge might be useful to me in the future, but right now what matters to me is getting a good grade.

That being said, if the teacher were to say to me "Everything I have taught you in class is examinable" everything changes.

My mindset suddenly changes to paying attention to everything, trying my best to understand everything. If getting my grade is what matters, I can now only achieve this by building on my knowledge of everything I have been taught in class. This is also useful in the way that I now find every class important, making me want to pay attention more and more relectunt to skip classes where I know I could be missing important things related to the exam.


Property of continuous maps from $S^3$ to $\mathbb{C}$. Let $p=e^{2\pi i/m}$ for some integer $m>1$. If $f:S^3\rightarrow\mathbb{C}$ is a continuous map, prove that $\sum_{k=1}^mp^{-k}f(p^kz_1,p^kz_2)=0$ for some point $(z_1,z_2)\in S^3$.

In class we have just learned the Borusk-Ulam theorem for maps from $S^2\rightarrow \mathbb{R}^2$. I also have access to the following fact. There exist no continuous maps $g:S^3\rightarrow S^1$ such that $g(pz_1,pz_2)=pg(z_1,z_2)$ for all $(z_1,z_2)\in S^3$.

I'm just not seeing how to deconstruct this problem. Any help is greatly appreciated.

Call your map $g$ (you mean to sum over k, not i). Is it clear that $g(pz,pw) = p g(z,w)$? If $g$ was always nonzero, then consider the map $h(z,w) = g(z,w)/|g(z,w)|$. This is a map to the circle with $h(pz,pw) = ph(z,w)$. Contradiction


Linear algebra and Multivariable calculus prerequisites for Stochastic Calculus Which topics are considered "graduate-level" for the following subjects:

Linear algebra
Multivariable calculus

On Internet, it is said that you need "graduate level" Linear algebra and multi-variable calculus for understanding Stochastic calculus, but topics are not mentioned.

Basically, you need to understand the abstract properties of Linear Algebra, e.g. group theoretic properties, etc. This is in contrast to "undergraduate" Linear Algebra, which focuses primarily on computational aspects and some basic algebraic properties (e.g. rank-nullity theorem, etc.).

For graduate-level multivariable calculus, you need to understand rigorous proofs regarding integration and differentiation in $\Bbb R^n$, as well as analytic properties of differential forms. This differs from undergraduate multivariable calculus, which again is typically computational, and focuses on vector calculus and use of Green's/Stoke's Theorems, rather than their construction and proof.


Is half a pie as big as a whole pie? I am reading an e-book called To Infinity and Beyond by Dr. Kent A Bessey. In the book the author makes the claim that Georg Cantor made a discovery "where half of a pie is as large as the whole".

In talking about it, he seems to claim that because half a pie can be broken into an infinite amount of pieces, and likewise a whole pie can be broken into an infinite amount of pieces they are infact the same size.

By the same concept, he states that if you took all of the pieces of the edge of a box you could create as many more boxes of whatever size you wanted using those pieces.

This seems undeniably false to me. I cannot help but draw a parallel between limits -> infinity. Where those limits may equal 2 or some other finite value. In my view, even if you were to break half a pie into an infinite amount of pieces the pieces could never add up to more than half a pie.

Am I misunderstanding? Can someone explain this concept better?

There are (at least) two kinds of "size" in mathematics.  One is cardinality. In set theory, the cardinality of a set is the number of elements it contains, and two sets have the same cardinality if there is a one-to-one mapping between them.  This is a coarse kind of "size", in that many different sets share the same cardinality: the interval $[0,1]$ is the same size as the entire real line, which in turn is the same size as all of $\mathbb{R}^3$.  In this sense, which is likely to be Cantor's meaning, half of a pie is certainly the same size as a whole pie.  Another type of "size" is measure, which assigns real numbers to (some) sets in such a way as to generalize the usual lengths of line segments, areas of polygons, volumes of cubes and spheres, etc.  This is much more precise: if you cut a disc of area $1$ into measurable pieces and then reassemble those pieces however you like, the result will still have area $1$.  However, if you allow any type of pieces (not just measurable ones), then the Banach-Tarski paradox can happen: a sphere of volume $1$ can be cut into a finite number of pieces and reassembled into a sphere of volume $2$.  (This can't happen in the plane, though, so your planar pie is safe.)

In my personal opinion, I would explain as follows.

half of a pie < whole pie.
half pie ---process---> infinity pieces.

For the same reason, whole pie ---process---> infinity pieces.
But process need ENERGE.
And I SUPPOSE that half pie need lots of energe to be infinity pieces.

For the same reason, whole pie need lots of energe to be infinity pieces.

I think that lots of energe = ∞.
So, half pie + lots of energe = half pie + ∞ -> infinity pieces

whole pie + lots of energe = whole pie + ∞ -> infinity pieces

by my understanding:

half pie + ∞ = whole pie + ∞

∞ = ∞
If someone can slice the half pie into infinity pieces, I think the guy could easily restore the pieces to a pie as big as the whole pie.


The Diophantine equation $x^2 - 97 - 40 = 0$ I am trying to determine whether the equation below  has a solution or not

$$x^2-97y-40 =0.$$

If a solution exists, $x^2-40$ must be congruent to 0 modulo $97$.

If I could show the congruence above implies that solution exists.

Thanks for your help...

$\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$

We are interested in the value of the Legendre symbol $\kron{40}{97} = \kron{8}{97} \kron{5}{97}$. In general, $2$ behaves differently from the rest of the primes.

By what is sometimes called the second supplemental law of quadratic reciprocity, we know that $\kron{2}{p} = (-1)^{(p^2-1)/8}$, or rather that $2$ is a square mod a prime iff that prime is congruent to $\pm 1 \pmod 8$. Since $97 \equiv 1 \pmod 8$, we see that $2$ is a square mod $97$. (Proofs of the second supplemental law can be found both here on MSE and on my site, and in most elementary number theory texts).

We must still consider $\kron{5}{97}$. By quadratic reciprocity, this is the same as $\kron{97}{5} = \kron{2}{5}$. The squares mod $5$ are $1$ and $4$ (or alternatively, $5$ is not congruent to $\pm 1 \pmod 8$), so $\kron{2}{5} = -1$.

In total, we have that $\kron{40}{97} = 1 \cdot -1 = -1$, which means that $40$ is not a square mod $97$. And so this quadratic Diophantine equation has no solution. $\diamondsuit$

you can use legendre symbol for calculating quadratic residue.so you need to compute (40/97).

  (40/97)=(2/97).(2/97).(2/97).(5/97)

        =(2/97).(5/97)

        =(97/2).(97/5)

        =(1/2).(2/5)

       =1.(-1)=-1

so 40 is not a quadratic residue mod 97.

no solution exists.


A is thrice as good as workman as B and therefore is able to finish a job in 60 days less than B. Working together, they can do it in? A is thrice as good as workman as B and therefore is able to finish a job in 60 days less than B. Working together, they can do it in:

A.  20 days

B. 22 1/2 days

C.  25 days

D.  30 days

How do we approach towards these kinds?

Let $v$ be the working speed of $B$. Then, the working speed of $A$ is $3v$. The working speed of $A$ and $B$ together is $4v$.

Now, the time $A$ spends is $t$ (in days), and the time $B$ spends is $t+60$.

Since the speed and the time are inversely proportional, their product is constant, so $3v\cdot t=v(t+60)$.

Can you continue?

Let A be X where as b = 3x.
So,
3x – x = 60.
x = 30.
a = 30, b = 90.

Together they can do the work in 22 (1/2) days.

A is thrice as good as workman as B and therefore is able to finish a job in 60 days less than B. Working together, they can do it in


Intersection of Connected Sets This is an old exam question that I don't have a solution to:

Let $X$, a compact Hausdorff (T2) space, and let $\phi$ a family of closed, non-empty, and connected subsets of $X$, such that for every $A, B \in \phi$, $A \subset B$ or $B \subset A$.

Prove that $Y:= \cap \{A: A \in \phi\}$ is connected.

I tried to solve this question with a friend, and this is what we came up with:

Obviously, $X$ is normal space (T4).
We tried to see what happens if $Y = U_1 \cup U_2$, disjoint and open sets (and?)
We tried to use nets and maybe see if we can create a net that converges to $x \neq y$ (and contradict X being Hausdorff space).
We tried to work with continuous functions, but this idea didn't lead us anywhere either.

I feel like there is a simple observation that we are missing. Any ideas?

Thanks!

Re-corrected: $\newcommand{\cl}{\operatorname{cl}}$Suppose that $Y=H\cup K$, where $H\cap K=\varnothing$, $H\ne\varnothing\ne K$, and $H$ and $K$ are clopen in $Y$. Let $f:Y\to\{0,1\}$ take $H$ to $0$ and $K$ to $1$, use the Tietze extension theorem to extend $f$ continuously to $\hat f:X\to[0,1]$, and let

$$\begin{align*}
U&=\hat f^{-1}\left[\left[0,\frac12\right)\right]\supseteq H\;,\\
V&=\hat f^{-1}\left[\left(\frac12,1\right]\right]\supseteq K\;,\text{ and}\\
F&=\hat f^{-1}\left[\left\{\frac12\right\}\right]\;.
\end{align*}$$

For each $A\in\phi$ we must have $F\cap A\ne\varnothing$, as otherwise $U\cap A$ and $V\cap A$ would be a disconnection of $A$. Thus, $\mathscr{C}=\{F\cap A:A\in\phi\}$ is a nested family of non-empty compact sets. But then $\varnothing\ne\bigcap\mathscr{C}=F\cap Y=\varnothing$, which is absurd.

Seems to me that if either $A \subset B$ or $B \subset A$
then for any $ Y = \bigcap [ A \mid A \in \phi ]$ there exists an set in this union, call it $H$, such that for any other set in the union, lets call them $K_\lambda$, $ H \subset K_\lambda$. From which we can conclude that $ Y = H$ and is thusly connected.

Intuitively, there is a minimal element in this union that is induced by the ordering on $\phi$ so this element is our 'limiting factor' so to speak.


Reflection inside spherical mirror Suppose you are inside a perfectly spherical mirror. You shoot one beam of light and it reflects on the walls of the mirror. Considering the intensity is constant will the beam of light hit you again?

I can shoot it from anywhere inside the sphere and I am a point.

One answer mentions that the beam will always come arbitrarily close. How to prove this?

I thought of this question while sleeping. But even after a day of thinking about this problem I couldn't solve it.

Note

The only answer is brief and does not explain or prove what is says. Looking for detailed answers preferably using illustration and valid mathematical proofs for the statements they make. Would like to read about possible generalizations and variations of this question. Please don;t restrict yourself to this specific situation and do not hesitate to write long answers which give a wide overview of these type problems. Bounty-awarded answer is likely to be long, detailed and self-sufficient mathematically in terms of proving the facts it states.

By the laws of optics, the reflections will occur in the plane formed by the initial ray and the center of the sphere, and this is a planar problem.

Now consider the circle where you are standing and the successive intersection points of the reflected rays with it.

By symmetry, these points will be located at angles that follow an arithmetic progression, and the angular delta from the initial point is $n\alpha\bmod1=\{n\alpha\}$, where the angles are expressed in turns. Now it is clear that the ray will come back iff $\alpha$ is a rational number. If it is irrational it will never come back exactly but you can always find an $n>0$ such that $\{n\alpha\}<\epsilon$ for any $\epsilon$.

The situation is similar for the second intersection points with the ray, at angles $n\alpha+\beta$, where $\beta$ is independent of $\alpha$*. But then, it may turn out that $n\alpha+\beta$ is a integer by coincidence so that even with irrational $\alpha$ there can be an exact return (only one because $n'\alpha+\beta$ cannot be another integer).

To summarize:

The return angles are $\{n\alpha\}$ and $\{n\alpha+\beta\}$, corresponding to

irrational $\alpha\to$ zero or one exact return plus infinitely many close ones, or
rational $\alpha\to$ infinitely many exact periodic returns but no close ones.

*As said somewhere else, the figure has two degrees of freedom: the (relative) distance to the center and the (relative) starting ray direction.

As has been mentioned, one should consider the plane formed by the source of the light, the first contact point, and the center of the sphere. The light beam will be confined to this plane, because the vector orthogonal to this plane will be tangent to the sphere at every point of contact. Now the problem is reduced to a similar argument, but considering a circle intead of a sphere.

Using Snell's Law (as Oscar Lanzi has pointed out), the length of each chord formed by the light beam will be the same. Now consider the angle 'a' around the circle formed by one of the chords. We will define the initial chord along which the beam was fired to be the 0'th chord, the next one to be the 1st chord, etc.

There are now two possibilities:

1) If 'a' is some rational multiple of 2*pi, say (p/q)*2pi (assume gcd(p,q) = 1), then we are guaranteed that the (n+q)'th chord will simply be the n'th chord rotated around the center by an angle of p*2pi. Since p is an integer, the (n+q)'th chord will therefore be identical to the n'th chord, meaning the 0'th chord will be identical to the q'th chord. Therefore, intersection will occur every q*b reflections for every non-negative integer b.

2) If 'a' is an irrational multiple of 2pi, let m[0] be the least positive integer such that:

m[0]*a mod 2pi < a.

We are guaranteed that such an m[0] exists, indeed m[0] will simply be the least positive integer such that m[0]*a > 2pi. Notice this implies that the angle between the m[0]'th chord and the 0'th chord is less than 'a'.

We can simply repeat this process by defining m[n+1] to be the least positive integer multiple of m[n] such that:

m[n+1]*a mod 2pi < m[n]*a mod 2pi

The geometrical interpretation of this is that the angle between the m[n+1]'th chord and the 0'th chord is less than the angle between the m[n]'th chord and the 0'th chord (for every n > 0). We can prove the existence of such an m[n+1] by letting j be the least positive integer such that:

j*(m[n]*a mod 2pi) > 2pi;

m[n+1] is simply j*m[n].

Define k[n] to be the angle between the m[n]'th chord and the 0'th chord, where k[0] is let to be 'a'. It is simple to see that the sequence k[n] is positive and decreasing. This means the sequence is convergent; in other words:

As n -> infinity , k[n+1]-k[n] -> 0.

So, for every real number e > 0 , there exists an n such that k[n+1]-k[n] < e.

Since the m[n+1]'th chord is at an angle k[n+1] from the 0'th chord, and the m[n]'th chord is at an angle k[n] from the 0'th chord, this implies that as n goes to infinity, the angle between chord m[n+1] and chord m[n] approaches 0.
Notice that for any positive integers b,c, and an integer d (not greater than min(b,c)) the angle between chord b and chord c is identical to the angle between chord (b-d) and chord (c-d). This implies that the angle between chord m[n+1] and chord m[n] is identical to the angle between chord (m[n+1]-m[n]) and chord 0.

As stated, for any real e>0, there exists an n such that the angle between the m[n+1]'th chord and the m[n]'th chord is less than e, implying the angle betweeen chord (m[n+1]-m[n]) and chord 0 is less than e. This guarantees arbitrary precision.

It could also be the case that one chooses wisely the initial firing point in a way that 'a' is an irrational multiple of 2pi, but the initial firing point is met anyway; consider, for instance, the case where one fires the beam of light from the intersection of chord 0 and chord m[0]. In this case, the beam of light will clearly pass through the firing point, but will only do so once, since a given point on a given chord is shared only with exactly one other chord (of the same length), and for 'a' being an irrational multiple of 2pi, we are guaranteed that no chord is ever repeated.

Sorry for the lack of fancy formatting, I'm new here and haven't had a chance to learn how to do that properly.

I realize this is a bit of a tome, so feel free to ask me about any uncertainties that might arise!


(Homework) Prove the law of syllogism Trying to prove, by symbol manipulation, that if $(P \rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R)$

I am stuck after doing these steps:

(P $\rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R$)

$(\neg P \vee Q) \wedge (\neg Q \vee R) \rightarrow (P \rightarrow R)$

$\neg [ (\neg P \vee Q) \wedge (\neg Q \vee R) ] \vee (\neg P \vee R)$

$[\neg (\neg P \vee Q) \vee \neg (\neg Q \vee R) ] \vee (\neg P \vee R)$

$(P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)$

I am really clueless by this point, this is the first problem propositional calculus problem I ever try. I was thinking maybe if there was some way to negate one of the Qs so I could then group them together then maybe I could get somewhere but I'm not sure how.

Sorry if this is a bad use of LaTex, its my first time using it.

You want to prove that your first formula (expression) is a tautology (has value true, whatever the truth values of the variables $P$, $Q$, $R$).

Use repeatedly the rewrite rule $$A\to B\quad \rightsquigarrow\quad \neg A\vee B \ .$$
The given expression is then equivalent to
$$\neg\bigl((\neg P\vee Q)\wedge(\neg Q\vee R)\bigr)\vee(\neg P \vee R)\ .\tag{1}$$
According to $\neg(A\wedge B)=\neg A\vee\neg B$ and its dual  the left part of expression $(1)$ is equivalent to
$$\neg(\neg P\vee Q)\vee\neg(\neg Q\vee R)=(P\wedge\neg Q)\vee(Q\wedge\neg R)=P\vee\neg R\ .$$
This shows that $(1)$ is equivalent with
$$(P\vee\neg R)\vee(\neg P \vee R)\ ,$$
which is certainly true.

You can prove it using a truth table. A more intuition based "proof" would be to think of them as a stack of dominoes. p is the first domino, q is the second domino and r is the third domino. Since p knocked over (implied) q which knocked over (implied) r, we can say that p knocked over r.

As for a more formal proof I wouldn't know. Maybe try taking
$[(p \rightarrow q) \wedge (q \rightarrow r)] \rightarrow (p \rightarrow r)$ (which is syllogism in a logical form) and reducing it to a tautology, but that is only a suggestion.

Here is an example using Modus Ponens (Also known as Rule of Detachment)


Decompositions of open sets in $\mathbb{R}^n$ This may be a basic question. It's well known that open sets in $\mathbb{R}$ are the union of disjoint open intervals. Does it similarly hold that open sets in $\mathbb{R}^n$ are the union of disjoint connected open sets? Moreover, is a connected open set the union of disjoint connected convex sets? Thanks.

The first property you ask for is fairly trivial to show; in particular, for any open set $O$ define an equivalence relation $$a\sim b$$ defined by the property that, if $S$ is a set of disjoint open sets covering $O$, then $a\in s\in S$ implies $b\in s$ - that is, $a$ and $b$ are in the same connected component. The equivalence classes of this can easily be shown to be disjoint open sets, whose union is $O$.

The second property is somewhat more difficult, but still doable. One approach is essentially to build an octree as a partition. In particular, let $S$ be the set of intervals of the form
$$\left[\frac{x_1}{2^n},\frac{x_1+1}{2^n}\right)\times \left[\frac{x_2}{2^n},\frac{x_2+1}{2^n}\right)\times \left[\frac{x_3}{2^n},\frac{x_3+1}{2^n}\right)$$
along with the set $\mathbb R^2$ itself. That is, we have axis aligned cubes whose corners are at "adjacent" dyadic rationals - if we put $8$ of these cubes together, we get a bigger cube which is also in the set. Then, we can quickly come up with a partition $P\subseteq S$ of $O$ - in particular, let $P$ be the set of $s\in S$ such that $s\subseteq O$ but for which there does not exist any $s'\in S$ which (strictly) contains $s$ but is contained in $O$ - that is, $P$ is the set of cubes of maximal size fitting in $O$.

This is a partition since, for any $p\in O$, there is some ball around $p$ contained in $O$ - and therefore, as every point is contained in a cube of arbitrarily small radius, there is some $s\in S$ such that $p\in s\subseteq O$. We can then argue that if two cubes $s_1,s_2\in S$ contain $p$, then either $s_1\subseteq s_2$ or $s_2\subseteq s_1$ (because of how the cubes nest) - and thus, the set of cubes containing $p$ forms a chain when ordered by inclusion - and our partition has the property that the union over such a chain is still in $S$ - therefore, we conclude that there is a maximal element in $S$ containing $p$ and that this is in $P$, thus $P$ is a partition.

We can generalize this argument to say that, if $S$ is a set satisfying:

If $s_1,s_2\in S$ then $s_1\cap s_2$ is either $s_1$, $s_2$, or the empty set.
Every subset $S'\subseteq S$ which is totally ordered by inclusion (i.e. a chain) has that the union of all $s\in S'$ is a member of $S$. (Equivalently, every subset of $S'$ has a least upper bound when ordered by inclusion)
For any open set $O$ and $p\in O$, there exists a $s\in S$ which contains $p$ and which is contained wholly within $O$.

then there is a partition $P$ of any open set satisfying $P\subseteq S$. In our particular example, we chose a suitable $S$ composed of convex sets with non-empty interior.

The open sets of $\mathbb{R}^n$ in the standard Euclidean topology are generated by the open balls $B(x,\epsilon) = \{ y \in \mathbb{R}^n | ||x-y||<\epsilon \}$ where $\epsilon >0$ and $x \in \mathbb{R}^n$. Notably, for $n=1$ the $||x-y||$ (Euclidean norm) is just $|x-y|$, the absolute value.

It is true that in $\mathbb{R}$, the open sets are disjoint unions of intervals. For instance, the set $(-\infty,6) \cup (14,\infty)$ is a disjoint union of intervals, but if I write something like $(-\infty,6) \cup (4,\infty) = (-\infty, \infty)$, that is still an open set, even though I've written it as the union of non-disjoint open intervals.

After simplification of set union wherever it may occur, every open set in $\mathbb{R}^n$ will be the disjoint union of open balls, but it may not necessarily be written that way. Once we do all simplification, we should end up with a collection of disjoint open sets.


Solve $(D^2 + 3D + 2)y = e^{e^x}$ using method of variation of parameters? This question was asked in a test and I'm stuck while solving this using method of variation of parameters. Here's an screenshot of my solution,

While finding particular integral I was not able to solve integration of e^e^x?
Can anyone please help me out a bit here. I was not able to understand how to solve it further.

You are almost there, but note that $W(x)=e^{-3x}$
$$PI=-e^{-2x} \int e^{2x} e^{e^{x}} dx + e^{x} \int e^{x} e^{e^{x}} dx$$
Let $e^x =t \implies dx=\frac{dt}{t},$ then
$$PI=-e^{-2x} \int t e^{t} dt + e^{-x} \int e^{t} dt$$
$$PI=-e^{-2x}e^{t}(t-1)+ e^{-x} e^{t}= e^{-2x+e^{x}} .$$

the final answer should be
$PI = e^{-2x} * e^{e^x}$