Problem about problem solving I am having some problems on how to solve problems. When I read a chapter on say group theory or real analysis, I feel that I have understood the concepts quite well, but when I start solving exercises, after 5 or 6 problems I get stuck. When I see a tough problem, I get messed and cannot find how to come out of it. When I see the solution I have no problem in understanding it. I think about many things but cannot come up with a solution. Is it a problem of my basics not being right? I have an entrance exam & being in this situation is frustrating for me. Please help.

Well, it's possible that the books your reading have really bad exercises. But if this happens often, the more likely problem is that your feeling that you have grabbed the concepts quite well must be mistaken.

As useful test, when you look at a problem, is to ask yourself "Can I define precisely every single term used in this problem? " And then "What theorems do I know about these things?" If you can't recite the theorems -- with all the hypotheses! -- then you're probably not going to be able to do the problem. It's like trying to build a cabinet while you keep forgetting there's a saw in your toolbox.

I know that's not a lot of help, but it's the best I can do without more detail.

suppose {T} is a collection of bounded operators on a Hilbert space H, with  IT<1   for all k. Suppose also that.
Let SN - Σ Ν T k =-Ν
Show that SNf)     converges as N00 , for every Є Н . If  Tf denotes the limit, prove that  |T||< 1 . [Hint: Consider first the case when only finitely many of the  TK are non-zero, and note that the ranges of the TK are mutually orthogonal.]


Spectrum of $\mathbb{Z}[x]$ Can someone point me towards a resource that proves that the spectrum of $\mathbb{Z}[x]$ consists of ideals $(p,f)$ where $p$ prime or zero and $f$ irred mod $p$? In particular I remember this can be proved simply using localizations, but can't quite remember how to do it! I definitely don't want a link to a long involved argument about polynomials, I can find quite enough of those!

Many thanks in advance.

Here is a geometric (schemes!) way to think about it.

The inclusion $\Bbb Z\to\Bbb Z[x]$ defines a morphism $\operatorname{Spec}(\Bbb Z[x])\to\operatorname{Spec}(\Bbb Z).$ Thus to figure out the primes of $\operatorname{Spec}(\Bbb Z[x]),$ we can simply determine all the fibres of this map. How do we compute the fibres of this map?

For $\langle p\rangle\subseteq\Bbb Z$ a prime ideal, we pull back the morphism given above over the map $\operatorname{Spec}(\kappa(p))\to\operatorname{Spec}(\Bbb Z)$ induced by $\Bbb Z\to\Bbb Z_p/\frak{m_p}$ $=\kappa(p)$, where $\kappa(p)$ is the residue field of $p.$ The residue field $\kappa(0)=\Bbb Q$ and for all other primes $p$ we have $\kappa(p)=\Bbb F_p.$

The fibre over $\langle 0\rangle$ is thus $\operatorname{Spec}(\Bbb Q\otimes_{\Bbb Z}\Bbb Z[x])=\operatorname{Spec}(\Bbb Q[x])$ which is all irreducible polynomials over $\Bbb Q$ and the zero ideal. Similarly, the fibre over $\langle p\rangle$ is $\operatorname{Spec}(\Bbb F_p[x]),$ which is just the irreducible polynomials over $\Bbb F_p$ along with its zero ideal. (The zero ideals correspond to those in $\Bbb Z.$)

There are two cases: if a prime ideal $P$ of $Z[x]$ does not contain any constant then considering the ideal generated by $P$ in $Q[x]$, it is a proper ideal of $Q[x]$; so that it is a principal ideal generated by a single polynomial $f(x)\in Q[x]$. But then an irreducible element $g(x)\in P\subset Z[x]$ can be written as $g(x)=f(x)h(x)$ with $h(x)\in Q[x]$. By considering   the common denominators,  $f(x)=f_1(x)/b$ and $h(x)=h_1(x)/c$ where $f_1(x), h_1(x)  \in Z[x]$. Now $bcg(x)=f_1(x)h_1(x)$. Looking at the content of polynomials we can conclude that $P=(f_1(x))$ is a principle ideal of $Z[x]$.

The case where $P$ contains a constant is easy to solve by passing to the quotient ring.


Determine if the matrix is idempotent? I am dealing with an example to show that the matrix($M = I − X(X'X)^{−1}X'$) is idempotent. X is a matrix with T rows and k columns and I the unit matrix of dimension T. And then to determine the rank of this matrix by using the properties of the trace of the matrix.
1.
Idempotent means that matrix $A^2=A*A=A$

$$M = I − X(X'X)^{−1}X'$$
$$M = XX' − X(X'X)^{−1}X'$$
$$MM = (XX' − X(X'X)^{−1}X')(XX' − X(X'X)^{−1}X')$$
$$MM = (XX' − X(X'X)^{−1}X')(I − I)$$
-> MM is not idempotent

Is that correct?

2.
$$Tr(AB)=Tr(BA)$$
$$Tr(M)=Tr(I − X(X'X)^{−1}X') = Tr(I − I) = Tr(0) = 0$$

Are my assumptions correct?

UPDATE

$$Tr(A-B)=Tr(A) - Tr(B)$$
$$Tr(M)=Tr(I) − Tr(X(X'X)^{−1}X')) = Tr(I) − Tr(I) = Tr(0)  or Tr(I)= Rank(n)$$
Is this correct?

You've wrongly assumed that $XX'=I$. To prove that $M$ is idempotent, note that $Y^2=(X(X'X)^{−1}X')^2=X\underbrace{(X'X)^{−1}X'X}_{=I}(X'X)^{−1}X'=:Y$, so $M^2=(I-Y)^2=I-2Y+Y^2=I-Y=M$.
Indeed $\operatorname{tr}(X(X'X)^{−1}X')=\operatorname{tr}(X'X(X'X)^{−1})=\operatorname{tr}(I)$, but the size of this $I$ is $k\times k$, while the $I$ in $\operatorname{tr}(I-X(X'X)^{−1}X')$ has size $T\times T$. So, no, the trace of $M$ is not zero in general, but $\operatorname{tr}(I_T)-\operatorname{tr}(I_k)=T-k$. To find the rank of $M$ using the trace, observe that (a) every eigenvalue of $M$ is either $0$ or $1$ (why?) and (b) $M$ is unitarily diagonalizable (again, why?). So, the rank is equal to the trace. (Why~y~y~~???)


Exercise 1.19 in Brezis' Functional Analysis I would like a clarification to an exercise in Brezis' Functional Analysis. Exercise 1.19(2) says

  Let $E$ be a normed vector space. Let $F:\mathbb R \rightarrow (-\infty, +\infty]$ be a convex lower semi continuous function such that $F(0)=0$ and $F(t)\geq t$ $\forall t\in \mathbb{R}$. Set $\phi (x)=F(\|x\|)$. Prove that $\phi$ is convex, lower semi continuous and that $\phi^{\ast}(f)=F^{\ast}(\|f\|)$ $\forall f\in E^{\ast}$.

Now I can prove everything except for the last statement, where I can't understand something. The book defines the conjugate function of $\phi:E\rightarrow (-\infty, +\infty]$ to be $\phi^{\ast}:E^{\ast}\rightarrow (-\infty, +\infty]$ with
$$ \phi^{\ast} (f) =\sup_{x \in E}\{ \langle f , x \rangle - \phi (x)\} $$

With this in mind, the $F^{\ast}$ of the exercise should take as argument elements of $\mathbb{R}^{\ast}$, that is continuous linear functionals $g:\mathbb R\rightarrow \mathbb R$. In this case it takes $\|f\|$, where $f\in E^{\ast}$, so $f:E\rightarrow \mathbb{R}$. I can't understand how this can happen. Surely $\|f\|$ can't be just the norm of $f$ since it would not be linear. So my question is: what is $F^{\ast}(\|f\|)$ supposed to mean in this context?

Please don't offer any hints on how to solve the exercise!

Since $F$ is convex and $F(0) = 0$ is a global minimum, $F$ is monotonically decreasing on $(-\infty, 0]$ and monotonically increasing on $[0, \infty)$. Therefore, for any $x$, $y \in \mathbb{R}$ and any $\lambda \in [0, 1]$,\begin{align*} \phi(\lambda x + (1 - \lambda)y) & = F(\|\lambda x + (1 - \lambda)y\|) \le F(\lambda\|x\| + (1 - \lambda)\|y\|) \\ & \le \lambda F(\|x\|) + (1 - \lambda)F(\|y\|) = \lambda\phi(x) + (1 - \lambda)\phi(y).\end{align*}Let $M \in \mathbb{R}$ and let $H = \{x : F(x) < M\}$. Then $\{x : \phi(x) < M\} = [0, \infty) \cap (H \cup -H)$ is closed since $H$ is closed, as $F$ is lower semicontinuous. Thus, $\phi$ is lower semicontinuous.

Finally,\begin{align*}\phi^*(f) & = \sup_{x \in E} (fx - F(\|x\|)) = \sup_{x \in E} (\pm\|f\|x - F(\|x\|) \\ & = \sup_{x \in E} (\|f\|x - F(\|x\|)) = \sup_{x \ge 0} (\|f\|x - F(\|x\|)),\end{align*}since $\|f\|x - F(\|x\|)$ is strictly less than $0$ for $x < 0$, which is less than the $0$, which is the value achieved when $x = 0$. Therefore,$$\phi^*(f) = \sup_{x \ge 0} (\|f\|x - F(x)) = F^*(\|f\|),$$where the final equality holds since $\|f\|x - F(x)$ is strictly negative when $x < 0$, and hence less than the value at $0$, which is $0$.


Calculating $e^{ar}+e^{ar^2}+..+e^{ar^n}$ Calculate the sum,

$$e^{ar}+e^{ar^2}+..+e^{ar^n}\ \text{where} \ a,r\in \mathbb{R}$$

It's easy to calculate the sum when the powers of $e$ are in A.P.
But, how to proceed when the powers are in G.P.?

Let ${ar}^i=i\log m.$ Then the series becomes $$\sum_{i=1}^{n}{e^{ar^{i}}}=\sum_{i=1}^{n}{e^{i\log{m}}}=\sum_{i=1}^{n}{{m}^i},$$ which is a geometric series.


Exact vs. conservative I'm having trouble understanding definitions.

What's the difference between something being exact and being conservative? I understand both involve proving that a potential function $f$ exists such that
$$\vec{F}(x,y,z)=M\hat{i}+N\hat{j}+P\hat{k}=\frac{∂f}{∂x}\hat{i}+\frac{∂f}{∂y}\hat{j}+\frac{∂f}{∂z}\hat{k}$$
but I'm not understanding what makes something exact as opposed to conservative, or vice versa.

Is it just that differential equations can be exact and vector fields can be conservative, or is there more to it?

EDIT: Fixed a mistake.

Exactness is a property of differential forms, like $M \,\mathrm{d}x + N \,\mathrm{d}y + P \,\mathrm{d}z$. In particular, if a differential form $\alpha$ is exact, then the equation $\alpha= 0$ is also said to be exact.
Conservativeness is a property of vector fields, like $(M,N,P)$.

They are particular case and general case:

Differential forms are a generalization of scalar/vector fields.

Exterior derivative is a generalization of gradient/divergence/curl.

${\bf F} = \nabla f$ is a particular case of $\lambda =d\omega$.


Question that can not be solve analytically . You can know that the solution of this non-linear simultaneous equations is y=2 and x=3; but the question is : How can mathematically ( algebraically ) find this.
\begin{array}{lcl} x^y & = & 9 \\ y^x & = & 8 \end{array}

This is equivalent to solving

$$ x^{a^x} = b $$

which, I think, has no analytic solution.

Ln both equations to get:

$\ln x^y = \ln 9$ and $\ln y^x = \ln 8$

They then become $y \ln x = \ln 9$ and $x \ln y = \ln 8$

Solving for $x$ and $y$ you get

$y = \frac{\ln 9}{\ln x}$ and $x = \frac{\ln 8}{\ln y}$

Substituting $x = \frac{\ln 8}{\ln y}$ into the first equation you get

$y = \frac{\ln 9}{\ln(\ln 8/\ln y)}$

Doing the same for $x$, you get

$x = \frac{\ln 8}{\ln(\ln 9/\ln x)}$

...?


There are 10 men and 10 women. Alice (woman) and Brad (man) never stand next to each other. There are 10 men and 10 women. Alice (woman) and Brad (man) never stand next to each other. Assume that the men and women alternate in a line, how many possible ways are there for the arrangement?

Without the condition of Alice and Bob not standing next to eachother, it would be 10! * 10! * 2. Now I need to subtract all the ways in which they could be stuck together, or 9! * 9! * 10 * 2. (I can elaborate on how I got this part if it is wrong)

So would the final answer just be 10!10!2 - 9!9!10*2 ??

Pick the position of the leftmost member of alice and brad.  There are $19$ options.

Then, pick whether it goes male-female-male-female-... or vice versa.  $2$ options.

Finally from left to right for each spot designated for a male pick one of the remaining males to fill it and same for the females.  $9!\cdot 9!$ options.

This gives a total of $19\cdot 2\cdot 9!\cdot 9!$ options for Alice and Brad to stand next to one another, not $10\cdot 2\cdot 9!\cdot 9!$ as you had calculated.  You had effectively missed the cases where the leftmost of them was in an even index (with indices counting from one).

Continuing, this gives $10!\cdot 10!-19\cdot 2\cdot 9!\cdot 9!$ ways for them to not stand next to one another.

I agree that you're on the right track with subtracting from the total number of way in which just 10 men and 10 women can alternate each other. However, the formula for the ways in which Alice and Bob could be stuck together is 9!9!*4, because there are 9! ways for the women to be arranged, 9! for the men to be arranged, and 2! (or 2) ways for Alice and Bob to be next to each other, then 2 ways for the 9 men and 9 women to be alternating. So 9!9!*2*2, or 9!9!*4.
Now get back to your CS 240 HW.


How can I find the points at which two circles intersect? Given the radius and $x,y$ coordinates of the center point of two circles how can I calculate their points of intersection if they have any?

This can be done without any trigonometry at all. Let the equations of the circles be
$$(x-x_1)^2 + (y-y_1)^2 = r_1^2, \tag{1}$$
$$(x-x_2)^2 + (y-y_2)^2 = r_2^2. \tag{2}$$
By subtracting $(2)$ from $(1)$ and then expanding, we in fact obtain a linear equation for $x$ and $y$; after a little rearranging it becomes
$$-2x(x_1 - x_2) - 2y(y_1 - y_2) = (r_1^2 - r_2^2) - (x_1^2 - x_2^2) - (y_1^2 - y_2^2).$$
(If the circles intersect, this is the equation of the line that passes through the intersection points.) This equation can be solved for one of $x$ or $y$; let's suppose $y_1 - y_2 \ne 0$ so that we can solve for $y$:
$$y = -\frac{x_1 - x_2}{y_1 - y_2} x + \dotsc. \tag{3}$$
 Substituting this expression for $y$ into $(1)$ or $(2)$ gives a quadratic equation in only $x$. Then the $x$-coordinates of the intersection points are the solutions to this; the $y$-coordinates can be obtained by plugging the $x$-coordinates into $(3)$.

following the very nice hint of arkeet you can after defining a,b,c,g,h  using rc1,zc1,rc2,zc2, as the center point of the circles and R1 and R2 their radii
and assuming that rc2!=rc1 (the case where rc2=rc1 can be also done in the manner or arkeet, however the present assumption was useful to me)

g = (zc2 - zc1)/(rc2 - rc1);
h = (R1*R1-R2*R2 + zc2*zc2 - zc1*zc1 + rc2*rc2 - rc1*rc1 )/(2*(rc2 - rc1));

a = (g*g+ 1);
b = -2*g*h + 2*g*rc1 - 2*zc1;
c = h*h -2*h*rc1 + rc1*rc1 + zc1*zc1 - R1*R1;

zplus  = (-b +sqrt(b*b-4*a*c)) / (2*a);
zminus = (-b -sqrt(b*b-4*a*c)) / (2*a);
and
rplus  = -gzplus+h;
rminus = -gzminus+h;

you can test this by verifying that the intersection points do lie on the 2 circles.


How to find remainder when $ 975^{40153}$ is divided by $14$? I still find tricky this kind of problems.
I tried to do solve it by factoring $14$ in $2*7$.

Then, with Fermat's Little Theorem, I find that:

$975^6\equiv 1\pmod 7$

$975^1\equiv 1\pmod 2$

How can I proceed frome here?


Show that $A$ and $A^T$ do not have the same eigenvectors in general I understood that $A$ and $A^T$ have the same eigenvalues, since
$$\det(A - \lambda I)= \det(A^T  - \lambda I) = \det(A - \lambda I)^T$$
The problem is to show that $A$ and $A^T$ do not have the same eigenvectors. I have seen around some posts, but I have not understood yet why.

Could you please provide an exhaustive explanation of why in general $A$ and $A^T$ do not have the same eigenvectors?

The matrix $A=\begin{bmatrix}
1 & 1\\
0 & 1
\end{bmatrix}$, and its transpose $A^T$, have only one eigenvalue, namely $1$. However, the eigenvectors of $A$ are of the form $\begin{bmatrix}
a\\
0
\end{bmatrix}$, whereas the eigenvectors of $A^T$ are of the form $\begin{bmatrix}
0\\
a
\end{bmatrix}$.

Though $A$ and $A^T$ have the same eigenvalues, they may have different eigenvectors for that particular eigenvalue. This is because, if we assume the eigenvector (lets say $v$) to be non zero, then
$$Av = (eigenvalue(A).v)$$
and
$$A^Tv = eigenvalue(A^T).v$$
so $$Av - A^Tv = 0$$
so $$(A - A^T).v = 0$$

Now since we assumed $v$ to be non zero,  this will happen only if $(A-A^T)$ has
a valid non zero null space.

So $A$ and $A^T$ will not have same eigenvectors for a given eigenvalue, unless the above condition holds true.


If $(a_n)$ is such that $\sum_{n=1}^\infty a_nb_n$ converges for every $b\in\ell_2$, then $a\in\ell_2$ Please help me with this question. I've been thinking about it for almost two days.
Let $a_n$ a real series that have the following property:
for every series $b_n$ in $l_2$: $\sum_{n=1}^\infty a_nb_n$ converges.
prove that $a_n$ in $l_2$.

I figured this out thanks to a tip from my professor to use the uniform boundedness principle.

(1) Define $T_N : \ell^2(\mathbb{C}) \rightarrow \mathbb{C}$ by
$$
T_N(y) = \sum\limits_{i=1}^N x_i y_i
$$
which are each bounded linear functionals by Cauchy-Schwarz.

(2) Apply the uniform boundedness principle to the family $\{T_N\}_{N \in \mathbb{N}}$. The hypothesis ensures that this family is uniformly bounded.

(3) The linear map $T$ defined by $T(y)= \lim\limits_{N\rightarrow \infty} T_N(y)$ is bounded as well by (2), specifically,
$$
\|T\| := \sup\limits_{\|y\| \leq 1} \|Ty\| = \sup\limits_{\|y\| \leq 1} \lim\limits_{N\rightarrow\infty} \|T_N(y)\| \leq \sup\limits_{\|y\| \leq 1} M\|y\| = M
$$
for $M$ the uniform bound.

(4) The Riesz representation theorem implies that $T$ comes from a sequence in $\ell^2$. This sequence must be $x$.

Using Holder inequality we say that
$$\sum_{n} a_n b_n\leq \left(\sum_n |a_n|^p\right)^{1/p}\left(\sum_n |b_n|^2\right)^{1/2} $$
with $1/p+1/2= 1$ and from that we get $p=2.$ So the result.


Nth value of Function Given x and y we define a function as follow :

f(1)=x
f(2)=y
f(i)=f(i-1) + f(i+1) for i>2

Now given x and y, how to calculate f(n)

Example : If x=2 and y=3 and n=3 then answer is 1

as f(2) = f(1) + f(3), 3 = 2 + f(3), f(3) = 1.

Constraints are : x,y,n all can go upto 10^9.

Calculate the first dozen numbers.  You should find a simple result for this algorithm.

You can use this code:

#include <stdio.h>

int fib(int n,int x,int y){
     if (n==1) return x;
     else if (n==2) return y;
     else return fib(n-1,x,y) + fib(n-2,x,y);
}

int main()
{
   int x,y,n,z;
   printf("Give a value for x:");
   scanf("%d",&x);
   printf("Give a value for y:");
   scanf("%d",&y);
   printf("Give a value for n:");
   scanf("%d",&n);
   z=fib(n,x,y);
   printf("The result is: %d",z);
}


Action of a projection on a sequence of pairwise orthogonal subspaces. Let us consider a sequence of finite-dimensional subspaces $\{H_n\}$ with $dim H_n=dim H_m$  and $H_n\perp H_m$ ($m\neq n$) in the Hilbert space $H$. Does there exist any projection $P$ satisfying in the following relations:
$$0\neq \overline{P(H_n)}=\overline{P(H_m)}=\overline{P(\cup_{j\geq1} H_j)}$$
where $m\neq n$.

My answer was wrong. The mistake that invalidates the whole argument happened between $(5) $ and $(6)$, where
$$
\lambda_{jk}P_{jj}=\lambda_{jk}\lambda_{kj}P_{kk}
$$
should have been
$$
\lambda_{jk}P_{jj}=\lambda_{jk}\lambda_{kj}^2P_{kk},
$$ which gives no new information whatsoever.

Have you tried anything?

Try the simple case $H = \mathbb{C}^n$ and $H_i = \{(0,0, \dots, 0, z, 0, \dots) : z \in \mathbb{C}\}$ is the span of the $i$th standard basis vector. (Try $n = 2$ and $n = 3$.)

Can you find a projection with the above properties in this case? If not, then why not?

Can you extend this to the general case?


What is $2^{7!}\bmod{2987}$ Find the remainder when $2^{7!}$ is divided by $2987$.

I tried to factorise $2987$ to make it simple but it was in vain.

Hint: The unique prime factorization of $2987$ is,

$$2987=29\times 103$$

Now, use Fermat's Little Theorem to reduce the exponent and get the remainder modulo $29$ and $103$.

Combine the results using Chinese Remainder Theorem.

Alternatively, you can use Euler's totient function to compute $\phi(2987)$ and then use Euler's Totient theorem but that might result in tedious calculations and we being lazy never want to do it the tedious way. :P

Computational answer=755 (Cloud Sage)

Edit: 7! not 71. Sorry


Find the invariant factors and elementary divisors from the relations matrix. Let $V$ be a finite dimensional vector space over $\Bbb C$, and $T$ be a linear operator on $V$. Consider $V$ as an $\Bbb C[x]$-module by defining $xv = T(v)$ for each $v \in V$.
Let $$A = \begin{bmatrix}
    x^2(x - 1)^2      & 0 & 0\\
   0       & x(x - 1)(x - 2) & 0 \\
   0      & 0 & x(x - 2)^2
\end{bmatrix}$$
be the relation matrix for $V$ with respect to $\{v_1, v_2, v_3\}$.

List the invariant factors and elementary divisors of $V$.

Attempt: In general, I would reduce the relation matrix to smith normal form to find the invariant factors, and from there I could find the elementary divisors. However, this matrix is hard to reduce to SNF, so I think they want me to find another approach.
From the relation matrix I believe $$V = \frac{F[x]}{x^2(x - 1)^2} \oplus \frac{F[x]}{x(x - 1)(x-2)} \oplus \frac{F[x]}{x(x - 1)^2}$$ and the elementary divisors are $ x^2, (x-2)^2, x, x, (x-1)^2, x - 1, x - 2$, which would mean the cyclic decomposition is
$$V=\frac{F[x]}{x^2(x - 1)^2(x-2)^2} \oplus \frac{F[x]}{x(x - 1)(x-2)} \oplus \frac{F[x]}{x}$$ with invariant factors $x^2(x - 1)^2(x-2)^2, x(x - 1)(x-2), x$.

Describe the decomposition of $V$ by the primary decomposition theorem, and find the Jordan form of the operator $T$.

Attempt: From the invariant factors, I believe the minimal polynomial $p = x^2(x - 1)^2(x-2)^2$, and the characteristic polynomial is $ f = x^2(x - 1)^2(x-2)^2x(x - 1)(x-2)x$. Hence if $N_1 = \mathrm{null}(T^2), N_2 = \mathrm{null}(T - I)^2, N_3 = \mathrm{null}(T- 2I)^2$, then $V=N_1 \oplus N_2 \oplus N_3$ is the primary decomposition. I'm not sure, but I think the Jordan form will be
$$A= \begin{bmatrix}
   1      & 0 & 0 & 0 &0\\
   0       & 1 & 0 & 0 & 0\\
   0      & 0 & 2 & 0 & 0 \\
   0      & 0 & 0 & 2 & 0 \\
   0      & 0 & 0 & 0 & 0 \\
   0      & 0 & 0 & 0 & B \\
\end{bmatrix}$$ for some block matrix $B$.

1) Your answer to this question is right (but a comma is missing in the list of elementary divisors).

2) From the list of elementary divisors you have written the answer is the matrix given by user346069


Dropping a Lowest Score I have a lab class, where I drop the lowest score students receive, easy enough. Except, all items are not weighted equally,  (lab A might be worth 10 points, while lab B might be worth 23 points, and so on).

Right now, what I do in an excel file is calculate the total points earned and the maximum points, except in each instance I remove a different assignment from the calculation. Then compare the various percentages and drop the one that yields the highest overall percentage.

TL;DR, here is the main question part ;)

Is this a problem that can be solved more easily, or can I answer the question of which to drop with a formula? I'd love to include the calculation in my grade book so it happens automatically. Right now, I have to go in and drop an assignment manually for each student, since my only option is to drop "lowest score" which doesn't work since 5/10 has a different impact than 3/30.
(I realize I could scale everything and make them all worth the same amount, but that complicates other parts of the grade for me, so isn't ideal)

I've included a screen shot of what I do in excel for hopeful clarity.

The bottom three rows are what I look at.

Total Score w/o: Total earned points (from row 2) without the lab corresponding to that column

Total Max w/o: Total maximum points possible (from row 3) without the lab corresponding to that column

Combined Percent w/o: Just the values from $\displaystyle\frac{\text{Total Score w/o}}{\text{Max Score w/o}}$ for each column.

I have conditional highlighting which shows me the highest percentage, so in this case, I would drop the student "Hydrate" lab assignment from their grade.

*Note: I will confess I really wasn't sure what tags I should use. This stackexchange is way out of my comfort zone, so most terms were not familiar. Feel free to change them to whatever is most appropriate.

Let $t_i$ and $s_i$ be the possible points and actual points scored, respectively, for each individual assignment, and let $T$ and $S$ be the respective sums over all assignments. Assuming that the goal is to produce the highest percentage for the student, you’re trying to maximize ${S-s_i\over T-t_i}$. With a bit of algebraic manipulation, this can be rewritten as $\frac S T+{St_i-s_iT\over T(T-t_i)}$, so drop the assignment that maximizes ${St_i-s_iT\over T(T-t_i)}$.

For the small example in your comment to Travis’ answer, these values are $0.129$, $-0.017$, $-0.026$ and $-0.060$, so the first score should be dropped. For the slightly larger data set in those comments, this method selects the 15/35 score ($0.036$), just as you had originally computed. For the example in your question, “Hydrate” is the winner with a value of $0.045$, so it should be dropped, which also agrees with the method you’d been using.

Of course, if you’re doing this in a spreadsheet anyway, you can compute ${S-s_i\over T-t_i}$ for each assignment and have the spreadsheet find the highest value for you, as Henry points out in his comment to your question.

Let the total points be $S$, the amount of possible points on an assignment be $K$, and the score the student got on the assignment be $x$.

$${SCORE} = x\frac{S}{K}$$

You'll have to apply this to every equation, and drop the one with the lowest result. In your examples, the student has scores of $1/30, 5/7, 15/25$ and, $13/17$. This means the total score is $30+15+25+17 = 87$. You then apply this to the equation: for the first assignment,
$$10\frac{87}{30} = 29$$
For the second assignment,
$$5\frac{87}{7} \approx 62.14$$
The third;
$$15\frac{87}{25} = 52.2$$
And finally,
$$13\frac{87}{17} \approx 66.53$$

Because the first assignment yeilds the lowest result, it has the largest negative effect on the grade, and should be dropped.

This works because you're taking the weight of the assignment $\frac{Points}{Total Points} $, then multiplying it by the score, yielding the negative weight on the total grade.


Calculating future value and Present Value I have been stuck on this one for hours ... not too great at math can someone help. Thanks.

Isaac borrowed $\$4000$ at $11.5\%$ compounded quarterly $5.5$ years ago.

One year ago he made a payment of $\$1500$. What amount will extinguish the loan today?

I've tried a bunch of different approaches, none were right.

From what I understand we should calculate the FV for $4.5$ years when $PV=\$4000$
then subtract $\$1500$ from answer and calculate FV for one more year.

But still no luck..

It sounds like your idea is correct. The current value of loan should be given by: $4000(1+ \frac{.115}{4})^{4 \times 5.5} - 1500(1+ \frac{.115}{4})^{4 \times 1}$

If you aren't getting the right answer, it could be a problem with using the calculator. Some can be difficult to use, for example, if they don't let you see what you are typing.

You also don't need to turn it into a multi step problem by calculating the value at 4.5 years, subtracting 1500, and then calculating the interest for the final year after everything else. If you calculate the current value of everything at once, you can save yourself some work. It is fairly easy to see that both must be equivalent if you draw a time diagram of the payments.


Determine if subspace - complex numbers $$ \mathbb{F} := \mathbb{C} \\ V := \mathbb{C}_2[x] $$
$V$ is the set of all polynomials with degree less than or equal to $2$ with complex scalars.
$$ U := \left \{ p(x) \in \mathbb{C}_2[x] | p(x) = p(2x) \right \} $$
Given $ U \subseteq V$ I need to determine if $U$ is a linear subspace of $V$
My try:
$$ p(x) = ax^2 + bx + c \\ p(2x) = a(2x)^2 +2bx + c \\ p(x) = p(2x) \Rightarrow ax^2 + bx + c = 4ax^2 + 2bx + c \\ 3ax^2 + bx = 0 $$
Now, I know that I need to check $3$ things:

$\vec{0} \in U $
If $\vec{v_1} \in U$ and $\vec{v_2} \in U$ then $\vec{v_1} + \vec{v_2} \in U$
If $t \in \mathbb{C}$ then $t \cdot \vec{v_1} \in U$

But I only got the rule of thumbs that " $ 3ax^2 + bx = 0$ "
Of course the zero vector is in $U$ because we can substitude $x=0$.
But how do I check closure over addition? what is really the rule of the subspace? I would appreciate you help.. I am lost. Thank you!

Your analysis shows that $a\,x^2+b\,x+c\in U$ if and only if $3a\,x^2+b\,x$ is the zero polynomial. This is the case if and only if $a=0$ and $b=0$. Hence $U$ is exactly the set of constant polynomials,
$$
U = \{\,0\,x^2+0\,x+ c\mid c\in\mathbb C\,\} = \mathbb C_0[x] \subseteq \mathbb C_2[x].
$$
This is of course a subspace of $\mathbb C_2[x]$.

Your justification for the fact that $0\in U$ is wrong. We have $0\in U$ because where $0$ is the null polynomial and if $n(x)$ is the null polynomial then it is indeed true that $n(x)=n(2x)$.
If $p(x),q(x)\in U$, then $p(x)=p(2x)$ and $q(x)=q(2x)$. So\begin{align}(p+q)(x)&=p(x)+q(x)\\&=p(2x)+q(2x)\\&=(p+q)(2x)\end{align}and therefore $p(x)+q(x)\in U$.
And if $p(x)\in U$ and $\alpha\in\Bbb C$, then $p(x)=p(2x)$ and \begin{align}(\alpha p)(x)&=\alpha p(x)\\&=\alpha p(2x)\\&=(\alpha p)(2x)\end{align}and therefore $(\alpha p)(x)\in U$.


Intuition behind Fourier coefficients Actually I'm trying to dive into Fourier series and have some trouble understanding the idea behind the Fourier coefficients.

Let's have a Fourier series $$f(x) = a_0 + \sum_{n=1}^{\infty}[a_n\cos(\omega_nx) + b_n\sin(\omega_nx)]$$ where $x \in \langle-\frac{T}{2}, \frac{T}{2}\rangle$, $n \in \mathbb{N}$, $\omega_n = \frac{2\pi}{T}n$ is angular frequency, $T$ is the period of function $f$.

If I understand it correctly I would say that $a_n$/$b_n$ is the amplitude of cosine/sine functions with frequency $n$ Hz (harmonic, since $n \in \mathbb{N}$). And by combining these (potentially infinite) number of functions I get function $f$ (visualization, animation).

Now comes the interesting part - amplitudes/coefficients $a_0$, $a_n$, $b_n$. I understand the calculations... multiplying the equation by $\cos(\omega_kx)$/$\sin(\omega_kx)$, $k \in \mathbb{N}$ and integrating over $\langle-\frac{T}{2}, \frac{T}{2}\rangle$ results in:
$$a_0=\frac{1}{T}\int\limits_{-T/2}^{T/2}f(x)\mathrm{d}x,$$
$$a_k=\frac{2}{T}\int\limits_{-T/2}^{T/2}f(x)\cos(\omega_kx)\mathrm{d}x,$$
$$b_k=\frac{2}{T}\int\limits_{-T/2}^{T/2}f(x)\sin(\omega_kx)\mathrm{d}x.$$

Since $\int_{-T/2}^{T/2}f(x)\mathrm{d}x$ is area beneath function $f$ on interval $\langle-\frac{T}{2}, \frac{T}{2}\rangle$, $a_0$ can be geometrically interpreted as the average value of function $f$ on interval $\langle-\frac{T}{2}, \frac{T}{2}\rangle$ or as the new center of oscillation instead of zero.

What I do not understand is that how $a_k$/$b_k$ can be geometrically interpreted. In particular, I can imagine how $f(x)\cos(\omega_kx)$ look like but I can't wrap my head around the fact that the area beneath $f(x)\cos(\omega_kx)$ on interval $\langle-\frac{T}{2}, \frac{T}{2}\rangle$ divided by $\frac{2}{T}$ is the correct amplitude for function $cos(\omega_kx)$ to be the proper function to be added to others to build up function $f$ (the same for sine function too). Why is there a $2$? And how is it possible that $\int_{-T/2}^{T/2}f(x)\cos(\omega_kx)\mathrm{d}x$ is the right number to determine the correct amplitude for the Fourier series? What is the connection between the area beneath the function and the amplitude? I can't see it geometrically so I think that I miss some very important idea. Or some property of sine/cosine maybe...

Can someone explain the idea behind Fourier coefficients or paste a link where this is explained, please? I've read/watched couple of materials covering this topic but didn't find the answers :( Usually calculations of Fourier coefficient where presented but never the explanation of what does it actually in "human language" means. I consider it to be very important in understanding the essence of Fourier series.

Thanks in advance for any advice.

I'm glad you reposted this here; I saw it on MathOverflow earlier and wanted to answer, but it was closed (and it really is more appropriate here.)

As the answer there suggested, perhaps the best way to think about this is in terms of linear algebra.

Your sines and cosines form a complete orthonormal basis for your space of functions. The inner product on this space is $<f,g> = \int f(x)\bar{g(x)}dx$, and this gives a direct geometric interpretation of the integrals involved in calculating $a_n$ and $b_n$: you are simply projecting your function down onto a given basis vector to see "how much" of it is in "that direction." The $2/T$ factor out front comes from normalizing the basis vectors.

(For more details, see Bessel's inequality and Parseval's identity, or a good book like Stein and Shakarchi's 'Fourier Analysis: An introduction.' They have a wonderfully explicit visualization of this type on page 78, where they prove that partial sums $S_N(x)$ of Fourier series of a function f(x) are the best approximation possible with a trigonometric polynomial of order at most $N$.)

Your Fourier series, then, is equivalent to 'building up' f(x) from (an infinite linear combination of) basis vectors in the space, and the coefficients $a_n$ and $b_n$ tell you how much of each you need. The fact that you can do this at all is the content of Parseval's identity.

The undestanding of intuition behind coefficients of the Fourier transform may be simplified as follows. The imaginary exponential runs from minus infinity to positive infinity. As a result, all imaginary parts (the sine functions) form the negative and positive sides cancel out. What is left is the cosine part. The coefficients are then calculated as an integral of the product of $ f(x)$ and $\cos (\omega x)$. To satisfy the conditions for a Fourier transform, f(x) has to be sum of cosine functions. As the cosine funcions are orthonormal, each integral extracts the correct cosine function from $f(x)$. Thus, $f(x)$ is transformed to a sum of cosine functions.


Probability with a uniform distribution A group of athletes have pulse rates uniformly distributed between 60 and 75. What is the probability that a randomly chosen member of the group has a pulse rate greater than 70?

I am thinking that because it is a uniform distribution, of interval length 15, that the probability would be $\frac{75-70}{15}=\frac{1}{3}$. Is it really that simple, or am I missing something hugely important?

Nope, that's it.  Your probability distribution looks like a rectangle:  $1/15$ on the interval $[60, 75]$ and zero elsewhere.  Slice off the part to the right of $70$ and you get your answer.

I believe the answer would be 5/16.  There are 16 possible pulse rates 60 to 75 both included.  And we are looking at 5 desired pulse rates 71 to 75.  So the probability would be 5/16 not 1/3.  We are looking at discrete distribution as you can not have pulse rates like 60.5 and 70.9.


Zero of a complex polynomial satisfying one of three assertions. Let $n$ be a positive integer greater than $1$. Prove that if $x$ is a zero of  $ X^n+1+(-1)^n(X+1)^n$ then $|x|=1$ or $|x+1|=1$ or $|x+1|=|x|$.

My initial thought was to study the cases $n=2,3,4$ (that confirm indeed the result) in order to establish a general approach, but I didn't succeed to do this.

The set of roots of this polynomial has several symmetries:

It is symmetric in the line $\operatorname{Im}(z) = 0$.
It is symmetric in the line $\operatorname{Re}(z) = -\tfrac{1}{2}$.
It is symmetric under $z \mapsto z^{-1}$ ($z \neq 0$).

Note that the last symmetry maps the line $\operatorname{Re}(z) = -\tfrac{1}{2}$ to $\{z \mid |z+1|=1\}$ and vice versa.

If $n$ is odd then $\{-1,0\}$ are roots.  Let $\zeta$ be a primitive third root of unity.  Then $\zeta + 1$ is a primitive sixth root of unity.  If $3 \nmid n$ then $\zeta^{\pm 1}$ are roots and if $n \equiv 1, 4$ ($\bmod$ $6$) then $\zeta^{\pm 1}$ are double roots.  (One can check this by considering the derivative at $\zeta^{\pm 1}$.)

If we can show that the polynomial has sufficiently many zeroes on the unit circle then its symmetries may suffice to locate all zeroes, which will then automatically satisfy the required conditions.

Substitute $X \leftarrow e^{2it}$ to get

$$\begin{eqnarray}
e^{2i n t} + 1 + (-1)^n(e^{2it} + 1)^n &=& e^{2int} + 1 + (-1)^ne^{int}(2\cos(t))^n \\
&=& e^{int}\left(2\cos(nt) + 2^n(-\cos(t))^n \right)
\end{eqnarray}
$$

and therefore $e^{2it}$ is a zero precisely if $$ \cos(nt) + 2^{n-1}(-\cos(t))^n = 0.$$

If $t \in [\tfrac{\pi}{3}, \tfrac{\pi}{2}]$ then $|2^{n-1}\cos(t)^n| \leq \tfrac{1}{2}$ while $\cos(n t)$ oscillates between $-1$ and $1$.  Therefore there must be a root between any two points where $\cos(nt)$ goes from $-1$ to $1$ or vice versa.  Now $\cos(n t)= \pm 1$ precisely if $nt=m \pi$ for some integer $m$.  By symmetry, each root in the open interval accounts for six roots of the polynomial.  Let's check what happens by considering six different cases $n$ $\bmod$ $6$.

$n = 6k$: $\cos(n t) = \pm 1$ when $2k \leq m \leq 3k$ so $k+1$ times and therefore at least $k$ roots on the open interval. All $6k$ roots are accounted for.

$n=6k+1$. At least double roots at $\zeta^{\pm 1}$ and simple roots at $\{-1,0\}$. Now $\cos(n t) = \pm 1$ when $2k + 1 \leq m \leq 3k$ so $k$ times accounting for at least $k-1$ roots.  So all $6k$ roots are accounted for.

$n=6k+2$. At least simple roots at $\zeta^{\pm 1}$. Now $\cos(n t) = \pm 1$ when $2k + 1 \leq m \leq 3k + 1$ so $k + 1$ times accounting for at least $k$ roots.    So all $6k + 2$ roots are accounted for.

$n=6k+3$. At least simple roots at $\{-1,0\}$.  Now $\cos(n t) = \pm 1$ when $2k + 1 \leq m \leq 3k + 1$ so $k + 1$ times accounting for at least $k$ roots.    So all $6k + 2$ roots are accounted for.

$n=6k+4$. At least double roots at $\zeta^{\pm 1}$.  Now $\cos(n t) = \pm 1$ when $2k + 2 \leq m \leq 3k + 2$ so $k + 1$ times accounting for at least $k$ roots.    So all $6k + 4$ roots are accounted for.

$n=6k+5$. At least simple roots at $\zeta^{\pm 1}$ and $\{-1,0\}$.  Now $\cos(n t) = \pm 1$ when $2k + 2 \leq m \leq 3k + 2$ so $k + 1$ times accounting for at least $k$ roots.  So all $6k + 4$ roots are accounted for.

So in all cases we conclude that the roots satisfy the required conditions.

The following doesn't really help:

This seems like a homework problem, so I'm leaving the details to you. But the key idea is to use the argument principle. For example, we can show that there are no roots with |z|<1 examine what occurs when $|z|<1$ and either $|z+1|<1$ or $|z+1|>1$ by considering $\oint_C \frac{f'(z)}{f(z)}dz$ for any closed contour contained inside the unit circle one of these domains (where $f(z)$ is your polynomial, after factoring out the trivial zeros). Then the integrand is a holomorphic function on this domain (prove it), so the integral evaluates to zero and thus there are no zeros in the interior of the unit circle.

In a similar way, you can extend to consider the domain on which $|z|>1$ and $|z| > |z+1|$, as well as the domain on which $|z| > 1$ and $|z| < |z+1|$.

Hope this helps!


Series which are not Fourier Series How to show that
$$
\sum_{n=2}^\infty \frac{\sin{(nx)}}{\log n}
$$
not the Fourier series of any function?

I have shown that the series is convergent by Dirichlet test.

Let $a(n)=\frac{1}{\log n}$.
What is $\sum (a(n))^2$, to apply Parseval's theorem?

Since $\Bigl\lvert\sum\sin(n x)\Bigr\rvert\leq M$ for $M<\infty$ and $\Bigl\{\frac{1}{\log(n)}\Bigr\}\to 0$ monotonically, by Dirichlet's test, $\sum_{n=2}^{\infty}\frac{\sin(nx)}{\log(n)}$ converges.

If $\sum_{n=2}^{\infty}\frac{\sin(nx)}{\log(n)}$ is a Fourier series, by Parseval's theorem, there exist a Riemann integrable function $f$ such that
$$
\int_{-\pi}^{\pi}\lvert f(x)\rvert^2dx=2\pi\sum_{n=2}^{\infty}\frac{1}{\log^2\lvert n\rvert}
$$

Theorem:

Suppose $a_1\geq a_2\geq\cdots\geq 0$. Then the series $\sum a_n$ converges iff $\sum 2^ka_{2^k}$ converges.
$$
\sum_{n=2}^{\infty}\frac{2^k}{k^2\log^2(2)}\geq\sum_{n=2}^{\infty}\frac{1}{k}=\infty
$$

Therefore, by Cauchy's condensation test, the $\sum_{n=2}^{\infty}\frac{1}{\log^2\lvert n\rvert}$ does not converge which contradicts Parseval's theorem. Thus, $\sum_{n=2}^{\infty}\frac{\sin(nx)}{\log(n)}$ is not a Fourier series.

Suppose that it is the Fourier series of $f(x)$ in $(-\pi,\pi)$, namely,
$$ f(x)=\sum_{n=2}^\infty \frac{\sin(nx)}{\log n},\quad x\in(-\pi,\pi).$$
Then by Pareraval's Identity,
$$\int_{-\pi}^\pi f(x) \, dx=\sum_{n=2}^\infty\frac{1}{\log^2n}=\infty.$$


Using RK4 on the van der Pol oscillator The van der Pol oscillator is modeled by

$$\frac{d^2y}{dt^2} + \mu(y^2 - 1) \frac{dy}{dt} + y = 0$$

This can be written as a system of first order equations,
$$
\begin{pmatrix} \dot x\\ \dot y\end{pmatrix} = \begin{pmatrix} \mu(1-y^2)x - y\\ x\end{pmatrix},
$$

where $x := \dot y$. Consider the case where $y(0) = 0$ and $x(0) = a$, where $a$ is some real number. A numerical approximation for the solution can be obtained using the RK4 method. I have two questions:

How do you find the region of stability for the RK4 method?
How can you verify RK4 is 4th order accurate? Surely you would need to know the true solution in order to verify this?

$\newcommand\rx{\mathfrak{x}}\newcommand\ru{\mathfrak{u}}\newcommand\mA{\mathfrak{A}}$

) For the definition of the most common stability properties one refers to the properties of solutions of linear systems of ODE. Apply the RK4 method to some linear system $\ru'=\mA\ru$ (for instance the linearization of a non-linear ODE system around a fixed point). You should get exactly the first 5 terms (up to degree 4) of the exponential series.

  The stability condition is that this propagator has to be non-expanding if the spectrum of $\mA$ is contained in the negative half-plane of the complex plane. On the level of singular eigenvalues $\lambda$ and $z=λh$ with step size $h$ this means that $z$ is in the stability region if  $$|1+z+z^2/2+z^3/6+z^4/24|\le1.$$

The half-circle with $\Im(z)\le 0$, $|z|\le 2.5$ is contained in that set.

If $L$ is a Lipschitz constant (or $L=\|\mA\|$), then this gives a bound $h<2.5/L$. At the upper bound the numerical solution is merely not totally wrong, for a useful solution one needs a much smaller step size, $Lh\in[10^{-3},10^{-1}]$. Step sizes much smaller than that lead to an accumulation of floating point errors that dominate the method error.

See Maximum timestep for RK4 for visualizations of the stability region and the effect of too small or too large step sizes.
) There are two readily available strategies to explore the error picture of a numerical ODE solver.

One proceeds to compute a series of results over a series of doubled step sizes $Lh=(1,2,4,8)·10^{-2}$. Compare these to the expected formula $y_h=y^*+C·h^4+O(h^5)$, that is, apply Richardson extrapolation to compute values for $C$ and $y^*$ and check if they are stable over all the doublings.
Another strategy uses MMS (manufactured solutions). Here one would fix some nice function $p$ and consider the equation
$$
y''+μ(y^2−1)y'+y=p''+μ(p^2−1)p'+p, ~~~y(0)=p(0),~~y'(0)=p'(0),
$$
for instance $p(t)=2\sin(t)$ or with the next perturbation term added. Then $p$ is the exact solution that the numerical solution can be compared against.
If you want to actually prove the order, that is, verify the order conditions, read up on Butcher trees, for instance on Butcher's homepage https://www.math.auckland.ac.nz/~butcher/ODE-book-2008/Tutorials/. Or read the original derivation of the low order Runge-Kutta methods in W. Kutta (1901) https://archive.org/details/zeitschriftfrma12runggoog/page/n449


Prove Vizing Class 1 if maximum degree vertices induce forest by induction I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $\chi'(G) \leq \Delta(G)$, in other words, the graph is in Vizing Class 1.

When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v \in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $G\setminus e$ for an edge $e$ incident with $v$.

If I remove $e$, there might be vertices of degree $\Delta(G) - 1$ inducing a cycle. This graph is an example. If we remove the degree 5 vertex, then the degree 4 vertices don't induce a forest.

How can I solve this problem? Is there a way to fix this proof?

if the maximum degree of G\e is not Δ(G),then Δ(G\e)+1≤Δ(G) and by Vizing there is a Δ(G) edge coloring. Thats all you need


The greatest revenue? A theatre seats 2000 people and charges $10 for a ticket. At this price all the tickets can be sold. A survey indicates that if the ticket price is increased, the number sold will decrease by 100 for every dollar of increase. What ticket price would result in the greatest revenue?

Hint: If we have $x$ dollars of increase, we get: $$(2000-100x)(10+x)$$
We are attempting to maximize this value.

To solve this problem, you need to use some simple calculus. Let $x$ be the price of the ticket. When $x=10$, we know that $2000$ seats are sold and that $100$ fewer seats are sold for every dollar increase in price. This nets us the equation:

seats sold $= 2000-100(x-10)$

If we multiply this by the price of the ticket, we can find the total revenue $R$:

$R=x(2000-100(x-10))$

$=2000x-100x(x-10)$

$=2000x-100x^{2}+1000x$

$=3000x-100x^2$

Since we're trying to find a maximum for this expression, we can run this function for revenue through any monotonically increasing analytic function and their maximum will occur at the same value of $x$. Therefore, we can divide the equation by $100$ to find:

$30x-x^{2}$

Taking the derivative with respect to $x$, we have:

$30-2x$

... and setting this to zero, we have:

$0=30-2x$

$2x=30$

$x=15$

Lastly, we can verify that this is a maximum and not a minimum because the second derivative of our revenue function is negative.

Therefore, you'll want to price your tickets at $15.


Sequence of natural numbers Numbers $1,2,...,n$ are written in sequence. It's allowed to exchange any two elements. Is it possible to return to the starting position after an odd number of movements?

I know that is necessarily an even number of movements but I can't explain that!

Hint: Define an inversion of a sequence $(a_1,\dots,a_n)$ as a pair $(i,j)$, such that $i<j$ and $a_i>a_j$. Check, that each movement changes the parity of number of inversions.

Basically, if you make an odd number of switches, then at least one of the numbers has only been moved once (unless you repeat the same switch over and over which is an easy case to explain). But if you start in some configuration and move a number only once and want to return to the start, you must move again.

Try induction -- an easy base case is $n=2$.


Probability of 3 people in a room of 30 having the same birthday I have been looking at the birthday problem (http://en.wikipedia.org/wiki/Birthday_problem) and I am trying to figure out what the probability of 3 people sharing a birthday in a room of 30 people is. (Instead of 2).

I thought I understood the problem but I guess not since I have no idea how to do it with 3.

The birthday problem with 2 people is quite easy because finding the probability of the complementary event "all birthdays distinct" is straightforward. For 3 people, the complementary event includes "all birthdays distinct", "one pair and the rest distinct", "two pairs and the rest distinct", etc. To find the exact value is pretty complicated.

The Poisson approximation is pretty good, though. Imagine checking every triple and calling it a "success" if all three have the same birthdays. The total number of successes is approximately Poisson with mean value ${30 \choose 3}/365^2$. Here $30\choose 3$ is the number of triples, and $1/365^2$ is the chance that any particular triple is a success.
The probability of getting at least one success is obtained from the Poisson distribution:
$$ P(\mbox{ at least one triple birthday with 30 people})\approx 1-\exp(-{30 \choose 3}/365^2)=.0300. $$

You can modify this formula for other values, changing either 30 or 3. For instance,
$$ P(\mbox{ at least one triple birthday with 100 people})\approx 1-\exp(-{100 \choose 3}/365^2)=.7029,$$
$$ P(\mbox{ at least one double birthday with 25 people })\approx 1-\exp(-{25 \choose 2}/365)=.5604.$$

Poisson approximation is very useful in probability, not only for birthday problems!

I am looking at this question and the complicated answers and it's confusing me. Supposing I want to solve in a group of 100 people. what is the probability that at least 3 people share a birthday. So I start from very basic - if there are 3 people, the probability of them sharing a birthday is $$\frac{1}{365} *\frac{1}{365}*\frac{1}{365}*(365)=\frac{1}{(365)^2}$$ 1/365 the prob. of 1 person having a birthday on a particular day multiplied by each person's probability multiplied by the total no. of days.
Similarly if there are 4 people, the probability of at least 3 of them sharing a birthday would be $\frac{1}{(365)^2}*^4C_3 $. and similarly for x people, $\frac{1}{(365)^2}*^XC_3 $
I am trying to find the fault in this logic.


Finding a pdf with a non-monotone function The approach I am taking involves first finding a CDF, then taking its derivative to find the PDF.   Say I have the function $f_{X}(x)=(x+1)^{2}/2$ such that $x$ is in $(-1,1)$ and $Y=1-X^2$.   I want to find the pdf of $Y$.   I guess the part I'm stuck on in finding the CDF is dealing with the $Y$.   What I want to do is to find $F_{X}(x)$, but I'm not sure if I should complete the squares or maybe I should be summing up probabilities.

Can I get some advice on this?

$P(Y\leq x)=P(1-X^2\leq x)=P(X^2\geq 1-x)$

Now if $x<0$ then $1-x>1$ so $P(X^2\geq 1-x)=0$ (since $X$ is in $(-1,1)$). So taking derivative w.r.t.$x$ also yields $0$.

So let's have $x>0$. If $x\in (0,1)$ then $1-x\in(0,1)$ so $P(X^2\geq 1-x)=P(X\geq\sqrt{1-x})+P(X\leq -\sqrt{1-x})$, each of which you can find since the pdf of $X$ is given to you. Taking derivative w.r.t. $x$ will yield the pdf of $$ within this range.

To do the computation, taking $\sqrt{1-x}=a$ we have $P(X\geq a)+P(X\leq-a)=\int_a^1(x+1)^2/2 dx+\int_{-1}^{-a}(x+1)^2/2dx=\int_a^1(x+1)^2dx=\dfrac{2^3-(a+1)^3}{3}=\dfrac{8-(a+1)^3}{3}=\dfrac{8-(\sqrt{1-x}+1)^3}{3}$.

Taking derivative w.r.t. $x$ we have $\dfrac{-3(\sqrt{1-x}+1)^2(-1)}{2\times3\sqrt{1-x}}=\dfrac{(\sqrt{1-x}+1)^2}{2\sqrt{1-x}}$

If $x>1$ then $1-x<0$ so $P(X^2>1-x)=1$ (since $X^2\geq0>1-x)$. Taking derivative w.r.t. $x$ you end up with the pdf on this range being $0$.

So the pdf is $f_Y(x)=\dfrac{(\sqrt{1-x}+1)^2}{2\sqrt{1-x}}$ if $x\in(0,1)$ and $0$ otherwise.

By change of variables $f_Y(y) = f_X(g^{-1}(y))\left\lvert\frac{\operatorname d g^{-1}(y)}{\operatorname d y}\right\lvert$ if $Y=g(X)$ and $g(x)$ is an invertable function (a one-to-one mapping).

The "trick" here is that $1-X^2$ is not strictly invertable in the interval $X\in(-1;1)$, it folds the interval onto $[-1;0)$.

The solution is to treat it as two functions, one mapping $(-1;0)$ to $(-1;0)$ and the other mapping $[0;1)$ to $[-1;0)$.

$$\begin{align}
g_1(x) & = (1-(-\lvert x\rvert)^2)\mathbf 1_{x\in(-1;0)} \\[1ex] g_2(x) & = (1-(+\lvert x\rvert)^2)\mathbf 1_{x\in[0;1)}
\\[2ex] g_1^{-1}(y) & = -\sqrt{1-y\;} \mathbf 1_{y\in(-1;0)}
\\[1ex] g_2^{-1}(y) & = +\sqrt{1-y\;}\mathbf 1_{y\in[-1;0)}
\\[3ex] f_Y(y) & = f_X(g_1^{-1}(y))\;\left\lvert\frac{\operatorname d g_1^{-1}(y)}{\operatorname d y}\right\lvert\;\mathbf 1_{y\in(-1;0)} + f_X(g_2^{-1}(y))\;\left\lvert\frac{\operatorname d g_2^{-1}(y)}{\operatorname d y}\right\lvert\;\mathbf 1_{y\in[-1;0)}
\\[1ex] ~ & = {\tfrac 1 2{\left(1+\left(-\sqrt{1-y^2\;}\right)\right)}^2\;\left\lvert \frac{\operatorname d -\sqrt{1-y^2\;}}{\operatorname d y}\right\rvert\;\mathbf 1_{y\in(-1;0)} + \\ \quad \tfrac 1 2{\left(1+{\left(+\sqrt{1-y^2\;}\right)\right)}^2\;\left\lvert \frac{\operatorname d +\sqrt{1-y^2\;}}{\operatorname d y}\right\rvert\;\mathbf 1_{y\in[-1;0)}}
\end{align}$$

Derivate and simplify to obtain the pdf.   Then integrate the result to get the CDF.


Is the set of points or the set of lines on a plane "larger"? Is the set of points or the set of lines on a plane "larger",or there is a 1-1 correspondence between lines and points?

I assume the question asked by Marios was about the real plane, but planes over finite fields might also lead to interesting statements. First, let's take an example. Let $P$ be the affine plane over the two-element field $\mathbb{F}_2$. There are 4 points in this plane, but there are 6 lines (i.e. one-dimensional affine spaces) in this plane.

The proof for $\mathbb{R}$

We have a one-to-one mapping from $\mathbb{R}^2 \setminus\{(0,0)\}$ to $\mathcal{L}$ (I couldn't find simpler) : take any element $(a,b)$ and form the line $d_{a,b}$ which is tangent at the circle of center $0$ and radius $\sqrt{a^2 + b^2}$ at the point $(a,b)$. This is injective. It is not surjective, as the lines going through $(0,0)$ (let's denote it by $\mathbb{P}_1(\mathbb{R})$ ) do not have the form $d_{a,b}$.

Therefore, the set $\mathcal{L}$ have the same cardinality as $\mathbb{P}_1(\mathbb{R}) \cup \mathbb{R}^2 \setminus\{(0,0)\}$. But it is known that there is a bijection $\phi$ between $\mathbb{P}_1(\mathbb{R})$ and $\mathbb{R} \cup \infty$ : if $d \in \mathbb{P}_1(\mathbb{R})$ , let $\phi(d)$ be $x$, where $(x,1)$ is the intersection between $d$ and the horizontal line $y=1$. If $d$ is the line $y=0$, then $\phi(d) = \infty$. This is a bijection (it is clear on a drawing).

To conclude, we have a bijection of $\mathcal{L}$ onto $\mathbb{R}^3$. It can be shown that there is a bijection of $\mathbb{R}^3$ to $\mathbb{R}$.

The general case

In the general case, we might expect the number of lines to be "greater" than the plane.

First, note that there is a bijection of the projective space $\mathbb{P}_1(\Bbbk)$ onto $\Bbbk \cup \infty$, where $\infty$ is another point added to $\Bbbk$. When the field $\Bbbk$ is finite, it means that there is exactly as much one-dimensional vector spaces than elements in $\Bbbk$, plus one. When $\Bbbk$ is $\mathbb{R}$ or $\mathbb{C}$ they have the same cardinality.

Now note $\mathcal{L}_A$ the set of lines going through some point $x$ belonging to the set $A$. For instance, $\mathcal{L}_x$ is the set of lines going through $x$ and $\mathcal{L}_P$ is the set of all lines.

Note that $\mathcal{L}_x$ has the same cardinality as $\mathbb{P}_1(\Bbbk)$. Moreover, if $x \neq y$, then $\mathcal{L}_x \cap \mathcal{L}_y$ is a singleton (there is only one line going through $x$ and $y$ when $x \neq y$).

Using this, we show that the set of lines $\mathcal{L}$ is strictly greater than $P$, whatever be $\Bbbk$. In fact, take two points $x,y$ in $P$, we  have a bijection of $\mathcal{L}_{\{x,y\}}$ onto $(\Bbbk)^2$ (we have removed an element counted twice).

This question has several answer. Strictly speaking, there exists a bijection but it is somehow a very complicated one and not very useful either. It is not continuous, meaning that two points that are close to each other can correspond to lines that are very far. In fact, both sets, lines in the plane and points in the plane, are also in bijection with... points in a line ! Even if these sets feel very different from each other.

The second answer is that there are more lines in the plane than there are points. But in that case, the correspondence is very easy to write :

For instance, you can take the following : $(a,b)\mapsto L_{a,b}$ where $L_{a,b}$ is the line whose equation is $y=ax+b$. It is obviously injective, but not onto, because the vertical maps are not in the image. Hence, we can say that there are more lines that points.


How to draw an undirected graph with nodes of degrees: $2, 2, 2, 2, 2, 1, 1, 1, 1$ I want to draw an undirected connected graph with $9$ nodes, having the degrees:

$$2, 2, 2, 2, 2, 1, 1, 1, 1$$

I know that this graph will have $7$ edges, but how? I am trying each time, I am stopping after node $7$ and if I draw $8$ it is having degree $2$ instead of $1$. Please help.

No such graph exists:

Proof 1:

This can be proved with the Havel-Hakimi theorem quite easily:

Iteration $1$:If $2,2,2,2,2,2,2,1,1$ is graphical, so is $1,1,2,2,2,2,1,1=2,2,2,2,1,1,1,1$, this is of total even degree, reapply H-H,

Iteration $2$: $2,2,2,2,1,1,1,1\to 1,1,2,1,1,1,1=2,1,1,1,1,1,1$ this is even, reapply H-H

Iteration $3$:  $2,1,1,1,1,1,1\to0,0,1,1,1,1$, this isn't connected, and hence doesn't meet the criteria. Hence no such graph is graphical.

Proof 2:

If such a connected graph existed, that joined all vertices(nodes), it would need to have atleast $8$ edges. This means the total degree would need to be $\geq 16$. Here we have a total degree of $14$, which isn't possible.

Even without the $8$ edge observation, we have $4$ vertices with degree $1$, this means the remaining degree is $10$ between the last $5$, this is $2$ each.

If we have $4$ with degree one, we have

Case 1) $4$ vertices to pick, each of them already have degree one

Case 2) $1$ that has degree $0$.

1) If we choose to join any of the $4$ together, they both become degree $2$, and we can do this with any choice, this instantly makes the problem unconnected, as we have $2$ edges to join $3$ disjoint paths.

2) If we connect this to one of our 'to be degree two', we have '$2,1,1,1,1,1,1,1,1$', with three edges to place. This can only leave us with '$2,2,2,2,2,2,2,1,1$'

Hence this cannot occur.

This is a different issue. Does there exist a graph on n nodes where the degrees are as different as possible. By that I mean that two of nodes have the same degree and the remaining n-2 nodes all have different degrees. Suppose that we have 2 nodes of degree 1 and that the remaining n-2 nodes have degrees
2 3 4 .........n-1. Does such a graph exist?


Decision theory vs. Game theory? Game theory is defined (here) as follows:

  "Game theory, branch of applied mathematics that provides tools for
  analyzing situations in which parties, called players, make decisions
  that are interdependent. "

And Decision theory is defined (here) as follows:

  "Decision theory is concerned with the reasoning underlying an agent’s
  choices."

Regarding to above definitions, can we say that Decision theory is a subset of Game theory? Or they are completely two different concepts? And in general, what are their common points?

Game theory has people as players, decision theory has probability distributions of decision networks. Game theory is concerned with what the probability and utility need to be to model an observed outcome. The probabilities and utilities are sometimes modelled as piecewise functions. Decision theory uses a prior probability to predict potential outcomes. Such potential outcomes might be a Markov chain. Game Theory is mathematical, decision theory is statistical, if the distinction makes sense. There are overlaps, but that is true with everything. I do not believe that decision theory is a subset of game theory.


Why are these representations of e the same? I heard that $e$ can be defined as the limit as n approaches infinity of $(1 + 1/n)^n$, but I also heard that $e$ is also defined as the sum of the reciprocals of the factorials from $0$ to $\infty$. How are these the same?

Let's find an infinite polynomial $p(x)$ having $p(0) = 1$ and $\frac{d}{dx}p(x) = p(x)$.  We know that the constant term must be 1, and the coefficient of $x^1$ must be 1.  After a little reflection, it's easy to see that
$$p(x) = \sum_{i=0}^{\infty} \frac{x^i}{i!}$$
This must be the only continuous function having these two properties.

Now let's look at the limit

$$L(x) = \lim_{n \rightarrow \infty} \left(1 + \frac{x}{n}\right)^n$$

$$\begin{align}
\frac{d}{dx} L(x)
& = \frac{d}{dx} \left\{\lim_{n \rightarrow \infty} \left(1 + \frac{x}{n}\right)^n\right\}\\
& = \lim_{n \rightarrow \infty} \frac{d}{dx} \left\{\left(1 + \frac{x}{n}\right)^n\right\}\\
& = \lim_{n \rightarrow \infty}\left(\frac{d}{dx} \left\{1 + \frac{x}{n}\right\}n\left(1 + \frac{x}{n}\right)^{n-1}\right)\\
& = \lim_{n \rightarrow \infty}\left(1 + \frac{x}{n}\right)^{n-1}\\
\end{align}$$

So:

$$\begin{align}
L(x) - \frac{d}{dx}L(x) & = \lim_{n \rightarrow \infty}\left(1 + \frac{x}{n}\right)^{n}-\lim_{n \rightarrow \infty}\left(1 + \frac{x}{n}\right)^{n-1}\\
& = \lim_{n \rightarrow \infty}\left(\left(1 + \frac{x}{n}\right)^{n}-\left(1 + \frac{x}{n}\right)^{n-1}\right)\\
& = \lim_{n \rightarrow \infty}\left(\left(1 + \frac{x}{n}\right)^{n-1}\left(\left(1 + \frac{x}{n}\right)-1\right)\right)\\
& = \lim_{n \rightarrow \infty}\left(\left(1 + \frac{x}{n}\right)^{n-
1}\left(\frac{x}{n}\right)\right)\\
& = \lim_{n \rightarrow \infty}\left(\left(1 + \frac{x}{n}\right)^{n-1}\left(0\right)\right)\\
L(x) - \frac{d}{dx}L(x) & = 0
\end{align}$$
So $L(x) = \frac{d}{dx}L(x)$, $L(0) = 1$, and $L$ is a continuous function.  So $L(x) = p(x)$, and specifically $L(1) = p(1) = e$.


Does there exist a function that is differentiable everywhere with everywhere discontinuous partial derivatives? Does there exist a function that is differentiable everywhere with everywhere discontinuous  partial derivatives?

I just had this doubt, talking about first order partials.

It is not possible  for such function  to exist.
The differentiability of $f$ implies $f$ is continuous , therefore $\frac{\partial{f}}{\partial{x}}$ and $\frac{\partial{f}}{\partial{y}}$ are both of Baire class one, which means they have a dense set of points of continuity .

By the way, I am also curious about if there exists a function with both partial derivative exist everywhere but are continuous nowhere. Since such function is only of Baire class one and its partial derivatives are of Baire class two (not necessarily of Baire class one), it seems to have a little possibility.


What is a Complex Name? On Page 38, Elementary Set Theory with a Universal Set, Randall Holmes(2012), which can be found here.

  We give a semi-formal definition of complex names (this is a variation on
  Bertrand Russell's Theory of Descriptions):

  Definition. A sentence  $\psi [(\text{the }y\text{ such that }\phi)/x]$ is defined as $$\begin{align*}&\big((\text{there is
exactly one }y\text{ such that }\phi)\text{ implies }(\text{for all }y, \phi\text{ implies }\psi[y/x])\big)\\&\text{ and }\\&\Big(\big(\text{not}(\text{there is exactly one }y\text{ such that }\phi)\big)\text{ implies }\\&\qquad\big(\text{for all }x,(x\text{ is the empty set})\text{ implies }\psi\big)\Big)\;.\end{align*}$$ Renaming of bound variables may be needed.

Definition of the form "$\phi[y/x]$" is:

  Definition. When $\phi$ is a sentence and $y$ is a variable, we define $\phi[y/x]$ as
  the result of substituting $y$ for $x$ throughout $phi$, but only in case there
  are no bound occurrences of $x$ or $y$ in $\phi$. (We note for later, when
  we allow the construction of complex names $a$ which might contain
  bound variables, that $\phi[a/x]$ is only defined if no bound variable of $a$
  occurs in  $\phi$ (free or bound) and vice versa).

I can't understand why  $\psi [($the$\, y\, $such that$\, \phi)/x]$ is defined as it is? Especially, "((not(there is exactly one $y$ such that $\phi$ )) implies (for all $x$, ($x$ is the
empty set) implies $\psi$  ))" seems to come out of nowhere.

Feel free to retag this question, I'm not sure if some other disciplines, like elementary set theory, lingusitics are more closely related to it.

Good question. A guess coming up.

General issue: How should we regard expressions of the form "the $\varphi$" or better "the $y$ such that $\varphi(y)$".

Option one: as mere "syntax sugar" that can be parsed away. This is Russell's line. "The $y$ such that $\varphi(y)$" isn't really a complex name, but vanishes on analysis, because (i) $\psi$(the $y$ such that $\varphi(y)$) is equivalent to (ii) there is at least one thing which is $\varphi$ and at most one thing which is $\varphi$ and whatever is $\varphi$ is $\psi$.

Option two: descriptions are complex names. "The $y$ such that $\varphi(y)$" is a complex name of the one and only one thing that is $\varphi$ if there is such a thing, and takes a default value, say the empty set, if there isn't. This was Frege's line.

Both treatments are logically workable. Or we can mix them. Which seems to be what Holmes is doing here.

We do parsing away (a la Russell): but treat the cases where there is and where there isn't a unique $\varphi$ differently, in effect supplying a default value when there isn't (a la Frege). So, roughly speaking, $\psi$(the $y$ such that $\varphi(y)$) says that whatever is $\varphi$ is $\psi$ if there is a unique $\varphi$, but becomes [equivalent to] $\psi(\emptyset)$ when there is no unique $\varphi$.

But I am making this up as I go along, you understand: caveat lector!

Note: if you want to downvote this, please read it first and then leave a comment.

The way Holmes presents this matter is not clear at all. How is the theory of descriptions and logic related?

A good example is the word "and". We use "and" in the english language and there is the symbol of symbol logic "$ \wedge $". Consider the mapping f from "and" to "$\wedge$" and g from "$\wedge$" to "and".

$f: $ "and" $\rightarrow "\wedge" $

$g: "\wedge" \rightarrow $ "and"

Now, Frege and Russell introduced the symbol logic, so that we can clearly distinguish between "and" and "$\wedge$", because they are not at all the same. Consider the expression "two and two is four". The expression is best translated as 2+2=4. Translation means really taking the first expression and putting into a proper system of logic. For instance here the word "and" was translated into the obivous symbol for addition "+", and not "$\wedge$", although a naive translator would not have known what "and" should stand for.

This matter is not at all trivial, and is not linguistics but logic proper (philosophy if you will). We want to know how the symbols "+" and "$\wedge$" operate. This study is what we call logic in the first place. For instance a few days ago, people downvoted my elementary proof of logic, probably because they thought real mathematicians use lots of strange symbols. However when we are concerned with logic, we can't be so presumptuous. We can't simply throw around symbols and hope that it will all make sense in the end.

Where this kind of analysis comes from is thinking about propositions. What does it mean to talk about anything? Well, if we talk about a thing, we are refering to its existence or non-existence. Which is why a mathematical expression will start with the phrase: $\exists x ...$ or $\nexists x ...$

In his theory of denoting Russells explains why every statements refers to all other things

Definition of all: $C(E) \leftrightarrow \forall x C(x)$
Definition of nothing: $C(N) \leftrightarrow \forall x \neg C(x)$
Definition of exists $C(S)\leftrightarrow \neg \forall x \neg C(x)$

E="Everything",N="Nothing",S="Something". Taken from wikipedia.
See also http://en.wikipedia.org/wiki/Theory_of_descriptions

What this achieves is that it shows a certain map, as explained above, but not for "and", but for the expression "exists". So we could say we have explained the map

$h: $ "exists x" $\rightarrow "\exists x"$

, although there are some remaining issues. What one should realize is that all of mathematics essentially is build on this theory, although very mathematicians realize it.

Holmes sentence is an ackward variant of this theory of description. You arrive at it, by applying the given definitions. A much better way to understand the operations is to look at the axioms, see metamath: PL, and play around with them.


Invariant subspaces of Frobenius automorphism Given finite field, is it true that any invariant subspace of its
  Frobenius automorphism is a subfield?

Firstly, I know that $F_{p^k}$ is a subfield of $F_{p^n}$ if and only if $k$ divides $n$.

For the second, it seems that we shall use that if finite field is of characteristic $p$ then any element satisfies $x^p=x$.

However, I can't proceed to the final answer from this remarks. Can anyone explain me is it truth or not and why?

$\newcommand{\F}{\mathbb{F}}$I understand the question to be

  Suppose the $\F_{p}$-subspace $V$ of the finite field $\F_{p^{n}}$ is invariant under the Frobenius automorphism.
  Is $V$ a subfield of $\F_{p^{n}}$?

The answer is negative.

Let $E = \F_{p^{6}}$.

Then $U = \F_{p^{2}}$, $W = \F_{p^{3}}$ are subfields of $E$, and thus $\F_{p}$-subspaces of $E$.

Then $V = U + W$ is an $\F_{p}$-subspace of $E$, which has dimension $2 + 3 - 1 = 4$ over $\F_{p}$, and thus order $p^{4}$, so that it is not a subfield of $E$.

However $V$ is invariant under the Frobenius automorphism, as $U$ and $W$ are.

It seems that I found a proof. Denote our finite field of characteristic $p$ by $F_{p^n}$. Then set of all elements invariant under $x \mapsto x^p$ contains prime subfield $F_p$ and roots of the polynomial $t^p-t$, but $\vert F_p \vert = p$, so the invariant subset is exactly the prime subfield $F_p$ and the answer is yes.

Moreover, multiplication group $F_{p^n}^*$ is cyclic of order $p^n-1$ and by Lagrange theorem any its element has order $k \in \mathbb{N}$, where $k$ divides $p^n-1$.

Is everything correct?


Fuzzy logic and topos theory Why doesn't one develop fuzzy logic by extending topos theory, by simply extending the subobject classifier $\Omega$ to the unit interval [0,1]?  Have people done that?

Here are some papers, which I have not read in detail. I'm somewhat troubled that there aren't any Math Reviews for most of them, and I certainly can't vouch for their correctness. (I know nothing of fuzzy logic, and only a miniscule bit of topos theory; I'm merely an enthusiast.)

Pitts, Andrew M. (1982). Fuzzy sets do not form a topos. In: Fuzzy Sets and Systems 8.1, pp. 101–104. DOI: 10.1016/0165-0114(82)90034-3

Let $H$ be a complete Heyting algebra. The main result is that the category of $H$-valued fuzzy sets $\textrm{Fuz}(H)$ defined by Eytan is a topos if and only if $H$ is a Boolean algebra. Apparently, the problem is that $H$-valued fuzzy sets are insufficiently ‘fuzzified’ (Pitt's word!) to be well-behaved enough to form a topos. To be precise, $H$-valued fuzzy sets ‘fuzzify’ only the $\in$ predicate, while $H$-valued sets ‘fuzzify’ both $=$ and $\in$. It can be shown that the category of $H$-valued sets is equivalent to the category of sheaves over $H$, and hence do form a topos $H\textrm{-Set}$. Pitt shows that $H$-valued fuzzy sets are equivalent to a certain full subcategory of $H\textrm{-Set}$
Stout, Lawrence Neff (1984). Topoi and categories of fuzzy sets. In: Fuzzy Sets and Systems 12.2 pp. 169–184. DOI: 10.1016/0165-0114(84)90036-8

Let $L$ be a completely distributive lattice. (Then it is also a complete Heyting algebra $H$.) The paper starts by showing that Goguen's characterisation of categories of sets having ‘fuzzy boundary with fuzziness measured in $L$’ $\textrm{Set}(L)$ are essentially incompatible with the axioms of elementary toposes: $\textrm{Set}(L)$ is a topos if and only if $L$ is the trivial lattice, in which case the category is the usual category of sets. As above, Goguen suggested that a ‘nicer category may result by taking maps which are fuzzy as well’; apparently this is what Eytan did with his $\textrm{Fuz}(H)$.

Stout continues with a brief examination of the internal logic of $\textrm{Set}(H)$, $\textrm{Fuz}(H)$, $\textrm{Sh}(H)$, noting that the internal logic of these categories and the usual fuzzy logic operations do not necessarily coincide, and $\textrm{Set}^{H^{\textrm{op}}}$ and concludes with some results about change-of-base for these categories.
Barr, Michael (1986) Fuzzy set theory and topos theory. In: Canad. Math. Bull. 29.4, pp.501–508. DOI: 10.4153/CMB-1986-079-9.

There is a Math Review for this paper: MR860861.

Let $L$ be a locale. Like the above two papers, the main contention is that $L$-valued fuzzy sets are not fuzzy enough for their categories to be toposes. Barr describes one generalisation and shows that it is equivalent to a sheaf on a locale $L^+$, obtained by extending $L$ with a new bottom element, and also shows that Eytan's  $\textrm{Fuz}(L)$ is equivalent to a certain subcategory of $\textrm{Sh}(L^+)$.
Stout, Lawrence Neff (1991). A survey of Fuzzy Set and topos theory. In: Fuzzy Sets and Systems 42.1, pp. 3–14. DOI: 10.1016/0165-0114(91)90085-5.

I'll just quote the paper directly: ‘Our survey of the various categorical formulations of Fuzzy Set theory and a variety of kinds of topoi will suggest that a synthesis of the two fields, involving some refinement of the notion of a category of fuzzy sets to give something weaker than a topos but with a richer logic, is desirable.

[...]

‘Throughout this process we should remember that the object is to find a proper foundation for Fuzzy Set theory, so that the original interval-valued fuzzy sets should at least be embeddable into our structure. The choice of definition should be based on what is natural, what is powerful, and what gives an elegant and complete foundation for fuzzy mathematics.’

Fuzzy set theory is a mathematical model of vagueness, which is assumed to be a basic property of our world. In different words, it is assumed that we live in a world with vague objects where nothing is actually crisp. Ordinary mathematics assumes that everything is crisp. Thus I find it at least strange to try to "embed" mathematics of vagueness into universes of crisp mathematics. So I do not really understand what a topos of fuzzy sets would be? Arrows should connect objects up to some degree but this does not happen when one deals with say categories of fuzzy sets. Since we have a new set theory, which was also formalized, we need a new catetory theory and why not a new type theory.


Let $f : E \rightarrow \mathbb{R}$. Show that if $|f|$ is measurable on $E$ and the set $\{f > 0\}$ is measurable, then $f$ is measurable on $E$. I'm learning about Measure Theory (specifically measurable functions) and need help with the following problem:

  Let $f : E \rightarrow \mathbb{R}$. Show that if $|f|$ is measurable on $E$ and the set $\{f > 0\}$ is measurable, then $f$ is measurable on $E$.

What I don't understand is that the implication $$|f| \ \text{measurable}  \implies f \ \text{measurable} \ \ (1)$$ is clearly false.

For example, let $A$ be a non-measurable subset of $\mathbb{R}$, and let $f$ be the function $$f(x) = \begin{cases} 1\text{ if }x\in A,\\ -1\text{ if }x\notin A.\end{cases}$$

Then $f$ is not measurable ($f^{-1}[\{1\}] = A$) but $|f|$ is measurable (it's the constant function $1$).

How does the additional condition that $\{f > 0\}$ is measurable makes the implication $(1)$ true and how do I prove it?

Ok, I make my comment an answer. I assume that you know that product and sum of two measurable functions is again measurable. Define $f_+ := \max\{f,0\} = |f|\cdot\chi_{\{f>0\}}$. This function is measurable. Also, define $f_- := \min\{f,0\} = (-|f|)\cdot\chi_{\{f\le 0\}}$. Also this function is measurable. So, $f = f_+ + f_-$ is measurable.

EDIT: To see that $\chi_A$ is measurable for each measurable set $A$, you only have to realize that $\chi_A^{-1}(B)$ can only be equal to $\emptyset$, the whole measurable space $E$, $A$ or $E\setminus A$ (depending on whether $0\in B$ or $1\in B$).


A Fourier Analysis Question I am stuck at If $f,g\in C[-\pi,\pi]$,and $f,g$ are $2\pi$ periodic, prove that $$\lim_{n\to\infty}\dfrac{1}{2\pi}\int_{-\pi}^\pi f(t)g(nt)\mathbb dt=\big(\dfrac{1}{2\pi}\int_{-\pi}^\pi f(t)\mathbb dt\big)\big(\dfrac{1}{2\pi}\int_{-\pi}^\pi g(t)\mathbb dt\big)$$

I tried to approximate $g(nt)$ by a trigonometric polynomial $T_n(t)$ but the problem is that $n$ is varying here. Nothing seems to work. I tried to interpret the left side as the constant Fourier coefficient of the function $f(x)g(nx)$ and the right side as the product of constant Fourier coefficients of $f(x)$ and $g(x)$ but because $f$ and $g$ are just continuous and not Lipschitz, I cannot replace $f$ and $g$ by their Fourier sums.

Please give me a hint only to get started on this problem.

Let $a_{k}$ and $b_{k}$ be
$$
      a_{k}=\frac{1}{2\pi}\int_{0}^{2\pi}e^{-ikx}f(x)dx,\;\;\;
      b_{k}=\frac{1}{2\pi}\int_{0}^{2\pi}e^{-ikx}g(x)dx.
$$
Then $g(x)=\sum_{k=-\infty}^{\infty}b_{k}e^{ikx}$ converges in $L^{2}$ on any finite interval to the periodic extension of $g$. More explicitly, if $S_{N}=\sum_{n=-N}^{N}b_{k}e^{ikx}$, then, for fixed $n=1,2,3,\cdots$,
$$
         \lim_{N\rightarrow\infty}\int_{0}^{2n\pi}|g(x)-S_{N}(x)|^{2}dx= 0.
$$
By a simple change of variables, for fixed $n=1,2,3,\cdots$, one has
$$
         \lim_{N\rightarrow\infty}\int_{0}^{2\pi}|g(nx)-S_{N}(nx)|^{2}dx = 0.
$$
Then, for $f \in L^{2}$, it follows that, for fixed $n=1,2,3,\cdots$,
$$
         \int_{0}^{2\pi}f(x)g(nx)dx = \lim_{N\rightarrow\infty}\int_{0}^{2\pi}f(x)S_{N}(nx)dx.
$$
The above is easily justified using Cauchy-Schwarz:
$$
     \left|\int_{0}^{2\pi}f(x)g(nx)dx-\int_{0}^{2\pi}g(x)S_{N}(nx)dx\right| \\
      \le \int_{0}^{2\pi}|f(x)||g(nx)-S_{N}(nx)|dx \\
      \le \left[\int_{0}^{2\pi}|f(x)|^{2}\right]^{1/2}
          \left[\int_{0}^{2\pi}|g(nx)-S_{N}(nx)|^{2}\right]^{1/2}\rightarrow 0
    \mbox{ as } N \rightarrow \infty \mbox{ for fixed n. }
$$

Therefore, for any fixed $n=1,2,3,\cdots,$
$$
\begin{align}
      \frac{1}{2\pi}\int_{0}^{2\pi}f(x)g(nx)dx &
            =\lim_{N\rightarrow\infty}\frac{1}{2\pi}\int_{0}^{2\pi}f(x)S_{N}(nx)dx \\
       & = \lim_{N\rightarrow\infty}\frac{1}{2\pi}\int_{0}^{2\pi}f(x)\sum_{k=-N}^{N}b_{k}e^{iknx} dx \\
       & = \lim_{N\rightarrow\infty}\sum_{k=-N}^{N}b_{k}\frac{1}{2\pi}\int_{0}^{2\pi}f(x)e^{iknx}dx \\
       & = \lim_{N\rightarrow\infty}\sum_{k=-N}^{N}b_{k}a_{-kn} \\
       & = \sum_{k=-\infty}^{\infty}b_{k}a_{-kn}.
\end{align}
$$
Finally, Applying Cauchy-Schwarz to the sum on the right gives
$$
\begin{align}
  \left|\frac{1}{2\pi}\int_{0}^{2\pi}f(x)g(nx)dx-a_{0}b_{0}\right|^{2}
   & = \left|\sum_{|k| \ge 1}b_{k}a_{kn}\right|^{2} \\
   & \le \sum_{|k|\ge 1}|b_{k}|^{2}\sum_{|k|\ge 1}|a_{kn}|^{2} \\
   & \le \sum_{|k|\ge 1}|b_{k}|^{2}\sum_{|k| \ge n}|a_{k}|^{2}\rightarrow 0 \mbox{ as } n\rightarrow\infty.
\end{align}
$$
The last term on the right tends to $0$ because the sum is convergent.

Hint: write $g(t)$ as the combination of $\sin(kt)$ and $\cos(kt)$, i.e., you need only solve the problem for $g(t)=\sin(kt)$ or $\cos(kt)$ for some $k$.


Non-associative operations There are lots of operations that are not commutative.

I'm looking for striking counter-examples of operations that are not associative.

Or may associativity be genuinely built-in the concept of an operation? May non-associative operations be of genuinely lesser importance?

Which role do algebraic structures with non-associative operations play?

There's a big gap between commutative and non-commuative algebraic structures (e.g. Abelian vs. non-Abelian groups or categories). Both kinds of algebraic structures are of equal importance. Does the same hold for  assosiative vs. non-associative algebraic structures?

IEEE-754 floating point, due to the rounding inherent in operations.
a + b involves a rounding step.
It's one of the reasons fused multiply-adds exist.
0.7 + 0.1 + 0.2 from here:
https://stackoverflow.com/questions/10371857/is-floating-point-addition-and-multiplication-associative


How to calculate $E [Z^2]$ when $E[Z]$ is known? For the following calculation, why $E[Z_1^2] = \pi/4$ ? In general, how to calculate $E[Z^2]$ ? Thanks much.

3 down vote

Let's also elaborate on Ross Millikan's answer, adapted to the case f(x)=1−x2−−−−−√, 0≤x≤1. Suppose that $(X1,Y1),(X2,Y2),\ldots$is a sequence of independent uniform vectors on $[0,1]\times [0,1]$, so that for each $i$, $X_i$ and $Y_i$ are independent uniform $[0,1]$ random variables. Define $Z_i$ as follows: $Z_i=1$ if $X_i^2+Y_i^2 \le 1$, $Z_i=0$ if $X_i^2+Y_i^2 > 1$, so the $Z_i$ are independent and identically distributed random variables, with mean $\mu$ given by
$ \mu = E[Z_1] =P[X_1^2+Y_1^2 \le 1]=P[(X_1,Y_1) \in \{(x,y) \in [0,1]^2 : x^2+y^2 \le 1\}]  = \pi/4$,
where the last equality follows from $P[(X1,Y1)\in A]=\text{area}A (A \subset [0,1]^2)$.

By the strong law of large numbers, the average Zˉn=∑ni=1Zin converges, with probability 1, to the expectation μ as n→∞. That is, with probability 1, Zˉn→π/4 as n→∞.

To get a probabilistic error bound, note first that the $Z_i$ have variance $\sigma^2$ given by
$\sigma^2=\text{Var}[Z_1]=E[Z_1^2]−E^2[Z_1]=\pi /4−(\pi /4)^2=\pi /4 (1−\pi /4)<10/59$.

Elaborating on my (second, according to date) answer from Approximating $\pi$ using Monte Carlo integration.

Suppose that $(X_1,Y_1)$ is a uniform vector on $[0,1] \times [0,1]$, so that $X_1$ and $Y_1$ are independent uniform$[0,1]$ random variables. Define $Z_1$ as follows: $Z_1 = 1$ if $X_1^2 + Y_1^2 \leq 1$, $Z_1 = 0$ if $X_1^2 + Y_1^2 > 1$. Then,
$$
{\rm E}[Z_1] = 1 \cdot {\rm P}[X_1^2 + Y_1^2 \leq 1] + 0 \cdot  {\rm P}[X_1^2 + Y_1^2 > 1] = {\rm P}[X_1^2 + Y_1^2 \leq 1].
$$
Similarly,
$$
{\rm E}[Z_1^2] = 1^2 \cdot {\rm P}[X_1^2 + Y_1^2 \leq 1] + 0^2 \cdot  {\rm P}[X_1^2 + Y_1^2 > 1] = {\rm P}[X_1^2 + Y_1^2 \leq 1].
$$
Hence, ${\rm E}[Z_1^2] = {\rm E}[Z_1] $.
Next, note that $X_1^2 + Y_1^2 \leq 1$ if and only if $(X_1,Y_1)$ belongs to the set $A \subset [0,1]^2$ defined by
$$
A = \lbrace (x,y) \in [0,1]^2 : x^2+y^2 \leq 1\rbrace.
$$
Thus,
$$
{\rm E}[Z_1^2] = {\rm P}[X_1^2 + Y_1^2 \leq 1] = {\rm P}\big[(X_1,Y_1) \in A].
$$
However, ${\rm P}[(X_1,Y_1) \in A] = {\rm area}A$, and ${\rm area}A = \pi/4$ (recall that the area of a disc of radius $1$ is $\pi$); hence ${\rm E}[Z_1^2] = \pi/4$.

An expectation operator is a basically integration. Provided you know the p.d.f. of a random variable $Z$, $f(z)$,
$$E(Z)=\int z f(z) dz$$
and
$$E(Z^{2})=\int z^2 f(z) dz $$
over the support (the interval of z in which $f(z)$ is positive) of $z$.


Prove that there exists an $m \times m$ matrix $X$ such that $AX-XA=C.$ Let $A$ be a real symmetric $m \times m$ matrix with $m$ distinct eigenvalues and $v_1,v_2, \cdots , v_m$ be the corresponding eigenvectors. Let $C$ be an $m \times m$ matrix such that $\left \langle Cv_j,v_j \right \rangle = 0$ for all $1 \leq j \leq m.$ Prove that there exists an $m \times m$ matrix $X$ such that $AX-XA=C.$

How do I prove that? Any help will be highly appreciated.

Thank you very much.

Take the equation
$$
AX-XA=C
$$
Pick $v_i, v_j$ and calculate the following:
$$
\langle v_i,(AX-XA)v_j\rangle=\langle v_i,AXv_j\rangle-\langle v_i,XAv_j\rangle
$$
Since $A$ is symmetric, we can move it to $v_i$ in the first term. So we get:
$$
\langle v_i,(AX-XA)v_j\rangle=(\lambda_i-\lambda_j)\langle v_i,Xv_j\rangle
$$
Motivated by this, we define $X$ by
$$
\langle v_i,Xv_j\rangle=\frac{1}{\lambda_i-\lambda_j}\langle v_i,Cv_j\rangle
$$
if $i\neq j$ and $0$ otherwise. This makes $X$ well-defined since $\langle v_i,Xv_j\rangle$ are its components in an orthogonal basis. Now we have:
$$
\langle v_i,(AX-XA)v_j\rangle=(\lambda_i-\lambda_j)\langle v_i,Xv_j\rangle=\langle v_i,Cv_j\rangle
$$
Since $\langle v_i,(AX-XA)v_j\rangle$ are just the components of $AX-XA$ in some orthogonal basis and they are equal to the components of $C$ in this same basis, $AX-XA = C$.

Hint: We may assume $v_i$ has unit length so $v_1,\dots,v_m$ is an orthonormal basis.  With respect to this orthonormal basis we need to solve $DY-YD=B$ for $Y$ where $B$ has all zeros on the diagonal and $D$ is diagonal with distinct entries.  Now write out the entries of $DY-YD$ to see you can solve this for $Y$.


Your favourite application of the Baire Category Theorem I think I remember reading somewhere that the Baire Category Theorem is supposedly quite powerful. Whether that is true or not, it's my favourite theorem (so far) and I'd love to see some applications that confirm its neatness and/or power.

Here's the theorem (with proof) and two applications:

(Baire) A non-empty complete metric space $X$ is not a countable union of nowhere dense sets.

Proof: Let $X = \bigcup U_i$ where $\mathring{\overline{U_i}} = \varnothing$. We construct a Cauchy sequence as follows: Let $x_1$ be any point in $(\overline{U_1})^c$. We can find such a point because $(\overline{U_1})^c \subset X$ and $X$ contains at least one non-empty open set (if nothing else, itself) but $\mathring{\overline{U_1}} = \varnothing$ which is the same as saying that $\overline{U_1}$ does not contain any open sets hence the open set contained in $X$ is contained in $\overline{U_1}^c$. Hence we can pick $x_1$ and $\varepsilon_1 > 0$ such that $B(x_1, \varepsilon_1) \subset (\overline{U_1})^c \subset U_1^c$.

Next we make a similar observation about $U_2$ so that we can find $x_2$ and $\varepsilon_2 > 0$ such that $B(x_2, \varepsilon_2) \subset \overline{U_2}^c \cap B(x_1, \frac{\varepsilon_1}{2})$. We repeat this process to get a sequence of balls such that $B_{k+1} \subset B_k$ and a sequence $(x_k)$ that is Cauchy. By completeness of $X$, $\lim x_k =: x$ is in $X$. But $x$ is in $B_k$ for every $k$ hence not in any of the $U_i$ and hence not in $\bigcup U_i = X$. Contradiction. $\Box$

Here is one application (taken from here):

Claim: $[0,1]$ contains uncountably many elements.

Proof: Assume that it contains countably many. Then $[0,1] = \bigcup_{x \in (0,1)} \{x\}$ and since $\{x\}$ are nowhere dense sets, $X$ is a countable union of nowhere dense sets. But $[0,1]$ is complete, so we have a contradiction. Hence $X$ has to be uncountable.

And here is another one (taken from here):

Claim: The linear space of all polynomials in one variable is not a Banach space in any norm.

Proof: "The subspace of polynomials of degree $\leq n$ is closed in any norm because it is finite-dimensional. Hence the space of all polynomials can be written as countable union of closed nowhere dense sets. If there were a complete norm this would contradict the Baire Category Theorem."

If $P$ is an infinitely differentiable function  such that for each $x$, there is an $n$ with $P^{(n)}(x)=0$, then $P$ is a polynomial. (Note $n$ depends on $x$.) See the discussion in Math Overflow.

I found one beautiful application of Baire Category Theorem which is the following:

Let $\mathcal H$ be a separable Hilbert Space with countable orthonormal basis $\{u_{k}\}_{k=1}^{\infty}$. Fix $n\in \mathbb N$ consider $\mathrm{Span}\{u_{1},u_{2},...,u_{n}\}$ then the following sets are dense in $\mathcal H$.

$A_{i,j}:=\{u\in \mathcal H: (u,u_{i})\neq (u,u_{j})\}$ where $1\leq i,j \leq n$ and $i\neq j$.

Proof Hints:(a) Any proper closed vector subspace of an Hilbert Space is nowhere dense.
(b)A closed set is nowhere dense $\Leftrightarrow$ its complement is everywhere dense.


A functional equation: $4f(x)^3 +f(3x)=3f(x)$ Find all functions $f:\mathbb{R}\to\mathbb{R}$ such that

  $$4f(x)^{3}+f(3x)=3f(x)$$

I know of 2 functions that satisfy the equation but I do not know how to prove that they are the only ones.

Thanks

Andrew

One solution is $f(x)=\sin(x),$ from the identity
$$\sin(3x)=3\sin(x)-4\sin^3(x)\tag{1}$$
which can be checked using the addition formula for sine.

Analytic solutions are (I think) only constants and those of the form $\pm \sin(kx).$ Sketch: Assume $f$ is a nonconstant solution. That $f(0)=0$ follows from the relation, and (this needs work but I think it could be shown) $f$ must be zero for some positive $x.$ Since generally if $f(x)$ is a solution so is $\pm f(kx),$ we may assume $f$ has its first positive zero at $\pi,$ and $f>0$ on $(0,\pi).$ Then the idea is to use the formula $(1)$ to produce the sequence $\pi,\pi/3, \pi/9,...,\pi/3^r,...$ on which $f$ has the same value as $\sin(x).$ We then would have two analytic functions agreeing on a convergent sequence in their domains and could conclude $f(x)=\sin(x)$ for all $x$. The use of the polynomial $g(x)=3x-4x^3$ for this, in getting values of $f(x/3)$ uniquely from values of $f(x),$ is not difficult since $g$ is strictly increasing on $[0,1/2]$ with range $[0,1]$ (one doesn't need $g$ beyond $[0,1/2]$ Of course the first value $f(\pi/3)=\sqrt{3}/2$ comes directly from $f(\pi)=0.$ After that $\pi/9 \approx .349$ is already in the interval $[0,1/2]$ on which $g$ is increasing.

I'm thinking of the Fast Fourier transform. Frequency shift (3x) is easily expressible in FFT domain (1->1 mapping). Multiplication is convolution. Then we get a set of equations. Those convolutions might be quite nasty though.


parentheses vs brackets for indexed family of sets I understand the definition of parentheses and brackets. However this problem involving indexed family of sets has me questioning the definitions.

Q: Let $\mathscr A = \{[-x,0]: x \in \mathbb R \text{ and } 0 < x < 1\}$.
Find the union over $\mathscr A$ and the intersection over $\mathscr A.$

A:  (The union over $\mathscr A$) $= [-1,0]$.
(The intersection over $\mathscr A$) $= \{0\}$.

So, I am confused how the set is defined with $[-x,0]$, and $x$ is restricted by $0 < x < 1$. So, would (the union of $\mathscr A$) $= (-1,0]$?

Thank you in advance!

$(-1,0]$ is correct.

The number $-1$ is not an element of any set in the family $\mathcal{A}$ and therefore cannot be in the union.


how to prove: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ need help to prove this: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $
where $n$ is integer $\geq 1$.

Question also said taking the derivative of $(1 + x)^n$ would be helpful which I've found to be $n(1+x)^{n-1}$

any help appreciated, thank you.

Using the binomial identity shown in $(3)$, we have
$$
\begin{align}
k\binom{n}{k}
&=\binom{k}{1}\binom{n}{k}\\
&=\binom{n}{1}\binom{n-1}{k-1}\tag{1}
\end{align}
$$
Now sum $(1)$:
$$
\begin{align}
\sum_{k=1}^nk\binom{n}{k}
&=\sum_{k=1}^n\binom{n}{1}\binom{n-1}{k-1}\\
&=n2^{n-1}\tag{2}
\end{align}
$$

Binomial Identity
$$
\begin{align}
\binom{n}{k}\binom{k}{j}
&=\lower{10pt}\overset{\displaystyle\overbrace{\binom{n-j}{k-j}\frac{n-j+1}{k-j+1}\cdots\frac{n}{k}}^{\binom{n}{k}}\binom{k}{j}}{\hphantom{\binom{n-j}{k-j}}\underbrace{\hphantom{\frac{n-j+1}{k-j+1}\cdots\frac{n}{k}\binom{k}{j}}}_{\binom{n}{j}}}\\
&=\binom{n-j}{k-j}\binom{n}{j}\tag{3}
\end{align}
$$

They gave you the hint !

Test with $n=4$:

$$(1+x)^4=\binom40x^0+\binom41x^1+\binom42x^2+\binom43x^3+\binom44x^4.$$

After derivation,

$$4\cdot(1+x)^3=0+1\cdot\binom41x^0+2\cdot\binom42x^1+3\cdot\binom43x^2+4\cdot\binom44x^3.$$

Don't you see the connection ?


What is $\lim_{n \to \infty} 2^n \tan\left(\frac{a}{2^n}\right)$? $$\lim_{n\to \infty}{2^n\cdot \tan\left(\frac{a}{2^n}\right)}$$

Experimenting with Wolfram Alpha, I came to suspect the limit is ${a}$. Any help on this matter? I couldn't find it with with half-angle formulas and the series expansion is not very productive either. A similar  result is used (without proof) in the answer of Rohan Shindes question:  Evaluate $$\lim_{n\to \infty} \sum_{r=1}^n \frac {1}{2^r}\tan \left(\frac {1}{2^r}\right)$$ yet eventhough I invested some effort, I was unable to find the solution. Any help would be appreciated.

Write your term in the form $$\frac{\tan\left(\frac{a}{2^n}\right)}{\frac{a}{2^n}}\times a$$

For $a=0$ we obtain:
$$\lim_{n\rightarrow+\infty}2^n\tan\frac{a}{2^n}=0.$$
For $a\neq0$ we obtain:
$$\lim_{n\rightarrow+\infty}2^n\tan\frac{a}{2^n}=a\lim_{n\rightarrow+\infty}\frac{\tan\frac{a}{2^n}}{\frac{a}{2^n}}=a,$$ which says that for all real $a$ we have:
$$\lim_{n\rightarrow+\infty}2^n\tan\frac{a}{2^n}=a.$$


Count how many number are there from $1$ to $N$ who have all $10$ digits in it at least once. Count how many number are there from $1$ to $N$ who have all $10$ digits in it at least once.

Can we have a generalized method to solve this problem?

Let me try another, more detailed answer:

We will call the amount of numbers $\leq N$ that contain all digits $A(N)$. And we say that $N$ has $d(N)$ digits. The smallest number of this kind is $1023456789$, since $0$ can not be the leading digit.

  Therefore $A(N) = 0$ if $N < 1023456789$ ($d(N) < 10$).

First, we will find $A(N)$ depending on the number of digits of $N$:

There are $d$ digits. The special digit $0$ may be placed at $d-1$ positions. The $1$ at $d-1$ positions, the $2$ at $d-2$ positions and so on to $9$. Now we have $d-10$ positions left without digit. Let us approximate that any digit may be placed on the free positions. This is just an approximation, since the $0$ must not stand at the leading position and some double counting may be included. However, the error is rather small, especially for big $N$. Everybody may feel free to post a solution to this error in the comments. We combine all this and get

  $$ A(d) \approx (d-1)(d-1)(d-2)...(d-9) \cdot 10^{d-10} = (d-1)\dfrac{(d-1)!}{(d-10)!} \cdot 10^{d-10}. $$

With this information we can now compose $A(N)$.

  $d(N)$ given by $$ d(N) = \lfloor \log_{10}N \rfloor + 1. $$

Therefore we have as good approximation

$$ A(N) \approx \log_{10}N\dfrac{(\log_{10}N)!}{(\log_{10}N-10)!} \cdot 10^{\log_{10}N-10} $$

and since $\log_{10}N-10 = \log_{10}{\frac{N}{10^{10}}}$:

  $$ A(N) \approx \log_{10}N\dfrac{(\log_{10}N)!}{(\log_{10}N-10)!} \cdot \frac{N}{10^{10}}. $$

Hint: For a number with $d \geq 10$ digits, there are
$$ 10! \cdot \prod_{n=0}^{d-11}(d+1-n) $$
combinations of numbers that include all digits. But this does include some double counting.

Also note: The number of digits of your number is
$$ \lfloor\log_{10}N \rfloor + 1. $$


Is it possible for a graph to have an Euler circuit and an Euler path? Is it true that an Euler path should have two vertices of odd degree and an Euler circuit should have no vertices of odd degree? Is it therefore impossible to have a graph with both an Euler path and an Euler circuit?

This link (which you have linked in the comment to the question) states that having Euler path and circuit are mutually exclusive. The definition of Euler path in the link is, however, wrong - the definition of Euler path is that it's a trail, not a path, which visits every edge exactly once. And in the definition of trail, we allow the vertices to repeat, so, in fact, every Euler circuit is also an Euler path.


orthogonal complement of interestion of 2 planes Question:Let $W$ be the intersection of the two planes: $x-y+z=0$ and $x+y+z=0$
Find a basis for and the dimension of the orthogonal complement, $W^{\perp}$

Answer:
The line $x+z=0$ intersects the plane, which is parameterized as $t(1, 0, -1)$
Then $W^{\perp}$ is the plane $x-z=0$

The basis for $W$ is $(1,0,1)$ I think, how do I find the basis for $W^{\perp}$ and the dimension? any help is appreciated :)

$$W = span\{(1,0,-1)^\top\}$$ the vector $(0,1,0)^\top$ is in  $W^\perp.$ to find a second vector that is orthogonal to both $(0,1,0)^\top, (1,0, -1)$ we can find the null space of $\pmatrix{1&0&-1\\0&1&0}.$ that is $(1,0,1)^\top$ is in the null space. therefore a basis for $W^\perp$ is
$$\{(0,1,0)^\top, (1,0,1)^\top\}. $$

Find the normals to each plane. Then each is orthogonal to its respective plane, $W$ lies in both planes, so is orthogonal to both normal vectors. The planes are distinct and intersect, so the normals are not parallel. Hence they form a basis of $W^{\perp}$, since its dimension cannot be larger than $2$ for the obvious reason that $W^{\perp} \neq \mathbb{R}^3$.


If $f$ and $g$ are continuous, then max(f, g) is continuous and differentiable If $f$ and $g$ are continuous on $[a, b]$ and differentiable on $(a, b)$, then $\max(f, g)$ is continuous on $[a, b]$ and differentiable on $(a, b)$.

I'm asked to either prove or disprove this statement.  So far I'm thinking that it's true because if a function is continuous and differentiable on an interval, it takes on it's max/min over the interval, but I don't know if this is correct, and if it is, I don't know how to prove it.  Any help would be appreciated.

Idea

Consider $\lvert x \rvert = \max\{x, -x\}$.

Can use the fact that max (f,g) = {f + g + |f-g|}/2


How to solve this simple problem So my younger brother asked me to solve a simple problem, but I'm not sure how to solve this. Any help would be much appreciated.

$$a^3 - 1/ a^3 = 4. $$

Prove that  $$a - 1/a = 1$$

Using  $$\displaystyle \left(a-\frac{1}{a}\right)^3=\left(a^3-\frac{1}{a^3}\right)-3\cdot a\cdot \frac{1}{a}\left(a-\frac{1}{a}\right)$$

So we get $$\displaystyle \left(a-\frac{1}{a}\right)^3=4-3\displaystyle \left(a-\frac{1}{a}\right)\;,$$ Now Put $\displaystyle \left(a-\frac{1}{a}\right)=x$

So we get $$\displaystyle x^3=4-3x\Rightarrow x^3+3x-4=0\Rightarrow (x-1)\cdot (x^2+x+4)=0$$

So we get $x=1$ or $\displaystyle x^2+x+4 =0\Rightarrow x=\frac{-1\pm \sqrt{1-16}}{2}$ (No real values of $x$)

So let's solve the first problem for $a$ in the reals.
$a^3-a^{-3}=4$. If thrown into mathematica you get the real solutions are $\frac{1}{2}(1\pm \sqrt{5})$. Then solving the second for $a$ in the reals gives us $a-a^{-1}=1$. This also has the same solutions. Alternatively if we were to assume $a>0$ both simplify to $a^2=a+1$.


Show that $x^{20}+x^{15}+x^{10}+x^5$ is divisible by $x^2+1$ Show that $ f(x)=x^{20}+x^{15}+x^{10}+x^5$ is divisible by $x^2+1$

I tried to simplify it by putting $x^5=y$
It simplifies the polynomial but I cannot put it in the case of the divisor.

So I assumed that $x^2+1$ is a divisor of $f(x)$
Then examine the assumption is correct then $x^2+1=(x-i)(x+i)$
Now for $x=\pm i$ using synthetic division it leaves remainder 0
Am I at the right direction, please tell

Hint: Show that $x^2+1$ divides $x^{10}+1$, and that $x^{10}+1$ divides $f(x)$.


Continuity of the following function Let $f:[a,b] \to \Bbb R$ be continuous . Define $g:[a,b] \to \Bbb R$ by $$g(x) = \sup[f(t) | t \in [a,x]].$$

Then is $g$ continuous? I tried to show the inequality $$|g(x)-g(y)| \le \sup(f(t) | t \in [x,y])$$ but wasn’t able to. Any hints or suggestions will be appreciated.

Let $a\leqslant x\lt y$. Then
$$
g(y)=\max\left\{\sup_{a\leqslant t\leqslant x}\left\lvert f(t)\right\rvert,\sup_{x\leqslant t\leqslant y}\left\lvert f(t)\right\rvert\right\}= \max\left\{g(x),\sup_{x\leqslant t\leqslant y}\left\lvert f(t)\right\rvert\right\}.
$$
We use the bound
$$
\sup_{x\leqslant t\leqslant y}\left\lvert f(t)\right\rvert \leqslant \sup_{x\leqslant t\leqslant y}\left\lvert f(t)-f(x)\right\rvert+ \left\lvert f(x)\right\rvert\leqslant \sup_{x\leqslant t\leqslant y}\left\lvert f(t)-f(x)\right\rvert+g(x)
$$
in order to get
$$
g(y)\leqslant \max\left\{g(x),g(x)+\sup_{x\leqslant t\leqslant y}\left\lvert f(t)-f(x)\right\rvert\right\}=g(x)+\max\left\{0,\sup_{x\leqslant t\leqslant y}\left\lvert f(t)-f(x)\right\rvert\right\}
$$
and since $g$ is non-decreasing, it follows that
$$
\left\lvert g(y)-g(x)\right\rvert\leqslant \sup_{x\leqslant t\leqslant y}\left\lvert f(t)-f(x)\right\rvert.
$$
Now the continuity of $g$ follows from the uniform continuity of $f$: fix a positive $\varepsilon$ and choose $\delta$ such that if $a\leqslant t_1,t_2\leqslant b$ are such that $\left\lvert t_2-t_1\right\rvert\lt \delta$, then $\left\lvert f(t_2)-f(t_1)\right\rvert\lt \varepsilon$.
If $a\leqslant x\lt y\leqslant b$ and $y-x\leqslant \delta$, the previous inequality shows that $\left\lvert g(y)-g(x)\right\rvert\leqslant\varepsilon$.

Your inequality is false. Suppose that $f:[0,1]\rightarrow \mathbf{R}$ is given by

$$f(x) = 2x-1.$$

then $g(x) = 2x-1$. What is $|g(1/4)-g(3/4)|$ and what is $\sup\{f(t)\mid t\in [1/4,3/4]\}$?

For a given $x>0$ consider that $\exists \xi_x$ such that $f(\xi_x) = g(x)$ for every $x$ (why is that?). Suppose that $f(x)<f(\xi_x)$ then $f(x+\delta)<f(\xi_x)$ for $|\delta|<d$ where $d$ is sufficiently small (why is that?). Then $g$ is constant on $(x-d,x+d)$ and hence continuous.

Suppose now that $f(x) = f(\xi_x) = g(x)$, given $\varepsilon>0$ pick $\delta>0$ such that $|y-x|<\delta$ implies that $|f(x)-f(y)|<\varepsilon$. What can then be said about $\sup\{f(t)\mid t\in [0,x+\delta]\}$?