Factorization of cyclic polynomial Factorize $$a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$$

Since this is a cyclic polynomial, factors are also cyclic

$$f(a) = a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$$

$$f(b) = b(b^2-c^2)+b(c^2-b^2)+c(b^2-b^2) = 0 \Rightarrow a-b$$

is a factor of the given expression. Therefore, other factors are $(b-c)$ and $(c-a)$. The given expression may have a coefficient a constant factor which is nonzero. Let it be $m$.

$$\therefore a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2) = m(a-b)(b-c)(c-a)$$

Please guide further on how to find this coefficient.

$$a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$$
$$=ab^2-ac^2+bc^2-a^2b+a^2c-cb^2$$
Now the method to factor cyclic expressions is to arrange the expression with the highest powers of the first variable, i.e:
We take powers of $a$ $$a^2c-a^2b+ab^2-ac^2+bc^2-cb^2$$
$$=a^2(c-b)-a(c^2-b^2)+bc(c-b)$$
$$=(c-b)(a^2-ac-ab+bc)$$
Now we look for powers of $b$,:
$$=(c-b)(bc-ab-ac+a^2)$$
$$=(c-b)(b(c-a)-a(c-a))$$
$$=(c-b)(c-a)(b-a)$$
$$=(a-b)(b-c)(c-a)$$
Thus, $m$ is $1$.


Proving that a function is surjective I want to prove that the function $\mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0$ defined as $(x,y) \mapsto 2^x \cdot (2y + 1) - 1$ is bijective. I have already proven that it is injective, but cannot figure out how to prove the surjectivity, since all other examples that I have seen only have 1 variable (i.e. $\mathbb{N} \rightarrow \mathbb{N}$).

We want to show that there exist $x,y \in \Bbb{N}$ such that $2^x(2y+1)-1 = z.$

This is equivalent to $2^x(2y+1) = z+1$.  Maybe there are better ways, but I would break into cases (at least as a "first draft" proof).

Case I: $z+1$ is odd.  In this case we can choose $y$ so that $2y+1 = z+1$.  Then we end up with $2^x = 1$, and so $x = 0$.
Case II(a): $z+1$ is a power of 2.  In this case we can choose $x$ so that $2^x = z + 1$.  Then we get $2y+1 = 1$, and so $y = 0$.
Case II(b): $z+1$ is even but not a power of 2.  This case is left as an exercise to the reader.  (Big hint:  Think about what you get if you divide out sufficiently large powers of 2 from evens that aren't powers of 2, such as 6, 18, 100, 576, etc.)

In order to show that the given function is surjective, we shall take $n\in \mathbb{N}_{0}$ and show that there exist $x$ and $y$ such that the desired relation holds. We can solve the problem by considering the following cases:

Case $1$: $n$ even : Write $n=2m$ for some $m\geq 0$. Then, clearly, $x=0,~y=m$ is the solution.

Case $2$: $n$ odd: Write $n=2m-1$ for some $m\geq 1$. Then, we have

\begin{eqnarray}
2^{x}(2y-1)=2m.
\end{eqnarray}

Let $l$ denote the largest divisor of $2m$ that is also a power of $2$. Then, putting $2^{x}=l$ and solving for $y$ gives the required solution.

Example: Suppose $n=19$. Then, $n=2(10)-1$, and thus $m=10,~2m=20$. The largest divisor of $20$ that is also a power of $2$ is $4$. Thus, $2^{x}=4$ or $x=2$. Solving $4(2y+1)=20$ gives $y=2$.


2D analog to Unit Quaternions for Rotation I have been working with 3D rotations for some time now, wth my preferred implementation being realised using unit quaternions - especially from a computational efficiency point of view by avoiding any trigonomtric operations (the target is typically a resource-constrained microcontroller, sometimes without an FPU).

I now have a problem where I need to operate only in 2D space, rotating by a single angle (or, more correctly, successive single rotations, and using the ersult to rotate vectors). Of course, I have the option of ordinary complex numbers, or a reduced quaternion set, keeping two of the complex terms at zero.

I'm guessing this isn't the first time someone has needed to tackle this problem.  So my questions are:

What would be the analog to unit quaternions in 2D space?  Does it have a name, and does it have similar properies to unit quaternions in 3D space? Is this simply a a "reduced set" of unit quaternions being a complex number with the angle encoded as $z = \cos(\theta/2) + j \sin(\theta/2)$?
What are the advantages and disadvantages - especially from a numerical error and computational efficincy point of view - of using this represenation vs a standard complex number represenation, i.e. $z = \cos(\theta) + j \sin(\theta)$?
Or, am I better off with a different rotation represenation altogether, given the goals stated above?

Bonus question: I'm guessing this is part of a more general field of mathematics.  What should I be looking at to find out more?

Quaternions with the restriction that you can only use a single rotation plane work just fine still. They would take the form

$$q = \cos \frac{\theta}{2} + v \sin \frac{\theta}{2}$$

for some unit quaternion $v$.

When we restrict ourselves to a single rotation plane, that means we consider rotating vectors (pure imaginary quaternions) that are perpendicular to the rotation axis (described by $v$).

It is not difficult to show that, for any vector $a \perp v$,

$$\exp(v \theta/2) a \exp(-v \theta/2) = \exp(v\theta) a = a \exp(-v \theta)$$

This is why complex rotations don't usually use the double-sided form that rotations in 3d use: it's simply unnecessary.

From a programming standpoint, the double-sided form requires more floating point operations; this is strictly unnecessary in 2d.

Of course, only the double-sided form of rotation generalizes beyond 3d.

With all this in mind, I think you can consider using quaternions with some terms zeroed out, but notice that when translating quaternions to 2d, the rotation axis is perpendicular to the vectors being rotated. This means you can't zero out particular components regardless of whether they're vectors being rotated or quaternions being used to rotate them.

Furthermore, I think the matter of ensuring some terms remain identically zero could be an issue. You might be better off converting to complex and then converting back when you're done.

What would be the analog to unit quaternions in 2D space?

These are the complex numbers.

  What are the advantages and disadvantages  of using this represenation vs a standard complex number represenation

If you compose rotations then you have to work in double not to loose precision.


Proving that a Sequence Approaches Infinity Using Lagrange's Theorem Let $f(x)$ be a differentiable function in $(0,\infty)$, so that $f'(x)>x$ for every $x>0$.

$(a_n)$  is the sequence defined recursively as

$$
a_1 = 1\\
a_{n+1}=f(1+a_n)-f(a_n)
$$

Q. Prove that

$$
\lim_{n\to\infty}a_n=\infty
$$

Using Lagrange's theorem, it's easy to show that for each interval $I_n=[a_n,a_n+1]$, there's some $c_n \in (a_n,a_n+1)$ so that

$$
f'(c_n) = \frac{f(1+a_n)-f(a_n)}{1+a_n-a_n} = f(1+a_n)-f(a_n)=a_{n+1}
$$

And by the the fact that $f'(x)>x$ for every $x>0$, we also know that

$$
a_{n+1}>c_n >a_n
$$

So, we've proved that $(a_n)$ is increasing and positve, but I cannot develop this further to prove that it is not bounded (to conclude it approaces infinity).

How can I prove this last step?

Note: I'm looking primarily for a solution without integrals. The question should be solveable with differential calculus alone - derivative, continuity, and limit of sequence.

For all $x$ you have $f'(x)-x >0$.

Then
$$0< \int_{a_n}^{a_n+1} [f'(x) -x] \mathrm dx = f(a_n+1)-f(a_n)-\frac{1}{2}((a_n+1)^2-a_n^2)=a_{n+1}-a_n-\frac{1}{2}$$
From this follows that
$$a_{n+1}>a_n + \frac{1}{2}$$
and this is enough to conclude that $a_n$ is unbounded.

After fiddling with this question for a while, I've arrived at the following solution, which does not require any further assumptions.

Suppose that $(a_n)$ is bounded. We've shown that it is monotone increasing and positive, so there exists some $L\in \mathbb{R}$ so that

$$
\sup{a_n} = \lim_{n \to \infty}a_n =L >0
$$

$f$ is differentiable in $\mathbb{R}$, and in particular continuous in $L$ and $L+1$, so

$$
\lim_{n \to \infty}{f(a_n+1)-f(a_n)} = f(L+1)-f(L)
$$

From the definition of $a_{n+1}$, we get

$$
L=\lim_{n \to \infty}{a_{n}} = \lim_{n \to \infty}{a_{n+1}} = \lim_{n \to \infty}{f(1+a_n)-f(a_n)} = f(L+1)-f(L)
$$

So

$$
(\star) \quad L = f(L+1)-f(L)
$$

Now, using Lagrange's theorem again with the interval $[L,L+1]$, we get that for some $t \in (L,L+1)$,

$$
f'(t) = \frac{f(L+1)-f(L)}{L+1-L} = f(L+1)-f(L) > t > L
$$

But from $(\star)$, we get

$$
L > L
$$

Which is a contradiction.


Two Klein Bottles Sewn Together? So, I'm pretty sure at least some of you know what a Klein Bottle is. If not, a Klein Bottle, named after German mathematician Felix Klein, is basically a shape that has one side and no edge. You basically would get this if you took 2 Mobius Loops and sew them together, which creates a shape(The Klein Bottle)that requires a 4-dimensional space to exist. Here's what I wonder though.

What would happen if you kept this going. What would 2 Klein Bottles create if you tried sewing them together? Is that even possible?

For each $n$, define the twisted $n$-sphere bundle to be the space
$$
S^n \times I / (x,0)\sim(\alpha_0^{(n+1)}(x),1)\,,
$$
where $I$ is the standard interval and $\alpha_0^{(n+1)}(x)$ flips the first coordinate of $x$ (considered as a point in $n+1$-dimensional space), leaving the others alone. In other words, we take a hollow $n$-cylinder and glue the ends together via $\alpha_0^{(n+1)}$. As examples:

The twisted $0$-sphere bundle is the boundary of the Möbius strip (a $0$-sphere is a pair of points, which are interchanged by the antipodal map).
The twisted $1$-sphere is the Klein bottle.

Define the twisted $n$-disk bundle to be the space
$$
D^n \times I/(x,0)\sim (\alpha_0^{(n)}(x),1)\,,
$$
where $D^n$ is the closed $n$-disk. As examples:

The twisted $1$-disk bundle is the Möbius strip (a $1$-disk is the same as the interval $I$).
The twisted $2$-disk bundle is called the solid Klein bottle. It is a three dimensional manifold whose boundary is the Klein bottle.

More generally, it is fairly intuitive to see that the boundary of the twisted $n+1$-disk bundle is the twisted $n$-sphere bundle.
Now what happens when we glue together two twisted $n$-disk bundles along their boundaries? Since the result of gluing together two $n$-disks along their boundaries is the $n$-sphere, we know that we have an $S^n$-bundle of some sort. Moreover, the gluing map at the boundary is given by $\alpha_0^{(n)}$ on each disk, so after gluing the two disks together (taking the gluing to take place in the $n+1$-th dimension), we see that the gluing on the boundary is precisely $\alpha_0^{(n+1)}$. In other words, when we glue together two twisted $n$-disk bundles along their boundaries, we get the twisted $n$-sphere bundle.
Putting all this together:

The twisted $0$-sphere bundle is the boundary of the Möbius strip (the twisted $1$-disk bundle).
Gluing two Möbius strips along their boundaries yields a twisted $1$-sphere bundle (a Klein bottle).
The Klein bottle is the boundary of the twisted $2$-disk bundle (the solid Klein bottle).
Gluing two solid Klein bottles along their boundaries yields a twisted $2$-sphere bundle.
The twisted $2$-sphere bundle is the boundary of the twisted $3$-disk bundle.
Gluing two twisted $3$-disk bundles along their boundaries yields a twisted $3$-sphere bundle...

... and so on.

all I can assume is that if this shape follows the same rules as other shapes and when you glue one side of a shape to an other identical shape both shapes loos one side and as a Klein bottle has only one side you would end up with a shape with no sides or edges.
In short gluing the surfaces of two Klein bottles together would create a shape with no edges, no sides, no corners and no volume. It`s only characteristics are that it is curved and looped.
I know I did not use any math to come up with my answer but I like it so pleas don`t delete it.


Factorization of conditional expectation I have to proof this. And I have no idea how to do it.

Let (X,U) and (Y,V) independent random vectors, s.t. X and Y are real valued r.v.s with finite expectations. Show that then:

E[X.Y|(U,V)]=E[X|U]E[Y|V]

I would really appreciate it, If any body could also give me an example for it that I would understand this better. Thank you.

Let's call the event $(U,V)=(H,K) $ as A, the event $U=H$ as B and the event $V=K$ as C, we have:

$E[XY|(U,V)=(H,K)]=E[XY|A]=\frac{E[XY \cdot 1_{A}]}{P(A)}=\frac{E[XY \cdot 1_B \cdot 1_C]}{P(B)P(C)}$ because $U,V$ are independent. Then because the two vectors are independent:

$\frac{E[XY \cdot 1_B \cdot 1_C]}{P(B)P(C)}=\frac{E[X \cdot 1_B ]E[Y \cdot 1_C]}{P(B)P(C)}=\frac{E[X \cdot 1_B ]}{P(B)}\frac{E[Y  \cdot 1_C]}{P(C)}=E[X|B]E[Y|C]=E[X|U=H]E[Y|V=K].$ $1_{A}(x)=1, \forall x \in A \; 1_{A}(x)=0, \forall x \notin A.$


Finding Locus of a Midpoint of a Chord Let $A$ and $B$ be points, and let $C$ be a point that varies on the open semicircle with diameter $AB$. Construct squares externally on sides $AC$ and $BC$, and let $D$ and $E$ be the centers of these squares, respectively. Find the locus of the midpoint $M$ of $DE$.

I found that the locus of $M$ is the upper half of the inscribed circle in the semicircle with $AB$ as the diameter, however, I am having trouble proving it, and proving that there are no other places where $M$ can exist. Can I have a hint as to how to prove it geometrically? Thanks!

Hints:

Let $O$ the midpoint of $AB$ and $Y$ the point where line $DC$ intercepts the circle$(O, OA)$.

Show that $C$ is a point of $DE$.
Show that $m(\angle AOY)=90 ^{\circ}$. Use the inscribed angle theorem.
Show that $m(\angle DMO)=90 ^{\circ}$.

So, if $Y$ and $O$ are fixed points and $OMY$ is a right-angled triangle, what comes after?

Hint:-

If we use $A$, $B$ as $(x_i,y_i)$ solution will become a bit complicated so you can try solving it by taking $A$ $(-1,0)$ and $B$ $(1,0)$.

Let the point $C$ be $(\cos x,\sin x)$.

For finding center of the square formed by joining $AC$, we will first have to find their mid point and shift it up by $\dfrac{AC}{2}$ on their $\perp$ bisector. Midpoint of $AC$ is $\left(\dfrac{\cos x-1}{2},\dfrac{\sin x}{2}\right)$, and by using distance form you can easily find the midpoint of the square and then you just have to eliminate $\sin, \cos$ by using $\sin^2x+cos^2x=0$.


Is $\frac{1}{\sqrt{2}}$ a fraction or not? Is $\frac{1}{\sqrt{2}}$ a fraction or not?

I just came across a Grade 8 student's class work where the teacher has given the above as an example to differentiate fractions from rational numbers. I think this is wrong fundamentally, as $\sqrt2$ is irrational while all fractions would be rational. Please advise. Thanks!

The word "fraction" is used outside of the scope of rational numbers as well. In that case, it's better not to use the term "fraction" to denote a kind of number, but rather to refer to the way of writing or representing it: i.e. as a structure with a numerator and a denominator.
Loosely speaking you could say "$\pi$ is not a fraction" because it cannot be written as a quotient of integers, but it's safer to say "$\pi$ is not a rational number" where you rely on a precise definition of rational number.

Generally, you want to be able to call anything of the form
$$\frac{a}{b}$$
a fraction because then you can refer to its two characterizing components: the numerator $a$ and the denominator $b$ with $a$ and $b$ not necessarily integers but any numbers or even more general expressions. Note that you can write any number $x$, not necessarily integer, as a fraction:
$$x = \frac{x}{1}$$but we generally don't refer to "$x$" as "a fraction". We do want to be able to call something like
$$\frac{1+\sqrt{3}}{1-\sqrt{3}}$$a fraction, although it's not a rational number, because then we can say things such as "multiply numerator and denominator with $1+\sqrt{3}$". The same goes for more complicated expressions (with fractions in fractions!), or even with one or more variables, such as:
$$\frac{e^2 - \frac{\sqrt{5}}{1+\sin\frac{\pi}{7}}}{1-\frac{\sqrt{3}}{2}} \quad ; \quad \frac{e^x-\sin y}{x^2+y}$$

Summarizing:

Is $\frac{1}{\sqrt{2}}$ a fraction or not?

I think we prefer to be able to call this a fraction, with numerator $1$ and denominator $\sqrt{2}$, but then obviously we shouldn't mix "fraction" with "rational number" or use them interchangeably.

"Fraction" just means "not a whole number."  For instance, irrational numbers can be written as "decimal fractions", like $\pi = 3.14159\ldots.$  If you had said "rational numbers" instead of "fractions", you'd be right.


How can a set contain itself? In Russell's famous paradox ("Does the set of all sets which do not contain themselves contain itself?") he obviously makes the assumption that a set can contain itself. I do not understand how this should be possible and therefore my answer to Russell's question would simply be "No, because a set cannot contain itself in the first place."

How can a set be exactly the same set as the one that contains it? To me it seems unavoidable that the containing set will always have one more additional level of depth compared to all the sets which it contains, just like those russian matryoshka-dolls where every doll contains at least one more doll than all the dolls inside it.

Of course one can define something like "the set of all sets with at least one element" which of course would include a lot of sets and therefore by definition should also include itself, but does it necessarily need to include itself just because its definition demands so? To me this only seems to prove that it's possible to define something that cannot exist beyond its pure definition.

Yes, this is an issue.

Naively, this issue cannot be dealt with, and we'll get to that in a moment. But in 1917 mathematicians already noticed that "normal sets" do not contain themselves, and in fact have an even stronger property. Namely, there are no infinite decreasing chains in $\in$, so not only that $a\notin a$ it is also true that $a\notin b$ whenever $b\in a$, and that $a\notin c$ whenever for some $b\in a$ we have $c\in b$; and more generally there is no sequence $x_n$ such that $x_{n+1}\in x_n$ for all $n$.

This is exactly what the axiom of regularity came to formalize. It says that the membership relation is well-founded, which assuming the axiom of choice, is equivalent to saying that there are no decreasing chains. In particular $A\notin A$, for any set $A$.

But we know, nowadays, that it is consistent relative to the other axioms of modern set theory (read: $\sf ZFC$) that there are sets which include themselves, namely $x\in x$. We can even go as far as having $x=\{x\}$. You can even arrange for infinitely many sets of the form $x=\{x\}$.

This shows that naively we cannot prove nor disprove that sets which contain themselves exist. Because naive set theory has no formal axioms, and is usually taken as a subset of axioms which include very little from $\sf ZFC$ in terms of axioms, and certainly it does not include the axiom of regularity.

But it also tells us that we cannot point out at a set which includes itself, if we do not assume the axiom of regularity. Since these sets cannot be defined in a nontrivial way. They may exist and may not exist, depending on the universe of sets we are in. But we do know that in order to do naive set theory and even more, we can safely assume that this situation never occurs.

A non expert reflection.

Russell did not make the assumption that a set could contain itself. Of technically reasons he elaborated with a construction "of all sets that not is a member of itself". Because with this technique he could prove that something was wrong in the previous notations of sets, especially with some ideas of Frege.

There is no canonical or categorical set theory and it's certainly possible to define a set theory where certain sets contain themselves as elements, even though axiomatic set theories use to pay attention to find out axioms to prohibit this. In no set theory it's wrong to claim that 'x do not belong to x'. And you can claim that without having to claim that there are sets that belongs to themselves.

There are no sets i nature other than groupings in human mind, so there are no real objects to  model. In my mind a set is some objects with identity, thought of as surrounded by a fence. The objects could be inside or outside the fence. But this is a very naive picture that at most works for finite sets. And of course, in my definition a set could not contain itself.

But mathematicians are free to define whatever they manage to define and there are persons interested in set-like objects that isn't prohibited to contain them self.

In my opinion the problems in set theory emanates from unrestricted use of the word "all" and not from modelling of sets as such.


Pseudo-inverse Alternative Forms In the book Convex Optimization by Stephen Boyd on page 649, the pseudo-inverse is defined as:

$A^{\dagger}=V\Sigma^{-1}U^T$

this is the SVD decomposition.

After that it says alternative forms are:

$A^{\dagger}=\lim_{\epsilon \to 0}(A^TA+\epsilon I)^{-1}A^T = \lim_{\epsilon \to 0}A^T(A^TA+\epsilon I)^{-1}$

How are these two equations obtained?
Also why is the inverse equal to:
$A^{\dagger} = A^T(A^TA)^{-1}$ when the system is under-determined that is the rank is the number of rows and columns > rows.

Let $Ax=b$, $A\in\mathbb{R}^{m\times n}$. If A is over-determined, so that the number of linearly independent rows is equal to the number of columns then the $\textit{normal equations}$ read $A^TAx=A^Tb$. $A^TA$ is invertible by the rank condition on $A$, thus $x=(A^TA)^{-1}A^Tb$. This motivates the choice to call $A^\dagger$ a pseudo-inverse of $A$.

Now to show that the above formula agrees with the one given in Boyd, let $A=U\Sigma V^{T}$ be the SVD of $A$. Then $A^T=V\Sigma U^T$ and $(A^{T}A+\epsilon I)^{-1}=(V^T(\Sigma+\epsilon I) V)^{-1}$. Multiplying and taking the limit of the resulting expression product results in the above formula.

The formula in the second question is incorrect (check Boyd, it should read $A^{\dagger} = A^T(AA^T)^{-1}$).


Test for convergence: I'm studying a chapter of my Analysis book, it's on convergence and divergence tests for series. The chapter concludes with some series to test, and these are the few I am having problem with:

Test for convergence:
$$\sum \frac{\ln{k}}{k^2}$$
$$\sum (\sqrt[k]{k}-1)$$
$$\sum \frac{k!}{k^k}$$

Now for the first series. It's obvious to by writing out terms that $\ln{k}\le \sqrt{k}$ and that the comparison test therefore yields that the given series converges. However I am failing to prove the $\ln{k}\le \sqrt{k}$ without using derivatives and other calculus-related methods, and I'm interested in a rather neat way of proving the given series converges.

For the second one.. It's clear that $\sqrt[k]{k}$ goes to $1$ as $k$ get's really large, (I've proven that in an earlier chapter), but I'm not sure how to test this series.

The third series seems to converge when I write out the first terms. I notice that the terms are less or equal than those of $\sum \frac{1}{2^k}$, which I know converges. However here again I'm having trouble proving these inequalities (at least in a neat way).

Herein, we show using non-calculus based tools that $\log(k)\le \sqrt{k}$ for all integer $k\ge 1$.  We begin with a primer on an elementary inequalities for the logarithm and exponential functions.

  PRIMER:

  In THIS ANSWER, I showed using only the limit definition of the exponential function and Bernoulli's Inequality that the logarithm and exponential functions satisfy the inequalities

  $$\frac{x-1}{x}\le \log(x)\le x-1\tag1$$

  for $x>0$

  and

  $$1+x\le e^x\le \frac{1}{1-x} \tag 2$$

  for $x<1$.

PROBLEM $(1)$:

Let $f(x)=\frac x2-\log(x)$.  Then, using $(1)$ we find for $h>0$ that

$$\begin{align}
f(x+h)-f(x)&=\frac h2-\log\left(1+\frac hx\right)\\\\
&\ge \frac h2-\frac hx\\\\
&\ge 0
\end{align}$$

for all $x\ge 2$.  So, $f(x)$ is monotone increasing for $x\ge 2$. And since $f(2)=1-\log(2)>0$ we have

$$\log(x)<x/2 \tag 3$$

for $x\ge 2$.

Now, setting $x= \sqrt{k}$ in $(3)$ reveals

$$\log(k)\le \sqrt k$$

for $k\ge 4$.

We also have from $(1)$, that $\log(x)\le 2(\sqrt x-1)$.  When $x\le 4$, we see that $2(\sqrt x-1)\le \sqrt x$.

Hence, for all $x>0$, we find that $\log(x)\le \sqrt x$.  Certainly then for all integer $k\ge 1$, $\log(k)\le \sqrt{k}$ as was to be shown!

PROBLEM $(2)$:

We can write $k^{1/k}=e^{\frac1k \log(k)}$.  Using the left-hand side inequality in $(2)$ reveals

$$k^{1/k}-1\ge \frac{\log(k)}{k}>\frac{1}{k}$$

for $k\ge 3$.  The series $\sum_{k=1}^\infty (k^{1/k}-1)$ diverges by comparison with the harmonic series.

PROBLEM $(3)$

Note that we can write

$$ \frac{k!}{k^k} =\frac{1\cdot 2\cdot 3\cdots k}{k\cdot k\cdot k\cdots k}\le \frac 2{k^2}$$

The series converges by comparison with the series $\sum_{k=1}^\infty \frac{1}{k^2}$.

Why downvoting. it is correct .

Hint  for he first
$x\mapsto \ln(x)-\sqrt{x}$ is decreasing $\implies \ln(x)\leq \sqrt{x}$  for large enough $x$.

we have

$$\lim_{k\to+\infty}k^{\frac{3}{2}}\frac{\ln(k)}{k^2}=0$$

since the power grows quickly than logarithm.

$$\implies k^{\frac{3}{2}}\frac{\ln(k)}{k^2}\leq 1$$ for large enough $k$.

$$\implies \frac{\ln(k)}{k^2}\leq \frac{1}{k^{\frac{3}{2}}}$$

and you can conclude.

  for the second

$$\sqrt[k]{k}-1=e^{\frac{\ln(k)}{k}}-1\sim \frac{\ln(k)}{k}\;\;(k\to+\infty)$$

use the integral comparison test.


Is a sinusoidal signal the only one not distorted by an LTI system? In a signals and systems class in engineering school, I was shown a proof that a sinusoidal signal goes through a linear time-invariant (LTI) system undistorted; its shape and frequency are not changed - only its amplitude and phase (potentially) are.

In other words, if the input is of the form $v_i = V\sin\left(\omega t + \phi\right)$, then in general the output is of the form $v_o = V^{\prime}\sin\left(\omega t + \phi^\prime\right)$.

This was an "aha! moment" for me in understanding the usefulness and power of the Fourier series/transform.

Now I wonder, however, is a sinusoidal signal the only type of (periodic) signal that goes through an LTI system undistorted?

If so, I would love to be directed to a proof, and to hear any insight about why this is so.
If not, is it possible to define a
new transform based on the alternative kernel?

Complex exponential function $x(t)=e^{i\omega_0 t}$ is the eigenfunction of an LTI system. That is, the output of an LTI system to this input is an scaled version of it. The scaling factor is the system function when evaluated at $\omega_0$. That is:
$$y(t)=H(\omega_0)e^{i\omega_0t} \tag{1}$$
The proof is not so difficult. Just substitute the input $x(t)=e^{i\omega_0 t}$ in the differential equation that describes the system, take the Fourier transform, and then simplify. Note that the given equation in the question is also derived from $(1)$.

The eigenvalues and eigenfunctions of LTI systems are given by the Laplace transform

In the continuous case :
not only the sines but also any exponential. With an input $f(t) = e^{s t}$ where $s  \in \mathbb{C}$ the ouput of your LTI system is
$$f \ast h(t) = \int_{-\infty}^\infty e^{s (t-\tau)}h(\tau)d\tau = H(s) e^{st}$$
where $H(s)=\int_{-\infty}^\infty h(t) e^{-st}dt$ is the (bilateral) Laplace transform of the impulse response $h(t)$.
In the discrete case :
not only the sines but also any discrete exponential. With an input $f(n) = z^n$ where $z  \in \mathbb{C}$ the ouput is
$$f \ast h(n) = \sum_{n=-\infty}^\infty z^{n-m}h(m) = H(z) z^n$$
where $H(z)=\sum_{-\infty}^\infty h(n)z^{-n}$ is the Z-transform of the impulse response $h(n)$.

And the only other eigenfunctions are the linear combination of such, if associated to the same eigenvalue $H(s),H(z)$.

Now in the context of signal processing, you'll accept slight modifications of the input signal (some sort of approximate eigenfunctions). Studying those is the purpose of filters theory, one of the most important problem being the approximation of the ideal low-pass filter.


Can existence of pure Nash strategies simplify discovery of mixed ones? Let's say I'm interested in two player games.

I'm aware of the complexities of finding mixed Nash equilibria. To really be sure we've found all we have to enumerate all possible combinations of row and column strategies and check for indifference (ignoring other simple tricks).

Although, let's assume some pure Nash equilibria exist. Does this say anything about mixed ones?

If pure strategies do exist can my search for mixed strategies include only those that contain at least one of the strategies from the pure Nash equilibrium in their support?

The answer is no, that is, if you have a $2$-player game with NE in pure strategies, not necessarily you can rely on the fact that the actions that are in the pure NE are also in the support of the mixed NE.

Here there is an example,

where the actions of the Row player are Top, Middle, Down,
and the actions of the Column player are Left, Center, Right.

$$\begin{bmatrix}
 1,1 & 0,0 & 0,0 \\
        0,0 & 1,-1 & -1,1 \\
        0,0 & -1,1 & 1,-1 \\
\end{bmatrix}$$

[Notice that this is really like matching pennies, with the addition of the first row/column.]

There is one pure strategy NE, given by $(T, L)$, and a mixed strategy NE where players equally randomize between Middle/Down and Center/Right, much in the same spirit of matching pennies, and there is neither $T$ nor $L$ in the support of this mixed strategy NE equilibrium.

If pure Nash equilibria exists, it can be the case that there is no strictly mixed one: for example, consider a simple game where two players call an integer in range $0,\cdots,n$ independently, with the result $a-b$, where the first player called $a$ and tries to maximize the result and the second called $b$ and tries to minimize. It is obvious that for the first the most beneficial option is to call $n$, and for the second - $0$, independently of the choice of other. Thus this pure strategy pair is the only Nash equilibria.

We can also consider a vacuous game, where the players have many options, but the result score is always the same for both. Then we have all possible pure and mixed strategy pairs as Nash equilibria, which have no connections with each other at all.


Finding what the sum of $(2^n)(3^{(-n+1)})$ from $n=1$ to infinity converges to Sorry for the lack of math symbols but I'm trying to find what the sum of
$f(x)=(2^n)(3^{-n+1})$ from $n=1$ to infinity converges to. I have tried using the sequence of partial sums but I'm too stupid to find what Sn is equal to in order to take the limit. Any help would be greatly appreciated.

Define $$S=\sum_{n=1}^{\infty}2^n\cdot3^{-n+1}.$$

Observe that $$S=\sum_{n=1}^{\infty}2^n\cdot3^{-n+1}=-2^0\cdot3^{-0+1}+\sum_{n=0}^{\infty}2^n\cdot3^{-n+1}=-3+\underbrace{\sum_{n=0}^{\infty}2^n\cdot3^{-n+1}}_{:=S_0}.$$
Rewrite the summand:
$$S_0=3\sum_{n=0}^{\infty} \frac{2^n}{3^{n}}=3\sum_{n=0}^{\infty} \left(\frac{2}{3}\right)^n.$$
By the geometric series this equal to $$\frac{3}{1-\frac{2}{3}}=9.$$ Since
$S=S_0-3$, the final answer is $S=6$.


For a countably infinite dimensional vector space, the localisation of $A= End_k(V)$ at surjective endomorphisms is the zero ring If $k$ is a field and $V$ a countably infinite dimensional vector space, let $A = End_k(V)$ and $S = \{ s \in A : s \text{ is surjective} \}$. I am trying to show that $S^{-1}A$ is the zero ring.
I have shown that $S$ is multiplicatively closed.

It seems to me that $A$ can be considered as infinite matrices where the columns eventually have only zero entries.

1.) Is this right?

Assuming this, it seems to me then that in much the same way for the finite dimensional case for a fixed $s \in S$, for any $a \in A$ we can find a $b \in A$ so that $sb=a$

2.) Is this true?

It then follows that for any $s^{-1}a \in S^{-1}A$, $s^{-1}a = b$ and further, there exists $s’ \in S$ such that $s’a = s$, so $s^{-1}a = s’^{-1}$.

Now my formal definition of $S^{-1}A$ is:
$$\frac{A\langle i_s : s \in S \rangle}{\langle si_s - 1, 1 - i_ss \rangle} $$

And I have shown that any $i_sa = i_{s’}$ - a formal symbol, AND $i_sa = b\in A$. Which shows $S^{-1}A=0$ ?

The answers to your questions (1) and (2) are yes, but your subsequent arguments have some errors.  In particular, it is not true that there exists $s'\in S$ such that $s'a=s$ (consider what happens if if the kernel of $a$ is not contained in the kernel of $s$).  And in any case, nothing you have written would prove that $S^{-1}A=0$.  (Notably, as far as I can tell you have never used the assumption that $V$ is infinite-dimensional, so your argument, if it were valid, would work when $V$ is finite-dimensional.  But the conclusion is false in that case, since all surjections are already invertible $S^{-1}A=A$.)

Here is the direction you want to be thinking here.  Suppose you have a surjection $s\in S$ with kernel $W\subset V$ and $a\in A$ has image contained in $W$.  Then $sa=0$, so in $S^{-1}A$, $a$ becomes $0$.  So there are a lot of elements of $A$ that become $0$ in $S^{-1}A$.  If you could use this line of argument to eventually show that the unit element $1\in A$ becomes $0$ in $S^{-1}A$, then you could conclude that $S^{-1}A=0$.

Attempt number two following the very generous hint in previous answer:

$E_{ii} \in A$ has image in $\{(0, ..., 0, a_i, 0, ...) : a_i \in k\}$.

Then letting $s_i \in S$ be the map $(a_1, a_2, ....) \mapsto (a_{i+1}, a_{i+2}, ...)$ we see that $sE_{ii} = 0$ and so $E_{ii} = 0$ and hence $I = \sum_i E_{ii}$ is zero in $S^{-1}A$ and we’re done?


Bijection between $\mathbb{R}$ and $\mathcal{C}_0(\mathbb{R})$ It's possible to prove that $\mathcal{C}_0(\mathbb{R})$ (continuous function from $\mathbb{R}$ to $\mathbb{R}$)  and $\mathbb{R}$ have that same cardinality ('cause of you only have to choose the image for $\mathbb{Q}$).

But what's an explicit bijection?

Using Schroeder-Bernstein, you have that there are at least $|\mathbb R|$ continuous functions--the constant functions-- and there are at most $|\mathbb R^{\mathbb Q}|=|\mathbb R|$ functions; this last is the cardinality of the Real functions defined on the rationals , since not all functions defined on the dense subset of the rationals into the Realsextend (e.g., $f(x)= \frac {1}{(x-\ (2)^{1/2})})$ does not extend) into a continuous function from the Reals to themselves. I think Schroeder-Bernstein has an algorithm for producing a bijection.

Since $\mathcal{C}_0$ contains continuous functions, each function can uniquely express as a Taylor Series which is a polynomial of infinity degrees. You put all the coefficients of this polynomial together with the constant term and you can create an ordered sequence which is unique. eg, for $f(x)=\sin(x)$, you can express as $f(x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}...=x-\frac16x^3+\frac1{120}x^5...$. Then the sequence you create is $<0,1,0,-\frac16,0,\frac1{120},......>$

Let $\mathcal S$ be the set of all these function, then $\mathcal C_0=\mathcal S\preceq\mathbb R^{\mathbb N}=\mathbb R$. Of course $\mathbb R\preceq \mathcal C_0$ since for each real number, there is a constant function for it. Then by Schroeder Bernstein Thm, $\mathbb R\sim \mathcal C_0$


Prove/disprove $(\int_0^{2 \pi} \!\!\cos f(x) \, d x)^2+(\int_0^{2 \pi}\!\!\! \sqrt{(f'(x))^2+\sin ^2 f(x)} \, dx)^2\ge 4\pi^2$ Let $f(x)$ be a differentiable function on $[0,2\pi]$ s.t. $0\leq f(x)\leq 2\pi$ and $f(0)=f(2\pi)$. Prove or disprove that
$$
\left(\int_0^{2 \pi} \cos f(x) \,d x\right)^2+\left(\int_0^{2 \pi} \sqrt{(f'(x))^2+\sin^2 f(x)} \, d x\right)^2 \geq(2 \pi)^2
$$

It seems that when $f$ is an arbitrary constant, the left side equals $(2\pi)^2$ and seems to be the minimum. But how can I show that there's no other $f$ that makes the left side equal (or be less than) $(2\pi)^2$?

A geometric interpretation of the inequality has been found: Consider a closed curve on a sphere: $C=\{(\cos x\cdot\sin f(x),\,\sin x\cdot\sin f(x),\,\cos f(x))\mid x\in[0,2\pi)\}$, we have its perimeter $\displaystyle L=\int_0^{2\pi}\sqrt{(f'(x))^2+\sin^2 f(x)}\,dx$ and its area $\displaystyle S=2\pi-\int_0^{2\pi}\cos f(x)\,dx$. From spherical isoperimetric inequality $L^2\ge S(4\pi-S)$, we have $(2\pi-S)^2+L^2\ge(2\pi)^2$, and the equality holds iff $C$ is any circle on the sphere. In this way we get the original inequality in the sense of geometry.
Now the question is, how to prove the inequality with only pure analysis methods?

<This is not an answer!! This is just some of my thoughts, and also I am not good at English. If there are any things to fix, please be my guest.>

Prediction: For two functions $A(x)$ and $B(x)$, $$(\int_{\alpha}^{\beta} A(x) dx)^2+(\int_{\alpha}^{\beta} B(x) dx)^2 \geq (\int_{\alpha}^{\beta} \sqrt{A(x)^2+B(x)^2} dx)^2 $$
holds.

If this is true(which I am not able to prove...), the problem can be solved easily.
Let $A(x)=\cos f(x)$ and $B(x)=\sqrt{{f'(x)}^2+\sin^2 f(x)}$, and $\alpha=0, \beta=2\pi$.
Then, by the Prediction, $$(\int_{0}^{2\pi} \cos f(x) dx)^2+(\int_{0}^{2\pi} \sqrt{(f'(x))^2+\sin^2 f(x)} dx)^2\geq (\int_{0}^{2\pi} \sqrt{(f'(x))^2+1}  dx)^2 $$
We know that the right hand side is the form of the length of a curve $f(x)$.
As $y=f(x)$ satisfies $f(0)=f(2\pi)$, the shortest length of the curve $y=f(x)$ in the interval $[0, 2\pi]$ would be just a simple line connecting $(0, f(0))$ and $(2\pi, f(2\pi)=f(0))$, so the length will be just the x-coordinate difference, which is $2\pi$. Therefore, the RHS will have the minimum of $(2\pi)^2=4\pi^2$, and the problem is solved.
However, I couldn't think of a sharp way to prove this Prediction, or even it is true at all. I managed to think of the integrals as sequences, and tried solving this.
$$(\sum_{k=0}^{n} a_k)^2+(\sum_{k=0}^{n} b_k)^2 \geq (\sum_{k=0}^{n} \sqrt{(a_k)^2+(b_k)^2})^2$$
I think this equation can be solved by mathematical induction, but I am not sure.

Maybe I am simplifying this too much, but if f(x) is not constant, then $$\sqrt{(f'(x))^2 + (\sin f(x))^2} > |\sin f(x)|$$ because $$f'(x) \neq 0$$ for some value(s) in the interval of integration. This leads to the following:
$$\left(\int_0^{2\pi} \cos f(x) \: dx \right)^2 + \left( \int_0^{2\pi} \sqrt{(f'(x))^2 + \sin^2 f(x)} \: dx \right)^2 $$
$$ \geq \left(\int_0^{2\pi} \cos f(x) \: dx \right)^2 + \left( \int_0^{2\pi} \sqrt{\sin^2 f(x))^2} \: dx \right)^2 = (2 \pi)^2$$


Show that $x=2\ln(3x-2)$ can be written as $x=\frac{1}{3}(e^{x/2}+2)$ Show that $x=2\ln(3x-2)$ can be written as $x=\dfrac{1}{3}(e^{x/2}+2)$.

Is there a rule for this?

exponential function is injective, so $x = y$ iff $e^x = e^y$. use this fact and then some elementary symbol manipulations should give you the desired result (if it's true of course)


Find the mgf and E(x) of exponential family $P(X=x)=\frac{f(x)n^x}{g(n)}$ where $g(n)=\sum^\infty_{x=0}f(x)n^x$ I have to prove this is in the exponential family and find the mgf and $E(x)$

So I have that it is in the exponential family because

$I(x)_{0,1,2,...}\frac{f(x)}{\sum^\infty_{x=0}f(x)}=h(x)$,

$c(n)=1$,

$\sum^\infty_{x=0}exp([1-x]log(n))$ where $\sum^\infty_{x=0}exp([1-x]$ and $\sum^\infty_{x=0}exp(log(n))$ are the two parts to the exponential.

$I(x)_{0,1,2,...}\frac{f(x)}{\sum^\infty_{x=0}f(x)}*1*\sum^\infty_{x=0}exp([1-x]*log(n))$

I am not sure how to simplify the equation when taking the sum with $e^{tx}$ is put into the function.

$\sum^\infty_{x=0} e^{tx}I(x)_{0,1,2,...}\frac{f(x)}{\sum^\infty_{x=0}f(x)}*1*\sum^\infty_{x=0}exp([1-x]*log(n))$

$\sum_{x=0}^\infty \frac{f(x)(ne^t)^x}{g(n)}$

I dont know where to go from here.

When finding the mgf, does my sum on the inside cancel the sum on the top?

Note that

$$\sum_{k=0}^{\infty} f(k) n^k = \sum_{x=0}^{\infty} f(x) n^x$$

A distribution $g(x;n)$ belongs to an exponential family if it can be represented in the form:

$$g(x;n)=\nu(x)\exp[\xi(n)T(x)-S(n)]$$

We have

$$g(x;n) = P(X = x; n) = f(x) \exp[\ln(n) x -\ln[\sum_{k=0}^{\infty} f(k) n^k]]$$

$$E[X] = \sum_{j=0}^{\infty} j P(X = j; n) = \sum_{j=0}^{\infty} j[f(j) \exp[\ln(n) j -\ln[\sum_{k=0}^{\infty} f(k) n^k]]]$$

or

$$E[X] = \sum_{j=0}^{\infty} P(X \ge j; n)$$

where

$$P(X \ge j; n) =\sum_{m=j}^{\infty} f(m) \exp[\ln(n) m -\ln[\sum_{k=0}^{\infty} f(k) n^k]]$$

///ly, we have

$$E[e^{tX}] = \sum_{j=0}^{\infty} e^{tj} P(X = j; n) = \sum_{j=0}^{\infty} f(j) \exp[\ln(n) j -\ln[\sum_{k=0}^{\infty} f(k) n^k]]$$


Finding the minimum of $\frac pq + \frac rs$ for distinct integers $p, q, r, s$ from $\{1,2,3,4,5,\ldots,16,17\}$ Here is the question:

  Four distinct integers $p$, $q$, $r$ and $s$ are chosen from the set $\{1, 2, 3, 4, 5, \ldots, 16, 17\}$. The minimum possible value of $\frac pq + \frac rs$ can be written as $\frac ab$, where $a$ and $b$ are positive, co-prime integers. What is the value of $a+b$?

I got the answer as $321$. I took the numbers as $\frac pq$ as $\frac 1{16}$ and $\frac rs$ as $\frac 2{17}$ and added them to get $\frac ab = \frac{49}{272}$. Well I first took $\frac pq$ and $\frac rs$ as $\frac 1{17}$ and $\frac 2{16}$ respectively.

So without calculating both the results I wouldn't have got the answer. So can you help me by giving the way to get the answer?

Obviously, we want the minimum, so as small $p,r$ as possible, and as large $q,s$ as possible. There are 2 choices:

$1/17+2/16=50/(16\cdot17)$ and $1/16+2/17=49/(16\cdot17)$. The second one is smaller, the fraction is $a/b=49/272$ and hence $a+b=321$.

I don't know what other answer you want. In general case of choosing from $\{1,2,\dotsc,n\}$ you will get $a+b=(n+2(n-1))+(n(n-1))=n^2+2n-2$, the reasoning is the same.

p/q + r/s = (p.s + r.q)/q.s

to gain smallest value, denominator q.s must be bigest, there are 16 and 17 for q and s
and nominator must be smallest, p.17 + r.16, so p=1 and r=2

(1.17 + 2.16) / 16.17 = 49/272 a+b=321


Two dimensional integral involving Dirac delta It seems to me that
$$
\int_{-\infty}^\infty \int_{-\infty}^{\infty} \delta(x^2 + y^2 - R^2) dx dy
$$
should evaluate to $2\pi R$, the perimeter of a circle of radius $R$, but I'm having trouble getting this answer. I tried using the identity
$$
\delta(x^2 + y^2 - R^2) = \frac{1}{2\sqrt{R^2 - y^2}}\left[\delta\left(x - \sqrt{R^2 - y^2}\right) + \delta\left(x + \sqrt{R^2 - y^2} \right)\right]
$$
But it wasn't clear to me how to evaluate the $x$ integral after making this substitution.

How do you evaluate the above integral? Does the integral represent the perimeter of a circle of radius $R$? If not, how should such an integral be written?

Keep in mind the dirac delta is not a function, but rather a distribution. In fact, its precise definition (in this case) is that for all test functions $f(x,y)$,
$$
\int_{\mathbb R^2}f(x,y)\delta(x^2+y^2-R^2)\ dx\ dy :=\int_{\theta=0}^{2\pi}f(R\cos\theta,R\sin\theta)\ d(R\theta).
$$
The left side has no independent meaning - it is defined to equal the right side.

In your case, take $f(x,y)$ to be the constant $1$ function and you get your answer.

EDIT: After the discussion in the comments, I see this question really boils down to asking

  What is a precise definition of $\delta(g(x,y))$?

More generally, one may ask for the definition of $\delta(g)$ where $\delta$ is the $n$-dimensional delta function and $g\colon \mathbb R^n\to \mathbb R^n$ is a smooth function. And the answer turns out to be that there is no such definition that has all the desired properties in general, even for $n=1$. An explicit counterexample is furnished in Remark 2 of these notes by Terry Tao.

Delta functions are just shorthand notation to restricting integration to a lower dimensional region (in this case, a circle). Delta function only makes real sense inside an integral, and has its own rules for changing variables.

In this case, just change variables to polar coordinates (not forgetting the Jacobian):

$$\int_{-\infty}^\infty\int_{-\infty}^\infty \delta(x^2+y^2-R^2)dx\,dy=
\int_0^{2\pi}\int_0^\infty \delta(r^2-R^2)r\,dr\,d\phi$$
The $\phi$ integral is trivial:
$$\color{red}{=2\pi\int_0^\infty \delta(r^2-R^2)r\, dr }$$

Consider now the defining property of the delta function that says it just evaluates the function at its peak position:

$$\int f(x)\delta(x-x_0)dx=f(x_0)$$

The other important part is the variable substitution rule:

$$\delta(g(x))=|g'(x_0)|^{-1}\delta(x-x_0)$$
where $x_0$ is the zero of $g(x)$.

In our case, $g(r)=r^2-R^2=(r-R)(r+R)$ has a zero at $r=R$ (the negative one is outside the integration range). We have $g'(R)=2R$. So, the above integral in $\color{red}{\text{red}}$ can be transformed into

$$=2\pi\int_0^\infty \frac{1}{2R}\delta(r-R)r\, dr=\pi$$

where we took into account that this delta function just evaluates the function $\frac{r}{2R}$ at $r=R$.

Notice that it is extremely important that the argument of the delta function is not $\sqrt{x^2+y^2}-R=r-R$ but $x^2+y^2-R^2=r^2-R^2$.

Another way of looking at this is to start from the red integral again, but change variables to $r^2=u$.

$$2\pi\int_0^\infty \delta(r^2-R^2)r\, dr=
2\pi\int_0^\infty \delta(u-R^2)\frac{du}{2}=\pi
$$
where the delta function now just evaluated function $\frac{1}{2}$ at $u=R^2$ which doesn't matter because the function was just a constant.

The moral of the story: it's not just important where the zero of the delta function's argument is, you have to take into account the functional form (especially the derivative). Stretched delta isn't the same as delta even if the peak is at the same place. If you imagine it as a narrow and tall Gaussian peak, you can see that stretching the function by changing variables changes its area.

You could also write your delta function as $$\delta(r^2-R^2)=\delta((r-R)(r+R))\equiv \delta(2R(r-R))\neq \delta(r-R)$$ where I took into account that the pre-factor $r+R$ is only important where $r=R$, so I put that in.


How does the binomial expansion helps understanding graph connectedness? I read this post about graph connectedness and adjacency matrix. But I do not understand how the last comment about using the binomial expansion would help. I know this approach is correct, but just do not fully grasp it.

Would you mind to elaborate a little bit more? I did the binomial expansion and got $\binom{n-1}{0}A^{0}+\binom{n-1}{1}A^{1}+.....+\binom{n-1}{n-1}A^{n-1}$ which is a linear combination of all the As. but I still don't know how this helps.

What is the matrix $A^k$? It is the matrix that will have entry $i,j$ non-zero (strictly positive) if, and only if, there exists a path of length exactly $k$ between nodes $i$ and $j$.

Now, the graph is connected iff there is a path of length at most $n-1$ between every nodes $i,j$. So using the binomial expansion, $II+A)^{n-1}$ will have entry $i,j$ non-zero iff there exists a path of length $1$, or $2$, or [...], or $n-1$ between nodes $i$ and $j$.

Indeed, $$(I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} A^k$$
so for any $1\leq i,j\leq n$,
$$\begin{align}
\left( (I+A)^{n-1} \right)_{ij} &= \sum_{k=0}^{n-1} \binom{n-1}{k} \left(A^k\right)_{ij}\\
&= \binom{n-1}{0} \left(A^0\right)_{ij}
+ \binom{n-1}{1} \left(A^0\right)_{ij} + \dots + \binom{n-1}{n-1} \left(A^{n-1}\right)_{ij}\\
&= \sum_{k=0}^{n-1} \binom{n-1}{k}\cdot \text{(number of paths between $i$ and $j$ of length exactly $k$)}
\end{align}$$
which is zero if, and only if, there is no path of length at most $n-1$ between $i$ and $j$, which is equivalent to not having any path at all between $i$ and $j$.

Side note: this expansion does not tell you how many such path there are, sadly. That is, there is no (as far as I know, at least) direct correspondence between the entry $\left( (I+A)^{n-1} \right)_{ij}$ (which is an integer) and the number of paths between $i,j\in[n]$ in the graph $G$ (whose adjacency matrix is $A$), because of the binomial coefficients which weigh each summand.

As far as I understand $$(I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}k A^k$$
Only shows how to calculate $(I+A)^{n-1}$ and there is no some extra meaning in such expansion.


Calculate how many ways to get change of 78 I been asked to calculate how many ways there are to get change of 78 cents with the coins of 25,10,5,1.

I been able to write this down:

$25a + 10b + 5c + d = 78$

But I do not know how to continue. Can you help me please?

It's the same as the coefficient of $x^{78}$ in $$(x^3+x^8+x^{13}+\cdots+x^{78})(1+x^5+x^{10}+\cdots+x^{75})(1+x^{10}+x^{20}+\cdots+x^{70})(1+x^{25}+x^{50}+x^{75})$$ That doesn't help you much by hand, but it gives you something concrete to enter into a CAS if that helps.

Consider the product in alex.jordan's answer. The product of the last two factors is
$$1 + x^{10} + x^{20} + x^{25} + x^{30} + x^{35} + x^{40} + x^{45} + 2 x^{50} + x^{55}
+ 2 x^{60} +  x^{65} + 2 x^{70} + 2 x^{75} + \ldots)$$
The product of the first two is
$$ 1 + \ldots + x^4 + 2 (x^5 + \ldots + x^9) + 3 (x^{10}+\ldots+x^{14}) + \ldots
+ 16 (x^{75}+\ldots+x^{79})+\ldots$$
So the coefficient of $x^{78}$ is
$$ \eqalign{ 16 & \text{ for } 1 \times 16 x^{78}\cr
+ 14 & \text{ for } x^{10} \times 14 x^{68}\cr
+ 12 & \text{ for } x^{20} \times 12 x^{58}\cr
+ \ldots\cr
+ 2 & \text{ for } 2x^{75} \times x^3}$$


Clever way to determine area of irregular shape... I recall seeing a clever method to estimate the area of an irregular shape.  It involved probabilities/ratios/proportions and superimposing the shape onto a 10x10 grid (area=100).

You then randomly scatter 100 pebbles/grains of sand/etc over the grid and see what percentage fall inside the shape.  The area of the shape is a percentage of the total area of 100 (the percentage of pebbles that fell inside the shape)..

Is there a better explanation of this concept somewhere?
Does it use a grid/area of surrounding area?
Was the example best explained with pebbles or sand or something else?

It's called Monte Carlo Method. –  Kaster Nov 21 at 21:11


In Frege proof systems, how to understand 2 if then? For axioms, e.g.
$(p_1 \supset p_3) \supset (p_2 \supset p_3) \supset (p_1 \lor p_2 \supset p_3)$

My understanding is if ($p_1$ can infer $p_3$, and $p_2$ can infer $p_3$), then (if $p_1$ is true or $p_2$ is true, then $p_3$ is true).

If so, how to understand the 2nd $\supset$, why not use $\land$?

The lack of parentheses introduces an ambiguity in the formula.

See e.g. Herbert Enderton, A Mathematical Introduction to Logic, Academic Press (2nd ed., 2001), page 33 on omitting parentheses :

  we adopt the following conventions : [...]

    The negation symbol applies to as little as possible.
    The conjunction and disjunction symbols apply to as little as possible,
    given that convention 2 is to be observed.
    Where one connective symbol is used repeatedly, grouping is to the right: $α → β → γ$ is $α → (β → γ)$.

Thus, I'll read the formula as :

  $(P \to Q) \to [(R \to Q) \to ((P \lor R) \to Q)]$.

It is simply Disjunction elimination written as a tautology instead of as a rule.

See Hilbert-style axioms system for intuitionistic logic (but why Frege's ?).

From it, we can recover the rule using modus ponens twice :

  $(P \to Q), (R \to Q) \vdash (P \lor R) \to Q$.

If we read the formula that way, your interpretation is correct : we can use $\land$ instead to express the same logical principle.

See Exportation :

  $((\varphi \land \psi) \to \sigma) \equiv (\varphi \to (\psi \to \sigma))$.

No.

It's more like:

"If, if p1, then p3, then if, if p2, then p3, then if p1 or p2, then p3."

In your translation you have a conjunction as the antecedent, having two conditionals as the conjuncts of that conjuction.  But, the formula says that the antecedent is a conditional "if p1, then p3".

There does exist a relationship via the exportation and importation laws that Mauro referenced, but such a relationship concerns formulas that differ.

In general, two 'if-thens' can get understood as multiple if-thens.


Determining maximal ideals of a quotient polynomial ring Let $K$ be a field and consider the quotient of the ring of polynomials in $X$ and $Y$ over $K$ by the ideal generated by $XY$:

$$R:=K[X,Y]/(XY)$$

I have to find the maximal ideals of such $R$. I know the correspondence between (maximal) ideals of $K[X,Y]$, that are all finitely generated, which contain $(XY)$ and (maximal) ideals of $R$ as it is a quotient ring however I'm not sure on how to approach this problem.

If K is algebraically closed the maximal ideals correspond to points on the axes, So they are $$\{(X, Y-a)~|~ a \in K\} \cup \{(X-a, Y)~|~ a \in K\}$$

When K not algebraically closed the answer is messy


An Inequality Involving $n$ positive real numbers and their sum Consider the following problem from Problems from the Book proposed by Gabriel Dospinescu

  Let $a_1, a_2, ..., a_n$ be positive real numbers and let $S = a_1 + a_2 + ... + a_n$ be their sum. Prove that
  $$ \frac{1}{n} \sum_{i = 1}^n \frac{1}{a_i} + \frac{n(n-2)}{S} \geq \sum_{i \neq j} \frac{1}{S + a_i - a_j}$$

I've been trying to solve this using standard methods such as fudging and Cauchy-Schwartz without any luck (the inequality would become too weak). Any suggestions or solutions?

Just an idea :
We try the substitution :
$$\frac{1}{a_i}=x_i$$
We have :
$$\frac{1}{Sx_ix_j+x_i-x_j}\int_{x_j}^{Sx_ix_j+x_i}\frac{x_ix_j}{Sx_ix_j+x_i-x_j}dy=\frac{x_ix_j}{Sx_ix_j+x_i-x_j}$$
Wich have the form :
$$\frac{1}{a-b}\int_{b}^{a}f(x)dx$$
So there is many possibilities and by example we can use Jensen's inequality for integrals  wich states :
$${\displaystyle \varphi \left({\frac {1}{b-a}}\int _{a}^{b}f(x)\,dx\right)\leq {\frac {1}{b-a}}\int _{a}^{b}\varphi (f(x))\,dx.}$$
For $f(x)\neq \infty$  a convex function and $a\neq b\neq 0$.
I hope for you !

Hints:
1. Use Karamata’s inequality for the convex function $t\mapsto \dfrac1t$. You will then need to show $$(\underbrace{na_1, na_2, \dots na_n}_{n \text{ terms}}, \underbrace{S, S, \dots, S}_{n(n-2) \text{ times}}) \succ (\underbrace{S+a_1-a_2, S+a_1-a_3, \dots S+a_n-a_{n-1}}_{n(n-1) \text{ terms}})$$

The majorisation can be established by noting WLOG $a_k$ can be ordered non-decreasing say...


Counter-example concerning isometry. Can $(\Bbb R^2 , \|\cdot\|_1)$ and $(\Bbb R^2, \|\cdot\|_2)$ be isometric?

I think that these two spaces can't be isometric. But I can't able to show that. Would anybody please help me in this regard?
Thanks in advance.

(Apologies, I cannot comment). This question is a duplicate, and already has answers here.

Assume that $U:(\mathbb{R}^d,\|\cdot\|_1)\to(\mathbb{R}^d,\|\cdot\|_2)$ is an isometry. Then
\begin{align*}
\|Ux+Uy\|_2^2+\|Ux-Uy\|_2^2&=2\|Ux\|_2^2+2\|Uy\|_2^2
\end{align*}
by the parallelogram law. On the other hand, as $U$ is an isometry,\begin{align*}
\|x+y\|_1^2+\|x-y\|_1^2&=2\|x\|_1^2+2\|y\|_1^2.
\end{align*}
Thus $\|\cdot\|_1$ also satisfies the parallelogram law, thus comes from a scalar product, a contradiction. The conclusion is the same if we replace $\|\cdot\|_1$ by any $\|\cdot\|_p$ with $p\neq2$.


$f(z)= az$ if $f$ is analytic and $f(z_{1}+z_{2})=f(z_{1})+f(z_{2})$ If $f$ is an analytic function with $f(z_{1}+z_{2})=f(z_{1})+f(z_{2})$, how can we show  that $f(z)= az$  where $a$  is a complex constant?

It's true under weaker assumptions, but let's do it by assuming that $f$ is analytic.

Fix $w \in \mathbb{C}$. Since $f(z+w) = f(z)+f(w)$, it follows that $f'(z+w) = f'(z)$ for all $z$. Hence $f'$ is constant, say $f'(z) = a$ which implies that $f(z) = az+c$.

Plug in $z_1 = z_2 = 0$ in the defining equation to conclude that $f(0) = 0$, so $f(z) = az$.

$f'(z)=\ lt_{h\to\ 0}\frac{f(z+h)-f(z)}{h}=lt_{h\to\ 0}\frac{f(z)+f(h)-f(z)}{h}\\=lt_{h\to\ 0}\frac{f(h)}{h}=lt_{h\to\ 0}\frac{f(0)+ \frac{hf'(0)}{1!}+\frac{h^2f''(0)}{2!}+...}{h} $

(by the taylor's series expansion  of $f(h)$
)

$so, f'(z)=lt_{h\to\ 0}\frac{f'(0)}{1!}+\frac{hf''(0)}{2!}+...$

since , $f'(0)$ is a complex constant,  then, $f'(z)$ is constant.
Then

$f(z) =az+b$ since $f(0)=0$, then we have that $f(z)=az $


Check proof that two functions are linearly independent. I am not very experienced with math and need help with a proof. I need to show that the pair of functions $t$ and $1/t$ defined for $t>0$ are linearly independent. Is the following a sufficient proof? If so, is there a simpler way?
Assume $at+b\frac{1}{t}=0$ is correct for any $t>0$. Substituting $t=1$ yields $a+b=0$ (Eq. 1). Substituting $t=2$ yields $2a+\frac{b}{2}=0$ (Eq. 2). Subtracting Eq. 1 from Eq. 2 yields $a-\frac{b}{2}=0$, so $a=\frac{b}{2}$. Substituting $a=\frac{b}{2}$ into Eq. 1 yields $\frac{3}{2}b=0$, therefore $b=0$, which implies $a=0$.
Since the only scalars $a, b$ such that $at+b\frac{1}{t}=0$ are $a=b=0$ then $t$ and $1/t$ are linearly independent.

Your proof is fine and straightforward.
Maybe little shorter proof would be to see that $\lim_{t\rightarrow\infty} at+b\frac{1}t$ can be zero if and only if $a=0$. It follows immediately that $b=0$ too.

Well they are actually not linear independent. Take $t=1$ and $a=1;b=-1$
and You have $1+(-1*1/1$)
@billiam Thanks for your answer, if it is only positive, then it is quite trivial, here is my previous answer. Well, I don't know whether it may help, but since $t>0;1/t>0$ therefore $t+1/t$ can only be zero if the coefficients are zero.
But i could prove that $1/t$ is at least poaitive. first lets show that if $0<x |*x \Leftrightarrow0<x^2$ so the sqaure is always positive. Now $0<t|*(1/t)^2\Leftrightarrow0* (1/t)^2<t*(1/t)^2 \Leftrightarrow0<1/t$ hope that helps
For any positive scalars the functions as it takes only positive values is positive again.


Find all solutions $f:\mathbb R \to \mathbb R$ to the functional equation $g(f(x+y)) = g(f(x)) + g(f(y))$ Let $g:\mathbb R \to \mathbb R$ be continuous and such that $g(0) = 0$ and $g(x)g(−x)>0$ for any $x > 0$. Find all solutions $f:\mathbb R \to \mathbb R$ to the functional equation $$g(f(x+y)) = g(f(x)) + g(f(y)),\quad x,y \in \mathbb R $$

I have deduced that (if $f$ is continuous) we must have $g(f(x)) = \lambda x$, because $g \circ f$ is a continuous linear function and all such functions must be of that form. I am then tempted to say that $f(x) = g^{-1}(\lambda x)$ but I cannot do this because I do not know that $g$ is bijective. Unfortunately I do not understand the significance of the conditions $g(0) =0$ and $g(x)g(-x)>0$ for $x > 0$. Any help would be appreciated.

First, notice that $g$ does not vanish except at $x=0$. So, by continuity, $g$ keeps a constant sign on $(0, +\infty)$, and a constant sign on $(-\infty, 0)$. Adding the condition $g(x)g(-x) > 0$, you get that $g$ keeps a constant sign on $\mathbb{R}$.
Now, let $x=y=0$ in the equation. You get $g(f(0))=2g(f(0))$, therefore $g(f(0))=
0$. For all $x \in \mathbb{R}$ then, you have
$$0 = g(f(x-x))=g(f(x))+g(f(-x))$$
But $g$ keeps the same sign everywhere as stated at the beginning, so $g(f(x))=g(f(-x))=0$. Because the only point where $g$ vanishes is $0$, you deduce that
$$f(x)=0$$
So the only solution is the function $f$ constant equal to $0$.

Assume that $f$ is continuous and $y_1 , y_2 \in f(\mathbb{R})$ and $$g(y_1 ) =g(y_2 )$$ then $$y_1 =f(x_1) , y_2 =f(x_2)$$ and  hence $$\lambda x_1 =g(f(x_1)) =g(y_1 ) =g(y_2) =g(f(x_2)) =\lambda x_2 $$ thus $$x_1 =x_2 $$ and consequently $$y_1 =y_2.$$
Therefore $g|_{f(\mathbb{R} )}$ is an bijection and you can use $g^{-1}.$


"Proof" that ZFC is inconsistent using Turing machines I came across the following "proof" for the inconsistency of ZFC and can't find the flaw in it (if there is one...):

Construct a Turing machine A which sequentially runs on all proofs in ZFC and checks if the claim "A does not halt or ZFC is inconsistent" is proved. If such a proof is found, A halts.

Note that A can know its encoding - see Kleene's recursion theorem - and even if it can't this "obstacle" can be overcome. So it seems to me such A is constructible.

Now, if A halts then it is because it has found a proof for "A does not halt or ZFC is inconsistent". Since A halted, it is implied that ZFC is inconsistent. So either A does not halt, or ZFC is inconsistent.

Now (and my guess is that this is the part where this proof "cheats") we have just proved the claim "A does not halt or ZFC is inconsistent", so such a proof exists in ZFC. So A must halt on this proof - and we have seen that this implies that ZFC is inconsistent.

Where is the mistake?

Here's my take on it. Use $(A \uparrow)$ to mean $A$ does not halt, and $(A \downarrow)$ to mean $A$ does halt. Let $\Phi$ be any sentence; the question uses $\lnot\operatorname{Con}\mathrm{(ZFC)}$ but this is not material. Let $\operatorname{Pvbl}(b)$ be the standard $\mathrm{ZFC}$-formalized provability predicate, which says that there is a coded proof of the formula with number $b$.

The question is right that, by the recursion theorem, we can create a specific machine $A$ such that
$$
(A \downarrow) \Leftrightarrow \operatorname{Pvbl}((A\uparrow) \lor \Phi)
$$

Moreover, because of the specific form of the formula $(A \downarrow)$, $\mathrm{ZFC}$ is able to prove
$$
(A \downarrow) \to \operatorname{Pvbl}(A\downarrow)
$$

Working in ZFC, assume $(A \downarrow)$. Then we know $\operatorname{Pvbl}(A \downarrow)$ and $\operatorname{Pvbl}((A \uparrow) \lor \Phi)$.  ZFC is able to prove enough about the $\operatorname{Pvbl}$ predicate to ensure that
$$\operatorname{Pvbl}(\psi) \land \operatorname{Pvbl}(\lnot \psi \lor \theta) \rightarrow \operatorname{Pvbl}(\theta)
$$
for all $\psi$ and $\theta$. So we can obtain $\operatorname{Pvbl}(\Phi)$.

Now: what we have obtained is: "A does not halt or $\operatorname{Pvbl}(\Phi)$". In the fourth paragraph of the question, it instead claims we can obtain "A does not halt or $\Phi$". That is a stronger statement, and this is the first error I see in the proof. In the fourth paragraph, it is silently assumed that provability implies truth, but this is not correct for formalized provability.

$\mathrm{ZFC}$ does not prove $\operatorname{Pvbl}(\Phi) \to \Phi$ in general. In particular, $\mathrm{ZFC}$ does not prove $\operatorname{Pvbl}(0=1) \to (0=1)$ because there are models of $\mathrm{ZFC}$ in which both $\operatorname{Pvbl}(0=1)$ and $0 \not = 1$ are satisfied.

Addendum: Löb's theorem addresses this exact question. Applied to $\mathrm{ZFC}$, it states that if $\mathrm{ZFC}$ proves $\operatorname{Pvbl}(\Phi) \to \Phi$ then ZFC already proves $\Phi$. So, in particular, $\mathrm{ZFC}$ does not prove that $\operatorname{Pvbl}\mathrm{(\lnot Con(ZFC))}$ implies $\lnot \operatorname{Con}\mathrm{(ZFC)}$.

Why not replace "ZFC is inconsistent" by false? Namely you can prove anything this way.

But this argument is not a proof because it has an extra assumption that A halts iff there is a proof that A does not halt. You mean A is constructible.

What does consistent mean? Someone defines consistent as ~provable(0 = 1), but this only implies the axioms are not against our intuition. But we could have 0 = 1 as an axiom.


Magma : Load file using variable file name I want to load an external Magma file within another Magma file. (Both files are saved in the same directory.) I want to be able to quickly change which external file is being loaded, ideally at the beginning of the file making the load call, so that I can easily run the same code with various inputs.
(The external file contains computations, whose ultimate result is used by the file making the load call. These computations vary depending on the object being analyzed.)
I tried creating a string-type variable that stores the external file's name, then using Magma's load command with this variable. For example,
fileName := "externalMagmaFile.txt";
load fileName;

However, this results in the error

User error: Could not open file "fileName" (No such file or directory)

The same error results when I include double quotes around the external file name:
fileName := "\"externalMagmaFile.txt\"";
load fileName;

It seems that, for the load command, Magma interprets the variable name as the string specifying the file name, instead of first evaluating the variable, then executing load.
(I am using Magma V2.23-1 on MacOS Version 10.15.5.)
Can I use a variable with the load command in Magma? If yes, how?

Another solution (which is also a bit of a work around) is to set the Magma path based on which file you want to load using the SetPath() function. The Magma path indicates which directories are searched for loading Magma files.
To clarify, if you have 2 different files by the same name in separate directories (or can set it up so that you do) and want to choose which one to load, you can set filepath := "directory1" or filepath := "directory2" and then SetPath(filepath) before loading the file.
If you are concerned about changing the path, you can use GetPath() to save off the previous one and restore afterwards. Or add the new path to the end of the current path before calling SetPath().
Side note: I would have added this as a comment rather than an answer since it is a workaround and it is not the ideal solution for every scenario. But adding comments requires reputation, and I came upon this question because I was in a similar situation and this answer would have helped me. In my case I wanted to load several files from the same path (where the path is a variable determined at runtime) so this worked better for me than trying to do a dummyloadfile for each. Also, sadly, the true answer to your question (afaik) is that there is no direct way to load a file using a variable name.

Here is sample code illustrating the approach proposed by @DavidCraven. (The file realFile.txt contains the Magma commands we desire to load.)
fileNameReal := "realFile.txt";
PrintFile("dummyLoadFile.txt","load \"" cat fileNameReal cat "\";" : Overwrite := true);
load "dummyLoadFile.txt";


How can I prove $ \ \bigcap_p \mathbb{Z}_p=\mathbb{Z}$? p-adic numbers

How can I  prove  $ \ \bigcap_p \mathbb{Z}_p=\mathbb{Z}, \ $ where $\mathbb{Z}_p$ is the ring of p-adic integer.

We have information from definition of projective or inverse limit that $\mathbb{Z}_p=\lim_{n} \mathbb{Z}/p^n$.

Also we know that each $\mathbb{Z}_p$ contains $\mathbb{Z}$ since it is a completion of $\mathbb{Z}$.

Also we  have the natural maps $\mathbb{Z} \to \mathbb{Z}_p$ and $ p^n \mathbb{Z} \to p^n\mathbb{Z}_p$ which give rise to the natural map $\mathbb{Z}/p^n\mathbb{Z} \to \mathbb{Z}_p/p^n \mathbb{Z}_p$.

How does these informations helps us to prove the above result?

Even though there is wide agreement about how $p$-adic integers behave, this agreement does not extend to how they are represented in set theory. There are several possible constructions which all produce isomorphic rings -- each author chooses one of them and then feels justified in calling the thing he has defined the $p$-adic integers. This usually doesn't produce a problem because the results are indeed isomorphic -- but it does matter for something like $\bigcap_p \mathbb Z_p$ which doesn't depend only on the internal structure of each $\mathbb Z_p$.

You could define $\mathbb Z_p$ as the $p$-adic metric completion of $\mathbb Z$. Then by definition every $\mathbb Z_p$ would contain $\mathbb Z$ as a subset -- but what else they have in common depends on exactly how you construct "the completion", which is often only defined up to isomorphism by a universal property.

If you construct the completion by taking equivalence classes of Cauchy sequences, we run into a problem that becomes a common theme below -- namely that even though each ordinary integer has a sequence that represents it canonically in each of the $\mathbb Z_p$s, the equivalence classes that contain this canonical representative are not the same in different $\mathbb Z_p$s. The actual set-theoretic intersection becomes empty in that case.
Another common definition of a more algebraic slant is as an inverse limit:

  A $p$-adic integer is a function $f$ with domain $\mathbb N_+$ such that for each $n$ we have $f(n)\in \mathbb Z/p^n\mathbb Z$, and additionally (... the $f(n)$s agree in some appropriate way ...)

Unfortunately, this doesn't resolve our question, because it now depends on, for example, what the intersection of $\mathbb Z/p\mathbb Z$ and $\mathbb Z/q\mathbb Z$ is. And there's a similar problem in defining the set-theoretic identity of those rings. Algebraists hugely prefer to let the elements of $\mathbb Z/p\mathbb Z$ be equivalence classes, and if we use that definition we get
$ \bigcap_p Z_p = \varnothing $
because there is no possible $f(1)$ that is at the same time an equivalence class modulo $p$ and an equivalence class modulo $q$ for $p\ne q$.
On the other hand, people who want a more elementary (programmer-like) understanding of things might want to define the integers modulo $p^n$ as the set $\{0,1,\ldots,p^n-1\}$ with particular addition and multiplication operations on it. In that case the sequences
$$ (0,0,0,\ldots) \qquad\text{and}\qquad (1,1,1,\ldots) $$
would be elements of every $\mathbb Z_p$, but nothing else would. So then we'd have $\bigcap_p\mathbb Z_p = \{0,1\}$.
We could also fuse the inverse limit construction with the construcion of modular arithmetic and define something like

  A $p$-adic pre-integer is a function $f:\mathbb N_+ \to \mathbb Z$ such that $f(n)\equiv f(n+1) \pmod{p^n}$ for all $n$.

  A $p$-adic integer is an equivalence class of $p$-adic pre-integers under such-and-such equivalence relation.

The goal of this might be to produce a clearer embedding of $\mathbb Z$ -- but it's actually not really an improvement for our purposes here. Even though we now seem to have $\mathbb Z$ embedded in $\bigcap_p\mathbb Z_p$ in the form of the constant sequences, that is only a representatives. The actual equivalence classes that encode the integers in each $\mathbb Z_p$ are still all different, so we still get $\bigcap_p\mathbb Z_p=\varnothing$.
Finally we could take a completely programmer-centric approach and define

  A $p$-adic integer is any function $f:\mathbb N_+ \to \{0,1,\ldots,p-1\}$.

where the $f(n)$s are single digits and we then define addition and multiplication by the obvious generalization of the grade-school digit-by-digit operations for $\mathbb Z$ in base $p$.

Now $\bigcap_p \mathbb Z_p$ consists of all infinite sequences of $\{0,1\}$ -- but in a way that is algebraically completely unsatisfying, because each such sequence behaves differently for different $p$s -- except for $(0,0,0,\ldots)$ and $(1,0,0,\ldots)$ which consistently represent $0$ and $1$.
I think there are also more esoteric constructions that would work, such as constructing $\mathbb Z_p$ as the quotient $\mathbb Z[[X]]/\langle X-p\rangle$ where $\mathbb Z[[X]]$ is the ring of formal power series with integer coefficients. Again this would lead to $\bigcap_p \mathbb Z_p$ being empty because none of the equivalence classes agree.

Now, for each of the above definitions we could "cheat" and explicitly rename the elements that correspond to ordinary integers, such that they are represented by the elements of our usual $\mathbb Z$. Then we indeed get $\bigcap_p \mathbb Z_p= \mathbb Z$, but a priori that is more a feature of the cheating we did to define $\mathbb Z_p$.

One might be able to find a precise sense in which $\mathbb Z$ is the largest ring that embeds in all the $\mathbb Z_p$ in a "sufficiently nice" way -- but that is something quite different from a set-theoretic intersection. (Though I suppose one could co-opt the $\bigcap$ symbol with a category-theoretic meaning that produces this outcome).

I don't think you need to use any maps or heavy machinery, just work from the definitions:

Clearly $\mathbb{Z} \subseteq \bigcap_{p}\mathbb{Z}_p$ because any integer is also a p-adic integer.

For $q = \frac{a}{b} \in \mathbb{Z}_p$, $gcd(b,p)=1$.

Therefore if $b$ is coprime to all primes $p$, indeed it is $1$. Therefore $q$ is an integer and you have the other inclusion.


Where does the function $f(x) = \frac{2x}{x - 7}$ have an increasing slope? Where does the function $f(x) = \frac{2x}{x - 7}$ have an increasing slope?

$a. x \le 0, x > 7$
$b. x<7$
$c. x > 7$
$d. x \in \Bbb R, x \neq 7$

This question is from a test of mine in a pre-calculus course (so no calculus allowed in answering the question).I have no idea as to how to solve this problem. I can tell where the function is negative and where it is positive, but that's about it, and I'm fairly sure that's no use here.

Any ideas?

I'd go for $$\frac{2x}{x-7}=\frac{2(x-7)}{x-7} +\frac{14}{x-7}$$

The first term is constant, and the second one is just the graph of $1/x$ shifted and rescaled.

Differentiating gives f'(x) = -14/(x-7)^2 which is always negative. Drawing the curve of y = 2 + 14/(x-7) as suggested by newbie one gets a rectangular hyperbola with asymptotes x = 7, y = 2 showing negative gradient at all times.I'd be happier if the problem stated 'decreasing' rather than 'increasing' slope, in which case the answer would be d.

CORRECTION. I've just read the solution above, and must have misunderstood the phrase 'increasing slope' to mean 'positive slope". The slope is always negative, but changes as x changes, so can of course be increasing negatively.


Can't figure out what's wrong with my solution to an indefinite integral I tried integrating $\int{\frac{xdx}{(Ax + B)^n}}$, and my solution was
$$
\int{\frac{xdx}{(Ax + B)^n}} = \frac{1}{A^2}\left[\frac{(Ax + B)^{-n}}{-n} - B\frac{(Ax + B)^{-n + 1}}{-n + 1}\right] + c
$$
which I got by substituting $u = Ax + B$ and then integrating $\frac{1}{A^2}\int{\frac{u-B}{u^n}du} = 1/A^2(\int{\frac{du}{u^{n-1}}} - B\int{\frac{du}{u^n}})$. WolframAlpha gives me a different answer, and I can't determine if the two answers are equivalent (which it doesn't look like they are). Is my answer the same as WolframAlpha's answer? And what algorithm or procedure might WolframAlpha have used to get a solution to this integral?

EDIT: Okay maybe I should post my solution, so that people get an idea of my thought process.

$$
\begin{align}
\int{\frac{xdx}{(Ax + B)^n}} & = \int{\frac{1/A(u - B)}{u^n}\cdot\frac{1}{A}du}, \ u = Ax + B \\
& = \frac{1}{A^2}\left(\int{\frac{udu}{u^n}} - B\int{\frac{du}{u^n}}\right) \\
& = \frac{1}{A^2}\left(\int{\frac{du}{u^{n-1}}} - B\int{\frac{du}{u^n}}\right) \\
& = \frac{1}{A^2}\left(\frac{u^{-n}}{-n} - B\frac{u^{-n+1}}{-n+1}\right) + c \\
& = \frac{1}{A^2}\left(\frac{(Ax + B)^{-n}}{-n} - B\frac{(Ax + B)^{-n+1}}{-n+1}\right) + c
\end{align}
$$

It seems alright to me, but I don't see how
$$
\frac{1}{A^2}\left(\frac{(Ax + B)^{-n}}{-n} - B\frac{(Ax + B)^{-n+1}}{-n+1}\right) = -\frac{(Ax + B)^{-n+1}(A(n-1)x+B)}{A^2(n-2)(n-1)}
$$
where the right hand side is what WolframAlpha is giving. So are the two expressions equivalent?

The step between the two following lines is wrong:

$$\frac{1}{A^2}\left(\int{\frac{du}{u^{n-1}}} - B\int{\frac{du}{u^n}}\right)$$

$$\frac{1}{A^2}\left(\frac{u^{-n}}{-n} - B\frac{u^{-n+1}}{-n+1}\right) + c$$

Actually, $\displaystyle{\frac{1}{u^{n-1}}=u^{-n+1}}$, so when you integrate, you get $\displaystyle{\frac{u^{-n+2}}{-n+2}}$, not $\displaystyle{\frac{u^{-n}}{-n}}$.


Prove that $co-RP \subseteq RP^{RP}$ This appears in solutions to an exercise I had:

Question: Prove that $RP^{RP}=RP$, or show that it is equivalent to an open question.
Answer: $RP^{RP}=RP$ is equivalent to the open question $RP=co-RP$.
If $RP=co-RP$, then $RP=RP \cap co−RP=ZPP$, and therefore $RP^{RP} = ZPP^{ZPP} = ZPP = RP$.
If $RP^{RP}=RP$, then $co−RP \subseteq RP^{RP} = RP$, therefore $RP=co-RP$.

I understand everything except for the last part, If $L \in co-RP$, I don't understand how access to the oracle helps to build a probabilistic machine that proves $L \in RP^{RP}$.
Any explanation would be appreciated.

A definition of $RP^{RP}$ is given at Wikipedia.

A definition of an oracle is given on the same page here.

An oracle $O$ therefore takes an input $I$ and has a list of strings $S$ that produce 'yes' if $I\in S$ and 'no' otherwise.

So let $S=\{'no'\}$, and if the output from $RP$ is 'yes', then the output from $O$ is 'no' and vice versa.


Show that $\frac{x}{3!}-\frac{x^3}{5!}+\frac{x^5}{7!}-\cdots\leq \frac{1}{\pi}$. My problem is to show that
  $$\frac{x}{3!}-\frac{x^3}{5!}+\frac{x^5}{7!}-\cdots\leq \frac{1}{\pi}$$
  for all $x\in\Bbb R$.

I was thinking of first finding the max and then show that its less than $1/\pi$. But it is hard to find it. I get that the series is equal to
$$f(x)=\frac{x-\sin x}{x^2}.$$
Then,
$$f'(x)=\frac{1-\cos x}{x^2}-\frac{2(x-\sin x)}{x^3}=0$$
if and only if
$$2\sin x=x(1+\cos x),$$
which I am unable to solve, appart from the obvious solutions $x=0$ and $x=\pi$. But if $x=\pi$ is the max, then we are done because $f(\pi)=1/\pi$.

Using $f(x)=\frac{x-\sin(x)}{x^2}$, the inequality is equivalent to:
$$
\frac{x-\sin(x)}{x^2}≤\frac{1}{\pi}\iff x\left(1-\frac{x}{\pi}\right)≤\sin(x)
$$
Thus, define $g(x):=x\left(1-\frac{x}{\pi}\right)$.

Note that $g(x)=g(\pi-x)$ and $\sin(x)=\sin(\pi-x)$. Therefore it suffices (by symmetry) to prove the inequality for $x\in\left(-\infty;\frac{\pi}{2}\right]$.

Firstly, we prove it for $x\in\left[0;\frac{\pi}{2}\right]$:

We have $g(0)=\sin(0)=0$, thus it is sufficient to prove, that $g'(x)≤\sin'(x)$ for $x\in\left[0;\frac{\pi}{2}\right]$. Now: $g'(x)=1-\frac{2x}{\pi}$ and $\sin'(x)=\cos(x)$. So it remains to prove:
$$
1-\frac{2x}{\pi}≤\cos(x)
$$
Since $\cos''(x)=-\cos(x)≤0\space\forall x\in\left[0;\frac{\pi}{2}\right]$, $\cos(x)$ is concave on the interval. As $g'(0)=\cos(0)=1$ and $g'\left(\frac{\pi}{2}\right)=\cos\left(\frac{\pi}{2}\right)=0$, $g'(x)$ connects two points on the graph of $\cos(x)$, and together with the concavity, this implies the above inequality.

Secondly, we prove it for $x\in\left(-\infty;0\right]$:

By the same argument as above, we just have to show, that on this interval $g'(x)≥\sin'(x)\iff 1-\frac{2x}{\pi}≥\cos(x)$ holds. This is true because $1-\frac{2x}{\pi}≥1≥\cos(x)$ for all $x\in\left(-\infty;0\right]$

So the inequality is indeed true.

That is o.k. for obtaining which solution get max and which min use second derivative test: if $f^"(a)<0$ then $a$ get max and if $f^"(a)>0$ then $a$ get min.


Existence of semi-primitive primes modulo a special class of numbers Let $p$ be a prime and $N$ be an integer.

Then $p$ is called semi-primitive modulo $N$ if there exists a positive integer $j$ such that $p^j \equiv -1 \pmod{N}$.

Now let $m$ be a positive integer and let $N = \operatorname{rad}\left(\dfrac{p^m-1}{p-1}\right)$, where $\operatorname{rad}(c)$ denotes the product of all the (distinct) prime divisors of an integer $c$.

Question: What are the solutions $(p,m)$ to the equation:
$$
p^j \equiv -1 \pmod{\operatorname{rad}\left(\frac{p^m-1}{p-1}\right)}?
$$
That is, for which $(p,m)$ is $p$ semi-primitive modulo $\operatorname{rad}\left(\frac{p^m-1}{p-1}\right)$?

One particular example is the case when $p$ is a Mersenne prime and $m = 4$.

The proof is a bit tedious but it turns out that this only works when $m = 2$ or when $p$ is a Mersenne prime and $m = 4$...


Optimization Question Finding closest point Find the point on the graph of the function that is closest to the given point.
The function: $f(x)= \sqrt {x-8}$; the point: $(15,0)$

Given two points
$$
\cases{p_0=(15,0)\\
p=(x,\sqrt{x-8})}
$$
the squared distance is given by
$$
\|p-p_0\|^2= d^2
$$
or
$$
(x-15)^2+(\sqrt{x-8}-0)^2 = x^2-30x+15^2+x-8 = d^2
$$
but
$$
x^2-30x+15^2+x-8 = \left(x-\frac{29}{2}\right)^2+\frac{27}{4}=d^2
$$
so we can conclude that $d^2$ is minimum for $x=\frac{29}{2}$ and the minimal distance is $d=\frac{3\sqrt{3}}{2}$

Well, actually you can deal with this problem even without differentiating. You just expected to find the distance from any point on the graph of f(x) to (15; 0), minimize it and find out where the minimum is reached. (It can be done without using of derivative).


Find $\lim_{n\to \infty}\sqrt[n]{a}$ where 0 < a Find $\lim_{n\to \infty}\sqrt[n]{a}$
Disclaimer: Since this is a sequence the fact that n approaches infinity is obvious, therefore I omitted it in the limit notation.
My idea is to analyze two cases: 1) $ 1 < a$ and 2) $ 0 < a < 1$.
(1) $1 < a$-n
$$\sqrt[n]{a} = 1 + t_n$$  And $t_n >0 $Now, I use the binomial formula to get $$a >1+nt_n \Rightarrow t_n<\frac{a-1}{n} \iff 0 <\lim t_n<\lim \frac{a-1}{n} \Rightarrow \lim t_n =0$$
And since $\lim t_n = 0 $ $\lim_{n\to \infty}\sqrt[n]{a}= 1$
Then, I will use the same method to prove the second case.
Is it a correct way to do this? If so, is there an easier way?

For $0 < a < 1$,
there is a interesting trick.
Bernoulli's inequality
does not seem
directly applicable.

However,
if you write
$a=\dfrac1{1+b}$
where
$b
= \dfrac1{a}-1
\gt 0$,
then
$\dfrac1{a^n}
=(1+b)^n
\ge 1+nb
\gt nb
$,
then
$a^n
\lt \dfrac1{nb}
\to 0
$.

Let $$\:a^n=e^{\ln \left(a^n\right)}=e^{n\cdot \ln \left(a\right)}$$
Then
$$\sqrt[n]{a} =a^{\frac{1}{n}}=e^{\frac{1}{n}\ln \left(a\right)}$$
Also
$$u = \lim _{n\to \infty }\left(\frac{1}{n}\ln \left(a\right)\right) = 0 \implies \lim _{u\to \:0}\left(e^u\right)=1$$
Therefore
$$\lim_{n\to \infty}\sqrt[n]{a} = 1$$


For which negative real $x$, does the expression $x^{1/x}$ gives real values? I started to think about the function $f(x) =x^{1/x} $ and how it behaves. How would you show for which negative real values of x that $f(x)$ gives real values?

I tried by rewritting, set $y=-x$ and we get $\displaystyle-\frac{(-1)^{((y-1)/y)} }{y^{(1/y)} } $. The nominator will be complex if $y>1$. Is there any other way to show this? By using euler's formula maybe? Since it is basically just the finding the roots for all negative x.

This is real when $x$ is negative only when $x$ is also an odd integer or a rational with odd numerator, for if $x$ were an even integer, we have complex values. If $x$ is rational, then it should have the form $$\frac{\text{odd integer}}{\text{nonzero integer}},$$ for the same reason as in the integer case. If $x$ is irrational, then we might want to write the expression as $$e^{\log x^{1/x}}=e^{\frac{\log x}{x}},$$ which is not then real.

Thus, in summary, if $x<0,$ then it should either be an odd integer, or a rational with odd numerator as well.

If you define $x^{1/x}$ to be $(-x)^{1/x}(-1)^{1/x}$ you get reals only when the exponent of $-1$ is an integer, i.e.

$$x=-\frac1n.$$

Anyway, this resolution is questionable.


Proof regarding an integral function I want to prove that $\exists c\in (-\infty,2]$ s.t let $h(x)=\int_0^x \frac{t^3e^{-2t}}{\sqrt{2-t}}$ then $h(2)=\frac{2c^3e^{-2c}}{\sqrt{2-c}}$.
The integral function $f$ is defined and continous in $(-\infty,2]$ since I can continously extends the function in $2$ for the reason why for $x\to 2^-$ then $\frac{t^3e^{-2t}}{\sqrt{2-t}}\sim \frac{8e^{-4}}{\sqrt{2-t}}$ that it is integrable.
The only thing thta I have thought is that by mean value theorem I would have $h(2)=f(c)(2-0)$ (f is the integrand) with $c\in [0,2]$, but what's about $(-\infty,2]$?
I have thought I can apply the mean integral value theorem, but I don't have a bounded interval so it is not possible. How can I prove this?
$\textbf{Edit with my work (thanks to the suggestions of André Armatowski)}$.
I know that the integrand function is continous and differentiable on $(-\infty, 2)$. Now so surely in $[0+\epsilon, 2-\epsilon]$ ( $\forall\epsilon>0$)the integrand will be continous and differentiable and here I will apply the mean value theorem:
$$\exists c\in [0+\epsilon, 2-\epsilon]: \int_{0+\epsilon}^{2-\epsilon}f(t)\, dt=2\frac{c^3e^{-2c}}{\sqrt{2-c}} $$. Now since $[0+\epsilon, 2-\epsilon]\subseteq (-\infty,2]$ $\forall \epsilon>0$ then this means that I have completed the proof.

We consider as in the question the function $h$:
$$h(x)=\int_{0}^{x}\frac{t^3e^{-2t}}{\sqrt{2-t}}\,dt$$
Because our goal is to use the Mean Value Theorem on $[0,2]$, we must first confirm that $h$ satisfies the assumptions of being continuous on $[0,2]$ and differentiable on $(0,2)$.
The differentiability of $h$ on $(0,2)$ is an immediate consequence of The Second Fundemental Theorem Of Calculus. The differentiability on $(0,2)$ for $h$ implies continuity of $h$ on $(0,2)$. To make $h$ continuous at $x=2$ we can define $h(2)=\lim_{x\to 2^{-}}h(x)$, provided it exists:
$$\lim_{x\to 2^{-}}h(x)=\lim_{x\to 2^{-}}\int_{0}^{x}\frac{t^{3}e^{-2t}}{\sqrt{2-t}}\,dt \leq \lim_{x\to 2^{-}}K\int_{0}^{x}\frac{1}{\sqrt{2-t}}\,dt=K2^{\frac{3}{2}}.$$
We can therefore extend $h$ to be a continuous function on $[0,2]$ by taking $h(0)=0$ and noting that $h(2) = \lim_{x\to 2^{-}}h(x)$ exists by monotonicity of $h$ and that it is bounded above by the above estimate for some $K>0$.
Applying the Mean Value Theorem to $h$ on $[0,2]$ there exists a $c\in(0,2)$ such that:
$$h(2)=\frac{2c^{3}e^{-2c}}{\sqrt{2-c}}$$

The question, as stated, makes no sense, but a data point:
$$h(2) = \frac{444 e^4-791 \sqrt{\pi }
   \text{erfi}(2)}{64 \sqrt{2} e^4}.$$


How to determine whether the series converges or diverges $$\begin{align*}
\sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)}
\end{align*}$$

I apprpach this problem by using the ratio test.

$$ \lim_{k\rightarrow \infty}\frac{\dfrac{(-1)^{k+1}}{2(k+1)+1}}{\dfrac{(-1)^k}{(2k+1)}}$$

which after simplifying gets me $(2k)/(2k+3) + (1)/(2k+3)$

How does one simplify this to $\sqrt{k+1}$ as the answer it is very perplexing?

Hint. The alternating series $\displaystyle \sum_{k=0}^{\infty}(-1)^{k}a_k$ converges provided:

1) $0< a_{k+1} \le a_k$ for $k$ greater than some index $N$.

2) $\lim_{k\to \infty}a_k = 0$

Just take $a_k:=\frac{1}{2k+1}$ here.

you can use the Alternating Series Test,

http://en.wikipedia.org/wiki/Alternating_series_test


If $A$ and $B$ commute, then prove that so also do $A^m$ and $B^n$ for all positive integers $m$ and $n$. If $A$ and $B$ commute, then prove that so also do $A^m$ and $B^n$ for all positive integers $m$ and $n$.

My Proof

So we want to show that, for all positive integers $m$ and $n$, $A^mB^n = B^nA^m$.

Let $P(n,m) = A^mB^n$, and let $A$ and $B$ be $p \times p$ matrices.

$n,m = 1$: $P(1, 1) = AB = BA$ Since we assumed that $A$ and $B$ commute.

We first perform induction over $n$.

$n = k, m = 1$: $P(k, 1) = AB^k = B^kA$ This is the induction hypothesis.

$n = k + 1, m = 1$: $P(k + 1, 1) = (AB^k)(B)$ By the induction hypothesis.

$= A(B^kB)$ Since matrix multiplication is associative.

$= AB^{k + 1}$

Q.E.D.

We lastly perform induction over $m$.

$n = 1, m = k$: $P(1, k) = A^k B = BA^k$ This is the induction hypothesis.

$n = 1, m = k + 1$: $P(1, k + 1) = (A)(A^k B)$ By the induction hypothesis.

$= (AA^k)(B)$ Since matrix multiplication is associative.

$= A^{k + 1}B$

Q.E.D.

I would greatly appreciate it if people could please take the time to review my proof for correctness.

Since both of the answers posted so far have been down-voted, I'm going to assume that they're both incorrect and instead post my new proof.

My New Proof

Let $A$ and $B$ be $n \times n$ matrices.

For every positive integer $m$, $A^m$ and $B$ commute.

Let $P(m) = A^nB = BA^m$.

$m = 1$: $P(1) = AB = BA$ Since we assumed that $A$ and $B$ commute.

$P(m) = A^mB = BA^m$ This is the induction hypothesis.

$P(m + 1) = (A)(A^mB)$ Since $(A)(A^mB) = (AA^m)B = A^{m + 1}B$.

$= (A)(BA^m)$ By the induction hypothesis.

$= B(AA^m)$ Since we assumed that $A$ and $B$ are commutative.

$= BA^{m + 1}$ Q.E.D.

For every fixed $m$ and variable $n$, $B^nA^m = A^mB^n$.

$P(1) = BA^m = A^mB$

$P(n) = B^nA^m = A^mB^n$ This is the inductive hypothesis.

$P(n + 1) = (B)(B^nA^m)$ Since $(B)(B^nA^m) = (BB^n)A^m = B^{n + 1}A^m$, since matrix multiplication is associative.

$= (B)(A^mB^n)$ By the inductive hypothesis.

$= A^m(BB^n)$ Since we proved in the last inductive proof that $A^m$ and $B$ commute for all $m$.

$= A^mB^{n + 1}$ Q.E.D.

I would greatly appreciate feedback as to whether my new proof is correct.

You have to modify your second induction. Show for fixed $m$ that $A^kB^m=B^mA^k$ by induction over $k$.

For $k=1$ this is your first induction (if you correct it).
For $k>1$ you get $A^kB^m=AA^{k-1}B^m=AB^mA^{k-1}$ by induction hypothesis. Now the case $k=1$ yields that this is equal to $B^mAA^{k-1}=B^mA^k$ which you wanted to show.

Your proof is incomplete. In second induction you should take $n = k'$. For $n = k', m = 1$ it is true from 1st induction and now you should prove for $n = k', m = k+1$ assuming it is true for $n = k', m= k$.


Proof that a certain fraction is always an integer Prove that $$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}$$ is or is not an integer for $0\leq k \leq n$, where $k$ and $n$ are integer values.
This looks like $\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$. The above statement is true for k=1 and k=2 as seen by observing modular residues. Not sure how to proceed.

I’m going to give the answer more or less as I worked through the problem, since these numbers turn out to be rather interesting; if you just want a quick and easy computational proof, skip to the end.
I rewrote it as
$$\frac{n!}{k!(n-k)!}\cdot\frac{(n+1)!}{(k+1)!(n-k+1)!}=\frac1{k+1}\binom{n}k\binom{n+1}k\,,\tag{1}$$
and calculated some values:
$$\begin{array}{c|cc}
n\backslash k&0&1&2&3&4&5\\\hline
0&1\\
1&1&1\\
2&1&3&1\\
3&1&6&6&1\\
4&1&10&20&10&1\\
5&1&15&50&50&15&1
\end{array}$$
The row sums are familiar: $1,2,5,14,42,132$ are the Catalan numbers $C_{n+1}$. This does suggest that these numbers may be counting something. And if we look up the triangle in OEIS by searching on the sequence
$$1,1,1,1,3,1,1,6,6,1,1,10,20,10,1\,,$$
the very first return is A001263, the sequence of Narayana numbers, whose first FORMULA entry is an offset version of the righthand side of $(1)$. If the entry in row $n$, column $k$ of my table is $t(n,k)$, then $t(n,k)$ is the Narayana number $N(n+1,k+1)$ and is the number of Dyck paths of length $2(n+1)$ having exactly $k+1$ peaks. Thus, it must be an integer.
That $N(n,k)$ is the number of Dyck paths having exactly $k$ humps is not obvious; one proof can be found in this PDF. However, the FORMULA section of the OEIS entry also notes that
$$N(n,k)=\binom{n-1}{k-1}\binom{n+1}k-\binom{n}{k-1}\binom{n}k\,,$$
which suggests the following purely computational proof that the original expression is an integer:
$$\begin{align*}
&\binom{n}k\binom{n+2}{k+1}-\binom{n+1}k\binom{n+1}{k+1}\\\\
&\qquad=\frac{n!(n+2)!}{k!(k+1)!(n-k)!(n-k+1)!}-\frac{(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\
&\qquad=\frac{n!(n+2)!-(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\
&\qquad=\frac{(n+1)!^2\left(\frac{n+2}{n+1}-1\right)}{{k!(k+1)!(n-k+1)!(n-k)!}}\\\\
&\qquad=\frac{n!(n+1)!}{{k!(k+1)!(n-k+1)!(n-k)!}}\,.
\end{align*}$$
Here the first expression is clearly an integer, and the last is easily seen to be equivalent to the original fraction.

$\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$ not quite but close
$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}=$
$\frac {(n+1)n(n-1)....(n-k+2)}{(k+1)k(k-1).....\cdot 1}\cdot \frac {n(n-1)....(n-k+1)}{k(k-1).....\cdot 1}=$
$\frac {(n+1)!}{(k+1)!(n-k-1)!}\cdot \frac {n!}{k!(n-k)!}$.
${n+1 \choose k+1}{n\choose k}$
You should know thatboth ${n+1 \choose k+1}$ and ${n\choose k}$ are both integers so their product is.
Combinitorially the number of way to pick $k$ objects from a collection of $n$ objects must be an integer (just do them one after another and counting them).  And if we try to calculate what that integer is we can prove it must be $\frac {n!}{k!(n-k)!}$ and so that must be an integer.
We can prove it algebraically be noting that every $m$ consecutive integers will have a multiple of $m$ so each $m = 1,2,3,....k$ will divide an integer in $n-k+1,....., n$.  so the product of $k!$ will divide the product of $(n-k+1)(n-k+2)...n$.
Okay... theres an issue that $m$ may divide a $n-j$ and $p$ may divide the same $n-j$ but we not have $mp$ dividing $n-j$.  But then the prime components must be split somewhere else.  (I've always found that very tedious.)  But combinitorially we know the result must be true.


Is the semigroup such that $\forall x\ (x\in S\to\exists y\ (y\in S\wedge\forall z\ (z\in S\to zxy=z)))$ a group? I have been dealing with this problem:

  Let $S$ be a semigroup that meets the following condition:
  $$\forall x\ (x\in S\to\exists y\ (y\in S\wedge\forall z\ (z\in S\to zxy=z)))$$
  Must $S$ be a group?

I have tried this as a counterexample:

Let $S=\{[a_1,\ldots,a_n]: n\ge 1, a_j\in\Bbb N^*, a_{j+1}-a_j\neq 1\text{ for } j\ge 2\}$. In words, the set of non-empty $n$-tuples of natural numbers with no two consecutive terms together (in increasing order), except the two first ones: they can be consecutive. The operation $*$ is concatenation and deleting possible illegal pairs. Note that $n\ge 1$, so I'm excluding the empty sequence to avoid having an identity.

For example, for $x=[7, 11, 13]$ we have $y=[14,12,8]$.

This definition implies that there are infinitely many identities at right for each element. For example, if $a$ does not end with $1$,
$$a*[1,2]=a$$
$$a*[2,3]=a$$
So this can not be a group.

But I find this solution too complicated. Any simpler one?

EDIT: In a deleted answer there is an example that shows that my try is not even a semigroup, because it is not associative.

Take the semigroup $S = \{a,b\}$, where $aa=ab=a$ and $ba=bb=b$.
Then, for each $x \in S$, take $y = x$. Then, for all $z \in S$, $zxy=zxx=z$. However, $S$ is not a group.

Scrap that, I made a mistake.

I think this always is a group. There exists a right-neutral element in this group and you can show that this is unique and also left-neutral. So for all $x\in S$ you can find a right-inverse, for which you can again show that it is unique and also left-inverse.

Concerning your example (I cannot comment due to insufficient reputation): I think the concatenation is ill-defined. What is the result of $[1,2]*[3,4]$? is it $[1,2]$ or $[1,4]$? Both work depending from the direction you start removing illegal pairs. Both variants are not associative:
$[1,2] * ([3,4] * [5,7]) = [1,2] * [3,7] = [1,7] \neq [1,2,5,7] = ([1,2] * [3,4]) * [5,7]$
$[1,2] * ([3,4] * [5,6]) = [1,2] * [3,4] = [1,4] \neq [1,6] = [1,4] * [5,6] = ([1,2] * [3,4]) * [5,6]$


Find the legs of isosceles triangle, given only the base Is it possible to find the legs of isosceles triangle, given only the base length? I think that the info is insufficient. Am I right?

The base length of an isosceles triangle is not enough to determine the triangle:

$\hspace{2cm}$

You will always need three data to determine a triangle. It can be any combination of angles, lengths, heights...

In your example, since you know it's an isosceles triangle, you'll have three data once you define an angle or a length apart from the base's length, because you know both angles at the base's ends are equal.

So, if you have the segment AB being the base of an isosceles triangle, once you know either angle C, height from base to C, length BC or length AC, you'll have everything you need.


Discrete random variable. Tossing a coin. Two coins are simultaneously tossed until one of them comes up a head
and the other a tail. The first coin comes up a head with probability $p$ and the second with probability $q$. All tosses are assumed independent.

(a) Find the PMF, the expected value, and the variance of the number of tosses.

$$P(X=k) = (1-p(1-q) - q(1-p))^{k-1}(p(1 − q) + q(1 − p)), \ \ k=1,2...$$
And the above is clear for me.
Now, we would like determine expected value:
$$E[X] = \sum_{k>0} kP(X=k)$$
and from solution:
$$E[X] = \frac{1}{p(1-q)+q(1-p) }$$
And I don't understand this. Please explain me.

Hint. One may recall the useful evaluation:
$$
1+r+r^2+\cdots+r^n+...=\frac{1}{1-r}, \quad |r|<1, \tag1
$$ giving by differentiation and multiplication by $r$:

$$
\sum_{k>0} k\: r^k=r+2r^2+3r^3+\cdots+nr^{n}+\cdots=\frac{r}{(1-r)^2}, \quad |r|<1\tag2
$$
and now put
$$
r:=1-p(1-q) - q(1-p)
$$ in $(2)$.

I'm not great with anything other than basic math, but I can tell you one thing:  The probabibility of the next coin tossed coming up heads is 50% and tails 50%.  You don't even need math for that one :).  That probability will remain the same the next million tosses.


Set theory: how to interpret multiple quantifiers How does one interpret this ZFC Union axiom? I can't quite understand what is meant after "There exists some elements y for all elements z"? I'm also wondering if the x is a typo.

  $\exists y \forall z(\exists w(z\in w \space \land w \in x)\implies z\in y)$

The $x$ is not a typo, but there should be a $\forall x$ in front of the whole thing:

$$\forall x\,\exists y\,\forall z\,\big(\exists w\,(z\in w\land w\in x)\to z\in y\big)\;.\tag{1}$$

Given a set $x$, the expression asserts the existence of a set $y$ with the following property: for any object $z$, if $z\in w$ for some member $w$ of $x$, then $z\in y$. That is, $y$ contains as an element each object that is an element of some member of $x$.

We want $\bigcup x$ to be $\bigcup\{w:w\in x\}$, meaning that $z\in\bigcup x$ if and only if there is some $w\in x$ with $z\in w$. $(1)$ says that there is a set $y$ that contains everything that we want to have in $\bigcup x$. This $y$ may, however, contain other things as well, since $(1)$ has only a one-way implication ($\to$, not $\leftrightarrow$). However, once we have this $y$, we can use the axiom schema of comprehension (or separation) to cut it down to exactly $\bigcup x$:

$$\bigcup x=\{z\in y:\exists w\in x\,(z\in w)\}\;.$$

The reading is "There exists a $y$ such that, for all $z$, the following statement is true: 'If there is a $w$ such that $z$ is in $w$ and $w$ is in $x$, then $z$ is in $y$'".

I think that there is a missing $\forall x$ before the entire statement. If you include that, then you're saying that for any set $x$, there is a set $y$ that is the union of the sets that are elements of $x$. The breakdown is that you consider all possible $z$, and then you check - is it true that there's a $w$ such that $z$ is in $w$ and $w$ is in $x$? In other words, is it true that $z$ is an element of at least one set that is an element of $x$? If so, then $z$ is in the set $y$.