How do you find a corresponding recurrence relation for some random algorithm? void doSomething(int *a, int left, int right) {
       if (left == right) {
          for (int j = 0; j < right; ++j)
             cout << a[j];
          cout << endl;
          return;
    }
       for (int i=left; i<right; ++i) {
          std::swap(a[left],a[i]);
          doSomething(a,left+1,right);
          std::swap(a[left],a[i]);
    }

}

With base case T(1) = right, swap runs in O(1) time, and n = right-left+1 for T(n).

Can someone please walk me through the steps one would take to find the recurrence relation for this algorithm (or any algorithm for that matter)?  In particular, I'm confused with the terminology of left and right, or how n = right-left+1 and T(1) = right effect how we determine what a final solution should look like.

A general method for analyzing the running time of any algorithm is to walk through the algorithm step by step, counting the number of statements executed and express this count as a function of the "size" of the input.

For example, suppose we defined a predicate, isSorted, which would take as input an array $a$ and the size, $n$, of the array and would return true if and only if the array was sorted in increasing order. It might look like this

bool isSorted(int *a, int n) {
   if (n == 1)
      return true;       // a 1-element array is always sorted
   for (int i = 0; i < n-1; i++) {
      if (a[i] > a[i+1]) // found two adjacent elements out of order
         return false;
   }
   return true;         // everything's in sorted order
}

Clearly, the size of the input here will simply be $n$, the size of the array. How many steps will be performed in the worst case, for input $n$?

The first if statement counts as 1 step
The for loop will execute $n-1$ times in the worst case (assuming the internal test doesn't kick us out), for a total time of $n-1$ for the loop test and the increment of the index.
Inside the loop, there's another if statement which will be executed once per iteration for a total of $n-1$ time, at worst.
The last return will be executed once.

So, in the worst case, we'll have done $1+(n-1)+(n-1)+1$ computations, for a total run time $T(n)\le 1+(n-1)+(n-1)+1=2n$ and so we have the timing function $T(n)=O(n)$.

For non-recursive algorithms, the process is, in theory, simple:

Find a parameter, $n$, that expresses the "size" of the input. Walk through the algorithm, assuming
Every statement executed will take time 1,
Every if statement will take its longest branch,
Every loop will iterate the maximum number of times allowable.

Then express the run time of your algorithm as a function of the sum of statements executed, using (2) through (4) above.

For recursive algorithms, you do the same thing, only this time you add the time taken by each recursive call, expressed as a function of the time it takes on its input.

For example, let's rewrite, isSorted as a recursive algorithm:

bool isSorted(int *a, int n) {
   if (n == 1)
      return true;
   if (a[n-2] > a[n-1])         // are the last two elements out of order?
      return false;
   else
      return isSorted(a, n-1); // is the initial part of the array sorted?
}

In this case we still walk through the algorithm, counting: 1 step for the first if plus 1 step for the second if, plus the time isSorted will take on an input of size $n-1$, which will be $T(n-1)$, giving a recurrence relation
$$
T(n) \le 1 + 1 + T(n-1) = T(n-1) +O(1)
$$
Which has solution $T(n)=O(n)$, just as with the non-recursive version, as it happens.

With this done, lets analyze your algorithm. We'll compute the run time as a function of right - left. That will be the size, $n$, so we'll try to find a recurrence relation that expresses the run time, $T(n)$, as a function of $n$.

If $n>0$, the function will take 1 step for the if test and then pass to the second loop. This loop will iterate $n$ times, doing two swaps and calling itself recursively with arguments that we'd express as $n-1, n-2, \dots 1, 0$. In other words, we'll have
$$
T(n) \le T(n-1) + T(n-2) + \cdots + T(1) + T(0) + kn
$$
where the last term takes account of the loop overhead and the two swaps. We have reached our goal: the timing function for the algorithm satisfies the recurrence
$$
T(n) = T(n-1) + \cdots + T(0) + O(n)
$$
and of course, when $n=0$, i.e., when left = right we just print the contents of the array, which we can do in a (possibly large) constant amount of time.

Any questions? Just ask.

. Consider the following recursive algorithm.
Algorithm RiddleA[0..n − 1]
// Input: An array of n real numbers
if (n = 1) return A[0]
else
temp ← Riddle(A[0, n − 2])
if temp ≤ A[n − 1] return temp
else return A[n − 1]
(b) Set up a recurrence relation for the algorithms basic operation count and solve it
can anyone help out with this


How to calculate $\sum_{n=1}^\infty \frac{2}{(2n-1)(2n+1)}$ How can I calculate the sum of the following infinite series: $$\sum_{n=1}^\infty \frac{2}{(2n-1)(2n+1)}$$


Orthogonal trajectories elimination of constant $$x^2+y^2-2ay=0$$
I just learnt orthogonal trajectories today. So basically we need to eliminate the constants and solve $dy/dx=f(x,y)$ right? How do I eliminate $2ay$ in this question.I tried a bunch of stuff but couldn't get it.

This is how to get the differential equation of the family of curves
$$
x^2+y^2-2ay=0 \ \implies\ a=\frac{x^2+y^2}{2y}\\
$$
by diffrentiating the given equation we get
$$
2x +2yy' -2ay' = 0  \Rightarrow y' = \frac{x}{a-y}\\
$$
substituting the value of $a$ in the expression for $y'$ we get
$$
y' = \frac{2yx}{x^2-y^2}\\
$$

The equation is $x^2+ y^2-2ay= 0$.  Differentiate with respect to x:  $2x+ 2yy'-2ay'= 0$. $2(y- a)y'= 2x$, $y'= \frac{x}{y- a}$. Now solve the original equation for a: $2ay= x^2+ y^2$ so $a= \frac{x^2+ y^2}{2y}$.  Replace a in the differential equation with that: $y'= \frac{x}{y+ \frac{x^2+ y^2}{2y}}= \frac{2xy}{2y^2+ x^2+ y^2}= \frac{2xy}{x^2+ 3y^2}$.


Proof that the nth root of a rational s/t is irrational unless s and t are perfect nth powers I'm trying to prove that $\sqrt[n]{\frac{s}{t}}$ is irrational unless both s and t are perfect nth powers. I have found plenty of proofs for nth root of an integer but cannot find anything for rationals. Also trying to work up from the proofs I have found is rather difficult.

My lecturer wants me to prove this using uniqueness of prime factorisation but I also have no idea where to start with that.

Any help is greatly appreciated.

This is more of a comment than an answer, because it doesn't use the uniqueness of prime factorisation. Instead, it uses the more basic result that if a positive integer $c$ divides the product of two positive integers $a$ and $b$, and $b$ and $c$ are relatively prime, i.e. they have no common factors other than $\pm1$, then $c$ divides $a$.

Suppose that the fraction $\tfrac{s}{t}$ is in its lowest terms, i.e. $s$ and $t$ are relatively prime; and suppose that $\left(\tfrac{u}{v}\right)^n = \tfrac{s}{t}$, where $\tfrac{u}{v}$ also is in its lowest terms, i.e. $u$ and $v$ are relatively prime. Then:
\begin{equation}
\tag{$*$}\label{eq:simple}
tu^n = sv^n.
\end{equation}

The hypothesis that $u$ and $v$ are relatively prime implies that $u^n$ and $v^n$ are also relatively prime:

Proof. Suppose that an integer $r > 1$ divides both $u^n$ and $v^n$. Every integer $> 1$ has a prime factor. (This fact is admittedly an ingredient of the proof of uniqueness of prime factorisation, but still, it is a simpler theorem.) Let $p$ be a prime factor of $r$. By the hypothesis that $u$ and $v$ are relatively prime, $p$ cannot divide both $u$ and $v$. But if $p$ does not divide $u$, then by repeated application of the theorem quoted above, $p$ does not divide $u^n$. Similarly, if $p$ does not divide $v$, then $p$ does not divide $v^n$. Therefore, $p$ does not divide both $u^n$ and $v^n$. This contradicts the hypothesis that $p$ divides $r$. Therefore, no such $p$ and no such $r$ can exist. $\square$

Now, four applications of our favourite theorem to \eqref{eq:simple} show that $s$ divides $u^n$, $u^n$ divides $s$, $t$ divides $v^n$, and $v^n$ divides $t$. Therefore, $s = u^n$ and $t = v^n$. $\square$

(Perhaps in an effort to be simple, this has ended up being too laborious? Oh, well.)

To build off Vasya and Calum's helpful comments:

Let $\frac{s}{t}$ be an irreducible fraction (to address Vasya's comment).

Continuing with the main proof, recall Vasya's comment:

  $\sqrt[n]{\frac{s}{t}} = \frac{\sqrt[n]{s}}{\sqrt[n]{t}}$

We will quickly prove this.

Obviously $(\sqrt[n]{\frac{s}{t}})^n = \frac{s}{t}.$

Notice $\frac{s}{t} = \frac{(\sqrt[n]{s})^n}{(\sqrt[n]{t})^n} = (\frac{\sqrt[n]{s}}{\sqrt[n]{t}})^n.$

It follows that $\sqrt[n]{\frac{s}{t}} = \frac{\sqrt[n]{s}}{\sqrt[n]{t}}$ since the $n$th root is either a bijection or always positive.

Without loss of generality, let $s$ have a prime factorization $p_1^{a_1}p_2^{a_2}...p_i^{a_i}.$ Let $\sqrt[n]{s}$ be an integer with prime factorization $q_1^{b_1}q_2^{b_2}...q_j^{b_j}.$

Clearly $p_1^{a_1}p_2^{a_2}...p_i^{a_i} = q_1^{nb_1}q_2^{nb_2}...q_j^{nb_j}.$
We know the prime factorization of $s$ is unique, so we know that each power of $p$ corresponds to some power of $q.$
It's not clear which $p$ corresponds to which $q,$ but it is clear that all the prime factors are $n$th powers.


How to prove that $7^{31} > 8^{29}$ How can I prove that $7^{31}$ is bigger than $8^{29}$?

I tried to write exponents as multiplication, $2\cdot 15 + 1$, and $2\cdot 14+1$, then to write this inequality as $7^{2\cdot 15}\cdot 7 > 8^{2\cdot 14}\cdot 8$. I also tried to write the right hand side as $\frac{8^{31}}{8^2}$.

I tried just approximate the numbers and I think I found a very ugly way to prove the inequality. Are there any mistakes?

We have $7^4>24\cdot10^2$ so $7^{31}=7^3\cdot(7^4)^7>7^3\cdot(24\cdot10^2)^7=2^{35} \cdot 3^7 \cdot 5^{14}
\cdot 7^3$. Also
$8^{29}=2^{87}$. So one has to prove the inequalities $2^{52}<3^7 \cdot 5^{14} \cdot
7^3=750141\cdot5^{14}<750142\cdot5^{14}$ or $2^{51}<375071\cdot5^{14}<375072\cdot5^{14}$.

This mean we have to
prove that $2^{51}<2^5 \cdot 3 \cdot 3907\cdot5^{14}$ or
$2^{46}<3\cdot3907\cdot5^{14}<3\cdot3908\cdot5^{14}=3\cdot2^2\cdot977\cdot5^{14}$ or equivalently
$2^{44}<3\cdot977\cdot5^{14}$. But $3\cdot977\cdot5^{14}<3\cdot976\cdot5^{14}=3\cdot2^4\cdot61\cdot5^{14}$ so
one has to prove that $2^{40}<3\cdot61\cdot5^{14}$.

But $3\cdot61\cdot5^{14}<3\cdot62\cdot5^{14}$ so one has to
prove that $2^{40}<3\cdot62\cdot5^{14}$ or $2^{39}<3\cdot31\cdot5^{14}$. But
$3\cdot31\cdot5^{14}<3\cdot2^5\cdot5^{14}$ so one has to prove that $2^{34}<3\cdot5^{14}$.

Now, lets approximate some square roots:

The inequality above is equivalent to $2^{17}<\sqrt{3}\cdot5^7$. But $\sqrt{3}>1.7$ so one has to prove that $2^{17}<1.7\cdot5^7$. This is the same as $\sqrt{2}\cdot2^8<\sqrt{1.7\cdot5}\cdot5^3$ or $256\cdot\sqrt{2}<\sqrt{8.5}\cdot125$. This is
the same as $(256/125)^2<8.5/2$ or $256^2\cdot2<8.5\cdot125^2$ or $131072<132812.5$.


Can I argue that $g'$ is non zero in this case? Consider two smooth maps $g,f$ given by

$$ {\partial \over \partial x} g(x)= g'(x) = \int_0^1 {\partial \over \partial x} f'(u + t(x-u)) dt = \int_0^1 f''(u + t(x-u)) \cdot t dt  $$

where $f' = {\partial f \over \partial x}$ and $u$ is a fixed point in $\mathbb R$.

I want to argue that if $f''$ is non zero then so is $g'$. I tried integration by parts and got

$$ {\partial \over \partial x} g(x) = g'(x) = \int_0^1 f''(u + t(x-u)) \cdot t dt  = {f'(x) \over x - u} - {f(x) - f(u) \over (x-u)^2}$$

but I really don't see why that should be non zero.

  Please, does anyone have any ideas on how to argue that $g' \neq 0$?

Suppose $g'(x)=0$ for all $x$. Then

$$f'(x)=\frac{f(x)-f(u)}{x-u}.$$

One possibility is $f(x)=ax+b$. To see that this is the only possibility, differentiate:

$f''(x)=\frac{f'(x)(x-u)-(f(x)-f(u))}{(x-u)^2}=\frac{(f(x)-f(u))-(f(x)-f(u))}{(x-u)^2}=0.$

Thus $f''(x)=0$ so $f(x)=ax+b$ is the only type of $f$ which makes $g$ identically zero.

Okay so OP has left most of the work to others.

From $$g'(x) = \int_0^1 {\partial \over \partial x} f'(u + t(x-u)) dt = \int_0^1 f''(u + t(x-u)) \cdot t dt$$ one can deduce that $f'$ means $\partial f \over \partial x $, $g'$ means $ dg \over dx$ and $f=f(t,x)$,$u$ is a constant.

As OP wrote, use integration by parts and get

$g'(x) = \int_0^1 f''(u + t(x-u)) \cdot t dt  = {f'(x) \over x - u} - {f(x) - f(u) \over (x-u)^2}$

We want to show that if $f'' \neq 0$ then $g' \neq 0$, which is equivalent to showing that $g'=0 \Rightarrow f''=0$  (basic fact of logic)

Assume $g'(x)=0$, you get $${f(x) \over (x-u)^2} - {f'(x) \over (x-u)}={f(u) \over (x-u)^2}$$ and hence $$ f(x)-f'(x)(x-u)=f(u), \tag{*}$$
Now$(*)$ is a first-order differential equation, you solve it and obtain $f(x)=A(x-u)+f(u)$ where A is an arbitrary constant, thus $f''=0$. By the logic I stated above, you obtain that $g' \neq 0$ provided $f'' \neq 0$

Just an advice: state partial differentiation clearly otherwise it is hard to guess what are you differential with respect for and what are the independent variables!


Find all $n$ with exactly $8$ divisors (counting $1$ and $n$ itself), the sum of which is equal to $684$. Find all $n$ with exactly $8$ divisors (counting $1$ and $n$ itself), the sum of which is equal to $684$.

I've written down two formulas from there https://en.wikipedia.org/wiki/Divisor_function?wprov=sfla1 and got stuck.

The possible numbers are as follows where $p,q,r$ are distinct primes:

$p^7$ where $\frac{p^8-1}{p-1}=684$ NO SOLUTIONS

$p^3q$ where $\frac{p^4-1}{p-1}(q+1)=684$ NO SOLUTIONS

$pqr$ where $(p+1)(q+1)(r+1)=684$ THE ONLY SOLUTION IS 2.5.37=370

For $n$ to have eight divisors, it must be of the form (all variables standing for different primes)
$$p^7,\quad p^3q,\quad\text{or}\quad pqr $$
(because $8=4\cdot 2=2\cdot 2\cdot 2$ ar all ways to write $8$ as product).
The sums of divisors then are
$$ p^7+p^6+p^5+p^4+p^3+p^2+p+1,\quad (p^3+p^2+p+1)(q+1),\quad (p+1)(q+1)(r+1),$$
respectively, and shall equal $684$.

In the first variant, $p=2$ leads to an odd sum, whereas already for $p=3$, the sum is $>684$. So this case  can be excluded.

In the second variant, from $q\ge 2$ we get the bound $p<\sqrt[3]{\frac{684}3}\approx 6.1$, so $p\le 5$. Then $p^3+p^2+p+1$ is one of $15$, $40$, $156$. None of these divides $684$, so this case  can be excluded as well.

In the third variant, we may assume wlog. that $p>q>r$. Note that $8\nmid 684$, so one of the three factors must be odd, $r=2$. Then the other factors are necessarily even and we arrive at $\frac{p+1}2\frac{q+1}2=3^2\cdot 19$, so either $\frac{p+1}2=19$, $\frac{q+1}2=9$, or $\frac{p+1}2=57$, $\frac{q+1}2=3$, or $\frac{p+1}2=171$, $\frac{q+1}2=1$. In other words,
$p=39$, $q=19$, or $p=115$, $q=7$, or $p=343$, $q=3$. As none of the candidates for $p4 is prime, we again fid no solution.


Which form of this quadratic do i use to solve intercept and range? So my equation is:
$-2x^2 + 4x + 30 = 0$

If I use this form to look at my y intercept, it will be 30.
However, once I simplify it to: $x^2 - 2x - 15$, then my y intercept will be $-15$. Which one do I use? Inclusively, I was taught that if the quadratic is positive, it is in a U shape, and if it is negative, it is an upside-down U shape.

How do I know which form to use to solve these questions?

Your equation is not $-2x^2 + 4x + 30 = 0$, but $f(x)=-2x^2 + 4x + 30 = -2(x^2-2x-15)$. You must find the $y$ intercept of a function, rather than an equation. To find the $y$ intercept, you need to let $x=0.$

$$f(0)=-2(0^2-2(0)-15)=-2(0-0-15)=-2(-15)=30$$

Thus, the $y$ intercept still occurs at $(0,30)$

When $-2x^2 + 4x + 30 = 0$, you are saying that you are trying to find where $f(x)=0$, and not a general function, $f(x)$. Note that $f(x)=-2x^2 + 4x + 30 \neq x^2-2x-15 $

Please comment if what I have said does not make sense.

It does not simplify to $x^{2} - 2x - 15$, you have to continue to account for the $-2$ you factored out:

$$-2x^{2} + 4x + 30 = -2(x^{2} - 2x - 15) = 0 $$

Evaluating at $x = 0$, the intercept remains $(0,30)$.


Global existence of solutions How do I see whether or not these ODE's have a global solution:

$$x'=t^2+x^2$$

$$x'=t^2+x$$

Why?

Applying the weaker form of the Cauchy theorem (probably known to many as Picard–Lindelöf theorem) to $$x'=f(t,x),$$ $\partial f/\partial x$ is required to be bounded (this implies it is Lipschitz with respect to $x$, for any $t$), and this is true for the second equation where such derivatives gives $1$, but not for the first, where it gives $2x$.

Here is a paper relating to this matter: Ref.


Prove that the sequence $u_i$ is periodic or the linear relation is trivial? I’m trying to prove the following statement for any field $F$ (with no zero-divisors). I don’t know for sure that it’s true, but I’m pretty sure, and I would appreciate some advice about how to come up with an elegant proof that doesn’t involve refer to other advanced theorems.

Suppose that $\alpha_i,u_i\in F$, and that
$$\alpha_1 u_1+\alpha_2 u_2+...+\alpha_n u_n=0$$
which also equals $0$ if we cyclically permute the $u_i$. It is also known that $\sum \alpha_i=0$ but $\sum u_i \ne 0$. How can we prove that either the sequence $u_1,u_2,...u_n$ is “cyclically periodic” or that all $\alpha_i=0$?

Whenever I try to prove this, I just keep going in circles. Can someone give me a hint?

NOTE: By “cyclically periodic” I mean that $u_{i+k}=u_i$ for all $i$ for some $0<k<n$, if we define $u_m=u_{m\bmod n}$ for $m > n$.

From the finite sequence $u_1,\ldots,u_n$, you can create an infinite sequence $(v_i)$ by setting $v_i := u_{i\pmod{n}}$. The linear relation you gave becomes $$\alpha_1 v_i+\cdots + \alpha_n v_{n+i}=0$$ which holds for all $i$. This shows that $(v_i)$ is a linear recurrence sequence. But on the other hand, $(v_i)$ takes values in the finite set $\{u_1,\ldots,u_n\}$.

It's not hard to show that if you have a linear recurrence with values in a finite set, then it must be periodic.


Evaluating $\sum\limits_{n=1}^{\infty} \frac1{n}\left(\frac{np}{p+n}\right)^{n+1}$ for $0<p<1$ I'm trying to find the value of the following sum

$$\sum_{n=1}^{\infty} \frac1{n}\left(\frac{np}{p+n}\right)^{n+1}$$

where $0<p<1$. Any ideas? Thanks.

I can't comment so that's why i'm giving an answer but isn't it true that    $\frac 1n \left( \frac {np}{p+n} \right)^{n+1} = \frac 1n \frac {n^{n+1}p^{n+1}}{(p+n)^{n+1}} =  \frac {n^np^{n+1}}{(p+n)^{n+1}} = \left( \frac {n^{-1}p}{p+n} \right)^{n+1}$
so couldn't you just sum     $\sum _{n=1}^{\infty } \left( \frac {n^{-1}p}{p+n} \right)^{n+1}$ using    $\frac {a}{1-r}$ with    $a = \left( \frac {p}{p+n} \right)^2$ and    $r = \frac {n^{-1}p}{p+n}$ which yields    $\sum _{n=1}^{\infty } \left( \frac {n^{-1}p}{p+n} \right)^{n+1} = \frac {\left( \frac {p}{p+n} \right)^2}{1-\frac {n^{-1}p}{p+n}} = \frac{p^2}{(p+n)^2} \frac {p+n}{p+n- n^{-1}p}$? or have i missed something? hope that helps.


Misanthropic Neighbors This week's 538 riddler is:

  The misanthropes are coming. Suppose there is a row of some number, N, of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s the expected fraction of occupied houses as the development gets larger, that is, as N goes to infinity?

If we define $E_N$ to be the expected number of occupied houses given $N$ houses in a row, then I could work out the recurrence as: $$E_N = 1 + \frac2N\sum_{i=1}^{N-2}E_i$$ just based on the open spaces left after we fix the first misanthrope moving in. However, I have no idea where to go from here - either in finding a closed form for $E_N$ that I can take the limit of or coming up with a different way of thinking about this problem. What's the next step?

Michael pointed out that an equivalent recurrence relation is
$$ (n+1)E_{n+1} = n E_n + 2E_{n-1} + 1.$$
We can solve this with generating functions. Let
$$f(x) = \sum_{n=0}^\infty E_n x^n.$$
Then we can construct a few useful quantities from this. First, note that
$$\frac{df}{dx} = \sum_{n=1}^\infty n E_n x^{n-1}.$$
Multiplying this by $x$ gives the useful relation
$$ x \frac{df}{dx} = \sum_{n=1}^\infty n E_n x^n.$$
Additionally, note that
$$ \frac{df}{dx} = E_1 + 2 E_2 x + 3E_3 x^2 + \cdots = E_1 + \sum_{n=1}^\infty (n+1) E_{n+1} x^n.$$
Multiplying $f(x)$ by $x$ gives us
$$x f(x) = \sum_{n=0}^\infty E_n x^{n+1} = \sum_{n=1}^\infty E_{n-1} x^n,$$
where we shifted the index in the last step.
Finally, from Taylor expanding about $x=0$, we have that
$$ \frac{x}{1-x} = \sum_{n=1}^\infty x^n.$$
Using this, we can write
$$ \frac{df}{dx} - E_1 = \sum_{n=1}^\infty (n+1)E_{n+1} x^n = \sum_{n=1}^\infty \left( nE_n + 2E_{n-1} + 1\right) = x \frac{df}{dx} + 2x f + \frac{x}{1-x}.$$
This gives us a first order differential equation for $f$. If there's only one house, then it clearly gets occupied, so $E_1 = 1$. Rearranging yields
$$ \frac{df}{dx} = \frac{2x}{1-x} f + \frac{1}{(1-x)^2}.$$
This differential equation can be solved exactly to give
$$f(x) = \frac{e^{-x} \sinh(x)}{(1-x)^2},$$
where we use the fact that $f(0) = E_0 = 0$ as our initial condition (since no houses can be occupied if there are no houses in the first place). Expanding this function in a Taylor series about $x=0$ gives the coefficients $E_n$ since
$$ E_n = \frac{1}{n!} \left.\frac{d^n f}{dx^n}\right|_{x=0}.$$
After playing with the series expansion a bit, you can show that
$$ E_n = \frac{n+1}{2} - \frac{1}{2}\sum_{k=0}^n (-2)^k \frac{(n-k+1)}{k!},$$
which is a nice closed form solution for $E_n$. From here, you can work out $\lim_{n\to \infty} E_n/n$ which should give you the expected fraction of occupied houses.

If there are n houses. Then 1 accepted event is 1 house out of n or 2 out of n all the way to n/2 out of n

So fraction of occupied houses is sum of 1,2,...n/2   Divided by nsqaured

Take a limit if n is infinity will be 25%


The language accepted by given Turing Machine Given a Turing Machine
$$M = (\{q_0, q_1\}, \{0, 1\}, \{0, 1, B\}, δ, B, \{q_1\})$$
Where $δ$ is a transition function defined as
$$δ (q_0, 0) = (q_0, 0, R)$$
$$δ (q_0, B) = (q_1, B, R)$$
The language $L(M)$ accepted by Turing machine is given as :

$0^*1^* $
$ 00^*$
$10^* $
$1^*0^*$

My attempt:

We, can draw DFA for given transition function of Turing Machine, and expression should be as $0^*$, but official key is given option $(2)\space 00^*$.

  Can you explain it, please?

$00^∗$  is subset of $0^∗$, so, this TM can also accept the all string of $00^∗$. However other than $00^∗$ only $ϵ$ is also accepted by given TM.


Why is $\sqrt[n]{a}$ equal to $a^{1/n}$ only when $n\ge 2$? My teacher gave us the following logarithmic equation to solve for $x$.

$\log 4$ + $(1+1/(2x))\log 3$ = $\log(\sqrt[x]{3} + 27)$

As you can see it involves the term $\sqrt[x]{3}$, which later in the solution was converted into $3^{1/x}$. The values of $x$ obtained were $1/4$ and $1/2$. However my teacher said these two values were to be rejected, citing this "rule"; $\sqrt[n]{a}$ is equal to $a^{1/n}$ only when $n\ge 2$. Why is this so? My teacher didn't provide any reasoning for this and told us just to remember this rule and apply it accordingly.

$\sqrt[n]{x}$ is typically treated as equivalent to $x^{\frac{1}{n}}$, as seen in symbolic solvers such as WolframAlpha.
However, there is a lot of convention needed to be taken into account. Typically, the radical is used when dealing with $n\in\mathbb{N}$. As dxiv pointed out, the case when $n=1$, i.e; $\sqrt[1]{x}$ is redundant, so we're left with the cases when $n\geq2$.
Personally, I use them interchangeably, so will your calculator. We can presume $\sqrt[\sqrt{2}]{x}$, for example, should be treated not so differently to $x^{\frac{1}{\sqrt{2}}}$. Obviously, the latter notation is preferred in this case.
I know some mathematicians differentiate the use in complex analysis, for instance. It's convention to use the radical only when referring to a principal root, and $\frac{1}{n}$ when dealing with other branches.
Should you be docked marks for using them interchangeably? Probably not.
Will it affect calculation? If in your calculation separate branches need to be taken into account, or the more likely scenario, the condition that $n\in\mathbb{N}$ is implied, as seems to be the case in the eyes of your teacher.

Because we define $y=\sqrt[n]x$ as the inverse function of $y=x^n$ in the suitable interval just for $n\in\mathbb N$ and not for other numbers.


$x^n +a_{n−1}x^{n−1} + · · · + a_1x + a_0 ∈ Z[x]$, and it has a linear factor which must be of the form $x − a$ with $a$ dividing $a_0$. Prove that if $x^n +a_{n−1}x^{n−1} + · · · + a_1x + a_0 ∈ Z[x]$, and it has a
linear factor, then this linear factor must be of the form $x − a$ with
$a$ dividing $a_0$.
I'm really struggling to understand this question, any help would be great.

If f(x) = $x^n +a_{n−1}x^{n−1} + · · · + a_1x + a_0 $ has a linear factor, then the following equation is true :
\begin{align} x^n +a_{n−1}x^{n−1} + · · · + a_1x + a_0   = (bx-a)(g(x)+c) =b(\frac{x}{b}-\frac{a}{b})(g(x)+c)\end{align}
where b$\neq0$ and g(x) is a n-1 order function that does not have a constant term.
For this equation, RHS constant term is  $\frac{ac}{b}$, the linear term is $\frac{x}{b}$, only when b=1 this factor becomes  (x-a), in which case   a$_0$ $\to$ ac=a$_0$, or  c=$\frac{a_0}{a}$ . So, the statement is not true.


Using A Venn Diagram To Illustrate Relationships The problem I am working on is:

  Use a Venn diagram to illustrate the relationship $A⊆B$ and $B⊆C$.

From my understanding, I should be drawing several Venn diagrams, corresponding to the different situations that are possible.

Since $A \subseteq B$ does not specify whether $A$ is a proper subset or not, we have two situations:

$(1)$: $A=B$

$(2)$: $A \subset B$

The same two situations apply to $B \subseteq C$

(This part is just a side note, but I'd appreciate a corroboration of my reasoning)
Also, by the transitive law, since for x we find in A, it is true that we can find it in B ($A \subseteq B$); and since for every x in B, it is true that we can find it in C ($B \subseteq C$), we can say that $A \subseteq C$. This is reasonable, because all of A is contained in B, and all of B is contained in C, so all of A must be contained in C.

Now, the different situations we have are as follows:

$(1)$: $A=B$ and $B \subset C$

$(2)$: $A \subset C$ and $B \subset C$

$(3)$: $A=B$ and $B=C$

$(4)$: $A \subset C$ and $B=C$

So, I would have to make a Venn diagram for each situation?

Here's the list I came up with, with the "$\subsetneq$" symbol meaning "is a proper subset of":

$(1): A = B\;$ and $\;B = C.\;$ (And hence $A = C$ by transitivity)

$(2): A = B\;$ and $\;B \subsetneq C.\;$ (And hence $A \subsetneq C$, necessarily).

$(3): A \subsetneq B\;$ and $\; B = C.\;$ (And hence, $A \subsetneq C$, necessarily).

$(4): A \subsetneq B\;$ and $\; B \subsetneq C.\;$ (And hence, $A \subsetneq C$, necessarily).

Yes, the Venn diagram for each of the four scenarios would necessarily be different, if we are distinguishing between equality of sets and "being a proper subset of" a set, so you can cover all possible relationships by drawing a Venn diagram for each case, separately.
For example, case $(1)$ would be a single circle, labeled A = B = C. Case two would be a circle A = B, contained within the larger circle C. etc...

Isn't the proposed solution the euler diagram, while the venn diagram would rather look like that?

venn diagram


Is Lagrange's mean value theorem is valid on $x^{1/3}$ in $[-1,1]$? Suppose I have a function $f(x)=x^{\frac{1}{3}}$ in interval $[-1,1]$ , is lagrange's mean value theorem valid here ? $f(x)$ is continuous in this interval but there's a confusion in it's derivative. What about it's derivative at $x=0$ it looks like not defined as $f'(x)=\frac{1}{3}x^{-\frac{2}{3}}$.

Lagrange's mean value theorem in it's standard form can not be applied since as you correctly point out $x^{\frac{1}{3}}$ does not have a finite derivative at $0$. To be perfectly honest off the top of my head I can't think of a function which has the behaviour of $x^\frac{1}{3}$  (i.e. has an infinite derivative at one point and is differentiable everywhere else) yet does not satisfy the conclusion of the mean value theorem. Which should not be taken to mean there are no such functions though.

The theorem requires the function to be differentiable in $(-1,1)$, and it isn't so you can't use it. However, there is a point where $f'(c)=\frac{f(b)-f(a)}{b-a}$:
$$ f'(c)=\frac{1}{3 \sqrt[3]{c^2}} = \frac{f(1)-f(-1)}{1-(-1)} = 1 \Leftrightarrow \sqrt[3]{c^2}=\frac{1}{3} \Leftrightarrow c=\pm \sqrt{\frac{1}{27}}$$


Motivation for the differentiability of a function $f: D \subseteq \Bbb R^m \rightarrow \mathbb R$ Suppose a function $f: D \subseteq \Bbb R^m \rightarrow \mathbb R$ is defined on an open subset $D \subseteq \Bbb R^m$. Then, we define that : $f$ is differentiable at $p$ if there exists a linear function $L: \Bbb R^m \rightarrow \Bbb R$ and a function $\eta: D_p \subseteq \Bbb R^m \rightarrow \Bbb R$ such that :
$$f(p+h)-f(p)=L(h)+ ||h|| \eta (h)$$
where $h \in D_p, ~~\lim_{||h|| \rightarrow 0 }\eta(h)=0.$
$D_p$ is defined as $=\{h \in \Bbb R^m:p+h \in D\}$

I wanted to understand the motivation behind this definition. Here's what I could think:
$\lim_{h \rightarrow 0} \dfrac{f(p+h)-f(p)}{||h||}$ represents the derivative at $p$
$\dfrac{f(p+h)-f(p)}{||h||}$ can be approximated as $f'(p)+\eta(h)$ where $\eta(h)$ represents an error function.
Thus, $f(p+h)-f(p)= ||h||f'(p) + ||h|| \eta(h)$.
Now, our definition calls $||h|| f'(p)$ as a linear function $L(h)$.
If we can prove that $||h|| f'(p)$ is linear, then this argument is a sufficient motivation for this definition of differentiability of function $f$.
But: for $\lambda \in \Bbb R: ||h_1+\lambda h_2|| f'(p) \ne ||h_1||f'(p) + |\lambda|~||h_2||f'(p)$ and hence not linear !!
If it would have been, there would have been a perfect motivation for the definition. Now, in  such a case, why do we call $L(h)$  a linear function in the original definition?
Could someone tell me how did this definition come about. What is the motivation behind this definition? Thanks!

You said:

$\lim_{h \rightarrow 0} \dfrac{f(p+h)-f(p)}{||h||}$ represents the derivative at $p$

No, it doesn't. Next, you write:

$\dfrac{f(p+h)-f(p)}{||h||}$ can be approximated as $f'(p)+\eta(h)$ where $\eta(h)$ represents an error function.

Again, this is false.

The definition of differentiability is that there exist a linear function $L:\Bbb{R}^m\to \Bbb{R}$ such that
\begin{align}
f(p+h) - f(p) &= L(h) + \lVert h\rVert\eta(h) \tag{$\ddot{\smile}$}
\end{align}
where $\lim_{h\to 0} \eta(h) = 0$. Typically, the notation used is that $L := Df_p$. Also, if we define $\Delta f_p(h) := f(p+h) - f(p)$, then the above equation becomes very memorable:
\begin{align}
\Delta f_p(h) &= Df_p(h) + \lVert h\rVert \eta(h).
\end{align}
This is exactly the formal way of saying that differentiable functions are locally approximately linear, because it says the actual change in the function (at the point $p$ by an amount $h$) $\Delta f_p(h)$ is equal to a linear part $Df_p(h)$ plus an error term $\lVert h\rVert\eta(h)$, and this error term is "small" in the sense $\eta(h)\to 0$ as $h\to 0$.
So, to address (1) above, it is $L= Df_p$ which is the derivative at $p$ (by definition).
For (2), we have
\begin{align}
\dfrac{f(p+h) - f(p)}{\lVert h \rVert} &= \dfrac{Df_p(h)}{\lVert h\rVert} + \eta(h) \\
&= Df_p\left(\dfrac{h}{\lVert h \rVert}\right) + \eta(h)
\end{align}
so, you can interpret this however you want. But the point remains: $L(\cdot) = Df_p(\cdot)$ is by definition a linear transformation which approximates changes in $f$ (i.e which is approximately equal to $\Delta f_p(\cdot)$).

In the comments you ask:

But, if we were to go by the basic definition of a derivative: it should be $f′(p)\cdot \lVert h\rVert$.

What do you mean by basic definition? The definition you wrote in the question is the definition of derivative in multivariable calculus. Do you mean the definition of single-variable calculus? If that's what you meant then the thing is you need to learn to re-interpret the definition in single variable calculus. We are often taught in the case of $f:\Bbb{R}\to \Bbb{R}$ to think of $f'(p)$ geometrically as "the instantaneous slope at $p$", because we define (if the limit exists)
\begin{align}
f'(p):= \lim_{h\to 0}\dfrac{f(p+h) - f(p)}{h}
\end{align}
so of course, geometrically this forces us to think in terms of slopes.
What I'm now suggesting to you is to think in terms of "local linear approximations (this allows for a much easier transition to multivariable calculus) and to rewrite this definition as
\begin{align}
\lim_{h\to 0}\dfrac{f(p+h) - f(p) - f'(p)\cdot h}{h} &= 0 \tag{$*$}
\end{align}
In this case, the mapping $\Bbb{R}\to \Bbb{R}$, $h\mapsto f'(p)\cdot h$ is a linear transformation which approximates the actual change $\Delta f_p(h):= f(p+h) - f(p)$.
Note that in this case, we are able to divide by $h$ because it is a real number and not a vector. But notice that $(*)$ is entirely equivalent to $(**)$:
\begin{align}
\lim_{h\to 0} \dfrac{|f(p+h) - f(p) - f'(p)\cdot h|}{|h|} &= 0 \tag{$**$}
\end{align}
and in this form, the relation with definition of differentiability in higher dimensions is much more clear, because $(\ddot{\smile})$ is entirely equivalent to the following statement (with appropriate domains and target spaces):

There exists a linear transformation $L$ such that
\begin{align}
\lim_{h\to 0}\dfrac{\lVert f(p+h) - f(p) - L(h)\rVert}{\lVert h\rVert} &= 0.
\end{align}

The motivation is this:
You want to know how $f(x$) changes with few movements of $x$ arround some open set $V$ with $x$ inside it. The task can be reached with a estimation of $f(x) \equiv T(x)$ where $T(x)$ is a linear function.
If this is true, then you can say: "oh well, I wanted to know what happened with $x$ moving inside the open set $V$, I can do this by $x+tu$, where $t$ is a tiny number and $v$ a small direction vector, so If I examine $$T(x+tu)=T(x)+tT(u).$$ My goal is to find the best $T(x)$ for $f(x)$, so I look for $T(x)$ from last equation:
$$T(x) = T(x+tu) - tT(u)$$
If $t$ is small as possible, then I'm taking the best linear function approximation of $f$ trough $x$ point.
You can identify some elements with respect the derivative definiton, such as the factor $t$ which is equivalent to your $||h||$, both must to be small enought for the good aproximation.


The three forces acting on the beam can be replaced with a single equivalent force R. Determine the angle θ and R. I was able to come up with the below equations but after the last one, regarding the moment of resultant, I got stuck.

Fx = 25kNcos(40) + 60kNcos(θ) - 80kNcos(50)

Fy = 25kNsin(40) + 60kNsin(θ) + 80kNsin(50)

∑Mo = Rd

[Moment at P2 point.]

Rd = -25sin(40)(4) + 80sin(50)(6)

Solve for theta first then solve sum of Fx and Fy:


Probability with replacement marbles Two marbles are drawn at random and with replacement from a box containing $2$ red, $3$ green, and $4$ blue marbles.
  Let's define the following events:
 A={two red marbles are drawn}
 B={ two green marbles are drawn}
C={two blue marbles are drawn}.

Let's say i want to find the probability of A.
 Since it's with replacement the first time i'm drawing, the probability would be $\frac29$ and the second time would also be $\frac29$ which would be $\frac4{81}$.
 Is this the correct way of thinking this?

Yes, you are on a right track:

Total number of balls always remains $9$.

For event $A$:
There are $2$ Red balls, for both draws:
$$P(A)=\frac29\cdot \frac29=\frac4{81}$$
For event $B$:
There are $3$ Green Balls, for both draws:
$$P(B)=\frac39\cdot\frac39=\frac{9}{81}$$
For event $C$:
There are 4 Blue Balls,  for both draws:
$$P(C)=\frac49\cdot \frac49=\frac{16}{81}$$

There is a very simple equation that everyone seems to forget to mention: $(x/t)^n$ where $x$ is the number of desired objects, $t$ is the total amount of objects, and $n$ is the number of times that you are drawing the object. For $P(A)$ it would be as follows: $(2/9)^2$; $P(B)$ would be: $(3/9)^2$ or $(1/3)^2$; etc.


Extending generating function into series. There is a reccurent equation: $a_{n+2}-2\cos(\phi)a_{n+1}+a_n=0$ and I must to solve it. I found generating function: $$A(t) = \dfrac{1 - t\cos(\phi)}{1 - 2t\cos(\phi) + t^2},$$ but I can not extend it into series to solve this equation. Please help me.

Set $z=te^{i\phi}$ then your generating function can be written as
$$A(t)=\frac{1-t\cos(\phi)}{1-2t\cos(\phi)+t^2}=\frac{1-\frac{1}{2}(z+\bar{z})}{(z-1)(\bar{z}-1)}=\frac{(1-z)+(1-\bar{z})}{2(z-1)(\bar{z}-1)}=\frac{1}{2}(\frac{1}{1-z}+\frac{1}{1-\bar{z}})$$
For $|z|<1$ we have the following series expansion
$$A(t)=\frac{1}{2}(\sum^{\infty}_{k=0}z^k+\sum^{\infty}_{k=0}\bar{z}^k)=\frac{1}{2}(\sum^{\infty}_{k=0}2t^k\cos(k\phi))=\sum^{\infty}_{k=0}t^k\cos(k\phi)$$
So you have $a_k=\cos(k\phi)$. Now notice that
\begin{align}a_{k+2}-2\cos(\phi)a_{k+1}+a_k&=\cos((k+2)\phi)-2\cos(\phi)\cos((k+1)\phi)+\cos(k\phi)\\&
=\cos((k+2)\phi)-2(\frac{\cos((k+2)\phi)+\cos(k\phi)}{2})+\cos(k\phi)\\&=
\cos((k+2)\phi)-\cos((k+2)\phi)\\&=
0
\end{align}
so $a_k=\cos(k\phi)$ is a solution.

HINT:

$(e^{i n \theta})$ , $(e^{-i n \theta})$ or if you want, $(\cos(n \theta))$, $(\sin(n \theta))$ are solutions.


Parameterizing a function where you cannot isolate y If I'm given a curve as an implicit function, is there some algorithm for obtaining a parametrization of the curve?

For example, how would I parameterize

$\frac{2x}{y} - \frac{3y}{x} = 8$

I know I might use $\cosh$ and $\sinh$, but I'm wondering if there's a surefire way to parameterize a curve, when you have a formula for it like this.

I can't isolate y, clearly, but you can re-arrange it to

$ 2x^2 - 3y^2 - 8xy = 0 $

I'm hoping there's a way to find a trig rep for an arbitrary equation that I don't know about.

Where do you go from here?

Is it just trial and error / recognizing the form and choosing trig functions?

Quoting Arturo Magidin:

There is no general algorithm that will always yield a good parametrization of any curve. Relatively simple trigonometric parametrizations cannot work in general, because they always yield closed curves (being periodic). Parametrizing curves generally takes ingenuity, not unthinking application of general rules, though practice and familiarity with a variety of tricks will help (much as with integration)


Dividing a paper into 3 parts using folding So I saw this video : https://www.youtube.com/watch?v=V7UJxeMlowQ, and it got me wondering: Why does that method divide the paper into exactly 3 equal rectangles, so I turned it into a math problem:

Draw a line from one vertex of a square to the midpoint of the opposite side. Draw a perpendicular bisector of the line you've drawn previously. Prove that the intersection of side of the square reflected over the perpendicular bisector to the other side of the square divides the side of the square it intersects in ratio $1:2$

Here is the picture I drew in Geogebra, in case the wording isn't clear:

The line $BC$ is reflected over the perpendicular bisector of $EC$, and the line $EI$ is formed. Prove that $AI$=$2IB$

Please don't use trigonometry while solving this problem, I'm not particulary good at it and I won't understand it.

If you like analytic geometry, you can set the coordinate system: $B(0,0)$, $A(0,a)$, $C(a,0)$. Then $E(\frac{a}{2},a)$, and $EC:\ y=-2x+2a$. If $M$ is a centre of $EC$, then $M(\frac{3a}{4},\frac{a}{2})$, and perpendicular through $M$ is $p:\ y=\frac{1}{2}x+\frac{a}{8}$. $p$ intersects $BC$ in $N(-\frac{a}{4},0)$, and $EN:\ y=\frac{4}{3}x+\frac{a}{3}$. The intersection of $EN$ and $AB$ is $I(0,\frac{a}{3})$, which implies $AI=2IB$.

If you denote by $M$ the centre of $EC$, perpendicular meets $BC$ in $N$, and $CD$ in $K$. By Pythagorean theorem, $EC=\frac{a\sqrt{5}}{2}$, and $MC=\frac{a\sqrt{5}}{4}$. By symmetry $\triangle EDC\sim\triangle KMC$, we have $\frac{KM}{MC}= \frac{ED}{DC}= \frac{1}{2}$, so $KM= \frac{a\sqrt{5}}{8}$. Then $KC= \frac{5a}{8}$ by Pythagorean theorem. By symmetry $\triangle KCN\sim\triangle EDC$ we have $\frac{CN}{CK}= \frac{DC}{DE}=2$, so $CN=\frac{5a}{4}$. Hence, $BN=CN-a=\frac{a}{4}$. By symmetry $\triangle IBN\sim \triangle IAE$ we finally have $\frac{IB}{IA}= \frac{BN}{AE}= \frac{1}{2}$.


Why is $\int_{0}^{t} e^{nt} \mathrm{\ dt} = \frac{1}{n} \left(e^{nt} - 1\right)$? [solved; notation is also faulty in the first place] If $e^{nt}$ can also be written as $\left(e^n\right)^t$ or $\left(e^t\right)^n$, $\int_{0}^{t} e^{nt} \mathrm{\ dt}$ can also be written as $\int_{0}^{t} \left(e^{t}\right)^n \mathrm{\ dt}$ which can also be written as … well, what? I need some more steps of calculation in order to understand why the solution is $\frac{1}{n} \left(e^{nt} - 1\right)$.

If $n \not= 0$, you are a fan of the power law, and like complicated answers to simple questions you could  compute $$\int_0^t e^{nx} \, dx = \int_0^t (e^x)^{n-1} e^x \, dx = \int_1^{e^t} y^{n-1} \, dy = \left[ \frac{y^n}{n} \right]_1^{e^t} = \frac{e^{nt} - 1}{n}$$ using the substitution $y = e^x$, $dy = e^x \, dx$.


Searching a Group Homomorphism Is there a non-zero group homomorphism from the abelian group $\prod_{n=2}^\infty \mathbb Z_n$ to $\mathbb Q$?

I  thought  of the map taking $(1,1,...)$ to $1$, but could not make through. Thanks for any suggestion!

No there isn't. The image of any finite subgroup must be $\{0\}$, which is the only finite subgroup of rationals, because the image of a finite group must be finite. So there's only the zero  homomorphism


What about the Fuchsian groups make them stand out? Why do we stop at Fuchsian groups (I.e. discrete subgroups of automorphisms of the hyperbolic plane) when we study things like quotients and what not?

Is there a maximalist or universality property behind that distinction?

Who stops? Not me. We continue on to:

Lattices in Lie groups
Cayley graphs
Geometric group theory

and on and on from there...

Depends on what kind of whatnot you want to study. It's a fact that any hyperbolic Riemann surface (that is, any connected complex manifold of dimension one except the Riemann sphere, complex tori, or the cylinder) can be written as the quotient of the upper half-plane by a Fuchsian group.

So the study of Riemann surfaces is basically equivalent to the study of Fuchsian groups.


what does the triangle in PDE notation mean? what does the triangle sign used in PDE equations represent?

example:
$$u_{tt}- \Delta u =0$$

I took the below example from the Evan's book PDE  p.4 (example 9). The equation is presented as the wave equation. I am not familiar with this notation and it is confusing to me. I know the wave equation in the form of $$u_{tt} - u_{xx} = 0$$
Could anybody clarify the notation? Are those two equations the same?

A capital delta $\Delta$ is sometimes used as notation for the Laplacian operator, see e.g. https://en.wikipedia.org/wiki/Laplace_operator. So yes the two equations are the same assuming that the Laplacian is one-dimensional in the first equation.

The upside triangle ($\nabla$) is called the Laplacian. Usually one starts using it as you get PDE's that involve not just $u(x,t)$, but deals with function such as $u(x, y, t)$ or $u(x, y, z, t)$. Hence, with increments of the dimension the Laplacian is generalization of the second partial with respect to the coordinates.

\begin{equation*}
\nabla\phi=\phi_x+\phi_y
\end{equation*}
oR more general,
\begin{equation*}
\nabla\phi=\phi_{x_1}+\dots+\phi_{x_n}
\end{equation*}
where $x_i$ are nothing more than the coordinates that your applying the second partials to, namely the Laplacian operator.


How many 7 letter 'words' can be made from the English alphabet which contains at least 3 vowels? Just a little bit unsure about this question:

How many 7 letter 'words' can be made from the English alphabet which contains at least 3 vowels?

And by 'words' I mean just a string of alphabet - does not have to be a real world in dictionary. I do know that you need to use Inclusion/Exclusion principle which says:

$|A \cup B| = |A| + |B| - |A\cap B|$

Let U be the set of all words containing 7 letters (26 letters to the power 7)
The only thing I'm not sure is what would be the sets A and B? Or do I need a third term C?

It would be easier to count the number of words that have $2$ or fewer vowels, and then subtract this number from the total number of words (which you have already computed).

I assume that by "$3$" or more vowels" you mean $3$ or more occurrences of vowels, so in particular a word with 2 e's, 2 i's, and the rest consonants qualifies.

How many words are there with no vowels? Clearly
$$21^7$$
 if, as per usual convention, we agree that there are $5$ vowels.

How many words with $1$ vowel?  Where the vowel occurs can be chosen in $\binom{7}{1}$ ways. For each of these ways, the vowel can be chosen in $5$ ways.  And once you have done that, the consonants can be filled in in $21^6$ ways, for a total of
$$\binom{7}{1}(5)(21^6)$$

Finally, how many with $2$ vowels? The location of the vowels can be chosen in $\binom{7}{2}$ ways.  Once this has been done, the actual vowels can be put into these places in $5^2$ ways.  And then you can fill in the consonants in $21^5$ ways, for a total of
$$\binom{7}{2}(5^2)(21^5)$$

Add up the $3$ numbers we have obtained, subtract from $26^7$.

Our argument was a little indirect. We could instead find, using the same sort of reasoning, the number of words with $3$ vowels, with $4$ vowels, with $5$, with $6$, with $7$, and add up.  This is only a little more work than the indirect approach.  But any saving of work is helpful!  Also, the indirect approach that was described lets us concentrate on pretty simple situations, the most complicated of which is the $2$ vowel case.

Remark: The calculation we have done is closely connected to the Binomial Distribution, and if you have already covered this, it may be the point of the exercise.  So if you know about the Binomial Distribution, imagine the letters to be chosen at random.  Then the number of patterns with $3$ or more vowels is the probability of $3$ or more vowels, multiplied by $26^7$.

Calculate: Let  = {, , ,…, , , , , } be the set of letters of the alphabet. Determine how many 5-letter anagrams can be formed with the letters of  so that the first and last letters are two distinct vowels and the remainder are three distinct consonants.


Inverse Functions and their intersection points Say you have $f(x) $ and $g(x)$ and $g(x) = f^{-1}(x) $.

I observed that these two curves need not intersect, for example with $f(x) = e^x$ and $g(x) = \ln x $ never intersecting each other.

I also observed that a function can either have one, two, or three intersections with its inverse, but I was unable to find a function which has more than 3 intersection points with its inverse.

How would I prove or disprove the hypothesis that an elementary function and its intersection can only have up to 3 intersection points? Any counterexamples are appreciated!

Consider $f(x) = x$.

Note that $g(x) = f^{-1}(x) = x = f(x)$.

So, there are infinitely many intersections!

  Good solution. I am aware of the infinite intersections solution, but does anyone have any functions which have 4 or more intersections with
  their inverse (but not an infinite number of intersections)?

Consider, over any finite interval say $X$, $f(x) = x + \sin x$.

Over the interval $X$ there are finitely many intersections. The exact number depends on $X$ itself. But you can have any finite number of
intersections.

At first, I was unsure of how to find the inverse of that function, so I decided to graph it to verify my claim and I'm right!

http://www.wolframalpha.com/input/?i=find+inverse+of+f(x)+%3D+x%2Bsin(x)

A function can have over $3$ intersection points with its inverse relation.

For example, take $f(x)=x^4-3x^2+2x-3$.

Finding points of intersection of $f(x)$ and $f^{-1}(x)$:

So, there are $4$ points of intersection. $4>3$, thus disproven.


An inequality by using general Hölder's inequality Let $w$ be a weight function and $\frac{1}{p}=\frac{1}{p_1}+\frac{1}{p_2}+\dots+\frac{1}{p_n}$. For suitable functions let $\overrightarrow{f}=(f_1,f_2,\dots,f_n)$ and operator $T$ satisifies the condition
$$
T(\overrightarrow{f})(x)\leq \prod_{i=1}^{n}f_{i}(x).\tag{*}
$$
By using (*) and generalization of Hölder's inequality, I get
$$
\left(\int_{\mathbb{R}^n}|T(\overrightarrow{f})(x)w(x)|^pdx\right)^{\frac{1}{p}}\leq \left(\int_{\mathbb{R}^n}| \prod_{i=1}^{n}f_{i}(x)w(x)|^pdx\right)^{\frac{1}{p}}\leq \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|f_{i}(x)|^{p_i}w(x)^pdx\right)^{\frac{1}{p_i}},
$$
where I apply Hölder's inequality  for the measure $d\mu(x)=w(x)^p$.

But the paper which I read now writes this inequality as following
$$
\left(\int_{\mathbb{R}^n}|T(\overrightarrow{f})(x)w(x)|^pdx\right)^{\frac{1}{p}}\leq \left(\int_{\mathbb{R}^n}| \prod_{i=1}^{n}f_{i}(x)w(x)|^pdx\right)^{\frac{1}{p}}\leq \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|f_{i}(x)w(x)|^{p_i}dx\right)^{\frac{1}{p_i}}.
$$
Which one is true?

Your result is absolutely true:

Here is a way to check it: Let $\mu $ be the  measure $$d\mu(x)= w^p(x)dx$$

Now we apply the Holder inequality w.r.t the measure $\mu$ then we have,

$$\left(\int_{\mathbb{R}^n}|T(\overrightarrow{f})(x)|^p\color{red}{d\mu(x)}\right)^{\frac{1}{p}}\leq \left(\int_{\mathbb{R}^n}| \prod_{i=1}^{n}f_{i}(x)|^p\color{red}{d\mu(x)}\right)^{\frac{1}{p}}\leq \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|f_{i}(x)|^{p_i}\color{red}{d\mu(x)}\right)^{\frac{1}{p_i}},$$

replacing $\mu $ by its value we get: $$\left(\int_{\mathbb{R}^n}|T(\overrightarrow{f})(x)w(x)|^pdx\right)^{\frac{1}{p}}\leq \left(\int_{\mathbb{R}^n}\color{red}{\left|\prod_{i=1}^{n}f_{i}(x)\right|^p} w^p(x)dx\right)^{\frac{1}{p}}\leq \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|f_{i}(x)|^{p_i}w(x)^pdx\right)^{\frac{1}{p_i}},$$

Which provide your result.

Warning: However, as $\color{blue}{xa_1\times xa_2\times xa_3 = x^3\times a_1\times a_2\times a_3}$,   note that there might be confusion between the following: $$\left|\prod_{i=1}^{n}f_{i}(x)w(x)\right|^p = w^{\color{blue}{np}}(x)\left|\prod_{i=1}^{n}f_{i}(x)\right|^p$$
and $$w^p(x)\left|\prod_{i=1}^{n}f_{i}(x)\right|^p =\left|\prod_{i=1}^{n}f_{i}(x)\right|^p\times w^p(x)$$

Use that:
$\left(\int_{\mathbb{R}^n}| \prod_{i=1}^{n}f_{i}(x)w(x)|^pdx\right)^{\frac{1}{p}}\leq \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|f_{i}(x)|^{p_i}w(x)^pdx\right)^{\frac{1}{p_i}}$

We can rename $\tilde{f}_i(x) = f_i(x)w(x)$ and $\tilde{w}(x) \equiv 1$ and get

$\left(\int_{\mathbb{R}^n}| \prod_{i=1}^{n}f_{i}(x)w(x)|^pdx\right)^{\frac{1}{p}} \\
= \left(\int_{\mathbb{R}^n}| \prod_{i=1}^{n}\tilde{f}_{i}(x)\tilde{w}(x)|^pdx\right)^{\frac{1}{p}} \\
\leq \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|\tilde{f}_{i}(x)|^{p_i}\tilde{w}(x)^pdx\right)^{\frac{1}{p_i}} \\
= \prod_{i=1}^{n}\left(\int_{\mathbb{R}^n}|f_{i}(x)w(x)|^{p_i}dx\right)^{\frac{1}{p_i}} $

Edit: So I'd say both inequalities are true.


Quaternion Multiplication: What is the correct way of doing it? I am not very familiar with quaternions, I was just doing a programming homework were I had to implement quaternions' arithmetic, however I got puzzled by the multiplication of 2 quaternions.

Let's say I have the following:

$a = \alpha_1 + \beta_1i+\gamma_1j+\delta_1k$

$b = \alpha_2 + \beta_2i+\gamma_2j+\delta_2k$

I have been given the following rules $i^2=j^2=k^2=-1$, $ik=-j$, $ij=k$, $ji=-k$, $jk = i$, $ki = j$, $kj = -i$

Doing the algebra I get the following expression for the product of a and b:

$$\alpha_1\alpha_2 - \beta_1\beta_2 - \gamma_1\gamma_2 - \delta_1\delta_2 \\
+i(\alpha_1\beta_2+\beta_1\alpha_2+\gamma_1\delta_2-\delta_1\gamma_2)\\
+j(\alpha_1\gamma_2-\beta_1\gamma_2+\gamma_1\alpha_2+\delta_1\beta_2)\\
+k(\alpha_1\delta_2+\beta_1\gamma_2-\gamma_1\beta_2+\delta_1\alpha_2)$$

However, when I looked for documentation on this operation in some languages such as matlab, the quaternion product has other definition:

http://www.mathworks.com/help/aerotbx/ug/quatmultiply.html

So, when I test my implementation against the example given the result is different. So, Why is that? What is the correct definition?

Your expression for the $j$ term is wrong. It should be:
$$ \alpha_1 \gamma_2-\beta_1\delta_2 + \gamma_1 \alpha_2  + \delta_1 \beta_2 $$

I do not understand quaternions at all, but what I have been told is that multiplication does not commute with quaternions. I suggest perhaps using only the rules given, and not passing to the distributive law as you have done, although that sounds a bit insane.

I believe quaternions can be represented as a matrix algebra in some form, perhaps start with that idea or assume it is true to begin with. That would make computation a lot easier!

Oh yeah and is there a stray gamma in there? :)


Is the product of a measurable and bounded function with a Lebesgue integrable function Lebesgue integrable? If we have one function $f$ which is Lebesgue integrable and one function $g$ which is both measurable and bounded, is the product of $f \cdot g$ Lebesgue integrable or not?

Thx in advance

A measurable function $u$ is lebesgue integrable iff there exists a (positive) lebesgue integrable function $w$ such that $$\forall x \in \mathbb{R}: |u(x)| \leq w(x)$$

In your case: Since $g$ is bounded there exists a constant $c>0$ such that $|g(x)| \leq c$ for all $x \in \mathbb{R}$. Try to find an estimate for

$$|\underbrace{f(x) \cdot g(x)}_{=:u(x)}|$$

such that the upper bound is still a lebesgue integrable function. (Note that $\lambda \cdot f$ is integrable for all $\lambda \in \mathbb{R}$.)

The answer is yes. This is really a very simple exercise though,you should try to prove it yourself.


Does $(X'X)^{-1}$ always exist? I'm studing Machine Learning theory and I have a questions about Normal Equation. Normal Equation is:
$\Theta = (X'X)^{-1}X'Y\tag 1$
I now that ( in some cases) we can use this other equation:
$\Theta = X^{-1}Y\tag 2$
But the problem is that $X$ might not have an inverse, so it's not recommended to use $(2)$.
My question is: If $(2)$ is not usually used because $X$ might not have an inverse, does $X'X$ in $(1)$ always have an inverse?
Thank you for everyone!

$(X'X)^{-1}$ is NOT always invertible. Consider X a row vector, then $X'X$ is a matrix with rank 1.
In fact, $(X'X)^{-1}X'$ is the MP pseudo inverse of X, a generalization of inverse $X^{-1}$.

For the standard least squares regression model,
$$y=X\beta+\varepsilon, \quad y\in\mathbb{R}^n,\quad \beta\in\mathbb{R}^m$$
the optimization problem  as you may now know is
$$\hat{\beta}:=\min_{b\in \mathbb{R}^m}\|Xb -y\|_2$$
where $\|\;\|_2$ stands for the Euclidean norm own $\mathbb{R^m}$. This is equivalent to finding the best approximation to $y$ through vectors in the range of the linear operator $b\mapsto Xb$. From linear algebra it is known that such best approximation $y'\in X(\mathbb{R}^m)$ exists. In fact, it has the property that $\hat{y}\in \big((\mathbb{R}^m)\big)^\perp$, that is
$$(\hat{y}-y)\cdot Xb=0$$
for all $b\in\mathbb{R}^m$. Since the range of the liner operator described above is generated by the columns of $X$, this means that
$$ (\hat{y}-y)^\top X=0$$
Thus, there is at least one $\hat{\beta}$ such that $hat{y}=X\hat{\beta}$. When $X$ is of full rank, then $X^\top X$ is invertible and so $\hat{b}=(X^\top X)^{-1}X^\top\hat{y}$ is unique. If not, then there are infinitely many $\hat{b}$'s that satisfy $\hat{y}=X\hat{b}$.
Among all those possible $\hat{b}$'s, there is a special $\hat{\beta}$ that also has the smallest Eucliden norm own $\mathbb{R}^m$.
It turns out that such $\hat{\beta}$ is is of the form $A\hat{y}$ where $A$ is a matrix that satisfies four properties:
$$AXA=A$$
$$XAX=X$$
$$(AX)^*=AX$$
$$(XA)^*=XA$$
where for any matrix $B$, $B^*$ is the transpose conjugate of $B$. The matrix $A$ is unique and is called Moore-Pensroe's pseudo inverse of $X$.


Does $f''(0^+)=f''(0^-)$? Consider the function, which is the join of two semicircles

$$ f(x) = \left\{ \begin{array}{cc} \sqrt{1 - x^2} & x > 0 \\
1 & x = 0 \\
\sqrt{ 2 - (x-1)^2} & x < 0\end{array} \right.$$

Near $x = 0$, $f(x)$ is continuous and $f'(0)$ makes sense.  Does $f''(0^+)=f''(0^-)$?


Inequality sign of sequences preserved in infinite convergence sums inequlities. Let $a_n$ and $b_n$ be two real positive number sequences, such that, for every $n\in \mathbb{N}$, $a_n<b_n$. Also, let $\sum_{n=1}^{\infty}a_n$ and $\sum_{n=1}^{\infty}b_n$ be two convergent series.
Why does the following inequality holds:

$$\sum_{n=1}^{\infty}a_n<\sum_{n=1}^{\infty}b_n$$

Clearly $\sum_{n=1}^\infty a_n \leq \sum_{n=1}^\infty b_n$.
If you assume by contradiction that equality holds, then necessarily you must have $a_n = b_n$ for every $n$.

Btw, if $a_j\leq b_j$ for every $j$, to get the result it is enough to assume that there exists $m$ such that $a_m < b_m$.

Namely, let $\delta := b_m - a_m > 0$. If $n\geq m$ one has
$$
\sum_{j=1}^n a_j \leq \sum_{j=1}^n b_j - \delta,
$$
hence
$$
\sum_{j=1}^\infty a_j \leq \sum_{j=1}^\infty b_j - \delta.
$$


Questions about a commutative ring with exactly three ideals Let $R$ be a commutative ring with identity. Assume that $R$ has exactly three distinct ideals: $\{0\},I, R.$

  1) Show that if $a \in R-I$, then $a$ is a unit in $R$.

  2) Let $a,b\ne0$ in $I$. Show that $ab=0$.

HINT for 1: $Ra$ is an ideal containing $a$, so what can we say about $Ra$?

HINT for 2: Consider the ideal generated by $ab$.

$\underline{\text{Part 1.}}$  Let $a\in R-I$, in particular this means that $a\neq 0$ since $0\in I$.  Now take the principal ideal generated by $a$, I'll write as $(a)=aR$.  This is an ideal and a subset of $R$.  Since $1\in R$ we have that $1\cdot a\in(a)$ which means that $(a) \neq I$ because $a\notin I$.  Also, $(a)\neq (0)$ since $a\neq 0$.  Therefore, we must have that $(a)=R$.

This tells us that $1\in (a)$, so for some ring element $r\in R$ we have,
$$r a=1 $$

and thus $a$ is a unit.

$\underline{\text{Part 2.}}$ Let $a,b\neq 0$ be elements of $I$.  Take the principal ideal generated by the element $ab$, which I will write as $(ab)$.  Since $ab\in I$ by the ideal property, we have that $(ab)\subset I$.  Since $(ab)$ is an ideal, this means we have two choices, either $(ab)=(0)$ or $(ab)=I$.

By way of contradiction, assume that $(ab)=I$.  Since $a\in I $ this means that $a\in (ab)$.  So for some $r_1\in R$ we have,
$$a=abr_1=a(br_1) $$

This implies that $b r_1=1$.  So $b$ is a unit.  But we also that that $b\in (ab)=I$, and any ideal containing a unit is the whole ring.  We know that $R$ and $I$ are distinct ideals though.  Contradiction.  Therefore, our assumption that $(ab)=I$ was incorrect.  So we are only left with the option that $(ab)=(0)$, thus $ab=0$.


Prove that there are no analytic function satisfying this property This kind I'm kindly asking you to help me in solving this question:

  Prove that there are no analytic functions $f:\mathbb R\to \mathbb R$ such that $$f\left(\frac 1n\right)=\frac{(-1)^n}{n^2},$$ for every $n\in\mathbb N$.

Thank you very much in advance for any hint because I'm out of ideas.

Regards

In fact there is no $f$ two times differentiable in a neighborhood of $0$ such that $f(n^{-1})=\frac{(-1)^n}{n^2}$. Indeed, if $f$ is such a function, then $f(0)=0$, $f'(0)=\lim_{n\to \infty}nf(n^{-1})=\lim_{n\to\infty}\frac{(-1)^n}n=0$ and $f''(0)=\lim_{n\to\infty}n^2f(n^{—1})$ but the last limit is the limit of $(-1)^n$, which doesn't exist.

suppose such $f$ were exist, define $g(z)= f(z)- (-1)^nz^2$ which is also holomorphic, but $g(1/n)=0\forall n$ and Uniqueness theorem says that $g(z)\equiv 0$, $f(z)=(-1)^nz^2$ but which is not unique, so no such analytic function cant exist.


Prime notation for derivatives This may seem like an overly trivial question, but I've just recently become confused about Langrange's 'prime' notation for derivatives (for example $f'(x)$).

I know for sure that $f'(x) = \frac{\delta f(x)}{\delta x}$.

But suppose we replace x with an expression, like 2x+1. Do we write $f'(x^2+1) = \frac{\delta f(x^2+1)}{\delta x}$ or $f'(x^2+1) = \frac{\delta f(x^2+1)}{\delta (x^2+1)}$?

Does putting the prime around the function instead of between its letter and parentheses make a difference? For example what does $(f(x^2+1))'$ mean?

$f'$ is a function, so $f'(2x + 1)$ denotes $f'$ applied to $2x + 1$, or $\frac{df}{dx}(2x + 1)$.  For example if $f = x^2$ then $f' = 2x$ and $f'(2x + 1) = 4x + 2$.

$(f(x^2 + 1))'$ is the derivative of the function $f(x^2 + 1)$, which is $2x f'(x^2 + 1)$ by the chain rule.

This question highlights a weakness of the $'$ notation, which is that it always comes with an implied variable with respect to which you're differentiating.  If this variable is clear from context there's no problem, but sometimes it isn't.

I am reading Quiaochu Yan when answering Cam:

1) $′$ is a function, so $′(2+1)$ denotes $′$ applied to $2+1$, or $\frac{\partial }{\partial }(2+1)$. For example if $=^2$ then $′=2$ and $′(2+1)=4+2$

2) $((^2+1))′$ is the derivative of the function $(^2+1)$, which is $2′(^2+1)$ by the chain rule

and I agree with Quiaochu but I don't understand why such difference is a weakeness of the $′$ notation. We see that $′(2+1)$ and $((^2+1))′$ are written differently, and they mean different things. There is no ambiguity, I think.
I am more puzzled about Hendrik Vogt's post, when he says that $(^2)′=2$ is ambiguous, where is the ambiguity?
On lessons, under the constrains of time, I use that notation constantly on introductory Calculus courses, wherever and whenever there is only one variable with respect to which we are differentiating with. I noticed that such notation is more common in European countries than in the UK and rare in the United States, to the extent that some colleagues told me that it was wrong to write $((^2+1))′$.


Randomly picking cards from deck with replacement If I randomly pick 80 cards, uniformly, from a standard 52-card deck, with replacement, what is the probability that every card is drawn at least once?

I understand that to tackle this question, I will most probably need to use Inclusion/Exclusion, however, I'm not entirely sure how to solve this.

Any help would be greatly appreciated.

Someone else asked a similar question a little while after this one. I'm modifying and reposting my answer from there to here. I've also added an example since it's early in the morning and the baby is still sleeping.

The short answer is $$\frac{{80\brace52}52!}{52^{80}}.$$

Explanation: Suppose we have a deck of $k$ cards, say $C=\{c_1,c_2,\ldots, c_k\}$, and we draw, with replacement, $n\geq k$ of them. Let $(d_1,\ldots, d_n)$ be the sequence of draws (so each $d_j\in C$). I'll call this a drawing.

Obviously there are $k^n$ possible drawings.

In how many drawings is each card chosen at least once? I'll call these good drawings. Well, let $(d_1,\ldots, d_n)$ be a drawing and suppose we have $k$ buckets labelled $\{c_1,c_2,\ldots, c_k\}$. Place $d_j$ into bucket $c_i$ when $d_j=c_i$. Then we know that the drawing is good if and only if each bucket is non-empty.

Now, suppose we have $k$ identical buckets and place symbols $\{D_1,\ldots, D_n\}$ into the buckets, making sure that each bucket gets at least one symbol. We make the convention that two such placements are the same if the buckets can be rearranged to get one from the other. By the definition of the Stirling number of the second kind, there are ${n\brace k}$ ways of doing this. Next, label the buckets with labels $\{c_1,\ldots,c_k\}$. There are $k!$ ways of doing this.

For each of the above placements and labellings, we can then define a good drawing $(d_1,\ldots, d_n)$ by setting $d_j=c_i$ if and only if $D_j$ was placed in bucket labelled $c_i$.

Thus there are exactly ${n\brace k}k!$ good drawings and so the probability that a drawing is good is $$\frac{{n\brace k} k!}{k^{n}}.$$

Example with a deck of $k=2$ cards, say $\{0,1\}$, and $n=3$ draws. In this case a drawing is simply a binary sequence of length 3, and clearly only $(1,1,1)$ and $(0,0,0)$ are not good drawings, so the probability should be $3/4$.

Now let $B_1$, and $B_2$ be the buckets. We want to put symbols $D_1,D_2,D_3$ into these and so there are ${3\brace 2}=3$ possibilities:

$D_1\in B_1, \{D_2,D_3\}\in B_2$ (which we consider the same as placing $D_1\in B_2$ and $\{D_2,D_3\}\in B_1$).

$D_2\in B_1, \{D_1,D_3\}\in B_2$,

$D_3\in B_1, \{D_1,D_2\}\in B_2$.

If $B_1$ is labelled $1$ and $B_2$ is labelled $0$ we get the drawings $(1,0,0)$, $(0,1,0)$ and $(0,0,1)$. The other labeling gives the drawings $(0,1,1)$, $(1,0,1)$ and $(1,1,0)$. As noted above, this is indeed all good drawings in this case and the probability of getting a good drawing is $$\frac{{3\brace 2}2!}{2^3} = \frac{3}{4}.$$

Hint: Think of the following situation:

You need to pick a specific card from a set of 52 cards. By specific, I mean choose a card in advance. What would be the probability of picking the card?
Do this 52 times, and make sure all the 52 cards are chosen. You can do this by not replacing the card picked before. You thus get a probability of choosing 52 different cards.
The remaining 28 cards can be picked without any restrictions. So, it would be just ${52 \choose 28} (\frac {1}{52})^{28} (\frac {51}{52})^{24}$.

Multiply the answer from 3 and 2 to get final answer.


Is a number written in the square root/fraction form called a non-integer even if it can be simplified to an integer This is very simple question, but I cannot get the ansewer from the internet.

Is a number written in the square root/fraction form called a non-integer even if it can be simplified to an integer.

For example 4/2, 12/4, sqr4, sqr64 etc... do these need to be simplified before we can call them integers.

Too make this easer to understand are sqr64 and 12/4 non-integers while 8 and 3 are integers.

No.  Numbers are what they are.  It doesn't matter how they are represented.

$7$ is an integer.  Period.

It doesn't matter if is written as $5 + 2$ or $\sqrt{49}$ or $\sqrt{25} + \frac{\sqrt[3]{16}}{2^{\frac 13}}$ or $\ln (e^7)$.

Those are all equal to $7$ and $7$ is an integer.  Period.

====

That said, it might not be easy (or even possible) to tell if a number is or is not an integer.  It's obvious that $7$ is an integer and $7.0000012142650469991421281354411.....$ isn't.  But it isn't clear whether $\sqrt[7]{823543}$ or $\sqrt[7]{823544}$ are integers.  (It turns out that those are the same numbers.)

But it doesn't matter whether we know if a number is an integer or not.   It either is or isn't.

If it can be simplified to an integer,
it can be called an integer
after the simplification.

Until the simplification is done,
I would just call the expression
"an expression"
when it is not clear if it could be
simplified to an integer.

Considering how expressions
involving nested radicals
can be sometimes
amazingly simplified,
I think that there would be cases
where the fact that
an expression simplifies
to an integer
is a surprise.


Find $B$ if $AB=BC$ and $A,C$ are invertible Suppose $A$ and $C$ are known invertible complex matrices of possibly different orders. If $B$ is an unknown matrix of appropriate order such that $AB = BC$, then how could one solve for $B$?

We can solve the problem theoretically and then compute it for low dimensions.

Consider $\phi: M(n, \mathbb{K}) \to M(n, \mathbb{K})$ mapping $X \mapsto AXC^{-1}-X$ and find the kernel.


Square root of $\sqrt{1-4\sqrt{3}i}$ How can we find square root of the complex number
$$\sqrt{1-4\sqrt{3}i}?$$

Now here if I assume square root to be $a+ib$ i.e.
$a+ib=\sqrt{\sqrt{1-4\sqrt{3}i}}$, then after squaring both sides, how to compare real and imaginary part?

Edit: I observed

$\sqrt{1-4\sqrt{3}i}=\sqrt{4-3-4\sqrt{3}i}=\sqrt{2^2+3i^2-4\sqrt{3}i}=\sqrt{(2-\sqrt{3}i)^2}$ which made calculation easier.

You need to first find the square root of $1 - 4 \sqrt{3}i$ using the same method: let $(c+di)^2 = 1 - 4 \sqrt{3} i$ and then compare real and imaginary parts to find $c$ and $d$ explicitly. This will give you two different answers. Then assume $(a+bi)^2 = c + di$, and compare real and imaginary parts to find $a$ and $b$ explicitly. This gives you two solutions for both solutions of $(c+di)^2 = 1 - 4 \sqrt{3} i$, so in total, you get four different answers.

The answer depends in part on the meaning that's ascribed to the square root symbol, $\sqrt{}$.  In almost all settings, $\sqrt a$ is taken to be positive if $a$ is a positive real number.  Assuming this to be the case, then the square root of the square root of $1-4\sqrt3i$ turns out to be one of the four number $z$, $zi$, $-z$, or $-zi$, where

$$z=\sqrt{{\sqrt7+2\over2}}-\sqrt{{\sqrt7-2\over2}}i$$

Exactly which one is meant depends on the convention you adopt for assigning an unambiguous value to $\sqrt{a+bi}$ if $a,b\in\mathbb{R}$ and $b\not=0$.  (Most conventions set $\sqrt a=\sqrt{-a}i$ if $a$ is a negative real number. Note that $\sqrt7\gt2$, so all values inside square root symbols in the displayed equation are positive.)  Let me explain what I mean by this, and in the process show how the expression for $z$ was obtained.

One convention says that $\sqrt{}$ applied to a complex number with non-zero imaginary part has a positive real part. (This corresponds to assuming $-\pi\lt\theta\le\pi$ in the equation $\sqrt{e^{i\theta}}=e^{i\theta/2}.)$  Under that convention we have

$$\sqrt{1-4\sqrt3i}=2-\sqrt3i$$

so it remains to find real values $a$ and $b$ with $a\gt0$ such that $(a+bi)^2=2-\sqrt3i$, which is to say

$$a^2-b^2=2\qquad\text{and}\qquad2ab=-\sqrt3$$

Plugging $b=-\sqrt3/(2a)$ into $a^2-b^2=2$ leads to

$$4a^4-8a^2-3=0$$

which implies $a^2=(2\pm\sqrt7)/2$.  In order for $a$ to be real, we must have $a^2=(2+\sqrt7)/2$, hence

$$a=\sqrt{{\sqrt7+2\over2}}$$

The corresponding value for $b$ is most easily obtained by noting that $a^2-b^2=2$ implies $|b|=\sqrt{a^2-2}$ while $b=-\sqrt3/(2a)$ implies $b$ is negative, hence

$$b=-\sqrt{a^2-2}=-\sqrt{{\sqrt7+2\over2}-2}=-\sqrt{{\sqrt7-2\over2}}$$

which gives us the answer

$$\sqrt{\sqrt{1-4\sqrt3i}}=\sqrt{{\sqrt7+2\over2}}-\sqrt{{\sqrt7-2\over2}}i$$

Another convention says that $\sqrt{}$ applied to a complex number with non-zero imaginary part has a positive imaginary part. (This corresponds to assuming $0\le\theta\lt2\pi$ in the equation $\sqrt{e^{i\theta}}=e^{i\theta/2}$.)  Under this convention we have

$$\sqrt{1-4\sqrt3i}=-2+\sqrt3i$$

and, if you carry out the same reasoning as before, this time with  $a^2-b^2=-2$ and $2ab=\sqrt3$, you arrive at

$$\sqrt{\sqrt{1-4\sqrt3i}}=\sqrt{{\sqrt7-2\over2}}+\sqrt{{\sqrt7+2\over2}}i$$

which can be recognized as $zi$.  (We can check that we have the correct signs by noting that $2ab=\sqrt3$ implies $a$ must have the same sign as $b$, which the convention requires to be positive.)

A final remark:  My thanks to Wojowu, who pointed out an egregious mistake in my original answer.  (I thought the number in question was $\sqrt{1-4\sqrt3}i$ rather than $\sqrt{1-4\sqrt3i}$, which, if you can see the difference, makes a world of difference.)


$\sigma(n) \equiv 1 \space \pmod{n}$ if and only if $n$ is prime For $n>1$, let $\sigma(n)$ denote the sum of all positive integers that evenly divide $n$. Then $\sigma(n) ≡ 1 \space(mod\space n)$ if and only if $n$ is prime.

I've been trying to prove this for a long time, but i can't figure it out.

I found a theorem that might be helpful:

$\sigma(n) = n + k$  has finitely many solutions for $k > 1$ (more specifically, this equation has no solutions for $n≥k^2$).

proof:

let  $n≥k^2>1,\space \sigma(n) = n + k$. Note that $n$ must be a composite number (otherwise $k=1$). Therefore, $n$ has a divisor $d≥\sqrt n$. From $\sigma(n)$'s definition:
$\sigma(n) ≥ n+d+1≥n+\sqrt n + 1 ≥ n + k + 1 > n + k$

If anyone can generalize this to $\sigma(n)=qn+k$, or something like that, it might help.

This is a hard problem.

If you can prove your conjecture, then it will imply immediately that there are no quasi-perfect numbers. The existence of quasi-perfect numbers is a long-open problem.

If $p$ is prime then the only number that divide $p$ are $1$ and $p$ so $\sigma (p) = 1 + p \equiv 1 \mod p$.

So that's one direction.

Let $\sigma(n)=1$ .

If $\sigma(n) \equiv 1 \mod n$ and if $k|n$ then $\sigma (n) \equiv 1 \mod \frac nk$ (because if $n|\sigma(n) -1$ and $\frac nk|n$ then $\frac nk|\sigma(n) -1$.)

Now $\sigma(n) = $ sum of all factors that are multiples of $\frac nk$ plus all the multiples that are not multiples of  $\frac nk $.

All the multiples that are not multiples of  $\frac nk =\sigma(\frac nk)$.

So $\sigma(n) \equiv \sigma(\frac nk) \mod \frac nk$.

So $\sigma(\frac nk)\equiv 1 \mod \frac nk$.

So by induction.

$\sigma(pq) \equiv 1 \mod pq$ where $p\ne q$ but $pq|n$ and $\sigma(p^2) \equiv 1 \mod p^2$ where $p^2|n$.

We can show these are impossible.  $\sigma(p^2) = 1 + p + p^2 \equiv 1+p \mod p^2$ and as $1 < 1+ p < p^2$ that is not equivalent to $1$.

If $pq|n$ and $p\ne q$ wolog assume $p\le 2  < q$ then $\sigma(pq) = 1 + p + q + pq \equiv 1+p + q \mod pq$.  But $1+p + q \le q + q \le pq$.  Equality can only hold if $p = 2$ and $q=3$ and in that case $1+ 2 + 3\equiv 0 \mod 6$.

So... these are contradictions.  It's not possible that $n$ has two or more unequal prime factors, and it is not possible that $n$ have any prime factor to a power higher than $1$ as a factor.

In other words, $n$ must be prime.


Function whose inverse is also its derivative? What are some good examples of a function  $f : \mathbb{R} \to \mathbb{R}$ where its derivative is equal to its inverse? I attempted to find a monomial that satisfied it by starting with $f(x) = ax^b$ and showing that $f^{-1}(x) = f'(x) \implies b-1=\frac{1}{b} \implies b=\phi$ and got
$$f(x) = \frac{x^\phi}{\sqrt[\phi]{\phi}}$$
Which seems to work according to WolframAlpha, but I'm having trouble double-checking it. Any other ideas?

Here is an alternative: You can use
$$
        f^{-1}(x)=\int\frac{1}{f'(f^{-1}(x))}\,dx + c. \tag{1}
$$
from "Inverse functions and differentiation".

Set $f^{-1}(x)=f'(x)$ and for simplicity take the derivative of $(1)$. You get
$$
f''(x)=\frac1{f'(f'(x))}.
$$
Now put in $f(x)=\phi^{-\frac1\phi}x^\phi$. Using $\phi-1=\frac1\phi$, you'll get
$$
f'(x)=\phi^{2-\phi}x^{\phi-1}\\
f''(x)=\phi^{1-\phi}x^{\phi-2}
$$
Now put it all together and use $\phi^2=\phi+1$:
$$
\begin{eqnarray}
f''(x)&=&\frac1{f'(f'(x))}\\
\phi^{1-\phi}x^{\phi-2}&=&\left(\phi^{2-\phi}\left(\phi^{2-\phi}
x^{\phi-1}\right)^{\phi-1}\right)^{-1}\\
&=&\left(\phi^{2-\phi}\left(\phi^{3\phi-2-\phi^2}x^{\phi^2-2\phi+1}\right)\right)^{-1}\\
&=&\left(\phi^{2\phi-\phi-1}x^{\phi+1-2\phi+1}\right)^{-1}\\
&=&\left(\phi^{\phi-1}x^{-\phi+2}\right)^{-1}\\
\end{eqnarray}
$$

Start with $\dot{y}=y^{-1}$  Apply Lie Group $G(x,y)=(\lambda x,\lambda^\beta y)\lambda_o=1$
Stabilizers for this group include $\mu=\frac{y}{x^\frac{1}{2}}$ and $\nu=x^{\frac{1}{2}}\dot{y}$.  Multiplying the DEQ by $x^{\frac{1}{2}}$ we have $x^{\frac{1}{2}}\dot{y}=\bigg(\frac{x^{\frac{1}{2}}}{y}\bigg)$ which makes our DEQ, in stabilizer form, $\nu=\mu^{-1}$.  Since $$x\frac{d\mu}{dx}=\nu -\beta\mu = \mu^{-1} -\frac{1}{2}\mu$$ $$\frac{d\mu}{\mu^{-1}-\frac{1}{2}\mu}=\frac{dx}{x}$$ Integrating this gives $$-ln(\mu^2-2)=lnx+lnC$$ Substituting for $\mu$ and rearranging arrives at the solution: $$y=\sqrt{2x+C}$$


What does rhythm mean when it comes to a periodic function like sine or cosine? I found this online click

I don't know what rhythm means.  I can't really find where it means anywhere.  Maybe I'm not a good searcher but I really really try to search it out.  I know the period is the length of one cycle.  I know the amplitude is the halfway distance between the max and min of a sine or cosine function.  I know the frequency is the number of cycles completed in a unit interval.

What does rhythm mean here?

I think it means whether it starts at the top and then goes down or starts at the bottom and then goes up. So, for the standard sine curve I would say the rhythm is "middle, top, middle, bottom, middle" Or "Up, down, up, down". I wasn't sure about it at first, but I think it will help them once they graph their starting, ending, max and min points. Then, they know for the sine function that they will go "middle, top, middle, bottom, middle". Or, we could use more math terms and say, "zero, max, zero, min, zero" Then for cosine, we could say "max, zero, min, zero, max." This would help later when putting it all together because they could take 1/4 of a period and mark each point following that rhythm. I actually think I like this way of thinking about it.


eigenvectors of $A^2$ and $A$ if $A$ is positive definite. Is it true that $A^2$ and $A$ has the same eigenvectors if $A$ is positive definite?

$Av = \lambda v$ $\implies $ $A^2 v = \lambda^2 v$  $ \, \,\, \,\, \,\, \,\, \, $what about $\iff$?

It is also known that the eigenvalues of $A^2$ are the square of eigenvalues of $A$  as in

$ A^2 v = \mu v \implies A w = \sqrt{\mu} \, w $.

How to show, if possible, that $v$ and $w$ above are the same?

Maybe (just a suggestion) using the fact that there is a unique square root of a positive definite matrix.

If $A$ is positive definite, the vector space has a basis $v_n$ consisting of eigenvectors of $A$.  Let $\lambda_n$ be the corresponding eigenvalues.
Suppose $v$ is an eigenvector of $A^2$ for eigenvalue $\mu$.  We can write
$$ v = \sum_n c_n v_n$$
Then $$A^2 v = \mu v = \sum_n c_n A^2 v_n = \sum_n c_n \lambda_n^2 v_n $$
But also $$\mu v = \sum_n c_n \mu v_n $$
Since $v_n$ are a basis, each vector has a unique expression as a linear combination of the $v_n$, so we must have $c_n \lambda_n^2 = c_n \mu$ for each $n$.  Thus
if $c_n \ne 0$, $\mu = \lambda_n^2$.  Since $A$ is positive definite, $\lambda_n > 0$ so $\lambda_n = \sqrt{\mu}$.  That is, $v$ is a linear combination of eigenvectors of $A$ for $\sqrt{\mu}$, and so it is itself an eigenvector of $A$ for $\sqrt{\mu}$.

Suppose that $A^2v= \lambda^2v$. Then compute the norm $ ||Av-\lambda v||^2_2.$

What happens ?


Prove that $A \circ B = AB$ if and only if both $A$ and $B$ are diagonal Definition. Hadamard product. Let $A,B \in \mathbb{C}^{m \times n}$. The Hadamard product of $A$ and $B$ is defined by $[A \circ B]_{ij} = [A]_{ij}[B]_{ij}$ for all $i = 1, \dots, m$, $j = 1, \dots, n$.

Remark. See details in this Hadamard product wiki article.

There is the following remark in Million's paper in Chapter 2:

  We can relate the Hadamard product with matrix multiplication via
  considering diagonal matrices, since $A \circ  B = AB$ if and only if
  both $A$ and $B$ are diagonal.

So there is a theorem, that $A \circ  B = AB$ if and only if both $A$ and $B$ are diagonal, but I don't know how to prove it, and I didn't find it in the literature, because not many books have written in this topic.

Edit. In this theorem probably $m=n$. Million didn't write about it.

The theorem you are trying to prove is not true:

Consider $A = B = \left(\begin{array}{cc}
1 & 0\\
1 & 0\end{array}\right)$.

Proof: (assuming $n=m$)

($\Rightarrow$) by assumption, $A$ and $B$ are diagonal.  Then $AB = diag(a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})$ and $[A\circ B]_{i,j} = [A]_{i,j} [B]_{i,j}$.  Since $A$ and $B$ are diagonal, then $[A\circ B]_{i,j} = 0$ for all $i\neq j$, and $[A\circ B]_{i,i} = a_{ii}b_{ii}$ $\Rightarrow$ $[A\circ B]_{i,j} = diag(a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})=AB$

($\Leftarrow$) (retracted)


Take any number and keep appending 1's to the right of it. Are there an infinite number of primes in this sequence? Ignoring sequences that are always factorable such as starting with 11, Can we take any other number such as 42 and continually append 1s (forming the sequence {42, 421, 4211, ...}) to get a sequence that has an infinite number of primes in it?

I think this is an open question. Lenny Jones gave a talk in which he noted that the numbers 12, 121, 1211, 12111, 121111, etc., are all composite - until you get to the one with 138 digits, that's a prime.

Jones' work appears in the paper, When does appending the same digit repeatedly on the right of a positive integer generate a sequence of composite integers?, Amer. Math Monthly 118 (Feb. 2011) 153-160. He finds that 37 is the smallest positive integer such that you get nothing but composites by appending any positive number of ones. It seems to be easier to find a sequence with no primes than a sequence which you can prove has infinitely many.

So it can't be true or can't be even false. As we know that primes gaps increases when we see large prime numbers. It is true there are infinitely many primes but these gaps really create the trouble to verified whether these types of prime numbers may exist. Let take an example let n=3 so the sequence will run like

(31, 311, 3111, 31111,...) in this sequence every third term will divisible by 3 and if we go higher the prime gaps increases but as we know the sequence is infinite and following a pattern then it can hit some prime numbers also, by this assumption we can state yes prime numbers like do exist till infinity.

In my knowledge I don't know any mathematical way to proof it except this above hypothesis.


Is $\{k \in \mathbb{Z}_{40} \,|\, k \text{ is a multiple of 3}\}$ a subgroup of $\mathbb{Z}_{40}$? Is $S = \{k \in \mathbb{Z}_{40} \,|\, k \text{ is a multiple of 3}\}$ a subgroup of $\mathbb{Z}_{40}$?

No, right? I have a student who doesn't believe my argument of non-closure because $3 \in S$ and $39 \in S$ but $3 + 39 \mod 40 \equiv 2 \not\in S$ since $2$ isn't a multiple of $3$.

The student claims that this is the group $3\mathbb{Z}_{40}$ and that $3\mathbb{Z}_{40} = \mathbb{Z}_{40}$ because every multiple of 3 loops around and that an algebra professor told her this. But it's not making any sense. I'm thinking either she or the professor are thinking of the cyclic subgroup generated by $3$, $\langle 3 \rangle = \mathbb{Z}_{40}$.

EDIT: Earlier in the student's problem set, we have a similar problem that asks you if $T = \{k \in \mathbb{Z}_{40} \,|\,k \text{ is odd}\}$ is a subgroup of $\mathbb{Z}_{40}$. The counter example I used was that $1 + 3 = 4 \not\in T$. Would this likely imply that my assumption of the definition was what the problem set had in mind? Since technically you'd have a loop-around of odd numbers becoming even.

The question is actually ambiguous, and I would be rather disappointed that the professor did not realise this.

The point is that the statement

  $a$ is a multiple of $b$

by itself, is ambiguous.  Unless otherwise specified, it means that

  there is an integer $c$ such that $a=bc$.

For example, $24$ is a multiple of $8$ because $24=8\times3$ and $3$ is an integer.

However, there is no need to be talking about integers!  Suppose that we are talking about even numbers only.  Then

  $a$ is a multiple of $b$

means

  there is an even integer $c$ such that $a=bc$,

and in this case $24$ is not a multiple of $8$.

Usually this ambiguity is unimportant, because the only things we could be talking about are the integers.  However, in your question, there is another alternative: we could be talking about ${\Bbb Z}_{40}$.

If we are talking about divisibility in $\Bbb Z$: then
$$\{k\in{\Bbb Z}_{40}\mid k\ \hbox{is a multiple of $3$}\}
  =\{0,3,6,\ldots,39\}\ ;$$
this is not a subgroup and you are right.
If we are talking about divisibility in ${\Bbb Z}_{40}$, then
$$\eqalign{
  \{k\in{\Bbb Z}_{40}\mid k\ \hbox{is a multiple of $3$}\}
  &=\{k\in{\Bbb Z}_{40}\mid 3x\equiv k\pmod{40}\ \hbox{has a solution}\}\cr
  &={\Bbb Z}_{40}\ ;\cr}$$
this is (obviously!) a subgroup, and the others are right.

Your student is correct.

A multiple of a quantity is a product of the quantity with any integer.

So,
$S = \{ k\in \mathbb{Z}_{40}|k$ $is$ $a$ $multiple$ $of$ $3 \} = \{ k\in \mathbb{Z}_{40}| k=3a, a\in \mathbb{Z}\} = \mathbb{Z}_{40}$.
Hence, $S$ is a subgroup of $\mathbb{Z}_{40}$.


Variable chord of hyperbola If a variable chord of hyperbola $x^2$$/4$ - $y^2$$/8$ $=$ $1$ subtends a right angle at the centre of hyperbola . If the chord touches a fixed concentric circle with hyperbola then we have to find the radius of the circle .

I thought of doing it by homozenizing , but not able to do how ?

Homogenise it and then
coeff.[x^2+y^2]=0 you will get constant term and since it is tangent to the circle x^2+y^2=r^2 then equate and u will get it.


trend of an integral function I have an array $f(x)$, which exhibits (at least in the first frequencies) a $x^{-5/3}$ dependence. This array theoretically has this relation with the array $g(x)$:
$f(x)=\frac{d g(x)}{dx}$
I wanted to find $g(x)$ so I did the cumulative trapezoidal numerical integration of $f(x)$. As you can see in the figure attached I have found this trend for $g(x)$.
[![enter image description here][1]][1]
I was expecting a trend of $x^{-2/3}$, since following the integral rule, the power should be $x^{(-5/3)+1}$
Can you explain me why this rule is not applied?

$$  \int x^{-5/3} \,\mathrm{d}x = \frac{x^{-2/3}}{-2/3} + C = \frac{-3}{2}x^{-2/3} + C  \text{.}  $$

Notice the minus sign.  This is a function that increases, asymptotically approaching the constant of integration.  Taking $C = 10\,000$ to roughly match your data and zooming in a bit,


Matrices that Commute with of a Specific matrix Let $a$ and $b$ be real numbers. Considere the $2\times 2$ matrix
\begin{equation*}A=\left[\begin{array}{cc}a&b\\-b&a\end{array}\right].
\end{equation*}
What is the centralizer of the matrix $A$ in $M_2(\mathbb R)$?

If $b=0$, then $A=aI_2$ and we have $AX=XA$ for every $X \in M_2(\mathbb{R})$, i.e. the centralizer of $A=aI_2$ is the whole $M_2(\mathbb{R})$.

Let us now assume that $b\ne 0$, and let
$$
X=\left[\begin{array}{cc}x_{11}&x_{12}\\x_{21}&x_{21}\end{array}\right] \in M_2(\mathbb{R}).
$$
Then
\begin{eqnarray}
AX&=&\left[\begin{array}{cc}a&b\\-b&a\end{array}\right]\left[\begin{array}{cc}x_{11}&x_{12}\\x_{21}&x_{22}\end{array}\right]=
\left[\begin{array}{cc}ax_{11}+bx_{21}&ax_{12}+bx_{22}\\-bx_{11}+ax_{21}&-bx_{12}+ax_{22}\end{array}\right]\cr
XA&=&\left[\begin{array}{cc}x_{11}&x_{12}\\x_{21}&x_{22}\end{array}\right]\left[\begin{array}{cc}a&b\\-b&a\end{array}\right]=
\left[\begin{array}{cc}ax_{11}-bx_{12}&bx_{11}+ax_{12}\\ax_{21}-bx_{22}&bx_{21}+ax_{22}\end{array}\right]\cr
\end{eqnarray}
It follows that
$$
AX=XA \iff
\left\{
\begin{array}{l}
ax_{11}+bx_{21}=ax_{11}-bx_{12}\\
ax_{12}+bx_{22}=bx_{11}+ax_{12}\\
-bx_{11}+ax_{21}=ax_{21}-bx_{22}\\
-bx_{12}+ax_{22}=bx_{21}+ax_{22}
\end{array}
\right.\iff
\left\{
\begin{array}{l}
b(x_{11}-x_{22})=0\\
b(x_{12}+x_{21})=0
\end{array}
\right..
$$
Since $b\ne 0$, we have $x_{22}=x_{11},\ x_{21}=-x_{12}$, i.e. the centralizer of $A$ is formed by matrices of the form
$$
\left[
\begin{array}{cc}
x&y\\
-y&x
\end{array}
\right], \quad x, y \in \mathbb{R}.
$$

Alternatively, if two matrices commute they must have the same eigenvectors if they are simultaneously diagonlizable.  Let $Av = \lambda v$  and $AB = BA$.  Then

$$  A(Bv)= (BA)(v) =    \lambda (Bv)     $$

Simultaneously diagonzliable matrices are discussed a few times in math.stackexchange:

Matrices commute if and only if they share a common basis of eigenvectors?
How do I prove that in every commuting family there is a common eigenvector?

In any case, since $\det A = a^2 + b^2 \neq 0$ your matrix is a rotation in the plane.  Therefore $B$ must also be a rotation, so

$$ B  = c \left( \begin{array}{cc}  \cos \theta  &  -\sin \theta \\ \sin \theta  & \cos \theta  \end{array} \right)
= \left( \begin{array}{cc}  c  &  -d \\ d  & c  \end{array} \right)$$
for some $c, d \in \mathbb{R}$.


Cantor Theorem assumes set is non-empty? Cantor's Theorem:

  For any set $X$, there is no onto function $f:X\to \mathcal{P}(X)$

While I was looking at the proof for this, my head decided to stop understanding it. I mean, I think I understand the proof itself, but doesn't it assume that the subset of the objects that aren't in the defined function is non-empty? Looking at it, I think that it only proves that that subset has no element. Doesn't it derive a contradiction from an assumption made earlier?
Can you guys help me understand?

No. The proof assumes nothing.

If $f\colon A\to\mathcal P(A)$ is any function, then $A_f=\{a\in A\mid a\notin f(a)\}$ is not in the range of $f$.

If $A=\varnothing$, then the only function with the empty domain is $\varnothing$ itself, which has an empty range. Then $A_f=\varnothing$, but $\varnothing\notin\operatorname{rng}(\varnothing)$. So we're fine.
If $A_f$ is empty, e.g. $f(a)=\{a\}$, then it just means that no element is mapped to the empty set. This is an extension of the first case, where indeed no element is mapped to the empty set.

In either case, it's fine, since $\varnothing$ is indeed a subset of $A$ and therefore an element of $\mathcal P(A)$.

Actually your observation on the emptiness of the set $B=\{a\in A\mid a\notin f(a)\}$ is good. Following your argument one could still prove the theorem along the following lines:

Assume $f:A\to \mathcal{P}(A)$ is surjective. Let $B=\{a\in A\mid a\notin f(a)\}$ and $B^c=\{a\in A\mid a\in f(a)\}$. Then $A = B\cup B^c$ since for every element $a\in A$ we know that either $a\in f(a)$ or $a\notin f(a)$. By Cantor's argument (as you pointed out) it follows $B = \emptyset$. Thus $A=B^c$, i.e. $\forall a \in A \Rightarrow a\in f(a)$. But this means that each $f(a)\in \mathcal{P}(A)$ is not empty. Consequently $f$ cannot be surjective since the empty set is not in the range of $f$ and $\emptyset$ is always member of $\mathcal{P}(A)$.

"Never stop thinking critically :)"


How find the $f(m+1)-f(m)=\text{constant},\forall m\in\Bbb{N}^{+}$ Let $f:\mathbb{N}^{+}\to \mathbb{N}^{+}$ be a strictly monotone increasing function such that
$$f(f(m+1))-f(f(m))=f(f(m+1)+1)-f(f(m)+1),\forall m\in \mathbb{N}^{+}.$$

Show that:
$$f(m+1)-f(m)=\text{ constant},\forall m\in \mathbb{N}^{+}$$

My attempt: Let $g(m)=f(f(m))-f(f(m)+1)$, then the condtion is
$g(m+1)=g(m)$, so $g(m)$ is constant, or
$f(f(m))-f(f(m)+1)$ be constant, then how prove it?

Here is a counter-example:

Define $f:\mathbb{N}^+\rightarrow\mathbb{N}^+$ by the following rule

$$f(1) = 1,$$$$f(2) = 3,$$$$ f(k) = 2k-2, \forall k\geq 3.$$

Then, $\forall k \geq 3$,

$f(f(k+1))-f(f(k)) = f(2k) - f(2k-2) = 4k-2-(4k-6) =4\\
f(f(k+1)+1) - f(f(k)+1)=f(2k+1)-f(2k-1)=4k-(4k-4)=4.$

So the stated condition holds $\forall k \geq3$.
It's easy to check that it also holds for $k=1,2$.

Furthermore, $f$ is strictly monotone. Hence satisfies the statement.

However,$$ f(3)-f(2) = 1 \neq 2 = f(2)-f(1).$$

BIG FAT EDIT:

I will build a counterexample to the problem. The problem is to prove that a function satisfying $f(f(m)+1)-f(f(m))=constant=K   (A)$ implies $f(m+1)-f(m)=constant=C   (B)$ because the original statemtn is equivalent to (A).

Lets start building the function and see what intuition we can gain in the process. Once we determine a value for 1, this is $f(1)$ shall we call it $a$ then if a>2 we have all the values till a that are determined by nothing, but once we put a alue to a we get a value for a+1. So we need to know which values of the naturals we are giving to the function and register them in order to remember when we will need to satisfy (A).

Lets say $a=3$ and also $K=3$ $f(2)=5$ and $f(3)=7$, I assigned those because they were free, but $f(4)=10$ yet we dont mind if $f(5)=12$ because this doesnt exclude $f(6)-f(5)=3$ (I care about 5 because it belongs to the span of the function) so we get the thing here. We only need to give consistent values to the span of f so I conserve the necessary properties.

So, we register the span (3,5,7)once in $x=3$ we jump $y=3$ to make $f(4)=10$ (and add 10 to the span (3,5,7,10))but because 4 didnt beling to the range previously registered we dont need $f(4)+3=f(5)$ so to prove how great we are we actually say $f(5)=f(4)+2=12$ (and add 12, (3,5,7,10,12)) and then we can build a function so that in these new added "spans" we "jump" 3 in the y axis to preserve the property, (also happy that this preserves monotonicity) AND we can actually violate this for other naturals in the domain. Whenever we are not on the "spans" we only add 2 to the previous value creating a slope 2 line and we add a new span, when we get to one span we jump 3 to preserve the property.

This produces a broken line so the conclusion doesnt follow.


What is known about $\operatorname{Aut}(\mathbb{I}^n)$ A few months ago, I asked a related question: Is $\operatorname{Aut}(\mathbb{I})$ isomorphic to $\operatorname{Aut}(\mathbb{I}^2)$? It was interesting for me to know that $\operatorname{Aut}(\mathbb{I})\,$ has a normal subgroup of index $2$. Now what other things are known about $\operatorname{Aut}(\mathbb{I}^n)$?
 I guess they are all non-isomorphic . Is there an easy way to show this like the answer in the question which I put a link for?

Another thing: I never studied geometric topology before. Are the above questions closer to geometric topology than algebraic topology?

The reason why I made this guess is because I saw this page.

I am also trying to get an idea of what Geometric topology is about.

Thank you.

You can generalise the result that $Aut(I)$ has an order 2 subgroup.

Lemma 1 Let $Q_d$ be the edge-graph of a $d$-dimensional hypercube. The automorphism group of $Q_d$ is isomorphic to a wreath product $\Sigma_2\wr\Sigma_d$, also called the hyperoctohedral group in dimension $d$. Here $\Sigma_i$ is the symmetric group on $i$ elements.

Corollary 2 $$|Aut(Q_d)|=2^dd!$$

Theorem 3 The automorphism group $Aut(I^d)$ has a subgroup of order $2^dd!$.

The above is a consequence of corollary 2 and $Aut(Q_d)$ being realised as a subgroup of $Aut(I^d)$. A proof of the above lemma can be found here[1].

[1] Frank Harary. The Automorphism Group of a Hypercube. J. UCS 6(1): 136-138 (2000).


Find $\lim_{x\to-\infty}{x+e^{-x}}$ I have this exercise in my worksheet:
$$\lim_{x\to-\infty}{x+e^{-x}}$$
I am always ending up with $-∞+∞$ or $\frac{∞}{∞}$. It says the answer is $+∞$, but how can I get that?

Negative numbers make me nervous, so let $t=-x$. We want
$$\lim_{t\to \infty} (e^t-t).$$
The answer is obvious, $e^t$ is much larger than $t$ if $t$ is large. If you want to be formal, after a (short) while $t\lt \frac{e^t}{2}$, so after a short while $e^t-t\gt \frac{1}{2}e^t$.

The given expression does not have a limit. That is to say, it does not converge on a value as $x$ grows large, negative.

As $x$ grows large and negative, the $x$ term grows large and negative. The $e^{-x}$ term grows large and positive, and its growth is faster than that of the $x$ term, because it is an exponential function whereas $x$ is polynomial. Exponentials grow faster than polynomials of all orders. Therefore, the exponential term dominates and the overall expression grows large, and positive.

However, it does so without limit.  We cannot say that the limit is $+\infty$, because that is nonsense. A limit, when it exists, is a number, whereas $+\infty$ is not a number and does not substitute for a limit that doesn't exist.


About twistor space of a K3 surface I know that for $X=(M,I)$ , where $I$ is the complex structure, a K3 surfaces and $\alpha \in H^2(X,\mathbb{R})$ a Kähler class, there exist a Kähler metric g and J,K complex structures such that

1) g is Kähler with respect to I,J and K

2) $\omega_I:=g(I , )$ represents $\alpha$

3) K=IJ=-JI

i know also that for each $\lambda=(a,b,c) \in S^2$, $aI+bJ+cK$ is still a complex structure for which g is Kähler. I write $\omega_\lambda$ for the Kähler form of $(M,\lambda)$ and $\sigma_\lambda$ for the generator of $H^0((M,\lambda),\Omega^2_{(M,\lambda)})$.

this article by huybrechts http://arxiv.org/abs/1106.5573 at page 16 says that the forms $\omega_\lambda$, $Re(\sigma_\lambda)$ and $Im(\sigma_\lambda)$ are contained in the 3-space generated by $\omega_I$, $Re(\sigma_I)$ and $Im(\sigma_I)$. this seems pretty obvious to Huybrechts, but i can't understand why it is..what am i missing?

I don't read Huybrecht's paper you referred to, but it is known that real and imaginary part of the period $\sigma_\lambda$, and any Kähler form span a positive 3-plane in $H^2(M,\mathbb{R})$; by decomposing $\sigma_\lambda$ into real and imaginary part, it is easy to see that they span a positive 2-plane. This plane is orthogonal to Kähler form because it is in $H^{1,1}$. So these three span a positive 3-plane.  On the other hand, such a positive 3-plane is unique because $H^2(M,\mathbb{R})$ has signature $(3,19)$.


find joint distribution $\min (X,Y)$ and $W$, where W is a discrete distribution Let, $X,Y$ are independent rv with pdf.s
$f_X(x\mid \lambda)=\dfrac{1}{\lambda}e^{-x/\lambda}$, $x>0$ and $f_Y(y\mid \mu)=\dfrac{1}{\mu}e^{-x/\mu}$, $y>0$.
Let $Z=\min\{X,Y\}$ and
$W=1$ if $Z=X$ and $0$ if $Z=Y$
Find joint distribution of $(Z,W)$?

I found pmf of $W$ which is $f_W(w)=\Big(\dfrac{\mu}{\lambda+\mu}\Big)^w\Big(\dfrac{\lambda}{\lambda+\mu}\Big)^{1-w}$
But have problem while calculating $P(Z\leq z, W=1)$.
$P(Z\leq z, W=1)=P(Z\leq z\mid W=1)P(W=1)=P(X\leq z)P(W=1)$
The last line does not look right to me. What should I do? Thanks for any help!

First, develop joint distribution of $W$ and $Z$ for both $W$ cases:

$$f(Z=z,W=0)=f(Z=z,Z=Y)=f(Y=z,Y<X)=f(Y=z,X>z)=f(Y=z)P(X>z)$$
$$f(Z=z,W=1)=f(Z=z,Z=X)=f(X=z,X<Y)=f(X=z,Y>z)=f(X=z)P(Y>z)$$

Last two terms can be written as follow:

$$f(Z=z,W=0) = f(Y=z)P(X>z) = \frac{1}{\mu}e^{-z/\mu} e^{-z/\lambda}$$
$$f(Z=z,W=1) = f(X=z)P(Y>z) = \frac{1}{\lambda}e^{-z/\lambda} e^{-z/\mu}$$

Finally, one can write:
$$f(Z=z,W=w)=e^{-\left(\frac{1}{\lambda} + \frac{1}{\mu} \right)z}\left(\frac{1}{\lambda}\right)^w\left(\frac{1}{\mu}\right)^{1-w}$$


A problem regarding derangement Recently I'm facing a problem on derangement.
The problem I'm facing is asked in the link: number of derangements

An answer is also given in that link.
But I can't understand the answer.

Can anyone tell me the solving way with better explanation and great details.I again asked the question in the following.

A derangement of $n$ numbers is a permutation of those numbers in which none of the numbers appears in its original place.

For example, the numbers $\{1,2,3\}$ can be deranged into $\{2,3,1\}$ and $\{3,1,2\}$. We can modify this slightly for $n$ numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers $\{1,1,2,2,3\}$ could be deranged into $\{2,2,1,3,1\}$, $\{2,2,3,1,1\}$, $\{2,3,1,1,2\}$, and $\{3,2,1,1,2\}$.

How can I find out the number of above derangement if a set like above is given?

For the number of derangements of $n$ distinct objects, the formula is:
$$D(n)=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots+(-1)^n\frac{1}{n!}\right)$$