How much information can you transfer by choosing one number out of two? Alice and Bob are playing a game. Alice (A) and Bob (B) agree on a protocol before the game starts.

Alice gets two uniformly random integers (without duplicates) from 1 through $n$, chooses one of the two numbers, and communicates it to Bob. Bob doesn't get to see anything other than the number that Alice chose (and he knows the maximum $n$, which is fixed for the game).

How many bits of information $b(n)$ can possibly be transmitted per number on average, if Alice and Bob play this game for a sufficiently long time?

$b(2) = 1$ is quite obvious, but even $b(3)$ is a difficult to reason about.

One protocol I came up with is that A always output $3$ for inputs $\{1, 3\}, \{2, 3\}$, and output $1$ or $2$ to transfer $1$ bit of information when the input is $\{1, 2\}$. This gets an average transmission rate of $\frac{1}{3}$ bits per number. But I have no idea how to generalize this to bigger $n$ or whether it's even optimal.

For large $n$ we can approach an efficiency of $0.188$ bits per symbol, in the following way:

In the protocol Alice can send a bit to Bob either "reliable-but-slow" or "fast-but-unreliable".

In reliable but slow mode, Bob ignores all symbols other than $0$ or $1$, and Alice simply waits until she gets a pair that allows her to send the symbol she needs. This takes $n/2$ symbols on average.

In fast but unreliable mode, Alice sends any even number for $0$ and any odd number for $1$.  One fourth of the bits she sends will be garbled because she doesn't have a number of the right parity to send.

Alice and Bob agrees in advance on a block size $b$, and the communication starts when Alice has accumulated $b$ bits to send. She sends them using fast-but-unreliable mode. Alice knows which bits went wrong, so she computes a correction sequence that Bob should XOR what he got with in order to get the real message. The bits in the correction sequence are not uniformly distributed: $0$ is three times as common as $1$. Therefore Alice can compress it using arithmetic coding to a length of about $0.811$ of the original $b$ (namely $-\frac34 \log_2(\frac34) - \frac14 \log_2(\frac14)$).

Alice uses reliable-but-slow bits to tell Bob the exact length of the compressed correction sequence, and now sends it using the same procedure as the original block -- that is, with its own correction sequence following, etc.

When the compressed corrections sequence is shorter than some prearranged length, Alice switches to sending it in reliabe-but-slow mode.

Analysis. When $b$ is large, the expected number of fast-but-unreliable symbols sent is
$$ b + 0.811b + 0.811^2b + 0.811^3b + \cdots = \frac{1}{1-0.811} b $$
There will be on the order of $\log b$ nested correction sequences, each needing up to $\log b$ reliable-but-slow bits to encode their lengths. So all in all in the reliable-but-slow phases use about $\frac n2 (\log^2 b+C)$ symbols, where $C$ accounts for the final reliable-but-slow corrections sequence).

For each particular $n$, by choosing $b$ large enough, Alice and Bob can make the $\frac n2 (\log^2 b+C)$ as small compared to $\frac{1}{1-0.811} b$ as they want! So in the limit of large $b$ they ought to achieve $1-0.811 = 0.189$ bits per symbol.

If $n\le 10$, the reliable mode is actually faster than the asymptotic behavior here, and should be used instead.

I suspect this might be asymptotically optimal for large $n$. I tried variants, such as decreasing the error percentage of the "fast" mode at the expense of speed by assigning a fraction of the $n$ symbols as "ignore this symbol" markers instead of letting all of them encode actual bits. But it looks like that always results in worse overall performance.

Alice divides the integers 1 through n into two distinct subsets T and F (for example T = numbers <= n and F = numbers > n, or T = even numbers and F = odd numbers). If n is even then there are n/2 numbers in each subset, if n is odd then she has two sets with n/2 numbers plus an extra number (which can be considered to be the sole element of a third set O).

To transmit TRUE she sends a number from set T if possible, otherwise  from O if possible, otherwise from F if both her numbers are in that set. To transmit FALSE she does the opposite.

Bob assumes any T number is TRUE, and F number is false, and any O number carries no information.

For n = 2, 3, 4, 5, 6, 7... the number of transmitted bits is 1, 2/3, 2/3, 3/5, 3/5, 4/7, 4/7... . I think the pattern is obvious. For sufficiently large n, the limit is 1/2 bits per transmission.


Independence between a constant random variable and another random variable. Intuitively, I understand that if $Y$ is a constant random variable and $X$ is another random variable, then $X$ and $Y$ are independent.

However, I can't make a formal proof because I can't show that their joint density function are the product of two functions that rely only on x's and y's respectively or using similar methods.

(What is the density function of a constant random variable for example?)

Can you give me a hint in order to make a proof?

$X$ and $Y$ are independent if and only if $P(X\in A, Y\in B)=P(X\in A)P(Y\in B)$ for all $A,B$.

Assume $Y=y$ for some $y\in\mathbb{R}$. Then $$P(X\in A, Y\in B)=\left\{\begin{array}{ll}0&\mathrm{if}\,\,y\notin B,\\ P(X\in A)&\mathrm{if}\,\,y\in B\end{array}\right.$$

But notice $P(Y\in B)=1$ if $y\in B$ and $P(Y\in B)=0$ if $y\notin B$.

Show a more general result, that if $Y$ is a constant random variable with value $c$ with probability 1, it is independent to any random variable $X$. Essentially, the result we need is from random statement 24. Let $k \neq c$ be a constant.
$\Pr(Y=c)=1$, so $\Pr (B, Y=c) = \Pr (B)$ for all events $B$. In particular, setting $B=\{ X=x \}$ gives $ \Pr (X=x) \Pr (Y=c) = \Pr (X=x) = \Pr(X = x, Y = c)$.
$\Pr(Y=k)=0$, so $\Pr (B \cup (Y=k)) = \Pr (B)$ for all events $B$. In particular, setting $B=\{ X=x \}$ and using the inclusion-exclusion rule gives $ \Pr(X = x, Y = k) = \Pr (X=x) + \Pr (Y=k) - \Pr (X=x \cup Y=k) = \Pr (X=x) + 0 - \Pr (X=x) = 0 = \Pr (X=x) \Pr(Y=k)$.


Is union of any number conjugacy classes is subgroup? Let $G$ be any group. We know that any subgroup $H$ of $G$ is normal if and only if $H$ is union of conjugacy classes. My first problem is let $a$ and $b$ are two elements of $G$. $Cl_G(a)$, $Cl_G(b)$, $Cl_G(identity)$ are conjugate classes of $a$ and $b$ and the identity of the group $G$ and $H$ is union of these classes, then is $H$ is subgroup of $G$? My second problem is if $|Cl_G(a)| + |Cl_G(b)| + 1 =n$ and $n$ divides $|G|$, then $H$ is definitely a normal subgroup? Or should we check that $H$ is subgroup or not then?

No. For example, consider $(\mathbb{Z}_4, +)$. Then $S=\{0, 1, 2\}$ is not a subgroup even though it is the union of conjugacy classes (and contains the identity). More generally, if $S\subset A$, $A$ abelian, is chosen such that $|A|>|S|>|A|/2$ then $S$ is not a subgroup.

As another counter-example, consider $(\mathbb{Z}, +)$. Then $S=\{-1, 0, 1\}$ is not a subgroup.

(These examples work because conjugacy classes in abelian groups are singletons. So more generally, in an abelian group every subset is a union of conjugacy classes.)

No. The conjugacy classes of $S_n$ are cycle types. Clearly $2$-cycles don't form a subgroup since they don't contain the identity.


Among all shapes with the same area, a circle has the shortest perimeter Is it true that "Among all shapes with the same area, a circle has the shortest perimeter"  ? and how to prove it ?

The question can be asked such as "Find the plane curve which encloses given area with shortest perimeter". Then by parametric formulation of coordinates $x(t),y(t)$ and assuming non-selfintersecting curve the area can be written as
$$A=\frac 12 \int_{t_1}^{t_2}\big(xy'-x'y\big)dt$$
and the perimeter
$$I=\int_{t_1}^{t_2}\sqrt{x'^2+y'^2}dt$$
Then the Euler-Lagrange becomes
$$-\frac{d}{dt}\bigg(\frac{x'}{\sqrt{x'^2+y'^2}}\bigg)-\frac{\lambda}2\bigg(y'+\frac{d}{dt}\bigg(y\bigg)\bigg)=0$$
$$-\frac{d}{dt}\bigg(\frac{y'}{\sqrt{x'^2+y'^2}}\bigg)-\frac{\lambda}2\bigg(-x'-\frac{d}{dt}\bigg(x\bigg)\bigg)=0$$
If $ds$ is the element of arc the equations can be reduced to
$$\frac{d^2x}{ds^2}+\lambda \frac{dy}{ds}=0$$
$$\frac{d^2y}{ds^2}-\lambda \frac{dx}{ds}=0$$
which has the solution
$$x(t)=K_1+C_1\cos(\lambda s)+C_2\sin(\lambda s)$$
$$y(t)=K_2-C_2\cos(\lambda s)+C_2\sin(\lambda s)$$
It can be further simplified by "Angle sum and difference identities"
$$x(t)=K_1+D\sin(\lambda s+\alpha)$$
$$y(t)=K_2-D\cos(\lambda s+\alpha)$$
where $D\sin(\alpha)=C_1$ and $D\cos(\alpha)=C_2$; and this solution represents a circle of radius $D$ and centre $(K_1,K_2)$

If you have a rope with length $P$ the shape with the biggest area that you can create is the circle. If you have a shape, rather than circle, with the same area with the first circle that is because you have used a longer rope.


How to simplify the equations below trying to find for ratio test a) $\frac{ \sin(n) + e^n}{\cos(n) + \pi^n}$ I expanded and got $\sin (n) + e^n/(cos(n) + \pi^n) x \cos (n+1) + \pi^{n+1}/\sin(n+1) + e^{n+1}$?

and also how to simplify $(n+1)^e/(n^e)e$

Edit: I totally got confused with the ratio test formula.Sorry my bad.But thanks for helping!

I can't really make out your work, but it should go something like this:
$$a_n = \frac{e^n+\sin(n)}{\pi^n +\cos(n)}$$

$$\frac{a_{n+1}}{a_n}
= \frac{  \frac{e^{n+1}+\sin(n+1)}{\pi^{n+1} +\cos(n+1)}  }{  \frac{e^n+\sin(n)}{\pi^n +\cos(n)}  }
= \frac{e^{n+1}+\sin(n+1)}{e^n+\sin(n)} \cdot \frac{\pi^n+\cos(n)}{\pi^{n+1}+\cos(n+1)}$$
Using trivial bounds on $\sin$ and $\cos$,

$$\underbrace{\frac{e^{n+1} - 1}{e^n + 1}}_{\to e} \cdot \underbrace{\frac{\pi^n - 1}{\pi^{n+1}+1}}_{\to 1/\pi} \leq \frac{a_{n+1}}{a_n} \leq \underbrace{\frac{e^{n+1} + 1}{e^n - 1}}_{\to e} \cdot \underbrace{\frac{\pi^n + 1}{\pi^{n+1}-1}}_{\to 1/\pi}$$
by the squeeze theorem $\lim_{n\to\infty}\tfrac{a_{n+1}}{a_n} = \tfrac{e}{\pi} < 1$. So we may apply the ratio test.

$$a_n = \frac{e^n+\sin(n)}{\pi^n +\cos(n)} =  \left( \frac{e}{\pi} \right)^n \cdot \frac{1+\frac{\sin{n}}{e^n}}{1+\frac{\cos{n}}{\pi^n}} \Rightarrow$$
$$\frac{a_{n+1}}{a_n}=\frac{e}{\pi}\cdot \frac{1+\frac{\sin{(n+1)}}{e^{n+1}}}{1+\frac{\cos{(n+1)}}{\pi^{n+1}}}\cdot \frac{1+\frac{\cos{n}}{\pi^n}}{1+\frac{\sin{n}}{e^n}} \stackrel{n\rightarrow\infty}{\longrightarrow}\frac{e}{\pi}\cdot \frac{1+0}{1+0}\cdot \frac{1+0}{1+0}=\frac{e}{\pi}$$


Prove: Square Matrix Can Be Written As A Sum Of A Symmetric And Skew-Symmetric Matrices Let $C^{n \times n}$ be a square matrix.

Prove that $$C=\frac{1}{2}(C+C^T)+\frac{1}{2}(C-C^T)$$

What I have manage so far is:

a. Let $S$ be a Symmetric Matrix so $S=C+C^T$

b. Let $N$ be a Skew-Symmetric Matrix so $N=C-C^T$

Proof:

$S^t=[C+C^T]^T=C^T+C=S$

$N^t=[C-C^T]^T=-C^T+C=-N$

If $A$ is a square matrix in $\mathcal M_n(\Bbb C)$ then
$$A=\underbrace{\frac12(A+A^t)}_{\text{symmetric matrix}}+\underbrace{\frac12(A-A^t)}_{\text{skew-symmetric matrix}}$$

Using indicial notation, show that the square matrix can be expressed as the sum of a symmetric and antisymmetric matrix by the decomposition:

    $$A=\frac{A+A^T}{2} + \frac{A-A^T}{2}$$


Does this mean that one can construct the cube root of two in three dimensions? The idea here is to extend to three dimensions what ordinary compass-and-straightedge constructions do in two dimensions.  The first thing is to define the tools and rules for their use.  For instance, in two dimensions, the tools are a compass and straightedge (like a ruler, but with only one edge and no markings), and with them, one may:
Draw a line between any two distinct points.
Draw a circle with one point as the center, and any other point on its circumference.
Draw an arbitrary point on a line or a circle, or off it.
Draw the point at the intersection of two lines (if they intersect).
Draw the point (or two) at the intersection of two circles (if they intersect).
Draw the point (or two) at the intersection of a line and a circle (if they intersect).

In three dimensions, the canvas is not a flat plane, as it is in two dimensions, but all of space.  And we introduce a new tool, which I will call a flatiron, which permits you to draw planes.  The flatiron rules are as follows; in addition to the above, one may:
Draw the unique plane containing any three non-collinear points.
Draw a sphere with one point as the center, and any other point on its surface.
Draw an arbitrary point on a plane or a sphere, or off it.
Draw the line at the intersection of two planes (if they intersect).
Draw the circle (or point) at the intersection of two spheres (if they intersect).
Draw the circle (or point) at the intersection of a plane and a sphere (if they intersect).
Draw the point (or two) at the intersection of a line or circle with a plane or sphere (if they intersect).
As an example of what one might do in a three-dimensional construction, consider the following fairly simple task: Given points P and Q, construct a regular tetrahedron with PQ as edge.  We proceed as follows:
Draw spheres of radius PQ around both P and Q.
Draw the circle C at the intersection of spheres P and Q.
Draw R, an arbitrary point on circle C.
Draw a sphere of radius PR around R.
Draw S, one of the two points of intersection between circle C and sphere R.  PQRS is then a regular tetrahedron.

Given these new abilities, would it be possible construct a cuberoot?

If you assume that when you intersect two spheres, or a sphere with a plane, or two planes, that $all$ of the intersection points are called constructed points,  then any real length is constructible.

But suppose that  you  only assume a limited amount of information (which I am too tired too specify now. I will get back to this) Then for about the same reason as in $2$ dimensions:  Examine the equations for the co-ordinates of lines, planes,circles, and spheres and for the co-ordinates of the intersections of any two of those types of figures.

Choose a $2$-D or $3$-D co-ordinate system where you start by being given the origin and a finite number of other points with rational co-ordinates. The co-ordinates of any constructible point will be members of $\;\mathbb Q[\sqrt {.}\;]\;$.... which is the smallest sub-field of $\mathbb R$ that contains the square roots of all its positive members.

The number $2^{1/3}$ does not belong to this field.

If we could construct two points whose distance apart is $2^{1/3}$ or two segments such  that the ratio of their lengths is $2^{1/3}$ then we could construct the point whose first co-ordinate is $2^{1/3}$ and whose other co-ordinate(s) is (are) $0.$

A good way to approach the problem is to define algebraic equations which describe all of your tools and the rules governing the use of each tool. The structure of the algebraic equations will determine what can be constructed.
Tool 1 lets you: Draw a line between any two distinct points. So:
Given $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$. Use the line equation.
Tool 2 the Flatiron lets you: Draw the unique plane containing any three non-collinear points. So:
Given $(x_1, y_1, z_1), (x_2, y_2, z_2)$ and $(x_3, y_3, z_3)$. Use the plane equation.
Tool 3 lets you: Draw a sphere with(I assume 'given' is better than with) one point as the center, and (taking) any other (constructed or known)point (to be)on its surface. So:
Given $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$. Use the sphere equation with center $(x_1, y_1, z_1)$ and radius as the distance between the points.
Tool 4 lets you: Draw an arbitrary point on a plane or a sphere, or off it. So:
I am stumped as to the meaning of tool 4 to be honest.
Tool 5 lets you: Draw the line at the intersection of two planes (if they intersect). This is a given. When you draw the planes you automatically draw that line.
Tool 6 lets you: Draw the circle (or point) at the intersection of two spheres (if they intersect). Another given with the same reasoning as above.
Tool 7 lets you: Draw the circle (or point) at the intersection of a plane and a sphere (if they intersect). Another given with the same reasoning as above.
The following two families of equations govern what values can be constructed under this ruleset:
$$(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2 - (x_2-x_1)^2 - (y_2-y_1)^2 - (z_2-z_1)^2 = 0$$
$$(x-x_1)[(y_2-y_1)(z_3-z_1)-(z_2-z_1)(y_3-y_1)] - (y-y_1)[(x_2-x_1)(z_3-z_1)-(z_2-z_1)(x_3-x_1)] + (z-z_1)[(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)] = 0$$
You can show that you don't need Tool 1 since anything constructed by Tool 1 can be constructed by Tool 2. It isn't too much work to show that.
Before continuing the analysis I would like to clarify the mysterious tool 4. I don't understand it. Sounds like it lets you construct anything which isn't very interesting. I must be misunderstanding your wording.


Is 'Some of x are true' a negation of 'All of x are true'? I don't think this necessarily means there exists a false x, just that at least some x are true.

Is my logic correct here in assuming this is NOT a negation?

The negation of "all $x$ are true" is "some $x$ is false (in the sense that there exists $x$ false, at least one is false)".

$$\left(\bigcap A_i\right)' = \bigcup(A_i') \neq \bigcup A_i$$


Splitting a sandwich and not feeling deceived This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an hour to an hour, and then just grins at me, and whispers whole day: "You will never solve me..."

Please save me from this torturer.

Here it is:

Let's say there are two people and a sandwich. They want to share the sandwich, but they don't trust each other. However, they found the way how both of them will have a lunch without feeling deceived: One of them will cut the sandwich in two halves, and another will choose which half will be his. Fair, right?

The problem is:

Is there such mechanism for three people and a sandwich?

EDIT: This was roller-coaster for me. Now, it turns out that there are at least two books devoted exclusively on this problem and its variations:

Fair Division

Cake Cutting Algorithms

Yesterday, I was in a coffee shop in a small company. We ordered coffee and some chocolate cakes. As I was cutting my cake for my first bite, I felt sweat on my forehead. I thought, 'What if some of my buddies just interrupt me and say: Stop! You are not cutting the cake in a fair manner!' My hands started shaking in fear of that. But, no, nothing happened, fortunately.

For more than two, the moving knife is a nice solution.  Somebody takes a knife and moves it slowly across the sandwich.  Any player may say "cut".  At that moment, the sandwich is cut and the piece given to the one who said "cut".  As he has said that is an acceptable piece, he believes he has at least $\frac 1n$ of the sandwich.  The rest have asserted (by not saying "cut") that is it at most $\frac 1n$ of the sandwich, so the average available is now at least their share.  Recurse.

Hmm, if you cut it into an approximate 3rd and 2/3rds portions, then the cutter would get a slice that both other people think is about 1/3rd.  To attempt to subvert this, player A could cheat and make 2 equal halves.  In the real world, such a player would never get invited to party games again.  ;)  But let's just say that then one of the other players would have to divide each half into 1/6th and 1/3rd slices.  Repeat ad nauseum?

If you can 'uncut' the sandwich, then it's easier:  Just keep having a different player cut the sandwich until the other 2 agree.  This is similar to the moving-knife solution but where the cut is not done unless all 3 agree, in actual practice since 'uncutting' really means just not cutting yet.

Once you get the bigger piece being roughly 2/3rds, then you can apply the normal 2-person method.  To go to 4 people, vote in pairs?  You could also apply this idea with 1/4th & 3/4ths slices.  This is generalizable to 5,...,dozens of people.


One point following another moving in a straight line? There is a plane with two points on it, let's say A and B.

A starts at an arbitrary constant point, let's say $(0, 0)$, and $B$ at a point that needs to be tested, which we'll call $(c, d)$.

A moves upwards in a straight line at speed $V$. At any given point in time, $B$ will move at that same speed $V$ from wherever it is at that moment towards wherever $A$ is at the same time until $B$ contacts $A$, if that will ever happen at all. In what range of points must $B$ start in order to ever catch $A$?

I've determined (at least I think) that, for $B$, $$\frac{dy}{dx} = \frac{y(A) - y(B)}{x(A) - x(B)} = \frac{\frac{dy}{dt}}{\frac{dx}{dt}}$$ and that if $B$ starts below $A$, or is ever at a point below $A$, it will never reach $A$. Also, for $A$, $\frac{dy}{dx} = \frac{V}{0}$ which is undefined, though $\frac{dy}{dt} = V$, and $\frac{dx}{dt} = 0$. Also, for $A, x = 0$ and $y = Vt$, where $t$ is time.

How can one determine if $B$ will reach $A$, given a starting point $(c, d)$? Can equations, likely using integrals, be formed to show the $x$ and $y$ values of $B$ as functions of $t$? If so, how?

The points meet at some time $t \geq 0$ if and only if the initial position of $B$ is $(0,y_0)$ for some $y_0 \geq 0$. In other words, $B$ must start directly above $A$.

We may assume that $V=1$ since we can speed up or slow down time by a constant factor. (If rigor is desired here we can use what Jack Lee calls the "rescaling lemma" in Introduction to Smooth Manifolds (Lemma 9.3). That book is way overkill for this problem, but I don't know a more appropriate reference.)

Let $(x_B(t), y_B(t))$ be the position vector of $B$ at time $t \geq 0$. The corresponding velocity vector is

$$
(x_B', y_B')
= \left(\frac{-x_B}{\sqrt{x_B^2 + (y_B - t)^2}}, \frac{-(y_B - t)}{\sqrt{x_B^2 + (y_B - t)^2}}\right).
$$

My approach will be to make the change of coordinates $\tilde y = y - t$. This corresponds to transforming to a coordinate system that moves with $A$ so that $A$ remains fixed at the origin. The velocity of $B$ in this new coordinate system is
$$
(x_B', \tilde y_B')
= (x_B', y_B' - 1)
= \left(\frac{-x_B}{\sqrt{x_B^2 + \tilde y_B^2}},
        \frac{-\tilde y_B}{\sqrt{x_B^2 + \tilde y_B^2}} - 1 \right).
$$
As the velocity only depends explicitly on the position, the trajectory $(x_B(t), \tilde y_B(t))$ is an integral curve of the vector field
$$
F(x,\tilde y)
= \left(\frac{-x}{\sqrt{x^2 + \tilde y^2}},
        \frac{-\tilde y}{\sqrt{x^2 + \tilde y^2}} - 1 \right)
$$
on $\mathbb R^2 \setminus \{(0,0)\}$. Note that

Each integral curve exists either (i) until it hits the origin or (ii) forever (this can be deduced from the fact that $F$ is bounded and continuous, using among other tools the Peano existence theorem); and
For $x \neq 0$, the ratio $\displaystyle\frac{F_2}{F_1} = \frac{\tilde y + \sqrt{x^2 + \tilde y^2}}{x}$ of the components of $F$ (i.e. the slope of $F$) is constant along each radial ray of constant polar angle, and is positive iff $x > 0$ and negative iff $x < 0$.

Now, if $B$ starts directly above $A$ then they will obviously collide. And as you noted, if $B$ is ever side-by-side with or below $A$ it will never catch up.

The remaining case is the one where $x_B(0) \neq 0$ and $\tilde y_B(0) > 0$. Because $\tilde y'_B(t) < -1$ when $\tilde y_B(t) > 0$, the trajectory reaches the line $\tilde y = 0$ in finite time. Let $T > 0$ be the earliest such time.

Assume for the sake of contradiction that $(x_B(T), \tilde y_B(T)) = (0,0)$. We define sequences $(t_n)_{n \geq 0}$ of times and $(u_n)_{n \geq 0}$ of $\tilde y$-coordinates (plus, for convenience, $x_n = x_B(t_n)$ and $\tilde y_n = \tilde y_B(t_n)$) as follows.

The initial conditions will be $t_0 = 0$ and $u_0 = \tilde y_B(0)$.

Next, suppose $t_n < T$ and $u_n > 0$ are such that $(x_n, \tilde y_n)$ and $(x_0, u_n)$ are at the same polar angle. In particular we have $$\operatorname{sgn} x_n = \operatorname{sgn} x_0 \neq 0,$$ where $\operatorname{sgn}$ is the sign function. Choose a $t_{n+1} \in (t_n, T)$ such that
\begin{equation} \tag{*} \label{ratio}
\frac{\tilde y_n}{x_n}
= \frac{F_2(x_{n+1}, \tilde y_{n+1})}{F_1(x_{n+1}, \tilde y_{n+1})}
\equiv \frac{\tilde y_{n+1} + \sqrt{x_{n+1}^2 + \tilde y_{n+1}^2}}{x_{n+1}};
\end{equation}
such a time exists due to Cauchy's mean value theorem. Then
\begin{align*}
\operatorname{sgn} x_{n+1}
&= \operatorname{sgn}(\tilde y_n / x_n) && \text{(by item 2 of the earlier list since $x_{n+1} \neq 0$)} \\
&= \operatorname{sgn} x_n && \text{(since $t_n < T \implies \tilde y_n > 0$)} \\
&= \operatorname{sgn} x_0.
\end{align*}
Thus, there is a (unique) $u_{n+1} > 0$ such that $(x_0, u_{n+1})$ has the same polar angle as $(x_{n+1}, \tilde y_{n+1})$. This finishes the construction.

However, observe that by \eqref{ratio} and item 2,
$$
\frac{u_n}{x_0}
= \frac{u_{n+1} + \sqrt{x_0^2 + u_{n+1}^2}}{x_0},
$$
which implies $u_{n+1} < u_n - \lvert x_0 \rvert$. This means that $u_n < u_0 - n \lvert x_0 \rvert$ for all $n > 0$, contradicting the fact that the $u_n$ are all positive.

Thus even in this last case $B$ eventually falls side-by-side with $A$, after which $B$ is condemned to make a futile chase from below forever.

A starts from (0,0)and B starts from (c,d)and both A and B move at a speed of V. After time t,say, B catches up with A at a point, say, (a,b).Then (a,b) is at a distance Vt from the origin and from (c,d).
Therefore, B can start from any point on the circle centered (a,b) and passing through the origin in order that it can meet A at (a,b).
(a,b) is at a distance of Vt both from the origin and from (c,d).


Convergence of a sequence of real numbers Let $\alpha, \gamma$ be real numbers such that $0<\alpha<1$ and $\gamma>0$. Consider the sequence of real numbers given by
$$
\begin{cases}
x_0\ne 0&\\
x_{k+1}=x_k\left(1-\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}\right) \quad (k\in \mathbb{N}).&
\end{cases}
$$
Suppose that $x_k\ne 0$ for all $k\in \mathbb{N}$.
Prove that :

The sequence $\{x_k\}_{k\in\mathbb{N}}$ does not converge.
The sequence $\{|x_k|\}_{k\in\mathbb{N}}$ converges to $[(1/2)(1+\alpha)\gamma]^{1/(1-\alpha)}.$

Let $L=(\gamma(1+\alpha)/2)^{1/(1-\alpha)}$.

Suppose that $|x_k| < L = (\gamma(1+\alpha)/2)^{1/(1-\alpha)}=((\gamma(1+\alpha)/2)^{\alpha/(1-\alpha)})^{1/\alpha}=((\gamma(1+\alpha)/2)^{-1}(\gamma(1+\alpha)/2)^{1/(1-\alpha)})^{1/\alpha}=((\gamma(1+\alpha)/2)^{-1}L)^{1/\alpha}$

from which we conclude that $|x_k|^{\alpha}(\gamma(1+\alpha)) < 2L$. Also $|x_k| < L=(\gamma(1+\alpha)/2)^{1/(1-\alpha)}$ implies that $\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}>2$.
Then $|x_{k+1}|=|x_k|\left|1-\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}\right|= |x_k|\left(\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}-1\right)>|x_k|$.
If $|x_{k+1}| >L$ then from $|x_k|^{\alpha}(\gamma(1+\alpha)) < 2L$ we manipulate to get
$|x_k|\left(\frac{(\gamma(1+\alpha))}{|x_k|^{1-\alpha}}-1\right) -L< L-|x_k|$
and finally $|x_k|\left|1-\frac{(\gamma(1+\alpha))}{|x_k|^{1-\alpha}}\right| -L< L-|x_k|$. So we conclude that $|x_{k+1}|-L < L - |x_k|$ and then from $|x_{k+1}| >L$  and $|x_k| < L$ we know that $||x_{k+1}|-L| < ||x_k|-L|$.

Supppose that $|x_k| > L = (\gamma(1+\alpha)/2)^{1/(1-\alpha)}=((\gamma(1+\alpha)/2)^{-1}L)^{1/\alpha}$
then $|x_k|^{\alpha}(\gamma(1+\alpha)) > 2L$.
Also $0<\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}<2$ and
$|x_{k+1}|=|x_k|\left|1-\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}\right|<|x_k|$.
If $|x_{k+1}| < L$ and $1<\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}<2$ then from $|x_k|^{\alpha}(\gamma(1+\alpha)) > 2L$ we manipulate to get
$|x_k|\left(\frac{(\gamma(1+\alpha))}{|x_k|^{1-\alpha}}-1\right) -L> L-|x_k|$
and finally $|x_k|\left|1-\frac{(\gamma(1+\alpha))}{|x_k|^{1-\alpha}}\right| -L> L-|x_k|$. So we conclude that $|x_{k+1}|-L > L - |x_k|$ and $L-|x_{k+1}| > |x_k|-L$ then from $|x_{k+1}| <L$  and $|x_k| > L$ we know that $||x_{k+1}|-L| < ||x_k|-L|$. If $|x_{k+1}| <L$ and $0<\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}<1$ then $\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}<1$ implies that $|x_k| > 2^{1/(1-\alpha)}L\ge 2L$. And from $|x_{k+1}|<L$ we know $||x_{k+1}|-L|<L< |x_k| - L = ||x_k| - L|$.

In summary we have shown that if $|x_k| < L$ then $|x_{k+1}| >|x_k|$. If $|x_k| < L$ and $|x_{k+1}| <L$ then $||x_{k+1}|-L|<||x_k|-L|$. If $|x_k| < L$ and $|x_{k+1}| >L$ then $||x_{k+1}|-L|<||x_k|-L|$. If $|x_k| > L$ then $|x_{k+1}| <|x_k|$. If $|x_k| > L$ and $|x_{k+1}| >L$ then $||x_{k+1}|-L|<||x_k|-L|$. If $|x_k| > L$ and $|x_{k+1}| <L$ then $||x_{k+1}|-L|<||x_k|-L|$. No matter what the case it is true that $||x_{k+1}|-L|<||x_k|-L|$. Therefore the sequence $|x_k|-L$ converges. Showing that the limit of $|x_k|$ must be $L$ is easy.

We only need to prove the second claim for the following reason.

If $|x_k|\rightarrow (\gamma (1+\alpha)/2)^{1/(1-\alpha)}$,
$$\frac{x_{k+1}}{x_k}=\left(1-\frac{\gamma(1+\alpha)}{|x_k|^{1-\alpha}}\right) \rightarrow-1.$$
Thus ${x_{k}}$ will be an oscillating sequence.

I will write it later about how to prove the second claim.


Proof that $\sqrt{2}$ is irrational I am having hard time flowing a proof from Introduction to the theory of computation (3rd ed.) by Michael Sipser.   Please points out what I am missing.  My questions is "Now, at least one of $m$ and $n$ must be add odd number." Why can we make such a statement already?

PROOF First, we assume for the purpose of later obtaining a contradiction
that $\sqrt{2}$ is rational.

Thus $\sqrt{2} = \dfrac{m}{n}$,

where $m$ and $n$ are integers. If both m and n are divisible by the same integer greater than $1$, divide both by the largest such integer. Doing so doesn’t change the value of the fraction. Now, at least one of m and n must be an odd number. We multiply both sides of the equation by n and obtain

$n\cdot \sqrt{2} = m$.

We square both sides and obtain

$2\cdot n^2 = m^2$.

Because m2 is 2 times the integer n2, we know that m2 is even. Therefore, m, too, is even, as the square of an odd number always is odd. So we can write m = 2k for some integer k. Then, substituting 2k for m, we get

$2n^2 = (2k)^2 = 4k^2$.

Dividing both sides by $2$, we obtain

$n^2 = 2k^2$.

But this result shows that $n^2$ is even and hence that $n$ is even. Thus we have established that both $m$ and $n$ are even. But we had earlier reduced $m$ and $n$ so that they were not both even—a contradiction.

If $m$ and $n$ are both even you can still divide both by 2. Absurd we already divided them by all integers possible greater than 1. Thus, at least 1 of them is odd.

There are numerous proofs for this fact, but my favorite is:

Assume $\sqrt{2} = m/n$.

Then $2 n^2 = m^2$.

The left side has an odd number of prime factors and the right side has an even number of prime factors.  By the fundamental theorem of arithmetic (unique prime factorization) we reach a contradiction.

$\square$


If $a+b=8$ and $ab+c+d = 23$ and $ad+bc=28$ and $cd=12\;,$ Then $abcd$ If $a+b=8$ and $ab+c+d = 23$ and $ad+bc=28$ and $cd=12\;,$ Then value of
$(1)\;\; a+b+c+d=$
$(2)\;\; ab+bc+cd+da = $
$(3)\;\; abcd=$

My attempt: Let $x=a\;,b$ be the roots of $(x-a)(x-b)=0$ and $x=c\;,d$ be the roots
of $(x-c)(x-d)=0.$
So, $(x-a)(x-b)(x-c)(x-d)=\left[x^2-(a+b)x+ab\right]\cdot \left[x^2-(c+d)x+cd\right]=0.$
Thus, $$\left[x^2-8x+ab\right]\cdot \left[x^2-(c+d)x+12\right]=0.$$
Where do I go from here? Any help would be much appreciated.

This problem actually checks your observational skills of algebraic products.
Now take this:
$(x^2+ax+c)(x^2+bx+d) $
$=x^4+(a+b)x^3+(ab+c+d)x^2+(ad+bc)x+cd $
$=x^4+8x^3+23x^2+28x+12=f(x) $
$12$ is the product of roots so by putting $ x=−1 $ we find  $f(−1)=0 $
$⟹(x+1) $ is factor of $  f(x) $
Similarly  $(x+2) $ and $(x+3)$ are factors of $f(x) $
Hence  $f(x)=(x+1)×(x+2)×(x+2)×(x+3) $
This can be written in two ways:
$(x^2+3x+2)×(x^2+5x+6) $
$⟹a=3,b=5,c=2,d=6$
$(x^2+4x+3)×(x^2+4x+4) $
$⟹a=4,b=4,c=3,d=4 $
Hence $2$ sets of solutions are possible


Finding $f(x)$ given a function $f : \Bbb N \to \Bbb N$ which satisfies $f\circ f(x) + f(x) = 2x+15$ I'm stuck on rewriting the function $f\circ f(x) + f(x) = 2x+15$ (into $f(x) = \dots)$. The answer given is $f(x) = x + 5$, which I can easily verify, but I do not know how to go about forming this aside from just trial and error. How would I go about doing this systematically?

It is also given that $f : \Bbb N \to \Bbb N$ is injective.

A reasonable thing to guess is that $f(x)$ is a polynomial. However, if the leading term is $x^n$, you get a leading term on the LHS of $x^{n^2}$ vs the leading term on the RHS of $x$. This means $n=1$ if a polynomial is going to work. So then we try $f(x)=ax+b$ and solve for the unknown coefficients.

does this naive argument work?

let $f(x) = y.$ $f(f(x)) + f(x) = 5$  implies  $f(y) + y = 5$ for all $y$ in the range of $f.$


Finding maxima of a function $f(x) = 4x(16 - x)(6 - x)$ without calculcus My question is how to prove that $f(x) = 4x(16 - x)(6 - x)$ has its maximum at point $x_0 = \frac{8}{3}$.
I am trying to use arithmetic-geometric inequality, but I am unable to solve it.

The problem can be greatly simplified by considering $f(8/3+t)-f(8/3)$.
This is $4(t^3-14t^2)$. The graph of this cubic has a repeated root at $0$ and a single root at $14$ and is negative at $7$. It therefore clearly has a local maximum at $t=0$ i.e. $x=8/3$.
The same idea can be used for other polynomial functions.

$f(x)=4x(16-x)(6-x)=4x^3 - 88x^2 +384x$
Now calculate it's derivative
$f'(x)=12x^2 -176x + 384 = 12(x-6)(x - \frac{8}{3})$
Now just find increasing and decreasing intervals
$f(x)$ is increasing on $ x< \frac{8}{3} $ and $ x>6$
And decreasing on ($ \frac{8}{3} ; 6)$ so after that you can say $x_0 = \frac{8}{3} $ is a local maximum point


Need help figuring out possible combinations in card game I am creating I am not sure if this is the right place to be asking the question, but hoping for some help. I created a simple card game for a D&D game I am running and I am trying to assign strength to each hand, I wanted to do this by knowing the possible combinations of each hand.
In this game, there is a deck of 45 cards, 5 suits each suit has cards value 1-9. Player has 5 cards in his hand, and the goal is to get cards in hand to equal a multiple of 5, i.e 5,10,15...,45. So I wanted to know how many possible ways are there for a player to get a hand equal to each of those multiples using the cards available in the deck? e.g. to get to a sum of 5 there is only 1 possible hand, you must have all 1's. However I do not know how to easily compute this for the values with many more combinations. Any help would be appreciated!
Thank you!

Neither answer so far has successfully gotten to the probabilities of certain hand totals as having occurred and are unfairly biased towards hands which can only exist with large numbers of suits and against hands which can occur with many or few suits.
Writing a quick and dirty javascript can give the actual totals:
totalHands = function(target){
count=0;
for(a=1; a<46; a++){for(b=a+1;b<46;b++){for(c=b+1;c<46;c++){for(d=c+1;d<46;d++){for(e=d+1;e<46;e++){if((a-1)%9+(b-1)%9+(c-1)%9+(d-1)%9+(e-1)%9+5 == target){count++;}}}}}}
console.log(count)}

This counts the total number of hands (suits relevant and order irrelevant) for your desired sums.  Dividing by $\binom{45}{5}$ gives the probability of having gotten said sum.
The multiples of five in particular occur with the following frequencies and probabilities:
$$\begin{array}{c|c|c}\text{Sum}&\text{Frequency}&\text{Probability}\\\hline 5&1&\approx 8.2\times 10^{-7}\\10&1776&\approx 0.00145\\15&18251&\approx 0.0149\\20&59226&\approx 0.0485\\25&85751&\approx 0.07019\end{array}$$
The probabilities are symmetric with respect to $25$, so the probability of hitting a sum of $20$ is the same as hitting a sum of $30$ for instance and so on...

The number of ways to make a total of $t$ is the coefficient of $x^t$ in $$(x+x^2+\cdots+x^9)^5$$  Each factor represents one of the cards and the term within that factor represents the card.  Since we multiply the terms by adding exponents, the claim follows.
Now, we can just ask Wolfram Alpha to multiply it out.  You just have to pick out the coefficients of terms of interesting degree.  For example, there are $976$ ways to make a total of $35$.


Characterisation of operator norm on $l^2$ Let $A$ be a bounded operator on $l^2(\mathbb C)$ and let $\{e_i\}$ be some orthonormal basis. Is there a sharp characterisation of the operator norm $\|A\|_{\mathcal L(l^2(\mathbb C))}$ in terms of the matrix elements $A_{ij}:=\langle e_i,A e_j\rangle$?

It is straightforward to show that
$$\sup_k\sum_i|A_{ik}|^2\leq \|A\|_{\mathcal L(l^2(\mathbb C))}^2 \leq \sum_{i,k}|A_{ik}|^2, $$

but simple counterexamples show that neither of the two inequalities can be sharp.


What does the derivative of an integral give you? I just find this so confusing. So if you evaluate the integral you are given its anti derivative.

So like if you have $f(x)$, $f'(x)$, the integral of $f'(x)$ is $f(x)$.

What does the derivative of an integral give you? For example, if I am at $$\frac{d}{dx}\big(\int_{0}^{x}\frac{t^2}{t^2+t+2}
dt\big)$$, what does this give you if $\frac{t^2}{t^2+t+2}$ is $f(x)$?

Okay, let's use my exact function above $y$, for example $$y = \int_{0}^{x}\frac{t^2}{t^2+t+2}
dt$$ Find the interval where it is concave down.

How would I do this?

I did: $$y' = \frac{x^2}{x^2+x+2}$$

$$y'' = \frac{x(x+4)}{(x^2+x+2)^2}$$

The two points at zero are $x = 0$ and $x = -4$. I completely forgot how to get concavity, but I'm pretty sure $x = -4$ would give us the concave down. So $$\int_{0}^{-4} \frac{t^2}{t^2+t+2} dt$$, would give me the correct answer, right?

That's exactly the fundamental theorem of calculus, part 1. I'd recommend you to read it on Wikipedia.

If $I$ is an intervall in $ \mathbb R$ and $f:I \to \mathbb R$ is continuous and if $a \in I$, then the fuction

$F(x)=\int_{a}^{x}f(t) dt$  $\quad $ ($x \in I$)  $\quad $

has the following properties:

$F \in C^1(I)$ and $F'=f$ on $I$


Derivative of a definite integral Could you help me to find the derivative of this definite integral?

$\frac{d}{dt}\int_0^t{e^{A(t-s)}f(s)ds}$,

where $A$ and $f$ are matrices.

Basically I want to find the maximum/minimum points for the general solution of a system of linear differential equations:

$\frac{d}{dt}x(t)=0=\frac{d}{dt}[e^{At}x_o+\int_0^t{e^{A(t-s)}f(s)ds}]$,

where $x_o$ is the initial conditions vector.

Regards,

Marcos.

Rewrite the integral as $\;\displaystyle\mathrm e^{At} \int_0^t\mathrm e^{-As}f(s)\,\mathrm d s $ and apply the First fundamental theorem of integral calculus:
\begin{align}\frac{\mathrm d}{\mathrm d t}\biggl(\mathrm e^{At} \int_0^t\mathrm e^{-As}f(s)\,\mathrm d s\biggr)&=A\,\mathrm e^{At} \int_0^t\mathrm e^{-As}f(s)\,\mathrm d s+\mathrm e^{At}\frac{\mathrm d}{\mathrm d t}\biggl(\int_0^t\mathrm e^{-As}f(s)\,\mathrm d s\biggr)\\
&=A\,\mathrm e^{At} \int_0^t\mathrm e^{-As}f(s)\,\mathrm d s+\mathrm e^{At}\,\mathrm e^{-At}f(t)\\
&=A\,\mathrm e^{At}\int_0^t\mathrm e^{-As}f(s)\,\mathrm d s+f(t).
\end{align}

Your question makes sense but the motivation does not: these are vectors!

Aynways,
$$
\frac{d}{dt}\left[e^{At}x_0+\int_0^t{e^{A(t-s)}f(s)\,ds}\right]=\frac{d}{dt}x(t)=Ax(t)+f(t).
$$


Find the number of routes from leftmost vertex to rightmost vertex Suppose that one can move from one vertex to another if, and only if,
  the two vertices are connected by a unique common edge. The number of
  routes that one can take from the leftmost vertex L through 6 edges
  and 5 intermediate vertices to the rightmost vertex R is .......

This is my scholarship practice exam (pre-university level) and the only way I did it correctly is by counting but I feel it was a bit messy but it can be simplified by writing with alphabets such as (u for up, d for down, s for go straight).

However, there could be other solutions such as combination or permutation, probably. The answer key provided is 12. Please advise what you think and how to solve this problem.

The annoying bit are the two triangles at the bottom and top. You can get the answer by considering paths that don’t and do go through those triangles. For the ones that don’t, there are $2\cdot \
2\cdot 1\cdot1\cdot 2\cdot 1=8$ paths.

For the ones that pass through the triangles, convince yourself that it’s only possible to pass through exactly one and not both. For the bottom triangle there are two possible paths (differing only at the R end). For the top triangle there are two possible ways to get to it from L and then only 1 way to get to R.

So the answer is 12

Try labeling the vertices and writing down the resulting adjacency matrix. Then raise it to the power of 6, and read the entry in the (i, j) position, where i and j are the labels of the left- and right- most vertices, respectively. Since the adjacency matrix is 14 x 14, you should probably use a computer. I recommend using the Wolfram alpha website. Although it wouldn't be too hard by hand, since A^6 = (A^2)^2 A^2.


Solving the homogeneous heat equation using the method of fundamental solutions I'm trying to solve the PDE $u_t=Du_{xx}$ using the method of fundamental solutions. I've used the ansatz $u(x,t)=t^{\alpha/2}f(x/\sqrt{t})$ and this has given me the following ODE: $$\frac{\alpha}{2}f(\phi)-\frac{1}{2}\phi f'(\phi)=Df''(\phi)$$ where $\phi=x/\sqrt{t}$.

I'm then told to let $\alpha=-1/2$, leaving me with the ODE $$-\frac{1}{4}f(\phi)-\frac{1}{2}\phi f'(\phi)=Df''(\phi)$$

I'm not sure how to solve this though.

Note: $D \in \mathbb{R}_{>0}$

Let's start from the top. Make the ansatz
$$
u(x,t) = t^\alpha f\left(\frac{x}{2\sqrt{Dt}}\right)
$$
Then after some massaging of the differential equation and substituting $\phi = x/(2\sqrt{Dt})$, you end up with
$$
f''(\phi) + 2\phi f'(\phi) - 4\alpha f(\phi) = 0
$$
The form of the differential operator suggests the substitution $f(\phi) = e^{-\phi^2}h(\phi)$, which then gives
$$
h''(\phi) - 2\phi h'(\phi) - 2(1+2\alpha)h(\phi) = 0
$$
This is a well-known differential equation called Hermite's equation. These solutions normally blow up extremely quickly for $\phi \rightarrow\pm \infty$, but for certain special values of $\alpha$ it will have polynomial solutions. Those values are $\alpha = -n-1/2, n\in \mathbb N$, and the polynomials are denoted by $H_n(\phi)$. These will be the only solutions for which $f(\phi)$ remains finite for all $\phi$. So, substituting back into the original expression, we find the fundamental solutions are
$$
u(x,t) = A_n t^{-n-1/2}H_n\left(\frac{x}{2\sqrt{Dt}}\right)\exp\left(\frac{x^2}{4Dt}\right)
$$
for some normalization constant $A_n$.

This answer was for the original version of the question asked

I would divide through by $y=f(\phi)$ first, and integrate w.r.t $y$:

$$\int\frac{y''}{y}dy=C\int 2\phi - 1 dy=Cy(2\phi-1)+G$$

Where $G \in \mathbb{R}$.

Then use a substitution, however I am not sure if the LHS integral has a closed form (exact) solution.


Integration by parts, What I should do next I'm integrating a function by parts but I get stuck in a part.

Since here, What should I do next?

alright so u got the integral $\int \:x\ln \left(x+1\right)dx$ ?

let

$u=x+1\quad \quad du=1dx,\:\quad \:dx=1du$

sub dx for du, and x+1 for u

$=\int \:x\ln \left(u\right)du$

$u=x+1\quad \Rightarrow \quad \:x=u-1$

$=\int \left(u-1\right)\ln \left(u\right)du$

integration by parts:

$u=\ln \left(u\right),\:\:u'=\frac{1}{u},\:\:v'=\left(u-1\right),\:\:v=\frac{\left(u-2\right)u}{2}$

$=\ln \left(u\right)\frac{\left(u-2\right)u}{2}-\int \frac{1}{u}\frac{\left(u-2\right)u}{2}du =\frac{\left(u-2\right)u\ln \left(u\right)}{2}-\int \frac{u-2}{2}du =\frac{\left(u-2\right)u\ln \left(u\right)}{2}-\frac{\frac{u^2}{2}-2u}{2}$

sub back u=x+1 and add the integration constant and ur done.


How to draw this finite automate? I would like to verify if i have the good approach to this problem, while looking at my solution it seems ok but i am not sure. Thank you.
I am using this tool to draw if you wanna help out : http://madebyevan.com/fsm/
Here's the question  :
Build a finite automata ( it can be deterministic or not) that accept this language on the alphabet $\{0,1\}$ :
$$L=\{w : w \neq 11 \text{ and } w \neq 101  \}$$
In other words, L includes all sequences except 11 and 101
Here's what i tried :

You might benefit from constructing a complete binary tree of depth three (each internal node has one child consuming a "0" and one consuming a "1"), determining which nodes are rejecting, which are accepting, and then simplify the tree.


Proof orthogonality of Legendre polynomials using Sturm Liouiville theory only I want to prove that Legendre Polynomials corresponding to different eigenvalues are orthogonal, using (if possible) only Sturm Liouville Theory. I had a look here but they seem to prove something harder and with different techniques.

I will highlight my questions, so it is clearer where I have doubts.

$1$ GENERAL THEORY

$1.1$ General Sturm-Liouville Problem

A regular SL problem on $[x_0,x_1]$ is $$\frac{d}{dx}\left(p(x)\frac{dy}{dx}\right)+q(x)y+\lambda(x)y=0$$ with $p(x)$, $p'(x)$, $q(x)$ and $w(x)$ continuous on $[x_0,x_1]$ and with $p(x)>0$ and $w(x)>0$ on $[x_0,x_1]$.

$1.2$ General Sturm-Liouville Linear Operator

We have a linear operator $\mathcal L\colon y\mapsto \mathcal L[y]:=-\frac{1}{w(x)}\left(\frac{d}{dx}\left(p(x)\frac{dy}{dx}\right)+q(x)y\right)$ with the property that $\mathcal Ly=\lambda y$. Hence the SL equation is an eigenvalue problem.

$1.3$ Linear Operator is Self-Adjoint

After defining $$\langle f,g\rangle_w=\int_{x_0}^{x_1}f(x)g(x)w(x)\,dx$$ we say $\mathcal L$ is self-adjoint if for all pairs of functions $y_a$ and $y_b$ we have $\langle \mathcal L[y_a], y_b\rangle_w=\langle y_a, \mathcal L[y_b]\rangle_w$. By writing this in form of an integral, we obtain that it works, provided suitable boundary conditions (zero-Dirichlet, zero-Neumann,  radiation, singular points, periodic).

$1.4$ Properties of Solutions and Eigenvalues

We then then prove various things among which "Eigenfunctions corresponding to distinct eigenvalues are orthogonal".

$2$ LEGENDRE CASE STUDY

Legendre Differential Equation

Is given by $$\frac{d}{dx}\left((1-x^2)\frac{dy}{dx}\right)+n(n+1)y=0$$
hence setting $p(x)=1-x^2$, $q(x)=0$ amd $w(x)=1$ we have a SL equation, with $\lambda=n(n+1)$.

Legendre Equation as Sturm-Liouville Problem on $[-1,1]$

Now $w(x)=1>0$ however we also require $p(x)=1-x^2>0$. This is true for $x\in [-1,1]$. Notice also that $p(x)$, $p'(x)$, $q(x)$ and $w(x)$ are all continuous on this interval. Hence we have a singular Sturm Liouville problem on $[-1,1]$.

Legendre Equation Linear Operator

We have found a linear operator $\mathcal L\colon y \mapsto \mathcal L[y]:=-\frac{d}{dx}\left((1-x^2)\frac{dy}{dx}\right)$. This enables us to write $\mathcal Ly=n(n+1)y$ or $\mathcal Ly = \lambda y$ where $\lambda=n(n+1)$.

  Can we just state that the Legendre polynomials (which are solutions to the Legendre equation) are orthogonal if they correspond to distinct eigenvalues (e.g.. $\lambda_n=n(n+1)$ and $\lambda_m=m(m+1)$ with $m\neq n$)?

Or do we have to prove it? If so, why do we have to prove it and how?

I mean it seems to me that we have the theory for the general Sturm Liouville problem. However in my textbook and in various pdfs found online, they prove everything saying that it is not sufficient to say it. How come?

The Legendre equation is a singular equation on $(-1,1)$ because $p(x)=1-x^2$ vanishes at $x=\pm 1$. Without endpoint conditions, this operator is not well-defined as a selfadjoint Sturm-Liouville operator. The conditions required at $x=\pm 1$ are not obvious. There are singular types of Sturm-Liouville problems where endpoint conditions cannot be imposed, but that's not the case here. There are non-standard conditions at $x=\pm 1$ that lead to fully selfadjoint operators, with corresponding eigenfunctions that are not the Legendre polynomials, and for which the eigenvalues are not $n(n+1)$, as they are for the Legendre polynomials.

Without specifying the endpoint conditions at $x=\pm 1$, every real number is an eigenvalue, in the same way that regular problems do not have discrete eigenvalues without imposing endpoint conditions. As it turns out, the standard Legendre operator $Lf=-\frac{d}{dx}\left((1-x^2)\frac{df}{dx}\right)$ can be formulated by requiring that $f$ be twice continuously differentiable on $(-1,1)$, that $f$ be in $L^2$, that $Lf \in L^2(-1,1)$, and that $f$ remain bounded near $\pm 1$. That's enough to force a discrete set of eigenvalues--namely $\lambda=n(n+1)$--and to give orthogonality of the eigenfunctions. Without such conditions, though, this is not a well-posed Sturm-Liouville problem. For example, $Lf=0\cdot f$ has two independent $L^2$ solutions $f_1 = 1$, $f_2 = \ln\frac{1+x}{1-x}$. And $f_2$ is not orthogonal to the polynomial solution $p(x)=x$ of $Lp=2p$, even though $x$ is orthogonal to $f_1=1$. So, it is absolutely true that something must be said about endpoint conditions, in other to obtain a selfadjoint problem where eigenfunctions corresponding to different eigenvalues are automatically orthogonal.

The Legendre equation is in the "limit-circle" case at $x=\pm 1$, which means that all classical solutions of $Lf=\lambda f$ are in $L^2(-1,1)$, regardless of $\lambda\in\mathbb{C}$. And that means that endpoint conditions are needed at each endpoint in order to obtain a selfadjoint problem, which is quite analogous to the case for regular Sturm-Liouville problems on a finite interval. The endpoint conditions, however, are non-trivial to describe. For example, if $f$ is twice continuously differentiable in $(-1,1)$ with $Lf \in L^2$, then there exist unique numbers $A_{\pm}(f)$ and $B_{\pm}(f)$ such that
$$
          f(x) = A_{\pm}(f)\frac{1}{2}\ln\left(\frac{1+x}{1-x}\right)+B_{\pm}(f)+o\left(\sqrt{1-x^{2}}\ln\left(\frac{1+x}{1-x}\right)\right), \;\;\; x\approx  \pm 1.
$$
The numbers $A_{\pm}(f)$, $B_{\pm}(f)$ are computed as limits:
\begin{align}
          A_{\pm}(f) & =  \lim_{x\rightarrow \pm 1}\left[(1-x^{2})f'(x)\right], \\
          B_{\pm}(f) & = \lim_{x\rightarrow\pm 1}\left[f(x)-A_{\pm}(f)\frac{1}{2}\ln\left(\frac{1+x}{1-x}\right)\right].
\end{align}
Valid endpoint conditions at $x=\pm 1$ that lead to selfadjoint problems are analogous to ordinary endpoint conditions, and have the general form
$$
          \cos\alpha A_{-}(f) + \sin\alpha B_{-}(f) = 0 \\
          \cos\beta A_{+}(f) + \sin\beta B_{+}(f) = 0.     \tag{$\dagger$}
$$
The conditions giving rise to the ordinary Legendre polynomials as eigenfunctions are:
$$
       A_{-}(f) = 0,\;\; A_{+}(f) = 0.   \tag{$\dagger\dagger$}
$$
Imposing conditions $(\dagger\dagger)$ forces $f$ to have limits at $\pm 1$.
But there are selfadjoint problems for $L$ that do not result in the Legendre polynomials as solutions; a two parameter family of such operators $L_{\alpha,\beta}$ are described by $(\dagger)$. It turns out that the above classical conditions $(\dagger\dagger)$ are equivalent to imposing a condition of boundedness on $f$ near $\pm 1$, which is the classical way that Physicists and Engineers generally pose the problem, not realizing that this is an actual endpoint condition where some endpoint quantity is $0$. The functionals $A_{\pm},B_{\pm}$ as described above form a basis for the continuous linear functionals on the graph of $L$ that vanish on $\mathcal{C}_{c}^{\infty}(-1,1)$, which is how abstract boundary functionals are defined for singular Sturm-Liouville operators.

This is perhaps easier to understand from linear algebra. Consider the eigenvalue problem with symmetric matrix $A$ (e.g. $A = A^T$). Let $(\lambda_1,u)$ and $(\lambda_2,v)$ be eigenvalue/vector pairs. Consider
$$ v^T A u - u^T A v = (\lambda_1 - \lambda_2) \langle u, v \rangle. $$
Finally note that $A = A^T$ implies that the LHS is 0 and so either $\lambda_1 = \lambda_2$ or the eigenvectors are orthogonal. The SL operator is a symmetric linear operator and so shares this property.


How can the smallest set of integers be generated such that the sums cover a given set? I have a set of positive integers S.  I want to generate a set of positive integers T such that every member of S is the sum of some combination of members from T.  I am looking for the smallest possible T.

I.e. Given $S = \{x|x \in \Bbb N\}$, generate the smallest possible $T = \{y|y \in \Bbb N\}$ such that for each $x$ in $S$ there exists a $K \subset T$ where $x = \sum_{y\in K} y$

This is for a real-world application.  A solution that is close to optimal is good enough. The size of $S$ is ~$2^{30}$

Does this problem have a well-known name?  I'm not getting anywhere with google.  Can you point me in the right direction?

Generate $T$ by stages. Say $A=\{a_1<a_2<a_3<\dots\}$. In stage $1$, put $a_1\in T$. In stage $2$, put $a_2\in T$. At the beginning of stage $n$, we have an approximation to $T$. If $a_n$ is sum of distinct elements of this approximation, we are done with this stage, and go to the next one. Otherwise, add $a_n\in T$, and this concludes stage $n$. At each stage we are adding elements only if they are needed. The set we get at the end is the "smallest" $T$ you require. Note that smallness here is assuming $T\subset S$. Otherwise, there may not be a smallest set. For instance, if $S=\{1,3\}$ then $T_1=S$ and $T_2=\{1,2\}$ work and are $\subseteq$-incomparable.


Integration by parts help $\int^3_{-1}\frac{1}{2}e^{\sqrt{x+1}}\,dx$ Use the substitution $u=\sqrt{x+1}$ to find the exact value of
  $\displaystyle\int_{-1}^3 \frac{1}{2}e^{\sqrt{x+1}}\,dx.$

I've substituted and found the derivative of u, but I'm not sure what to do when I substitute it back in. Can someone tell me every step I need to do?

The first step is to differentiate the substitution:

$\displaystyle u = \sqrt {x + 1} $

$\displaystyle \frac {du} {dx} = \frac d {dx} [(x + 1)^{\frac 1 2}] $

$\displaystyle \frac {du} {dx} = \frac {1} {2 \sqrt {x + 1}} $

The next step is determining the infinitesimal relationship:

$\displaystyle du = \frac {1} {2 \sqrt {x + 1}} dx $

Note however, that substitution at this point won't help:

$\displaystyle \int _{-1} ^{3} {\frac 1 2 e^{\sqrt{(x + 1)}}} \ dx = \int _{-1} ^{3} {\frac 1 2 e^u} \ dx $

The addition "trick" is the substitution in the infinitesimal relationship as well:

$\displaystyle {du} = {\frac {1} {2 \sqrt {x + 1}} dx} $

$\displaystyle {du} = {\frac {1} {2 u} \ dx} $

The substitution for $ dx $ is:

$\displaystyle dx = 2u du $

Applying the substitution, including the infinitesimal, yields:

$\displaystyle {\int _{-1} ^{3} {\frac 1 2 e^{\sqrt{(x + 1)}}} dx} = {\int _{u(x = -1)} ^{u(x = 3)} {u e^u} du} $

$\displaystyle {\int _{-1} ^{3} {\frac 1 2 e^{\sqrt{(x + 1)}}} dx} = [(u - 1)e^u] _{u(x = -1)} ^{u(x = 3)} $

The integral can now be calculated (taking care to preserve the correct boundaries):

$\displaystyle u(x = -1) = \sqrt {-1 + 1} = 0 $

$\displaystyle u(x = 3) = \sqrt {3 + 1} = 2 $

$\displaystyle [(u - 1)e^u] _{u(x = -1)} ^{u(x = 3)} = (2 - 1)e^2 - (0 - 1)e^0  $

Thus, the solution for the formula:

$\displaystyle \int _{-1} ^{3} {\frac 1 2 e^{\sqrt{(x + 1)}}} dx = e^2 + 1 $


Expressing $z^3 = -i$ in the form $z = a +bi$ How would I go about expressing $z^3 = -i$ in the form $z = a + bi$ without any trig functions in the answer?

I know that $z = a + ib$ so would I go ahead and solve that equaling $-i$?

Hint: use that

$$z^3+i = z^3-i^3=(z-i)(z^2+zi+i^2)$$

So $z_1=i$ and the other two you will get solving $z^2+zi-1=0$.

That you can do either by direct solving a quadratic equation or plug in $z=a+bi$ with $a,b$ real...

For $z = a+ib$, we have
\begin{equation}
 z^3 = (a+ib)^3 = (\underbrace{a^3 - 3ab^2}_0 )+(\underbrace{3a^2b- b^3}_{-1})i
\end{equation}
Now solve for $a,b$ using the two equations above and you must get three distinct solutions $(a_1,b_1), (a_2,b_2), (a_3,b_3)
$


Finding $t$ values that satisfy $\frac{\sqrt{3+\sqrt[3]{t}}}{\sqrt{3-\sqrt[3]{t}}} = 3$ My Attempt:

$t$ values that satisfy $\frac{\sqrt{3+\sqrt[3]{t}}}{\sqrt{3-\sqrt[3]{t}}} = 3$

Move the denominator to the right side of equality via multiplication.

$\sqrt{3+\sqrt[3]{t}} = 3\sqrt{3-\sqrt[3]{t}}$

Then

$\left(\sqrt{3+\sqrt[3]{t}}\right)^{2} = \left(3\sqrt{3-\sqrt[3]{t}}\right)^{2}$

Then

$3+\sqrt[3]{t} = 9\left(3-\sqrt[3]{t}\right) \therefore 3+\sqrt[3]{t} = 27-3\sqrt[3]{t}$

Move the constants to the right side.

$\sqrt[3]{t} = 24 - 3\sqrt[3]{t}$

Move the radical to the left

$4\sqrt[3]{t} = 24$

Removing the $4$ coefficient.

$\sqrt[3]{t} = 6$

Getting rid of the radical.

$\left(\sqrt[3]{t}\right)^{3} = 6^{3} \therefore t = 216$

When plugging this number back into the original equation, I get a denominator with $\sqrt{-3}$ which makes no sense.

You made a mistake in $$3+\sqrt[3]{t} = 9\left(3-\sqrt[3]{t}\right) \therefore 3+\sqrt[3]{t} = 27-3\sqrt[3]{t}$$  which should have been $$3+\sqrt[3]{t} = 9\left(3-\sqrt[3]{t}\right) \therefore 3+\sqrt[3]{t} = 27-9\sqrt[3]{t}$$

That gives $\sqrt[3]{t} = 2.4$ which satisfies the equation.

Try a simpler way:

squaring both sides

$$\dfrac91=\dfrac{3+\sqrt[3]t}{3-\sqrt[3]t}$$

Apply Componendo et Dividendo

$$\dfrac{9+1}{9-1}=\dfrac3{\sqrt[3]t}$$


$E[X]$ derivation in Coupon Collecting Problem in Ross Probability Models In Ross Probability Models 11th edition on page 307, the following is written (in picture link).
Coupon Collecting $E[X]$ derivation. $X=\max(X_j)$ is the time at which we obtain the collection of the coupons, and $X_{j}$ is independent exponential. I am not following why $E[X]=\int_{0}^{\infty} P(X \ge t)dt$?

This isn't specific to this particular random variable $X$. It's a general expression for the expected value of a non-negative random variable that you can derive from the corresponding integral with the density using integration by parts:

$$
E[X]=\int_0^\infty f_X(t)t\mathrm dt=\left[-P(X\ge t)t\right]_0^{\infty}+\int_0^\infty P(X\ge t)\mathrm dt\;.
$$

Let $(\Omega,\mathcal F,\mathbb P)$ be a probability space and $X:\Omega\to\mathbb R$ a random variable with $\mathbb P(X\geqslant0)=1$. The map $(\omega,x)\mapsto \mathsf 1_{\{X(\omega)>x\}}$ on $\Omega\times[0,\infty)$ is $\mathcal F\otimes\mathcal B(\mathbb R)$-measurable and is nonnegative. The measure $\mathbb P\otimes m$ ($m$ denoting Lebesgue measure) on $\Omega\times[0,\infty)$ is $\sigma$-finite, and hence by Tonelli's theorem the integral
$$
\iint_{\Omega\times[0,\infty)} \mathsf 1_{\{X(\omega)>x\}} \ \mathsf d(\mathbb P\times x) $$
exists and is equal to the iterated integrals in the sequel. One has
\begin{align}
\int_\Omega\int_{[0,\infty)}\mathsf 1_{\{X(\omega)>x\}}\ \mathsf dx\ \mathsf d\mathbb P(\omega) &= \int_\Omega\int_0^{X(\omega)}\ \mathsf dx\ \mathsf d\mathbb P(\omega)\\ &= \int_\Omega X(\omega)\ \mathsf d\mathbb P(\omega)\\ &= \mathbb E[X]
\end{align}
by definition of expectation, and further
\begin{align}
\int_{[0,\infty)}\int_\Omega \mathsf 1_{\{X(\omega)>x\}}\ \mathsf d\mathbb P(\omega)\ \mathsf dx &= \int_{[0,\infty)}\mathbb P(\omega\in\Omega:X(\omega)>x)\ \mathsf dx\\
&=\int_0^\infty \mathbb P(X>x)\ \mathsf dx.
\end{align}
Hence,
$$
\mathbb E[X] = \int_0^\infty \mathbb P(X>x)\ \mathsf dx.
$$


A sum involving Fibonacci numbers, $\sum_{k=1}^\infty F_k/k!$ Let $F_k$ be Fibonacci numbers. I am looking for a closed form of the sum  $\sum_{k=1}^\infty F_k/k!$.

I tried to use Wolfram Alpha, but it is not doing the sum Fibonacci[k]/k! , k=1 to infinity.

Can someone tell what is the problem with WA and what this sum equals to?

A hint:

You can prove for yourself or find in a book a formula of the form
$${\rm fib}(k)=a\lambda^k + b\mu^k$$
with certain constants $a$, $b$, $\lambda$, $\mu$. The requested sum can then be easily written as a sum of two exponentials.


Formula for producing numbers between 0 and 255? I'm writing a program that needs to cycle through numbers between 0-255 given mouse X position. If given number goes over 255, the difference should be subtracted, as in 0,1,2...255,254,253...3,2,1,0,1,2,3,4...255,254...

For example

Given  Output
  1      1
  2      2
 255    255
 256    254
 509     0
 510     1

I've been toying with different formulas (x mod 255) is close but when it goes over 255, goes straight to 0 rather than 254.

Another one I came up with was round( 127.5*cos(x/16)+127.5 ) it produced decent numbers but not good enough.

Am I making this too complicated? What is a formula that can produce numbers like this?

Here's a detailed solution which works for $5$ instead of $255$, but I easily extended it to your need at the end.

Let's start with a function $f(x) = x$. For $1$ to $9$ you get :

$1,2,3,4,5,6,7,8,9$

Then with $x-5$, you get :

$-4,-3,-2,-1,0,1,2,4,5$

With $\sqrt{(x-5)^2}$ you get :

$4,3,2,1,0,1,2,3,4$

Then $5-\sqrt{(x-5)^2}$ gives you :

$1,2,3,4,5,4,3,2,1$.

For $5$, the final formula is $f(x) = 5-\sqrt{(\bmod(x,9)-5)^2}$
For $255$, your final formula is then  $f(x) = 255-\sqrt{(\bmod(x,509)-255)^2}$ !

PS : I saw you using PHP so here's the PHP equivalent :

return 255-abs((x%509)-255)

As a single function:
$$\mathrm{sgn}\left(\sin(\dfrac{\pi x}{255})\right)x \pmod{255}$$

Or piecewise:
$$*\left\{\begin{matrix}
x \pmod {255} &&&1\leq x\leq 255 \mod (510)\\
-x \pmod {255} &&&256\leq x\leq 510 \mod (510)
\end{matrix}\right.$$

I think these should work.


How to rewrite an expression Let's say $Z=Y_1+Y_2$. I have this expression: $Y_1!Y_2!$. I want to rewrite the expression and express it by only $Z$. Is that possible?

No, because for example if you take $Y_1=5$, $Y_2=7$ or if you take $Y_1=4$, $Y_2=8$, then both give the same $Z$ but different $Y_1!Y_2!$.

Not possible. Consider $Z=4$ with $Y_1 = 1$ and $Y_2 = 3$, you'll get an answer of $6$. Now try this with $Y_1 = 2$ and $Y_2 = 2$, you'll get an answer of $4$.


Recurrence relationships and a "weighted Pascal's triangle" I was thinking about this problem a few days ago and in the process I came up with what I can best describe as a two-dimensional recurrence relationship. It seemed obvious to me that this was something akin to a description of Pascal's triangle, so I began to think more carefully about a recurrence relationship that would yield the binomial coefficients. I wondered what would be the output if I tinkered slightly with the nature of the recurrence relationship.

Let $t_{n,m}$ be the $m$th entry in the  $n$th column of what will be a triangle like Pascal's triangle.

Example 1:

Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$

For $n \ge1$ let $t_{n,0}=t_{n-1,0}$ and let $t_{n,i}=t_{n-1,i}+t_{n-1,i-1}$ for $i \ge 1$

I think it's pretty obvious that $t_{n,m}$ are simply the binomial coefficients.

Example 2:

Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$

For $n \ge1$ let $t_{n,0}=at_{n-1,0}$ and let $t_{n,i}=at_{n-1,i}+bt_{n-1,i-1}$ for $i \ge 1$

In this case $t_{n,m}$ are the coefficients of $\left(ax+b \right)^n$.

So far the recurrence relationships have been what I guess you could call homogeneous. The next example is what I stumbled across in the other question.

Example 3:

Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$

For $n \ge1$ let $t_{n,0}=it_{n-1,0}$ and let $t_{n,i}=it_{n-1,i}+t_{n-1,i-1}$ for $i \ge 1$

It's intersting to see the factorials and the triangle numbers here.

I then decided to generalise as follows:

Example 4:

Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$

For $n \ge1$ let $t_{n,0}=hit_{n-1,0}$ and let $t_{n,i}=(a+hi)t_{n-1,i}+(b+ki)t_{n-1,i-1}$ for $i \ge 1$

My spreadsheet will calculate the values of $t_{n,m}$ but I now have no idea what they are!

To conclude, my questions are:

How can I prove that Example 1 gives the binomial coeffients?

How can I prove that Example 2 gives the coefficients of $\left(ax+b \right)^n$ ?

Can we find a way to describe $t_{n,m}$ as a function of $n, m, a, b, h, k$ ?

Is there a more general situation that has already been studied? Something like $t_{n,i}=f(i)t_{n-1,i}+g(i)t_{n-1,i-1}$

I have been obsessed with this "weighted Pascal's triangle" for some time now, and it has become a goal of mine to determine a formula (n p) that can give me any one of these coefficients.

1

1 1

1 3 2

1 6 11 6

1 10 35 50 24

1 15 85 225 274 120

I have located several patterns.

Farthest to the right: the factorials.

Farthest to the left: N

Second column on the left: the triangulars.

Second column on the right: the harmonic numerators, n!*Hn

I have also developed a set of formulas which give any particular coefficient of any particular column (shifted to compensate for columns previously accounted for).

Third column on the left: (n+2)(n+3)(n+4)(3n+11)/24

Fourth column on the left: (n+2)(n+3)(n+4)^2(n+5)^2/48

Fifth column on the left: (n+2)(n+3)(n+4)(n+5)(n+6)(15n^3+240n^2+1265n+2192)/5760

Sixth column on the left: (n+2)(n+3)(n+4)(n+5)(n+6)^2(n+7)^2(3n^2+35n+96)/5760

And so on...

Plug in any n into any one of these particular formulas and it'll give you whichever coefficient of the weighted Pascal's triangle that you want.

I am currently stuck at this point, for it has been my goal to determine some kind of coherent link that binds these formulas together. Preliminary calculation suggests that the denominators are quite elementary (some form of factorial), though I have not solved them yet. And the numerator has a consistent addition of a factor (n+p), so indeed there are coherent *similarities* between these formulas.

The problem is with these seemingly random odd-ball factors that make no sense to me.

If you are still enthusiastic about the aforementioned triangle, I would like to propose a friendship; I will share with you how I derived these formulas and perhaps we can figure out an explicit formula that will give any value of this triangle we choose.

Thanks, Marcus.

fossamarcus@gmail.com


SAT Math: 3 Inequality Questions These 3 SAT math problems should be no-brainers, but I don't understand them
1.

x can't be 2 because you can't divide by 0. So that means B, C, and D should be wrong. That means A should be correct. However, if you input x=6 for example, you get 12/4 which is less than 6. That means all answer choices are wrong. But the answer key says C is correct.
Any explanations?
2.

I know that |p-q| <= 3 and -12<p+q<30. The book said the answer is A. But I disagree because you can plug in 16 for q then the great value for p would be 19 according to the first equation. When you add 19+16, then that is 34, and greater than 30. I chose D.
Any explanations?
3.

According to question, G:H is 4:5 which is equivalent to 8:10. H:J is 10:17. Since half of the people who voted for candidate H had instead voted for Candidate J, the new ratio for H:J should be 5:22. And in order to keep the ratio between G:H consistent I changed it to 4:5. This means J:G ratio should be 22:4 or 11:2, which isn't an answer. The book says the correct answer is D neglecting to change the votes for G after H:J was changed.
Any explanations?
Thank you very much. Have a good day.

The inequality $$\frac{x+6}{x-2} > 6$$ has the solution set $$2 < x < \frac{18}{5}$$ for real $x$.  Since we are told that $x$ is an integer, it follows that the unique solution is $x = 3$.  All of the options are incorrect.
The full solution of the inequality is as follows.  We consider two cases, $x > 2$ and $x < 2$.  In the former, both numerator and denominator are strictly positive, hence $$x + 6 > 6(x-2) = 6x - 12,$$ and we obtain $2 < x < \frac{18}{5}$, remembering that this corresponds only to the first case.  In the second case, we obtain $$x + 6 < 6(x-2) = 6x - 12,$$ hence $(x > \frac{18}{5}) \cap (x < 2) = \emptyset$ and there is no such $x$.

For your second question, the requirement that $|p-q| \le 3$ does not mean we must have $p > q$.  We can certainly choose $p < q$.  If $q = 16$, then $p = 13$ is permissible, and $p + q = 29$ which is between $-12$ and $30$.  But we cannot choose $q = 17$ since then $p = 14$ is the smallest permissible $p$, and $14 + 17 > 30$.
The formal solution proceeds as follows.  We must have $$-3 \le p - q \le 3, \\ -12 \le p + q \le 30.$$  Then $$-3 + q \le p \le 3 + q$$ from the first equation, and substitution into the second gives $$(-12 \le -3 + 2q \le 30) \cup (-12 \le 3 + 2q \le 30),$$ or equivalently $$(-\tfrac{9}{2} \le q \le \tfrac{33}{2}) \cup (-\tfrac{15}{2} \le q \le \tfrac{27}{2}).$$  The union of these intervals is $$-\frac{15}{2} \le q \le \frac{33}{2}$$ and when restricted to integers, becomes $$-7 \le q \le 16$$ as claimed.

For the third question, the way to think about it is to consider a deterministic cohort of voters that follow the proportions specified.  You already did the first step by converting the $G:H$ ratio.  The composite ratio is then  $$G:H:J = 8 : 10 : 17$$ prior to the hypothetical redistribution of voters from $H$ to $J$.  This means that in a cohort of $8 + 10 + 17 = 35$ voters, $8$ voted for $G$, $10$ voted for $H$, and $17$ voted for $J$.  If half of the $10$ voters for $H$ instead changed their votes to $J$, then the new ratio among the same $35$ voters is simply $$G : H : J = 8 : 5 : 22.$$  The resulting ratio $J : G$ is now $22 : 5$.  Your error was in thinking that the ratio between $G : H$ after the redistribution remains the same as before the redistribution; it clearly cannot.  As half of the voters who voted for $H$ were redistributed to $J$, the new ratio for $G:H$ should now be $4 : 2.5$ or $8 : 5$, not $4 : 5$.

The purpose o fan SAT, or related test, is to test if basic skills have been learned and not refined as to see faults in the problems. With this in mind the SAT style answer is:
For the first question: What is given is
$$ \frac{x + 6}{x - 2} > 6$$
which is essentially $x + 6 > 6 x - 12$ and becomes $18 > 5 x$. Now $x$ satisfies
$$ x < \frac{18}{5} = 3 + \frac{3}{5}.$$
Of the given graphs of $x$ value ranges then (C) would be the answer.


Evaluate $\int _0^{102} [\tan ^{-1} x].dx$ $$I=\int_{0}^{\tan 1} [\tan^{-1} x] + \int_{\tan 1}^{102} [\tan^{-1} x ]$$
Now the first integral is obviously zero. But I don’t know what the to do with the second one. Basically, I don’t know how to resolve floor functions in integrals. Can I get a hint?

One technique for approaching floor functions is looking at the graph of a function.  You noticed that between $0$ and $\tan 1$, the floor function is $0$.  On the other hand, the floor function between $\tan 1$ and $102$ is just $1$, due to the asymptotics of the tangent function (i.e. $1< \pi/2 < 2$).

Therefore,
$$\int_{\tan 1}^{102} [\tan^{-1} x ] \,dx = \int_{\tan 1}^{102} 1 \,dx = 102 - \tan 1.$$


Close packing of small spheres around a large one It is well known that, given a sphere, the maximum number of identical spheres that we can pack around it is exactly 12, corresponding to a face centered cubic or hexagonal close packed lattice.

My question is: given a sphere of radius $R$, how many spheres of radius $r<R$ can we closely pack around it?

With disks, the problem is rather easy to solve. Indeed, with reference to the picture at the bottom, we can see that we must have

$$\theta = \frac{2 \pi} n = 2 \arctan \left( \frac r {\sqrt{R^2+2 R r}} \right)$$

from which

$$n = \left \lfloor \frac \pi {\arctan \left( \frac r {\sqrt{R^2+2 R r}} \right)}\right \rfloor$$

The last expression gives the correct result for $R=r$, namely $n=6$ (hexagonal lattice). Moreover, when $R \gg r$, we get

$$n \simeq \left \lfloor \frac {\pi R}  {r}\right \rfloor$$

which is completely reasonable.

How can I tackle the same problem in the 3D case (spheres)?

It is clear that for  $R \gg r$ we must get

$$n \simeq \left \lfloor \frac {4 \pi R^2}  {\pi r^2}\right \rfloor$$

and also that we must have $n(R=r)=12$.

Any hint/suggestion is appreciated.

My question was how many spheres within the large ball given that the spheres have a radius of smallest known atom and the number of dimensions of packing  is equal to the radius of smallest known atom


prove sum of divisors of a square number is odd Don't know how to prove that sum of all divisors of a square number is always odd.

ex: $27 \vdots 1,3,9,27$; $27^2 = 729 \vdots 1,3,9,27,81,243,729$; $\sigma_1 \text{(divisor
 function)} =  1 + 3 + 9 + 27 + 81 + 243 + 729 = 1093$ is odd;

I think it somehow connected to a thing that every odd divisor gets some kind of a pair when a number is squared and 1 doesn't get it, but i can't formalize it. Need help.

Yes, you can assign a pair to every odd divisor, except one of them.

So, we have a square number $n^2$. Extract the largest power of $2$ from $n$ to get $n = 2^k m$ where $m$ is odd. Odd divisors of $n^2$ are the same as all divisors of $m^2$. If $d$ is a divisor of $m^2$, then $m^2/d$ is also its divisor. So they all come in pairs, except for $m$ which is paired with itself.

$144 = 12^2 = 12 \times 12$ = $2^4 \times 3^2$

so every square number is of the form $a^{2p} \times a^{2q}$

$\therefore$ total number of divisors = $(2p + 1)(2q + 1)$

$\because (2p + 1) \wedge (2q + 1)$ are both odd numbers $\forall(p \wedge q) \in \mathbb{Z}$, then every squared number $n^2$ will have an odd number of divisors.


What is a function that is equidistant from two functions? For example, let $f(x)$ be $x^2$ and $g(x)$ be $x^3 + 1$. It is easy to see that $h(x)=\frac{f(x)+g(x)}{2}$ is not equidistant from $f$ and $g$.

Then, what is a general form of a fucntion $h(x)$ that has the same distance between both of $f(x)$ and $g(x)$ ?

*If it is hard to define $h(x)$ over all range of $x$, limiting a range of $x$ is possible.

Imagine a circle moving so that it is simultaneously tangent to your two curves. Then the locus of the center of this circle would be the "equidistant" curve that you want. In computational geometry, this curve is called the "medial axis", and it has a great many uses. If you want to learn about it, you can get started at this page. The page includes a link to code that computes the medial axis. If your curves are very simple (straight lines and circular arcs, for example), there are closed-form solutions. In more general cases, the best you can do is a polygonal approximation.


Suppose $G$ is a group and $x^3y^3 = y^3x^3 ~ \forall ~x,y \in G.$ Let $H = \{x \in G |~~ |x| $ is relatively prime to 3$\}$. Suppose $G$ is a group and $x^3y^3 = y^3x^3 ~ \forall ~x,y \in G.$ Let $H = \{x \in G |~~ |x| $ is relatively prime to 3$\}$. Prove that elements of H commute with each other

$Attempt$: $x^3y^3 = y^3x^3 ~ \forall ~x,y \in G.$

And $H = \{x \in G |~~ |x| $ is relatively prime to 3$\}$

=> $\langle x \rangle = \langle x^3 \rangle ~ \forall ~x \in H$ and $O(x) = O(x^3)~ \forall ~x \in H$.

=> Elements in $\langle x \rangle$ are the same as in $\langle x^3 \rangle$ in some order.

=> $x = x^{3m}$ for some m

=> $x^{9m}y^{9m} = y^{9m}x^{9m} ~ \forall ~x,y \in G.$

Now i am unable to proceed further.

( Please note that this is a question from Gallian and i have studied only till cyclic groups before this question exercise.)

Thank you

Hint: If $k:=o(x)$ and $3$ are relatively prime, there exist $p,q$ such that $kp+3q=1$, hence $$x=x^{kp+3q}= \left( x^q \right)^3.$$


Proof $\log_b a\cdot\log_c b\cdot\log_a c=1$, Please help me proof $\log_b a\cdot\log_c b\cdot\log_a c=1$, where $a,b,c$ positive number different for 1.

Change all to the natural logarithm $\log\,$:

$$\log_ba\cdot\log_cb\cdot\log_ac=\frac{\log a}{\log b}\frac{\log b}{\log c}\frac{\log c}{\log a}$$

and voila.

Before we prove the given identity proof this idenity

$$\log_b a\log_c b=\log_c a$$

Proof: Implement the formula $\log_a b=\frac{\log_x b}{\log_x a}$

$$\frac{\log a}{\log b}\cdot\frac{\log b}{\log c}=\frac{\log a}{\log c}=\log_c a$$

Now proof the given identity.

$$\log_b a\cdot\log_c b\cdot\log_a c=1$$

$$\log_c a\cdot\log_a c=1$$

$$\frac{1}{\log_a c}\cdot\log_a c=1$$

$$1=1$$


Function for drawing $\sin x$ with a maximum value of $360$ and minimum of $70$? I want a function to draw $\sin x$ between an upper limit of $360$ and a lower limit of $70$.

Attempt: I know how to handle the lower limit but I'm having trouble with the upper limit.

$$y = a(\sin(x)+1) + 70$$

Since $\sin x$ goes from $-1$ to $+1$ you only need to make

$$f(x)=a\sin x+b$$ and solve the system $$\begin{cases}a+b=360\\-a+b=70\end{cases}$$ hence $$\color{red}{(a,b)=(145,215)}$$

Figured it out seconds after posting by luck. :)

$$y= \frac{290}{2}(\sin(x)+1)+70,$$

since $\sin (x)$ occupies a total height of $2$.


How many ways can we get 2 a's and 2 b's from aabb? We have the following group: $aabb$

It is commutative, so abab is the same as aabb.

I have figured out this is a combinatorics question.  Because abab is the same as aabb.  I was how to solve these problems with the blank slot method, i.e. _ _ _ _.

If I do this manually, it's clear to me the answer is 6,

aabb
abab
abba
baba
bbaa
baab

Which is the same as $$\binom{4}{2}$$

But I don't really understand why this is true? How is this supposed to be done without brute forcing the question?

You have four slots. Choose two of them to be a, and the other two will be forced to be b. There are $\binom 4 2$ ways to choose two slots from four, giving the answer.

This is a permutation of $4$ objects with $2$ groups of $2$ identical elements. Answer is therefore $\frac{4!}{(2! \times 2!)}$

Or, this can be also the problem of selecting $2$ places out of $4$ to replace $b$ with $a$ in the string $bbbb$, in which case the answer is $\binom{4}{2}$


Theorem of structure for abelian groups I was thinking that the structure theorem for abelian groups is not true for the trivial group. Am I missing something or is the theorem just valid for groups of order $>{1}$ ?

Edit: The theorem I'm working with is: Let $G$ be an abelian group of finite order, then there exist integers $d_1,...,d_k$ so that $$G\sim\Bbb{Z}/(d_1)\times...\times\Bbb{Z}/(d_k),$$
and so that $d_i\mid{d_{i+1}}$ for $1\leq{i}\leq{k-1}$. The trivial group clearly doesn't satisfy this.

I'm guessing you're talking about the structure theorem for finitely generated abelian groups, which is a product of groups of some form (depending on the version of the theorem you're talking about.)

The interpretation that works (which is perfectly sound) is that $\{0\}$ is the empty product of abelian groups.

I think you are confusing the trivial group with the empty set...  The latter isn't a group  (no identity )...

The trivial group is cyclic, so satisfies the theorem. ..


Completeness in $L^p$ and supremum norms As seen by this question, $C([0,1])$ is not complete in the $L^p$ norm ($1 \le p < \infty$) because one can choose a Cauchy sequence $$f_n(x) := \begin{cases}
 0   & \text{if $0 \le x \le \frac1{2}$}\\
 n(x-\frac{1}{2}) & \text{if $\frac {1}{2} < x \le \frac {1}{2} + \frac {1}{n}$}\\
 1              & \text{if $ \frac {1}{2} + \frac {1}{n} <x \leq 1 $}
\end{cases}$$ and find that, as $f_n \to f$, we have $$f(x)=\begin{cases} 0 &\text{if } 0 \le x < \frac 12 \\ 1 & \text{if } \frac 12 \le x \le 1 \end{cases},$$ which means $f \not\in C[0,1]$. Therefore $C[0,1]$ is not complete in the $L^p$ norm.

But what about the supremum norm $L^\infty$? I am not sure if $C([0,1])$ is complete in the $L^\infty$ norm, because would we not still have the counterexample of $f \not\in C[0,1]$?

I think you're forgetting the fact that completeness requires Cauchy sequences. Specifically you need $\|f_n-f_m\|_\infty<\epsilon$ for all $n,m\geq N$. However, $\lim_{m\rightarrow\infty}\|f_n-f_m\|_\infty\rightarrow 1$ for any fixed $n$. So your example is not a Cauchy sequence in $L^\infty$. Double check that it is Cauchy in $L^p$.


How to evaluate $ \lim_{x\rightarrow +\infty } \sqrt[x]{a^x+b^x} = ? $ If a>0 and b>0,
$ \lim_{x\rightarrow +\infty } \sqrt[x]{a^x+b^x} = ? $

What I was trying to do:
Suppose a>b. Then, for sufficiently large values of x, $ a^x >> b^x $; so $\sqrt[x]{a^x+b^x} \rightarrow \sqrt[x]{a^x} \rightarrow a $ when $x \rightarrow +\infty$.

Is that idea correct? How can I formalize it?

You can go this way. Assuming $b<a$

  $$ (a^x+b^x)^{1/x} = a \,e^{\frac{1}{x}\ln(1+(b/a)^x) }= a \,e^{\frac{1}{x}((b/a)^x-(b/a)^{2x}/2+\dots ) }\longrightarrow _{x\to \infty } a .$$

I think you can finish it!

Note: You need the following power series

  $$ \ln(1+t) = t-\frac{t^2}{2}+ \frac{t^3}{3}-\dots\,.  $$


In a finite field, is there ever a homomorphism from the additive group to the multiplicative group? I know that in infinite fields, such as $\mathbb{C}$, the mapping $e^x$ is a homomorphism from the additive group to the multiplicative group, and I was just wondering if in any finite field, there exists a (non trivial) homomorphism between the two.

This is impossible for finite fields.

Consider a finite field of order $q$; then the additive group also has order $q$.  However, the multiplicative group has order $q - 1$ which does not share any common factors with $q$.  Since the order of the image of an element $x$ under a homomorphism must divide the order of $x$ by Lagrange's theorem, it follows that any such homomorphism must be trivial.

Sometimes there is a homomorphism from the additive group of integers modulo N-1 and the multiplicative group of integers modulo N.

For example when N=5, given the additive group of four integers A = {0,1,2,3} and the finite field M = {0,1,2,3,4},
we can map each element a of A to a corresponding element m from the multiplicative group of M with m = 2^a mod 5.

With these groups, whenever z = x + y modulo (N-1),

it is also true that 2^z mod N = 2^x * 2^y modulo N.

(where addition, multiplication, exponentation, modulo, etc. are the common integer operations).

This is true whenever N is a Fermat prime.
(This is related to the "invertable multiplication", also called "multiplication IDEA style", used in the IDEA cipher).

I suspect there may be other mappings that work for other prime values of N.

(The additive group of four integers A = {0,1,2,3} is not exactly the same as the finite field of four elements GF(4), but they both have 4 elements, so perhaps this is close to what you are looking for.)


Basis vector & basic one-form coordinate changes in general relativity As I understand it, coordinate axes are defined by the tangents to coordinate curves. The coordinate curves are formed by the intersection of coordinate surfaces.  The nature of the particular coordinate surfaces will determine if the coordinate axis change direction from point to point.

In a book on general relativity, the author has two statements where basis vectors and basis one-forms are introduced, viz., "basis vectors are tangent to the coordinate curves (along which only one of the coordinates changes), and basis one-forms are gradients of the coordinate surfaces (on which only one of the coordinates remains constant)."

It is the parenthetical statements in bold about which I am puzzled.  Specifically, unless all the coordinate surfaces meet orthogonally everywhere, the meeting of which forms the coordinate curves, a restriction not specified in the book, then any movement, even infinitesimal, made along the tangent coordinate axis could change one or more of the other coordinates as well.  That is, aren't the bold statements either assuming orthogonality or are overly general?

The textbook (Collier, A Most Incomprehensible Thing, 2012, $\S5.1$) seems roughly alright, but your intuition is valid too:

  any movement... made along the tangent coordinate axis could change one or more of the other coordinates as well.

Now we can move along a coordinate curve without changing the other coordinates, as seen from your description of intersection of coordinate surfaces. I will use Schwarzschild[-Droste] coordinates $(t,r,\theta,\phi)$ as an example. You could take the coordinate surfaces $\theta=\pi/2$, $\phi=\pi/4$, and $t=0$ say, and then change $r$. This will not change the other coordinates!

But counter-intuitively, the $r$-coordinate curve does not depend on $r$ alone. Contrast Gullstrand-Painleve or Eddington-Finkelstein coordinates, which use identical $r$, $\theta$, $\phi$, but a different zero-th coordinate. Using one of these, the $r$-coordinate curves are actually different curves through spacetime! I learned this by accident, the hard way. (If you take the vector given by components $(0,1,0,0)$ in a given one of these coordinate systems, and transform it to another, you will not get components $(0,1,0,0)$ in the new coordinate system!)

On the other hand $dr$, which as the text says is a basis one-form, is independent of the other coordinates chosen. However I would call it the "gradient of $r$", to use the modern meaning of gradient as a one-form / dual vector. The textbook's language "gradient of the coordinate surface" makes me think of the traditional vector (not dual vector) definition of the gradient, and may mean the tangent $\partial_r$ to the coordinate curve, which should be used with caution as explained above.


Evaluate the Integral: $\int_0^2 \frac{dx}{e^{\pi x}}$ Evaluate the definite integral: $$\int_0^2 \frac{\mathrm{d}x}{e^{\pi x}}$$

My attempt:

$u=e^{\pi x}$

$du=\pi e^{\pi x}\ dx$

$\int_0^2 \frac{1}{u}\ dx$

So at this point do I divide $\pi e^{\pi x}$ by dx?

Thus, $\frac{du}{\pi\ e^{\pi x}}=dx$

and $\int_0^2 \frac{1}{u}\cdot \frac{du}{\pi\ e^{\pi x}}$

and $\frac{1}{u}\int_0^2\frac{du}{\pi\ e^{\pi x}} $

Find the new values for integral? I have no idea how to do this.

I basically would like to know if my process of solving this problem is correct and how to complete solving the problem.

You can simply do $$ \int_0^2 \frac{\mathrm{d}x}{e^{\pi x}} = \int_0^2 e^{-\pi x} \, \mathrm{d}x = \left[-\frac{e^{-\pi x}}{\pi}\right]_0^2 = \frac{1}{\pi} - \frac{e^{-2\pi}}{\pi} = \frac{1}{\pi} \left(1 - \frac{1}{e^{2\pi} }\right)$$

This is because we have, for $a\neq 0$: $$\int e^{ax} \, \mathrm{d}x = \frac{e^{ax}}{a} + c$$

note that in $\int_0^2 \frac{1}{u}\cdot \frac{du}{\pi\ e^{\pi x}}$ we can substitute $\pi\ e^{\pi x}$ with $\pi u$. Thus $$\int_0^2 \frac{1}{u}\cdot \frac{du}{\pi\ e^{\pi x}} = \int_0^2 \frac{1}{u}\cdot \frac{du}{\pi\ u} = \int_0^2 \frac{du}{\pi u^2} = \frac{1}{\pi}\left[ -\frac{1}{u} \right]^{u=2}_{u=0}$$.
However you forgot to change the range of the integral with the substitution with $u=e^{\pi x}$ thus this does not work. $x=0 \rightarrow u= 1$ and $x=2 \rightarrow u= e^{2 \pi}$. You have to put these in so we get:
$$\frac{1}{\pi}\left[ -\frac{1}{u} \right]^{u=e^{2 \pi}}_{u=1} = \frac{-1}{\pi e^{2 \pi}} +\frac{1}{\pi}  $$


Difference between a series and a sequence of partial sums I understand what a series is.
I understand what a partial sum of a series is.
But what is a sequence of partial sums? As i understand it, it's the same thing that a series.

The expression: $1+2+3+4+5+\cdots$ is a series.

The sequence of partial sums of that series is: $1, 3, 6, 10, 15, \ldots$.

Thus, a sequence of partial sums is related to a series. If the sequence of partial sums converges, as a sequence, then the corresponding series is said to be convergent as well, and to equal that convergent value.

Remember: a series is a sum; a sequence is a list.

A series $\sum u_n $ is defined by the couple $(u _n,S_n) $ where $(S_n )_{n\geq n_0}$ is the sequence of partial sums given by

$$S_n=u_{n_0}+u_{n_0+1}+...u_n .$$


How many distinct n-letter "words" can be formed from a set of k letters where some of the letters are repeated? How many distinct n-letter "words" can be formed from a set of k letters where some of the letters are repeated?

Examples:

__

How many 6-letter words can be formed from the letters: ABBCCC?

This is elementary. There are 6! arrangements counting repeats. Then we just divide by 2!3! to account for the repeats caused by the 2!3! identical arrangements of the Bs and Cs

How many 5-letter words can be formed from the letters: ABBCCC?

Excluding A we have $\frac{5!}{2!3!}$

Excluding either B $\frac{5!}{3!}$

Excluding any of the Cs $\frac{5!}{2!2!}$

Then take the sum.

How many 4-letter words can be formed from the letters: ABBCCC?

At this point I find it difficult to procede without far too many cases.

Is there a general approach?

There is a fairly systematic way to work this type of question. You were specifically wondering about:

How many 4-letter words can be formed from the letters: ABBCCC?

First, you write the 'source partition' for your word:

[C,B,A]
[3,2,1]  <-- this is the `source partition`

Note that the source partition provides for 1 triple, 1 double, and 1 single. Corresponding to that, you write every possible 'target partition' of 4-letters.

[3,1]    requests one triple and 1 single
[2,2]    requests 2 doubles
[2,1,1]  requests one double and 2 singles

For each 'target partition', you write an expression that gives the number of ways that the given target type can occur.  An example of the target type [3,1] is:

CCBC                                   # type [3,1]

The expression for that type is:

nCr(1,1)*nCr(2,1) * fac(4)/fac(3)

'nCr( n, r)' is the function for 'combinations', which gives the number of ways you can make a unique selection from n distinct things, taking r at a time.  'fac( n)' is the function for the factorial of n.

Note that source [3,2,1] provides 1 triple, and target [3,1] requests 1 triple.  Hence nCr(1,1).  After the triple is used up, the source [3,2,1] can provide 2 singles, and the target [3,1] requests 1 single.  Hence nCr(2,1) The call to fac(4), in each expression, always corresponds to the 4-letter word.  Any division, if it occurs in an expression, corresponds to each multiple request of the corresponding target partition.  That's all there is to the method, but it isn't always easy to get every last detail correct. The entire computation, as I did it in the programming language Python, follows:

# The `source partition` for the word 'ABBCCC' is:
#                 [3,2,1]
#                                                # target
w = 0                                            # ------
w += nCr(1,1)*nCr(2,1) * fac(4)/fac(3)           # [3,1]
w += nCr(2,2)          * fac(4)/(fac(2)*fac(2))  # [2,2]
w += nCr(2,1)*nCr(2,2) * fac(4)/fac(2)           # [2,1,1]
#
# The answer is 38

It is solved here. In general, you have to account for the duplicates as detailed in the link.

$\frac{_nP_r}{n_1!n_2!...n_k!}$.

where the denominator denotes factorial for indistinguishable or repeated letters.


Independence of two variables I ran into some problems while doing an exercise. The problem goes as follows:

Suppose we have two random independent variables $X$ and $Y$. Both are distributed normally with parameters $(0, \sigma^2)$. $\mathbb{P}(dx)=\frac{1}{\sigma\sqrt{2\pi}} \exp^{-\frac{x}{2\sigma^2}}dx$. For $\gamma \in \mathbb{R}$, we set $U = X \cos\gamma - Y\sin\gamma$ and $V = X \sin\gamma + Y\cos\gamma$. Show that $U$ and $V$ are independent, calculate their distribution function.

What I've tried:

I know that to check the independence I need to use $$\mathbb{E}(\varphi (X) \psi (Y) )= \mathbb{E}(\varphi(X)) \cdot \mathbb{E}(\psi(Y)) $$ For that I need to calculate $\mathbb{P}_U$, $\mathbb{P}_V$ and $\mathbb{P}_{(U,V)}$. There are two ways to do that, either pushforward measure or density function. So I'm stuck at calculating $\mathbb{P}_U$ since for pushforward measure I can't express $X$ and $Y$ by using only $U$ or $V$. And for density function I have a problem with trigonometric functions since it changes the sign according to the quadrant and so does an inequality $\mathbb{P}(X \cos\gamma - Y\sin\gamma\leq t)$.

Thanks in advance

It is straightforward to compute the joint density of $(U,V)$ from that of $(X,Y)$.  Jacobians and the like are involved in the standard undergraduate
treatment of this topic (which is often not understood very well by said
undergraduates). In this instance, the Jacobian approach is easier
since the transformation is linear.  Even more strongly for this
particular problem, the answer can be written down
with nary a mention of Jacobians, expectations, and the like. The
transformation in question is a rotation of axes, and since
the joint density $f_{X,Y}(x,y)$ has circular symmetry about the origin,
rotating the axes does not change the function: the
joint density $f_{U,V}$
is the same function as $f_{X,Y}$, that is,
$$f_{U,V}(u,v) = \frac{1}{2\pi\sigma^2}\exp\left(-\frac{u^2+v^2}{2\sigma^2}\right),
-\infty < u, v < \infty$$
and the independence of $U$ and $V$ follows immediately:
$$f_{U,V}(u,v) = \frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{u^2}{2}\right)
\cdot \frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{v^2}{2}\right)
=  f_X(u)f_Y(v)$$

To check independence of U and V you actually need $ E(UV)=E(U)E(V)$.  Since U and V are both linear combinations of X and Y even knowing that X and Y are independent does not make the independence of U and V obvious.

Now E(UV)= E([X cosγ - Y sinγ][X sinγ + Ycosγ])  expanding this we get

E(X$^2$ sinγ cosγ - Y$^2$ sinγ cosγ +XY cos$^2$γ -XY sin$^2$γ)=

E[(X$^2$-Y$^2$) sinγ cosγ +XY(cos$^2$γ - sin$^2$γ)]

Now we recognize the double angle indentities from trigonometry

cos2γ = cos$^2$γ - sin$^2$γ and

sin2γ = 2 sinγ cosγ

substituting in we get
E[(X$^2$-Y$^2$) sin2γ/2 + XY cos2γ]= E[(X$^2$-Y$^2$) sin2γ + 2XY cos2γ]/2=
(sin2γ/2) E[X$^2$-Y$^2$] + cos2γ E[XY]= (sin2γ/2) (E[X$^2$]-E[Y$^2$])+ cos2γ E[XY]
Assuming X and Y are independent we get

(1) (sin2γ/2) (E[X$^2$]-E[Y$^2$])+ cos2γ E[X] E[Y]

Now consider E[U] E[V] =E[X cosγ - Y sinγ]E[X sinγ + Y cosγ] =

(cosγ E[X] - sinγ E[Y])(sinγ E[X] + cosγ E[Y])=

sinγ cosγ E$^2$[X] + (-sin$^2$γ + cos$^2$γ)E[X] E[Y] - sinγ cosγ E$^2$[Y]

Applying the double angle formulae here we get

sinγ cosγ E$^2$[X] + cos2γ E[X] E[Y] - sinγ cosγ E$^2$[Y]=

(2) cos2γ E[X] E[Y] + [(sin2γ)/2] (E$^2$[X] - E$^2$[Y]).

This is the same as equation 1.  Hence E[UV]=E[U] E[V] and U and V are independent.


Equivalent definition of abelian group Assuming that given operation is commutative and associative, are following definitions equivalent?

1) A zero element $e_0$ exists such that $e_i+e_0=e_i$ and inverse $e_{i'}$ exists for every $e_i$ such that $e_i+e_{i'}=e_0$

and

2) For every pair of elements $e_i$ and $e_j$ there exists an element $e_k$ such that $e_i+e_k=e_j$

No, they're not equivalent. For example, let $S$ be any set, and let $+$ be the operation on $S$ given by $a + b = b$ for all $a,b\in S$. This satisfies (2) but not (1).

The issue here that you might be overlooking is that (1) says that there exists a single element $0$ which satisfies $a+0 = a$ for all $a$, while (2) only guarantees that for each $a$ there is some element $b$ such that $a + b = a$. It might be different for every $a$.

Now, you might complain that the $+$ operation in my example isn't commutative. If you mean to ask whether (1) and (2) are equivalent relative to some other axioms about $+$, you should specify exactly what axioms you have in mind.

Edit: Now that you've edited the question to add associative and commutativity of $+$, I can give a better answer. By the way, if $(S,+)$ is a set with an associative commutative operation, we call $S$ a commutative semigroup. Adding (1) makes $S$ an abelian group.

First, it's clear that (1) $\implies$ (2): Given $a$ and $c$ in an abelian group, and letting $b = (-a) + c$, we have $a + b = c$. In fact, we get something stronger, let's call it

(2'): For all $a$ and $c$ there exists a unique $b$ such that $a + b = c$.

Indeed, if we have $a + b = c$, then adding $(-a)$ to both sides, we must have $b = (-a) + c$.

Wikipedia calls (2') the Latin square property.

Now it turns out that also (2')$\implies$ (1). A binary operation satisfying (2') (for addition on the right and the left), but not necessarily associativity or commutativity, is called a "quasigroup", and every associative quasigroup is a group. The argument is simpler than the one in the link if we assume commutativity, so I'll give it here.

Identity: Let $x$ be any element of $S$, and let $e$ be the unique element such that $x + e = x$. Now let $y$ be any other element. We have $x + (y+e) = (x + e) + y = x + y$, so both $b = y+e$ and $b = y$ satisfy the equation $x + b = x + y$. Again by uniqueness, $y + e = y$. So $e$ is an identity element for $(S,+)$.

Inverses: Now that we have $e$, (2') gives inverses easily. For any $x$, let $(-x)$ be the unique element of $S$ such that $x + (-x) = e$.

So we've established that (1) is equivalent to (2'). Is it equivalent to (2)? I don't actually know... But here's an observation: Given $(S,+)$ for all $a$, there is a function $f_a\colon S\to S$ given by $f_a(x) = a+x$, and if $S$ satisfies (2), then $f_a$ is surjective for all $a$. Since any surjective function from a finite set to itself is also injective, any finite commutative semigroup satisfying (2) must also satisfy (2'). So any counterexample to the equivalence of (1) and (2) must be infinite. Maybe someone else can provide one or a proof that (2) $\implies$ (2') for commutative semigroups.

Edit 2: A proof that (2) $\implies$ (2') has been given in an answer to my follow-up question.

I'll make an attempt to answer although algebra is not my strongest area..

First of all. A field has two operations. What you seem to be talking about are a requirements on one of these operations which obey the axioms of a group.

Existance of zero or neutral element means there is one element
which if operated together with any other element yields that other element. This is a requirement for a group. However you clump it together with the inverse, which is a separate requirement. It is possible to have neutral elements without any inverse coupling between group elements.
This is the closure requirement of a group. That the "result" of the operation between any two elements must stay in the group.