Calculate width and height of a rectangle, given its diagonal and ratio Well, I know, it's easy. We did it in class some time ago and I forgot it, I'm stupid because I can't figure it out:

E.g. I have a 32" TV with 16:9 ratio and I want to know its width and height.

I'd like to know the whole derivation so I can understand it (again) ...

Enlightenment, please! Thanks.

Suppose that the unknown width and height are $x$ and $y$, and you’re given a diagonal $d$ and a ratio $m:n$ of width to height. That ratio means that the width is $\frac{m}{n}$ times the height, so you know that $x=\frac{m}{n}y$. You get a second relationship between $x$ and $y$ from the Pythagorean theorem: $x$, $y$, and $d$ are the lengths of the two legs and the hypotenuse of a right triangle, so $x^2+y^2=d^2$.

Now substitute $\frac{m}{n}y$ for $x$ in this second equation to get $\displaystyle\left(\frac{m}{n}y\right)^2 + y^2 = d^2$. Simplifying this, you get in turn: $$\frac{m^2}{n^2}y^2 + y^2 = d^2,$$ $$\left(\frac{m^2}{n^2}+1\right)y^2 = d^2,$$ $$\left(\frac{m^2+n^2}{n^2}\right)y^2=d^2,$$ and $$(m^2+n^2)y^2=d^2n^2.$$  Finally, solve for $y$: $\displaystyle y^2 = \frac{d^2n^2}{m^2+n^2}$, so $y=\displaystyle\frac{dn}{\sqrt{m^2+n^2}}$.
Once you have a numerical value for $y$, you can plug it into $x=\frac{m}{n}y$ to get a value for $x$.
(Or you can do that symbolically: $\displaystyle x=\frac{m}{n}\cdot \frac{dn}{\sqrt{m^2+n^2}} =$  $\displaystyle\frac{dm}{\sqrt{m^2+n^2}}$.)

Here is a code snippet from my gesture library. It is fully tested and calculates the width and height based upon and diagonal length and a width to height ration.

public void triggerFling(float dynamicFlingDistance, float width, float height) {

    float animationStartX = (int) matrixVals[Matrix.MTRANS_X];
    float animationStartY = (int) matrixVals[Matrix.MTRANS_X];
    float animationEndX = 0;
    float animationEndY = 0;

    if(dynamicFlingDistance == 0) {

        animationEndX = width;
        animationEndY = height;

    }
    else {

        if(width == 0 || height == 0) {

            if(width == 0 && height !=0) {

                animationEndX = (int) matrixVals[Matrix.MTRANS_X];
                animationEndY = height;

            }
            else if(width != 0 && height ==0) {

                animationEndX = width;
                animationEndY = (int) matrixVals[Matrix.MTRANS_X];

            }
            else if(width == 0 && height == 0) {return;}//End if(width == 0 && height !=0)

        }
        else {

            if(height > 0) {

                animationEndY = (float) Math.sqrt((dynamicFlingDistance * dynamicFlingDistance) / (Math.pow((width / height), 2) + Math.pow((height / height), 2)));
                animationEndX = (animationEndY / (height / width));

            }
            else {

                animationEndY = (float) -Math.sqrt((dynamicFlingDistance * dynamicFlingDistance) / (Math.pow((width / height), 2) + Math.pow((height / height), 2)));
                animationEndX = (animationEndY / (height / width));

            }

        }//End if(width ==0 || height == 0)

    }//End if(dynamicFlingDistance == 0)

    translateAnimation = new TranslateAnimation(animationStartX, animationEndX, animationStartY, animationEndY);
    translateAnimation.setFillEnabled(true);
    imageView.setAnimation(translateAnimation);
    imageView.getAnimation().setDuration(flingAnimationTime);
    imageView.startAnimation(translateAnimation);

    if(bounceBack == false) {

        final float animationEndXFinal = animationEndX;
        final float animationEndYFinal = animationEndY;

        new Handler().postDelayed(
                new Runnable() {
                    @Override
                    public void run() {

                        matrixVals[Matrix.MTRANS_X] = animationEndXFinal;
                        matrixVals[Matrix.MTRANS_Y] = animationEndYFinal;

                        matrix.setValues(matrixVals);
                        imageView.setImageMatrix(matrix);
                        imageView.invalidate();
                        imageView.requestLayout();

                    }
                }, flingAnimationTime);

    }//End if(bounceBack == false)

}


What is the difference between Finite Difference Methods, Finite Element Methods and Finite Volume Methods for solving PDEs? Can you help me explain the basic difference between FDM, FEM and FVM?
What is the best method and why?
Advantage and disadvantage of them?

This is a difficult question to answer.

  "The FDM is the oldest and is based upon the application of a local
  Taylor expansion to approximate the differential equations. The FDM
  uses a topologically square network of lines to construct the
  discretization of the PDE. This is a potential bottleneck of the
  method when handling complex geometries in multiple dimensions. This
  issue motivated the use of an integral form of the PDEs and
  subsequently the development of the finite element and finite volume
  techniques."
  (http://www2.imperial.ac.uk/ssherw/spectralhp/papers/HandBook.pdf)

Here are two references to review so you can get a better feel for these methods.

http://files.campus.edublogs.org/blog.nus.edu.sg/dist/4/1978/files/2012/01/CN4118R_Final_Report_U080118W_OliverYeo-1r6dfjw.pdf (see page 10 for a very nice comparison in the types of problems they were interested in - computational fluid dynamics)
There are some nice references for these methods at http://www2.imperial.ac.uk/ssherw/spectralhp/papers/HandBook.pdf (See section 7 for very nice references)

finite difference method is the oldest method to find the limited region or close region and FEM is the structural method to solve the partial deferential equation.


Why every second even number have same number of even and odd Divisors. Question: I was looking for natural numbers with same number of odd and even Divisors.Then I observed that, every second number in the list $2,4,6,8,10,12,14,...$ is such a number. Following list shows that, $2,6,10,14,...$ are even natural numbers that have same number of odd and even Divisors.
$2 \qquad 1 \qquad 1\quad\ast$
$4 \qquad 1 \qquad 2$
$6 \qquad 2 \qquad 2\quad\ast$
$8 \qquad 1 \qquad 3$
$10 \qquad 2 \qquad 2\quad\ast$
$12 \qquad 2 \qquad 4$
$14 \qquad 2 \qquad 2\quad\ast$
$16 \qquad 1 \qquad 4$
$18 \qquad 3 \qquad 3\quad\ast$
.........
How we can prove this in general? Is there is something special about this?
Note: I just copied the above list from  answer given here, https://math.stackexchange.com/a/48887/168676

First of all, what property does every 2nd even number have? if we look at 2, 6, 10, 14, etc we see that they are all divisible by 2, but not by 4. The so the even numbers which dont have that property are all divisible by 4.
can we prove that all numbers with the property are going to be all numbers which are even and not divisible by 4? Yes, it isn't too difficult so I would recommend you give it a try, use the fundamental theorem of arithmetic. But if you dont want to try it, here's an outline of a proof:
Lets start by seeing why every number which is divisible by 2 but not by 4 will have this property.
Let $n\in\mathbb{N}$ such that $n$ is even but not divisible by 4. Using the fundamental theorem of arithmetic, we know that
$n=p_1^{a_1}\cdot p_2^{a_2}\cdot...\cdot p_k^{a_k}$
where each $p_i$ is a distinct prime number, and $a_i$ is some natural number. Since we know $n$ is even, we know one of those primes is 2, so WLOG let $p_1=2$ then we also know that $a_1=1$ as otherwise $n$ would be divisible by 4.
Now, how many numbers divide n? well if $m$ is a natural number that divides $n$, then $k=p_1^{b_1}\cdot p_2^{b_2}\cdot...\cdot p_k^{b_k}$
where $0\leq b_i\leq a_i$.
At this point it should be easy to see that the number of possible dividers will depend on the number of ways to assign all of the $b_i$s in particular, there are 2 options for $b_1$, and $a_i+1$ different options for each $b_i$. Meaning the total number of dividers will just be $(a_1+1)\cdot (a_2+1)\cdot...\cdot(a_k+1)$ However, for exactly half of these, $b_1=0$ which will be an odd divisor, and in the other half $b_1=1$ which will be an even divisor.
It should now be easy to see why odd numbers, and numbers divisible by 4 will not have the same number of even factors as odd factors.


If $a^{n}-1$ is prime then $a=2$ and $n$ is prime? I was doing some basic Number Theory problems and came across this problem :

  Show that if $a$ and $n$ are positive integers with $n\gt 1$ and $a^{n} - 1$ is prime, then $a = 2$ and $n$ is prime

My Solution : (Sloppy)

  $a^{n}-1$ = $(a-1)$ . $(a^{n-1} + a^{n-2} + ... + a + 1)$
  This means that $(a-1)$ | $(a^{n}-1)$
  But $(a^{n}-1)$ is prime
  So , $(a-1)$ = 1 $\Rightarrow$ $a = 2$
  Now , let $n$ be composite
  $n = kl$ , where $1 \lt k \lt n$ and $1 \lt l \lt n$
  Now , $a^{kl}-1$ = $(a^{k}-1)$ . $(a^{k.{(l-1)}} + a^{k.{(l-2)}} + ... + a^k + 1)$
  This means that $2^{n} -1$ is composite
  Hence , we have achieved a contradiction

My Question :
Am I correct ?

The proof is alright there are two or three details though (the same issue twice actually), oe was already pointed out in comments:

Likely you should exclude the case $a=1$ right away. Just by saying $1^n -1 = 0$ is not prime so assume $a>1$.
You cannot derive from $a^n -1$ being a prime and  $(a-1) \mid (a^n-1)$ directly that $(a-1)= 1$. What you can do is say $a-1=1$ or $a-1 = a^n-1$. The latter is impossible as $n > 1$ (and $a >1$); note here you use $n>1$.
When you assert that $a^{kl}-1$ is composite, you should state explicitly that both factors you exhibit are not $1$.

These are not major problems, but if one is picky one could insist on them.

Since $a$ and $n$ are both positive integers so $a>0$ and $n>0$
then taking $a=1$ putting in $a^n-1$ we get $1^n-1=0$ which is not prime hence take $a=2$ where $2^n-1$ is a prime if and only if $n$ is a prime


Lebesgue integral basics I'm having trouble finding a good explanation of the Lebesgue integral. As per the definition, it is the expectation of a random variable. Then how does it model the area under the curve? Let's take for example a function $f(x) = x^2$.  How do we find the integral of $f(x)$ under $[0,1]$ using the Lebesgue integral?

As has been noted, the usual definition of the Lebesgue integral has little to do with probability or random variables (though the notions of measure theory and the integral can then be applied to the setting of probability, where under suitable interpretations it will turn out that the (Lebesgue) integral of (a certain) functions corresponds to the expectation of (a certain) random variable).

But this is not the origin of the Lebesgue integral. Here is an intuitive idea of what the Lebesgue integral is, as compared to the Riemann integral.

Recall from Calculus the idea behind the Riemann integral: the integral $\int_a^b f(x)\,dx$ is meant to represent the net signed area between the $x$-axis, the graph of $y=f(x)$, and the lines $x=a$ and $x=b$. The way we attempt to do this is by breaking up the domain, $[a,b]$, into subintervals $[a=x_0,x_1]$, $[x_1,x_2],\ldots,[x_{n-1},x_n=b]$. Then, on each subinterval $[x_i,x_{i+1}]$ we pick a point $x_i^*$, and we estimate the area under the graph of the function with the rectangle of height $f(x_i^*)$ and base $[x_i,x_{i+1}]$. This leads to the Riemann sums
$$ \sum_{i=0}^{n-1} f(x_i^*)(x_{i+1}-x_i)$$
as estimates of the area under the graph. We then consider finer and finer partitions of $[a,b]$ and take limits to estimate the area.

Lebesgue's idea was that instead of partitioning the domain, we will partition the range; if the function takes values between $c$ and $d$, we can divide the range $[c,d]$ into subintervals $[c=y_0,y_1]$, $[y_1,y_2],\ldots,[y_{m-1},y_m=d]$. Then, we let $E_i$ be the set of all points in $[a,b]$ whose value under $f$ lies between $y_i$ and $y_{i+1}$. That is,
$$ E_i = f^{-1}([y_i,y_{i+1}]) = \{ x\in[a,b]\,|\, y_i \leq f(x) \leq y_{i+1}\}.$$

If we have a way of assigning a "size" to $E_i$, call it its "measure" $\mu(E_i)$, then the portion of the graph of $y=f(x)$ that lies between the horizontal lines $y=y_i$ and $y=y_{i+1}$ will be $A$, where,
$$ y_i\mu(E_i) \leq A \leq y_{i+1}\mu(E_i).$$
So Lebesgue suggests to approximate the the area by picking a number $y_i^*$ between $y_i$ and $y_{i+1}$, and considering the sums
$$ \sum_{i=0}^{n-1} \mu(E_i)y_i^*.$$
Then consider finer and finer partitions of $[c,d]$, and this gives finer and finer approximations of of the area by these sums. The Lebesgue integral will be the limit of these sums. (The analogy given by Mike Spivey is very apt for the distinction between partitioning the domain and partitioning the range to find the sum.)

But in order for this to make sense, we need to develop a way of measuring fairly intricate subsets of the line, so that we can compute $\mu(E_i)$. So we first develop a way of doing this; turns out that if you accept the Axiom of Choice, then it is impossible to come up with a way of measuring that will (i) assign to an interval $[a,b]$ the "measure" $b-a$; (ii) will be invariant under translation, so so that if $F=E+c = \{e+c | e\in E\}$ then $\mu(F)=\mu(E)$; (iii) will be countably additive: if $E = \cup_{i=1}^{\infty}E_i$ and the $E_i$ are pairwise disjoint, then $\mu(E) = \sum\mu(E_i)$; and (iv) every subset of the line will have a well-defined (possibly infinite) measure. (If you don't accept the Axiom of Choice, then there are models of the reals where we can achieve this). So one drops the restriction (iv), and constructs a measure for which some sets will be "too weird" to have a measure. We then restrict attention to certain kinds of functions (called the measurable functions), which are the ones for which the sets we get in the process described above are all measurable sets. And then we define the Lebesgue integral for those functions, following the idea described above (but one does not define it exactly that way; instead the usual way is to describe $f$ as a limit of functions for which the integral is easy, and then compute the integral of $f$ as a limit of the integrals that are easy).

For your function, $f(x)=x^2$, this is fairly easy: the value all lie between $0$ and $1$, so say that we break up the range into subintervals of length $1/n$, so $y_i = i/n$, $i=0,\ldots,n$. Then
$$f^{-1}([y_i,y_{i+1}]) = f^{-1}([i/n, (i+1)/n]) = [\sqrt{i/n},\sqrt{(i+1)/n}],$$
so the $n$th estimate, picking $y_i^* = y_i = i/n$ is just
$$\sum_{i=0}^n (i/n)\left(\sqrt{(i+1)/n} - \sqrt{i/n}\right).$$
Take the limit as $n\to\infty$, and you will get that the limit is $\frac{1}{3}$, as expected. (I will spare you the details; see the end of this answer for a high-power way of getting the answer similar to the way you do it with the Riemann integral).

It turns out that not every function is Lebesgue-integrable, just like not every function is Riemann-integrable. But every function that is Riemann-integrable will also be Lebesgue integrable, and the value of its Lebesgue integral will be the same as the value of its Riemann integral. But there are functions that are not Riemann-integrable but are Lebesgue-integrable (for example, the characteristic function of the rationals is Lebesgue-integrable, with integral $0$ over any interval, but is not Riemann-integrable). We also have a "Fundamental Theorem of Calculus" for the Lebesgue Integral:

Theorem. If $F$ is a differentiable function, and the derivative $F'$ is bounded on the interval $[a,b]$, then $F'$ is Lebesgue integrable on $[a,b]$ and
$$\int_a^x F'\,d\mu = F(x) - F(a).$$

Here, the integral is the Lebesgue integral.

In particular, to finally answer the question you ask about your example, since $F(x)=\frac{x^3}{3}$ is a differentiable function whose derivative is bounded over any finite interval, in particular over $[0,1]$, then from this theorem you can deduce that the integral over the interval $[0,1]$ of the derivative $F'(x)=x^2$ is equal to $F(1)-F(0)$; that is,
$$\int_0^1 x^2\,d\mu = \int_0^1 \left(\frac{x^3}{3}\right)'\,d\mu = \frac{1}{3} - \frac{0}{3} =\frac{1}{3}.$$

I recommend the book A Garden of Integrals by Frank E. Burk (Dolciani Mathematical Expositions 31, MAA, 2007, ISBN 9-780883-853375); it discusses and compares the Cauchy integral, the Riemann integral, the Riemann-Stieltjes integral, the Lebesgue integral, the Lebesgue-Stieltjes integral, and the Henstock-Kurzweil integral; it also discusses the Wiener and Feynman integral. I just finished reading it recently.

I first understood Lebesgue as integral over range rather than integral over domain but it never seemed plausible to me that it can resolve the problem of discontinuity. I think that the trick is that measure is something that better "width" of the area (function value is the same) than Rieman's $\Delta x \rightarrow 0$ does. The Lebegue is basically

$$\int_S f(s)d\mu = \sum {f(s) \mu(s)}$$

You may think that you scan over f(s) -- all the values that you may have in the domain $S = \cup(s)$ -- and sum up all rectangles of size $height(s) \times width(s) = f(s) \mu(s)$.

You can say that you integrate over range of values f(s). However, you see also other differences. Whereas Riemann implies that the width of every interval is the same dx, that is, if you have function

$$f(1) => 1\\
f(2) => 1\\
f(3) => 2\\
f(4) => 1$$

the integral will accumulate the sum as 0+1+1+2+1. So, if you have 4 coins, you can compute the sum by simply iterating them. You see that the speed of growth is proportional only to the coin value f(x) and not to the coin index, x. This is not the case of Lebesgue. For Lebesgue, you group the coins by values (I am here from Scala), List(1,1,2,1) => Occurrences(1->3, 2->1), and you see immediately that you have two heaps of coins: ones in the first heap and doubles in the second. These are two rectangles (coin value x heap size) that you need to add together. So, you integrate by range here but you not simply add together the measures (the amount of coins) that exceed current value, you add coin value x count. This is different from Riemann. This is my second stage of understanding the integrals.

This enables integrating point-charge like discontinuities. Consider a step function. It jumps instantly at some points. It is an integral of some infinitely narrow spikes and integral grows instantly at the spike point, as if there is a finite finite amount of charge/mass concentrated in infinitesimal point of space, in contrast to continously distributed charge/mass in space. The amount of that charge in the point determines the height of the step. It seems that Riemann has difficulty with integrating the spike because regardless how infinitecimal you make your dx, they fail to break the infinitesimal interval into rectangles of constant (and infinite) height f(x) to sum them up. On the other hand, we can say that there is charge n at $x=x_0$ and when we integrate over axis of values, we suddenly pass through the value n, which is measured (countable measure) to have width of k (coins), regardless it is confined in a single real point of width 0.

Now, how is this related to expectations? Your 4 coins, 3*1 + 1*2 add up to 5 euros and, when you draw arbitrary coin, you expect its value to be 3*1+2*1/4 = 5/4 = 1.25 euros. That is, one coin contributes 1.25 euro in average. The Lebesgue integral is equal to expectation when the measure of all coins (amount of coins) is one. That is, every of n coins is not actually a coin but $1/n$th of it. Now, Lebesgue integral is 3/4*1 + 1/4*2 = 5/4 is the expectation. That is not surprising because integrating every value times its probability is what the expectation is.

I hesitated whether to post or not my undergraduate garbage reflections. But, this video persuaded me that I am on the right track.


prove - if a tends to L then Ma tends to ML Suppose that the sequence $(a_n)_{n=1}^{\infty}$ is such that $a_n \rightarrow L$ as $n\rightarrow\infty$.

Prove that for any $M>0, M \in \mathbb{R}$, we have that $Ma_n \rightarrow ML$ as $n \rightarrow \infty$.

Given $\epsilon>0$ there exists $\overline{n}\in\mathbb{N}$ such that $|a_n-L|<\frac{\epsilon}{M},\forall n\geq\overline{n}$, because by hypothesys $a_n$ converges to $L$. Now, for every $n\geq\overline{n}$, you'll get

$$|Ma_n -ML|=M|a_n-L|\leq M\frac{\epsilon}{M}=\epsilon$$

This proves $Ma_n\rightarrow ML$

Let $\varepsilon>0$ be given. By the assumption, we can find an $N$ such that
$n\geqslant N \Rightarrow |a_{n} - L| < \varepsilon /M$.
then,
$n \ge N  \Rightarrow |Ma_{n}−ML|=M|a_{n} − L|< M*ϵ/M=ϵ$
which shows that if the sequence $\{a_{n}\}_{n=1}^\infty$ tends to limit $L$ as $n\to\infty$ then, for any fixed number $M>0$, the sequence $\{Ma_{n}\}_{n=0}^\infty$ tends to the limit $ML$.

source: Course Introduction to Mathematical Thinking / Dr Keith Devlin


Solving a logarithmic polynomial I want to solve this equation for $x$:

$${\frac{1}{\sqrt{2 \pi x}} \left(\frac{e z}{2x}\right)^x} = \epsilon$$

Is there a closed form for it, or does it have to be solved numerically?  I can turn it in to this:

$$2 x \log(ez) - (2x + 1) \log(2x) = \log(\epsilon^2 \pi)$$

Which is in a form similar to $a + b\ \log x + c \ n + d \ n \log n = 0$, which is a deceptively simple equation that I don't know how to solve analytically.  It feels very similar to a polynomial, but instead of powers of $x$ it's increasing $\mathcal{O}(x)$.

Failing a closed form answer, is there a useful closed form bound?

AFAIK there is no closed form solution to the equation.

Assuming $ez, x, \epsilon > 0$, as $z \to \infty$ you have an asymptotic
solution

$$ x = \dfrac{ez}{2} - \dfrac{\ln(e \epsilon^2 \pi)}{2} - \dfrac{\ln(z)}{2} + O(1/z) $$

Imagine if you had $x^{x+1}=5$. If you can get your equation into that type of form you will be in a better position.

Let's deal with this hypothetical equation because it is simpler and easier to manipulate. And if we can solve this equation, it will be easy to go back and solve your equation, just some of the constants will be different.

First thing, we have $\log_x5 = x+1$.

We need to get that base $x$ out of there. What if we went $x=5^{\frac1{x+1}}$
then take the log of that?

$$\log_5x = \frac1{x+1}\\[5pt]
(x + 1) \log_5x = 1$$

Do you know the general formula for multiplying two log expressions?

$$\log_{x^a}x^y\times\log_{x^b}x^y=\log_{x^{ab/y}}x^y$$

Choose a convenient substitute $x$ that will work, such that $x^y$ is equal to your $x$, and the $x$ makes for a convenient base.

In these types of equations, eventually you are going to move the $x$ variable into the exponent, leaving behind constants

I mean you will have constant $A$ raised to the exponent of the log of $x$ multiplied by constant $B$ raised to a different base log of $x$. Making the constant $B$ into constant $A$ is easy if you just move it into the exponent. Once the two constants are the same, the exponents can be added together over the same constant.

Adding together two logs of $x$ with different log bases is not that difficult. Make the first log term equal to variable $a$, and the other log term equal to $b$. Use some substitution.


The preimage of a Lebesgue measurable set under a measurable function need not be measurable I am reading measure theory from Royden, and I am stuck in some of them. I have this question:

  suppose  $E$ is  a measurable set and let $f: E \to \mathbb{R}$. Prove that : $f$ is measurable if and only if $f^{-1}(A)$ is measurable for any $A \subseteq \mathbb{R}$.

I know this is not true if measurable means "Lebesgue measurable", can anyone give a counterexample in details ?

Let $C \subset [0,1]$ denote the Cantor set and let $f : [0,1] \to [0,1]$ be the Cantor function.

The function $g(x) = f(x) + x$ has the property that $g : [0,1] \to [0,2]$ is strictly increasing, continuous, and maps the Cantor set to a set of positive measure. Thus $g(C)$ contains a nonmeasurable set $Z$, and $g^{-1}(Z) \subset C$ is measurable since $C$ has measure zero.

Now define $h = g^{-1}$. Then $h : [0,2] \to [0,1]$ is continuous and thus measurable, $g^{-1}(Z) \subset [0,1]$ is measurable, but $Z \subset [0,2]$ is not. Finally observe $h^{-1}(g^{-1}(Z)) = Z$.

Thus it is possible for $h$ to be measurable, $A$ to be measurable, but $h^{-1}(A)$ to be nonmeasurable.

What is your definition of measurability? Mine goes like this : a function $f : (X, \mathcal F) \to (Y, \mathcal G)$ is measurable if and only if $f^{-1}(\mathcal G)\subseteq \mathcal F$. At this point there are two things to do :

Know the definitions of all the objects involved in your question (Measurable spaces, $\sigma$-algebras, measurable functions, inverse images). Write them down explicitly, it helps. See what are the elements of the sets involved and the properties they satisfy.
Think for a bit. (We're doing mathematics after all!)

Hope that helps,


Dense Subspaces: Intersection Hilbert Space: $\mathcal{H}$

Dense Subspaces:
$$\mathcal{D},\mathcal{D}'\leq\mathcal{H}:\quad\overline{\mathcal{D}},\overline{\mathcal{D}'}=\mathcal{H}\not\Rightarrow\mathcal{D}\cap\mathcal{D}'\neq\{0\}$$
(Counterexample?)

Let $\mathcal{H}=L^2[0,1]$. Let $\mathcal{D}$ be the subspace of polynomials on $[0,1]$. Let $\mathcal{D}'$ be the subspace generated by $\{ \sin(n\pi x) \}_{n=1}^{\infty}$. Both are dense, and they have nothing in common except the $0$ vector.

What about subspaces $\mathbb Q$ and $\mathbb R\setminus \mathbb Q$  in $\mathbb R$?


If we define $\arcsin(x)=\int_0^x 1/\sqrt{1-t^2}dt$, how to show $\arcsin(x)$ is continuous and increasing Specifically, want to show that $\arcsin(x)$ is an increasing continuous function from $[-1,1]$ onto $[-\pi/2, \pi/2]$. My thought is that there is not much work to do since the integrand is positive, the function must be increasing? How does one show continuity?

From the fundamental theorem, $F(x)=\int_0^xf(t)\,\mathrm dt$ with $f$ continuous, implies $F'(x)=f(x)$. So $\arcsin(x)$ is not just continuous, it is differentiable!

Note that we have some problems at $x=\pm1 $ because the integrand grows to infinity thaer. But that implies that we have an improper integral for these $x$, so that by definition $\arcsin(\pm1)=\lim_{x\to\pm1}\arcsin(x)$.

The following result may be helpful for you:

  $f^{-1}(x)$ is increasing and continuous iff $f(x)$ is increasing and continuous.


Why does ln n use root n as a direct comparison? $$
\sum^{\infty}_{n=1}\frac{(\ln n)}{n^2}
$$

Use the direct comparison test

My teachers solution is:

$\frac{(\ln n)}{n^2} < \frac{\sqrt n}{n^2} = \frac{1}{n^\frac{3}{2}}$ and so it converges because p-series > 1

How does the direct comparison go from $\ln n$ to $\sqrt n$?

hint

For $x\geq 4$, put

$$f (x)=\ln (x)-\sqrt{x}$$

$$f'(x)=\frac {2-\sqrt {x}}{2x}\leq 0$$

thus $f $ is decreasing at $[4,+\infty). $

For   enough great $n $, we have

$$f (n)\leq f (4)=\ln (4)-2\leq 0$$
and
$$\ln (n)\leq \sqrt {n} .$$

we also use this to prove that

$$\lim_{n\to\infty}\frac {\ln (n)}{n}=0.$$

It is a well known fact that $y=\ln x$ is always growing at a slower rate than $f(x)=x^\alpha$ for all values of $\alpha\gt0$ as $x\to+\infty$. It is straightforward to prove this fact.

Thus, your teacher could have chosen $\alpha = 0.0001$, for instance. The choice of $\alpha = 1/2$ is just a convenience because she could then obtain an inequality for all values of $n\ge 1$.


Relative interior of convex sets It is known that whenever a set $C$ in $\mathbb{R}^n$ is convex then $\text{cl}(\text{ri}\hspace{0.1cm} C)=\text{cl}\hspace{0.1cm} C$ and $\text{ri}(\text{cl}\hspace{0.1cm}C)=\text{ri}\hspace{0.1cm}C$ where $\text{cl}\hspace{0.1cm}C$ and $\text{ri}\hspace{0.1cm}C$ are the closure and the relative interior of a set $C$. Why wouldn't this statement hold in general? What are counterexamples when $C$ is not convex?

Consider a sphere $C$ (without interior) in $\mathbb{R}^2$. How would you sensibly define "relative interior"? The set $C$ should serve as a counterexample.


How do I prove this field homomorphism is an isomorphism? The question is as follows. Let $F$ be a finite field with unit $1$ not equal to zero. Let the function $f: F \to F$ be given by $f(x) = x^3$, where the $\operatorname{char}(F) = 3$. Prove it is a ring isomorphism.

I can prove it is a ring homomorphism by showing $f(xy) = (xy)^3 = x^3y^3 = f(x)f(y)$ by commutativity. Similarly, since the characteristic is three,

$$(x+y)^3 = x^3 + y^3$$

$$f(a+b) = f(a) + f(b)$$

$$f(1) = 1,\ \ \textrm{and}\ \  f(0) = 0$$

Now, how do I show $f$ is a bijection?

That homomorphism is necessarily injective, but not necessarily surjective. For example, the field $F=\mathbb{F}_3(t)$ has characteristic $3$, and the homomorphism $\varphi:F\to F$ defined by $\varphi(a)=a^3$ for all $a\in F$ is not surjective because there is no $a\in F$ with $\varphi(a)=t$.

For a more in-depth analysis, take a look at my answer on the thread How to prove that the Frobenius homomorphism is surjective?

To get started, $\ker(f)$ is an ideal in the ring $F$.


Machine epsilon definition Assume representation of floating point in decimal, in the form $0.q_1q_2...q_n\cdot 10^{exp}$. By definition $1+\epsilon_{\text{mach}} = 1$, but a textbook claims that with this definition, $\epsilon_{mach} = 10^{-n}$.
The question I have is, suppose I do $0+\epsilon_{\text{mach}} = 0.00....01 \cdot 10^0 \ne 0$. It is representable in floating point as non-zero number. Doesn't this contradict the definition of $\epsilon_{\text{mach}}$?
And if we were to say $\epsilon_{mach} = 10^{-(n+1)}$, then wouldn't another number, say $2\cdot 10^{-(n+1)} > \epsilon_{mach}$ also be ignored?

What you are missing is that floating-point addition isn't quite the same as (theoretical) real addition.  A floating-point number has only finitely-many digits in its mantissa.  When you add two floating-point numbers of different exponents, the mantissa of the smaller has to be shifted rightward, to align the radix points correctly - e.g if you add 1 to 1e-5, you are actually adding 1.0000... and 0.00001000... together.  If you have to shift rightward more than the number of digits of the mantissa, when their sum is (truncated or rounded, depending) to the mantissa length, the extra digits past the end get dropped, so in effect the sum doesn't change the larger number.
This means the machine epsilon is the value 1 multiplied by the smallest (in magnitude) negative power of ten such that this dropping occurs.


Sample standard deviation relationship to true standard deviaton If I have a set of observations $x_1, ..., x_n$ which come from the distribution

$X_i \sim N(\mu, \sigma^2)$ independently

then why is the standard deviation of the sample

$\sigma/\sqrt{n}$

This is a result I have been told by a lecturer but I'm not sure why its true.  Just to clarify, I am NOT asking about the standard deviation of the sample mean here.

Let x1, x2, x3,... be iid r.v and  X i ∼N(μ,σ^2 )
(x1+x2)/2 has variance cov((x1+x2)/2,(x1+x2)/2)= 1/4var(x1)+1/4var(x2)+2cov(x1/2,x2/2) where 2cov(x1/2,x2/2) = 0 ,then cov((x1+x2)/2,(x1+x2)/2)= 1/4var(x1)+1/4var(x2)=1/2 (σ^2 + σ^2). We take the square root of it and get  σ for distribution of (x1+x2)/2 = σ/square root of 2. Same thing happens with (x1+x2+...+xn)/n(ommited), the result follows that its sd is σ/square root of n.
This proof requires theorems that x1+x2 follows normal distribution ~ N(2μ,2σ^2)
sorry for not providing it, and for writtig in non-math format for symbols as I am new on this site.


A committee of four people, containing at least one man and one woman, must be chosen from four men and three women. A committee of four people, containing at least one man and one woman, must be chosen from four men and three women. How many different committees are possible?

I dont really now how to solve this. I tried solve them by counting them in groups. but thats not really the right way I guess. Can anyone give me a clue to solve this.

Hint: Choose four people from seven.  You only need to avoid the one combination of picking all four men.

Let's think about this. There are four ways to choose one man and three ways to choose one woman. This means that there are 4 * 3 = 12 ways to choose one man and one woman. So what's left over? We have 3 men + 2 woman left to fill the remaining two positions. Gender doesn't matter anymore since we've met the criteria of picking one man and one woman. That means there are 5 * 4 = 20 ways to choose the rest of the committee. Combining what we now know, there are 12 * 20 = 240 ways to organize this committee.


Expected Value of independent random variables with an ${\rm Exp}(\lambda)$ common distribution Question is:

Jack is selling his house, and has decided to accept the first offer exceeding $k$. Assume that successive offers are independent random variables with common distribution $\mathrm{Exp}(\lambda)$.
a) Find the expected number of offers he will reject before he sells the house;
b) Find the expected value of the offer he will accept.

I have solved Part A as :
$p = e^{-\lambda r}$
$P(N=n) = (1-p)^{n-1}p$
$E(N) = \sum_{n=1}^\infty nP(N=n) = p \sum_{n=1}^\infty n(1-p)^{n-1}$
Eventually this will reduce down to $E(N) = \frac {1}{p} = e^{\lambda r}$
This should be correct.
Part B :
I am not sure how we go about finding the value of the actual offer that he will accept. I feel we have to find some conditional expectation but not sure. Any help would be great!

The exponential distribution is memoryless: the conditional distribution of $X-k$ given $X>k$ coincides with the distribution of $X$ (you may check this property). That said, $$\mathrm{E}[X\mid X>k] = k + \mathrm{E}[X-k\mid X>k] =  k + \mathrm{E}[X].$$

Can you see why this is the calculation?

$$
{\cal E}[x] = \frac{\int\limits_{x = x_0}^\infty x p(x)\ dx }{ \int\limits_{x = x_0}^\infty p(x)\ dx}
$$

The only conditions you must consider are those for $x>x_0$.

The only cases that contribute to your answer are those where the value is greater than some cutoff, $x_0$.  Consider this the relevant distribution.  The numerator is the expected value of $x$ from this distribution.  However, this is not a true distribution because it isn't normalized.  That's what the denominator accomplishes, where of course $p(x) \propto e^{-x}$.


Bartle, Introduction to Real Analysis (2011 4 ed), Ex 14, Section 6.2, p 179. Let $I$ be an interval and let $I : I \rightarrow \mathbb{R}$ be differentiable on $I$. Show that if the derivative $f'$ is never $0$ on $I$, then either $f'(x) > 0$ for all $x \in I$ or $f' (x) < 0$ for all $x \in I$.

I was thinking to proceed by Darboux's theorem. Is that correct?

Write out the book's details, like section and page numbers, as I did. You're correct. Here are details.  In his solution manual, Bartle wrote

Apply Darboux’s Theorem 6.2.12.


derivative of multiplication of three matrices with a matrix In short, my problem is to compute $\frac{d(X^tAX)}{dX}$; where both $A$ and $X$ are matrices.

I have to maximize a negative-log likelihood function $L$

$$L = \frac{1}{2}\ln(|\Sigma|)+\frac{1}{2}\varepsilon^t\Sigma^{-1}\varepsilon;$$

where $\Sigma$ is the covariance matrix, $\varepsilon$ is a column vector of residuals (in my case) and $t$ denotes the transponse. The probelm is that $\Sigma$ is a function of other matrices

$$\Sigma = J^tCJ$$

where, both $J$ and $C$ are matrices. The matrix $J$ is again a function of a vector $\lambda$. I have to maximize the function $L$ w.r.t. vector $\lambda$. I tried chain rule to solve this problem as follows

$$\frac{dL}{d\lambda}=0\implies\frac{dJ}{d\lambda}\frac{d\Sigma}{dJ}\frac{dL}{d\Sigma}=0.$$

In the above equation, $\frac{dJ}{d\lambda}$ and $\frac{d\Sigma}{dJ}$ becomes a tensor. So, I am no longer able to write these quantities on paper. Also, taking derivative of $L$ w.r.t. an individual element of $ \lambda$ does not solve the problem. There are few online resources which suggest using $vec$ operator to deal with tensors; but they heavily use Kronecker product etc. which I have not been able to understand very well, because most of the online material is very opaque.

Can someone please point me to the solution? If someone can refer a good text dealing with a similar problem, that would be great.

As you've discovered, the chain rule can be difficult to use with matrix functions. Instead let's stick with differentials, and change the independent variable as necessary, until we obtain an expression in terms of $d\lambda.\,$ Then in the final step, we can recover the gradient.

For convenience, define some new variable
$$\eqalign{
S &= S^T = \Sigma =J^TCJ \cr
E &= E^T = ee^T \cr
M &= M^T = S^{-1} -S^{-1}ES^{-1} \cr
G &= \frac{\partial J}{\partial\lambda} \cr
}$$
Let's also use a colon to denote the inner/Frobenius product, which is a convenient notation for the matrix trace, $$A:B={\rm tr}(A^TB)$$

Now we can write the objective function in terms of these definitions
$$\eqalign{
2L &= \log\det S + E:S^{-1} \cr
\cr
2\,dL &= d\log\det S + E:dS^{-1} \cr
 &= d{\rm tr}\log S - E:S^{-1}\,dS\,S^{-1} \cr
 &= (S^{-1} - S^{-1}ES^{-1}):dS \cr
 &= M:dS \cr
 &= M:(dJ^T\,CJ + J^TC\,dJ) \cr
 &= M(CJ)^T:dJ^T + C^TJM:dJ \cr
 &= (CJM + C^TJM):dJ \cr
 &= (C+C^T)JM:G\,d\lambda \cr
\cr
\frac{\partial L}{\partial\lambda}
 &= \frac{1}{2}(C+C^T)JM:G \cr
 &= \frac{1}{2}(C+C^T)\,J\,(\Sigma^{-1}-\Sigma^{-1}ee^T\Sigma^{-1}):\frac{\partial J}{\partial\lambda} \cr
\cr
}$$
I think that last expression has cast everything back in terms of your original variables.

Note that the rules for rearranging the Frobenius product follow from the properties of the trace. Here is a quick list
$$\eqalign{
A:BC
 &= B^TA:C \cr
 &= AC^T:B \cr
 &= BC:A \cr
 &= (BC)^T:A^T \cr
}$$

When you differentiate a matrix wrt a matrix you need a special calculus developed by Neudecker and Pollock (as key names). The solutions are matrices of matrices. For example to differentiate a matrix X wrt X we get In^2 ie the identity matrix of order n squared. To differentiate AX wrt to X the answer is (I @ A) where @ is Kronecker product of matrices. There are many papers on the subject and a few different calculuses. I take the Pollock and Neudecker method as the one to follow. There are mistakes in some of the others.


Compute the floor of $(\sqrt{3}+ 1)^5$, or of $(x+ 1)^n$ with $x$ irrational How to find $\lfloor(x+ 1)^n\rfloor$ where $x \in\Bbb R - \Bbb Q$ and $n \in \Bbb Z_+$ without using a calculating or calculating the series by hand.
For example, what is $\lfloor(\sqrt{3}+ 1)^5\rfloor$ ?

I thought I would use Bernoulli's inequality, $ 1+ 5\sqrt{3} \le(\sqrt{3}+ 1)^5$, but it is too weak to give a correct answer.
I also tried, $2 < \sqrt{3} + 1 < 3 \implies 32 < (\sqrt{3} + 1)^5 < 243$ but this is also too weak.
I can use $\lfloor x \rfloor = x - \{ x \}$ where $\{x\}$ is fractional part function. Here I need to find $\{x\}$. I don't have any idea to do that either.

You have chosen a very special example.  $1+\sqrt 3$ is a Perron number in that its absolute value exceeds $1$, clearly, but the absolute value of its conjugate, $1-\sqrt 3$, is less than $1$.

To work with this example, start with the minimal polynomial $x^2-2x-2$.  That leads us to consider the Fibonacci-like recursion $$a_{n+2}=2a_{n+1}+2a_n$$  Of course such a recursion will always have solutions of the form $a_n=A(1+\sqrt 3)^n+B(1-\sqrt 3)^n$ for suitable constants $A,B$.  For our purposes we want $A=B=1$ so we get the initial conditions $a_0=2=a_1$.

We use the recursion to compute $a_5=152$.  This means that $$(1+\sqrt 3)^5=152-(1-\sqrt 3)^5$$  thus $$\boxed {\lfloor (1+\sqrt 3)^5\rfloor =a_5=152}\quad \& \quad  \boxed {\{(1+\sqrt 3)^5\}=-(1-\sqrt 3)^5}$$

Of course, this holds for all odd exponents.  For even exponents you get $$\lfloor (1+\sqrt 3)^{2n}\rfloor = a_{2n}-1\quad \& \quad \{(1+\sqrt 3)^{2n}\}=1-(1-\sqrt 3)^{2n}$$

Note:  this trick will only work with Perron Numbers.

First consider $(\sqrt {3}+1)^5=a + b \sqrt{3}$ . Now consider $(\sqrt {3}+1)^5-(\sqrt {3}-1)^5=2a , (\sqrt {3}+1)^5+(\sqrt {3}-1)^5=2b\sqrt {3} $ . I think you know why this is true. Now $\lfloor(\sqrt {3}+1)^5\rfloor=\lfloor a+b\sqrt {3}\rfloor $


Show $\sum_{k=1}^{\infty}\left(\frac{1+\sin(k)}{2}\right)^k$ diverges Show$$\sum_{k=1}^{\infty}\left(\frac{1+\sin(k)}{2}\right)^k$$diverges.

Just going down the list, the following tests don't work (or I failed at using them correctly) because:

$\lim \limits_{k\to\infty}a_k\neq0$ — The limit is hard to evaluate.
$\lim \limits_{k\to\infty}\left|\dfrac{a_{k+1}}{a_k}\right|>1$—Limit does not converge; inconclusive.
$\lim \limits_{k\to\infty}\sqrt[k]{|a_k|}>1$—Limit does not converge; inconclusive.
$\int \limits_{1}^{\infty}a_k\,dk$—How do I even do this.
There exists a $|b_k|\geq|a_k|$ and $\sum b_k$ converges—Cannot think of any such a $b_k$.
$\lim \limits_{k\to\infty}\cfrac{a_k}{b_k}$ exists and $\sum b_k$ converges — Cannot think of any such $b_k$.

Can I have some help?

EDIT

We will show that there is no $\delta$ or corresponding $\epsilon$ so that $k>\delta$ implies$$\left|\left(\frac{1+\sin(k)}{2}\right)^k-\lim_{n\to\infty}\left(\frac{1+\sin(n)}{2}\right)^n\right|<\epsilon$$

Let the first term be denoted $a_k$ and the second $L$ (for limit). Pick the the smaller number of $|a_{\frac{3\pi}2}-L|$ or $|a_{\frac\pi2}-L|$. Whichever was chosen (denote choice as $\epsilon$), it is clear that setting $k:=k+\pi$, which is greater than $\delta$, will produce a result such that $|a_k-L|\geq\epsilon$.

Therefore, the limit does not exist, and the sum diverges.

EDIT AGAIN

The proof above is no good. More help pls. I can't figure this one out.

The trick is to use the classic theorem of Hurwitz on rational approximation of irrationals, that there are infinitely many $m,n$ with $|\frac\pi2-\frac{m}{n}|\lt\frac1{n^2}$ (more specifically, you need infinitely many such pairs with $n\equiv 1\bmod 4$, but this result is known; see below).  Any such pair will have $|m-\frac{n\pi}{2}|\lt\frac1n\lt\frac2m$; but then $\sin(\frac{n\pi}{2}) = 1$ (this is where the restriction on $n$ comes from), and by quick application of either the addition identity for sin or the mean value theorem, we get $\sin(m)\gt1-\frac2m$ for any such pair.  This means that infinitely often we have $\frac{1+\sin(m)}{2}\gt1-\frac1m$, and $\left(\frac{1+\sin(m)}{2}\right)^m\gt\left(1-\frac1m\right)^m$, and you should be able to bound the RHS of this away from zero.  This means that you've found infinitely many $a_m$ bounded away from zero, and that's enough to show divergence.

IMPORTANT CAVEAT: as @robjohn points out in the comments, it's not as easy as I thought at first to get the Hurwitz result in an arbitrary residue class!  The paper "On The Approximation Of Irrational Numbers With Rationals Restricted By Congruence Relations" gives the following result:

  For any irrational number $\xi$, any $s\geq 1$, and any integers $a$
  and $b$, there are infinitely many integers $u,v$ satisfying
  $\left|\xi-\frac uv\right|\lt \frac{2s^2}{v^2}$ with $u\equiv a\pmod s$ and $v\equiv b\pmod s$.

We can take $\xi=\frac\pi2$, $s=4$, $b=1$ here and get infinitely many $u,v$ with $\left|\frac\pi2-\frac uv\right|\lt\frac{8}{v^2}$ and $v\equiv 1\pmod 4$; this is a factor of 8 away from the result above, but it's still good enough to give infinitely many $m$ with $\left(\frac{1+\sin(m)}{2}\right)^m\gt\left(1-\frac8m\right)^m$ and that's good enough to give a bound away from zero and prove divergence.

It's clearly convergent because of

$$ 0 < \frac{1+sin(n)}{2} < 1 $$

$$ \sum_{n=1}^{\infty} a^n \ , \ 0<a<1 $$


Least prime of the form $38^n+31$ I search the least n such that

$$38^n+31$$

is prime.

I checked the $n$ upto $3000$ and found none, so the least prime of that form must have more than $4000$ digits. I am content with a probable prime, it need not be a proven prime.

This is not a proof, but does not conveniently fit into a comment.

I'll take into account that $n=4k$ is required, otherwise $38^n+31$ will be divisible by $3$ or $5$ as pointed in the comments.

Now, if we treat the primes as "pseudorandom" in the sense that any large number $n$ has a likelihood $1/\ln(n)$ of being prime (which is the prime number density for large $n$), the expected number of primes for $n=4,8,\ldots,4N$ will increase with $N$ as
$$
\sum_{k=1}^N\frac{1}{\ln(38^{4k}+31)}
\approx\frac{\ln N+\gamma}{4\ln 38}
\text{ where }\gamma=0.57721566\ldots
$$
and for the expected number of primes to exceed 1, you'll need $N$ in the order of 1,200,000.

Of course, you could get lucky and find it at much lower $n$, but a priori I don't see any particular reason why it should be...or shouldn't.

Basically, in general for numbers $a^n+b$, the first prime will usually come fairly early, otherwise often very late (or not at all if $a$ and $b$ have a common factor).

Of course, this argument depends on assuming "pseudorandom" behaviour of the primes, and so cannot be turned into a formal proof. However, it might perhaps be possible to say something about the distribution of $n$ values giving the first prime over different pairs $(a,b)$.

In general, is there any prime of the form $\frac{ab^n+c}{\gcd(a+c,b-1)}$ with integer $n\ge1$, for fixed integers $a\ge1$, $b\ge2$, $c\ne0$, $\gcd(a,c)=1$, $\gcd(b,c)=1$? It is unknown whether this problem is solvable, e.g. let $a=4$, $b=72$, $c=-1$, the smallest prime of the form $\frac{4\cdot72^n-1}{\gcd(4+1,72-1)}$ with $n\ge1$ is at $n=1119849$
If we want to solve this problem, we must for every such $(a,b,c)$ integer triple, either find a prime of this form or prove that there is no prime of this form, e.g.:
$(a,b,c) = (78557,2,1)$, in which all numbers are divisible by at least one of $3, 5, 7, 13, 19, 37, 73$
$(a,b,c) = (11047,3,1)$, in which all numbers are divisible by at least one of $2, 5, 7, 13, 73$
$(a,b,c) = (47,8,1)$, in which all numbers are divisible by at least one of $3, 5, 13$
$(a,b,c) = (334,10,-1)$, in which all numbers are divisible by at least one of $3, 7, 13, 37$
$(a,b,c) = (9,4,-1)$, in which all numbers factored as difference of squares
$(a,b,c) = (1,8,1)$, in which all numbers factored as sum of cubes
$(a,b,c) = (25,12,-1)$, in which even $n$ factored as difference of squares and odd $n$ is divisible by $13$
$(a,b,c) = (64,936,-1)$, in which even $n$ factored as difference of squares and $n$ divisible by $3$ factored as difference of cubes and other $n$ divisible by either $37$ or $109$, etc.


Given a ring with circumference n, if a person walks s distance per step on it, could we prove that the person will eventually step on every point? If we add more restriction so that the question became

Given a circle divided into x points each have same distance between each other. Now a person who walks s amount of point per step, if x and s are co-prime, then eventually the person would step on every points.

But that only applies on $\mathbb{Z}^+$ realm, could we extend it to $\mathbb{R}$ realm to say that if circumference is not a multiple of the distance the person walks each step, eventually the person would step through every point on the ring?
What I thought is that if circumference $n$ isn't a multiple of the step distance $s$, it means $n\mod{s}\neq 0$ and with an offset not equal to 0, I think eventually the offset would go through the whole circle hence walking though all points. But this was only obvious what the points on a circle in finite, and if we push things to continuum, I couldn't give a solid proof.

I think if written in style of sets, we could write (n is circumference, s is step distance)
$$
n,s\in\mathbb{R} \\
\mathbb{A}=\{n\cdot s, n\in\mathbb{Z}^+\} \\
\mathbb{B}=\{x\mod{n}, x\in\mathbb{A}\}\\
\text{Ask if }\mathbb{B}=[0,n)
$$

My initial reaction is a proof by contradiction. Assume the person does not step on every point. All that is needed to be proven is something to the degree of the amount stepped eventually repeats, that is it is a repeating decimal or something. This is just a rough intuition/idea; but again I think mathematics is all about ideas so I hope this gives some insight and helps.


Standard Error is of Population Total We have the following data and we are required to obtain the standard error of unbiased estimate of the population total:

$N=160,n=64,\sigma^2=4$

My approach

We know that:

$SE(\bar{X})=\frac{\sigma}{\sqrt{n}}$
So, it can be written as:

$SE(\frac{Total}{n})=\frac{\sigma}{\sqrt{n}}$

Which in turn will be equal to:

$SE(Total)=(\sigma)(\sqrt{n})$.

In the above formula, after plugging in values, I am getting $SE=(2)(8)=16$

But this is not correct. The correct answer is $40$. Am I doing it incorrectly? I am not sure.

Any help?

The correct answer is obtained by multiplying the standard error with the total population.

S.E.$~=\frac{2}{8}\times160
   =40$


Solving non-linear recurrence relation $p_{n+1} = \frac{2p_n}{p_n + 1}, p_1 \neq 0$ Given the following recurrence relation $p_{n+1} = \frac{2p_n}{p_n + 1}, p_1 \neq 0$, I want to show that as $n \rightarrow \infty, p_n \rightarrow 1$.

By assuming that such a limit exists, and setting $p_{n+1} \approx p_n$ for large $n$, I found that $p_n$ tends to 1.

Is there a more rigorous way of doing this?

Note: I just want to show that $p_n$ tends to 1, I don't need an explicit formula for $p_n$.

Hint

Let $q_n=\frac 1 {p_n}$ to get something much more pleasant to work

If the sequence converges, it converges to $p$ such that

$$p=\frac{2p}{p+1}$$ or $$p^2-p=0.$$

But as $p_n\ne0\implies p_{n+1}\ne0$, $p=0$ is excluded, and $p=1$.

For the study of convergence, the hint by @claudeleibovici is highly recommended.


Finding a necessary and sufficient conditon for the coefficient $(p,q)$ so that $fRg$ where $f(x)=x^2$ and $g(x)=x^2+px+q$ $R$ is the relation defined in $\Bbb R^{\Bbb R}$  by:

$$fRg \Leftrightarrow \exists \psi \in \Bbb R^{\Bbb R} , \psi  \text{ bijective and }\psi \circ f = g \circ \psi$$

I know that $R$ is an equivalence relation however I don't see how I can use that in any way.
I tried to find different conditions like $(p-1)²\gt 4q$ but there's  no way to prove that they are sufficient.

Further observations, too long for a comment.

We have
$$\psi(x^2)=\psi^2(x)+p\psi(x)+q,\tag{1}$$
which gives for $k\in\{0,1\}$ that
$$\psi(k)=\psi^2(k)+p\psi(k)+q,\tag{2}$$
from where in case of
$$(p-1)^2\geq 4q,\tag3$$
the solutions
$$\psi(k)=-\frac{p-1}{2}\pm\sqrt{\frac{(p-1)^2}{4}-q}$$
follows (which doesn't mean that $\psi(0)=\psi(1)$).  Now if we assume that $\psi$is $C^1$, we have
$$\psi'(x^2)\cdot 2x=2\psi(x)\psi'(x)+p\psi'(x),$$
which gives for $x=0$ that
$$0=\psi'(0)\bigl(2\psi(0)+p\bigr),$$
that is either $\psi'(0)=0$ or $\psi(0)=-p/2$.  Let's first deal with $\psi(0)=-p/2$ and plug it in $(2)$, which yields in
$$-\frac12=\pm\sqrt{\frac{(p-1)^2}{4}-q}.$$
Now that gives $4q=p^2-2p$ as Michael Burr stated above.  Investigating $\psi'(1)$ gives  the same result: either $\psi'(1)=0$ or $\psi(1)=(2-p)/2$ and $4q=p^2-2p$ again.  This leaves the cases $\psi'(k)=0$ open. If we further assume that $\psi$ is also $C^2$, the $\psi''(k)$ must be zero as well, otherwise $\psi$ would not be bijective.

Now we can give an example of $\psi$, namely the straight line passing through $(0,-p/2)$ and $(1,1-p/2)$:
$$\psi(x)=x-\frac p2.$$

Consistent with comments, we can observe that $\psi\left(0\right)$ is a fixed point of $g$. And another important observation is that $$\psi\left(t^2\right)=\psi\left(t\right)^2+p\psi\left(t\right)+q=\psi\left(-t\right)^2+p\psi\left(-t\right)+q$$ holds for any natural $t$. Since $g$ is quadratic, it must be $\psi\left(t\right)=\psi\left(-t\right)$ or $\psi\left(t\right)+\psi\left(-t\right)=-p$ where $t\neq0$, and $\psi$ is bijective according to assumption, so the latter holds. $\\$Now it's clearly that $\psi$ also maps $0$ to the extreme point of $g$, hence we obtain the general expression of $g$ :$$g=\left(x-a\right)^2+a$$, where $p=-2a,\,q=a^2+a$ and $a$ is an arbitrary natural number. $\\$Of course the sufficiency could be proved. In fact, let $f\left(x\right)=x^2$ and $g\left(x\right)=\left(x-a\right)^2+a$, $\psi\left(x\right)=x+a$ is an eligible mapping.


Irreducible polynomial over Q Let $f(x) = 3x^4+6x^3+24x^2+18 \in \mathbb Z[x]$. Is $f(x)$ irreducible over $\mathbb Q$ ?

In my course, Eisenstein's criterion is apply for monic polynomial only, hence, I can't use it with p =2. If I can, everything turn easy.

My attempt: If $f(x)$ is irreducible over $\mathbb Z$, then $f(x+1)$ is irreducible as well. Replace x by x+1, I have $f(x+1) = 3(x+1)^4+6(x+1)^3+24(x+1)^2+18\\=3x^4+18x^3+60x^2+78x+51$

But in mod 3, I have f(x+1)=0 I don't know how to argue further. Please, explain me

Since $3$ is invertible in $\mathbb Q$, $f$ is irreducible in $\mathbb Q[X]$ iff so is $\frac f3=x^4+2x^3+8x^2+6$. Now you can apply Eisenstein's criterion.

I have given two speeches in South America over a decade ago with an irreducibility criteria I established: “if a polynomial $h(x)$ of $\mathbb{Z}[X]$ has degree $n$ and $h(n)$ is prime for $2n + 1$ rational integers then $h$ is irreducible”. I apply this result here. The nine couples $(n, h(n)) = (1, 17), (-1, 13), (-7, 2113),$ $(-11, 12953), (13, 34313), (19, 146933),$ $(31, 990797), (43, 3592613), (-65, 17335181)$ where the nine $h(n)$ are prime, prove, according to this result, that $h = \frac{f}{3}$ is irreducible over $\mathbb{Z}$ an so is $f$.

NOTE: This criterion is not very comfortable to apply but could be useful sometimes in algebraic number theory.


Prove that $\limsup_{n\to\infty} |X_n|/n \le1 $ almost surely Suppose $\{X_n\}$ a sequence of random variables.
If $\sum_{n=1}^\infty P(|X_n|>n)< \infty$

Prove that $$\limsup_{n\to\infty}\frac{ |X_n|}{n} \le1 $$ almost surely

What i have done so far:

I thought using the Borel-Cantelli lemma could lead me somewhere, but i didn't have any luck.

From Borel-Cantelli lemma we know that if $\sum_{n=1}^\infty P(|X_n|>n)< \infty$ then $P(|X_n|>n)=0$

How could I proceed?
I would appreciate any help, advice. Thank you all very much in advance for your time and concern.

The first Borel-Cantelli lemma yields
$$\mathbb P\left(\limsup_{n\to\infty}|X_n|>n\right)=0. $$
As for each $n$ $$\{|X_n|>n\}\subset \bigcup_{k=n}^\infty \{|X_k|>k\}, $$
it follows that
\begin{align}
0&=\mathbb P\left(\bigcap_{n=1}^\infty\bigcup_{k=n}^\infty \{|X_k|>k\}\right) \\&=\mathbb P\left(\lim_{n\to\infty}\bigcup_{k=n}^\infty \{|X_k|>k\}  \right)\\
&=\lim_{n\to\infty}\mathbb P\left(\bigcup_{k=n}^\infty \{|X_k|>k\} \right)\\
&\geqslant\lim_{n\to\infty}\mathbb P(|X_n|>n)
\end{align}
and hence $\lim_{n\to\infty}\mathbb P(|X_n|>n)=0$. Further, $$\bigcap_{k=n}^\infty \{|X_k|>k\}\subset\{|X_n|>n\} $$
so that
\begin{align}
\mathbb P\left(\limsup_{n\to\infty} |X_n|\leqslant n\right) &= \mathbb P\left(\bigcap_{n=1}^\infty\bigcup_{k=n}^\infty\{|X_k|\leqslant k\}\right)\\
&=1 - \mathbb P\left(\bigcup_{n=1}^\infty\bigcap_{k=n}^\infty \{|X_k|>k\} \right)\\
&=1 - \mathbb P\left(\lim_{n\to\infty} \bigcap_{k=n}^\infty\{|X_k|>k\} \right)\\
&=1 - \lim_{n\to\infty}\mathbb P\left(\bigcap_{k=n}^\infty\{|X_k|>k\}\right)\\
&\geqslant1 - \lim_{n\to\infty}\mathbb P(|X_n|>n)\\
&= 1,
\end{align}
which implies that
$$\mathbb P\left(\limsup_{n\to\infty} \frac{|X_n|}n\leqslant 1 \right)=1. $$

Important inequalities

Williams - Probability with Martingales

Deduced similarly:

(iii) If $\liminf x_n > z$, then

$ \ \ \ \ \ \ \ (x_n > z)$ eventually (that is, for infinitely many n)

(iv) If $\liminf x_n < z $, then

$ \ \ \ \ \ \ \ (x_n < z)$ infinitely often (that is, for infinitely many n)

By BCL1, we have $P(\limsup (|X_n| > n)) = 0$

$$\to P(\liminf (|X_n| \le n)) = 1$$

$$\to P(\liminf (|X_n|/n \le 1)) = 1$$

$$\to P([\limsup |X_n|/n] \le 1)) = 1$$

The last step follows by the contrapositive of 2 (see above)


Becoming Better at Math How can I become excellent at math? It really interests me but when I fail I become demotivated and begin to give up.

EDIT: Could anyone suggest books for someone with a math education that just barely touches on high-school Algebra (got into parabolas, rationalizing, some graphing and functions). This is what I am currently doing: attending high school as a Junior.

Be honest with yourself about what you do and don't understand. Don't fall victim to "proof by intimidation," where someone attempts to shame you into saying you understand something by implying that you're dumb if you don't. Always ask questions until you really get it. Similarly, don't let yourself move on before you understand something fully; pretty much everything will come back to bite you at some point down the line.  If this seems like a pessimistic attitude, it's not - it is simply humility, and humility is the path to genuine knowledge.

EDIT: I just noticed your question about books. How To Prove It is a great transition to more advanced mathematics.  After that, check out some of the Dover books, they are all very cheap and most are decent introductions to their respective subjects.

You may find it useful to start with http://www.khanacademy.org/

Once completed, look for additional resources and side by side track how much you completed from http://mathworld.wolfram.com/


What is the probability of sinking all ships in a simplified game of battleship? Consider a simplified game of battleship. We are given a $4\times 4$ board on which we can place $2$ pieces. One destroyer which is a $1 \times  2$ squares and a submarine that is $1 \times 3$ squares. The pieces are placed on the board and cannot overlap, and are placed either vertically or horizontally.

Your opponent picks $8$ (of the $16$ squares) uniformly at random and then "shoots" at these $8$ squares. A ship is "sunk" if all the squares were the ship was were "shot".

What is the probability that both of the ships are sunk?

This is what I was told the answer is:

$$\frac{11 \choose 3}{16 \choose 8}$$

Since the solutions don't have an explanation this is what I think is the correct explanation, with the answer they gave (if you know the actual/correct answer, please explain it to me):

${16 \choose 8}$ are the total number of ways that the opponent can pick where to shoot bombs. Therefore the total number of outcomes (that we could choose) that we are considering is ${16 \choose 8}$.

That part makes sense to me. However, what doesn't make $100\%$ sense to me is how to get the numerator for our probability.

Given a fixed location where my ships are, then there are $5$ blocks that I have chosen. This can be interpreted that I have "fixed" a set of $5$ numbers (the location of the ships) and I am choosing from it. Therefore, from this set of $5$ numbers, the number of ways to sink the ships are:

First the opponent chooses the five correct location of the ships: $5 \choose 5$

Second, then the opponent chooses the remaining $3$ numbers on the board (since we already choose $5$ and we have to bomb $3$ places, the remaining number of time we can choose is $3$). However, we choose from the remaining $16-5 = 11$ remaining places leading to: $11 \choose 3$

Which is what the answer seem to suggest... However, I do not think this analysis is $100\%$ correct.

This is the reason:

This analysis only holds if I fixed a location for the ships. However, the question asks for the probability that both ships are sunk. For me that event should consider all possible places where the ships could be placed, which the answer that I explained doesn't incorporate. Since the question restricts how to place ships, because a destroyer has to have its whole body connected and hence its pieces next to each other, then it complicates how to count.

With this extension (different interpretation of the question), what would the probability be?

It feels to me that its the above probability, times the number of ways we can place the ships with the restriction that we can just "split the ships". What do people think?

Also, is my second interpretation of the question meaningful? Maybe there is a reason this interpretation wasn't used, maybe it leads to a problem that doesn't make sense? Not sure...

Also, it seems to me that I might be confused in the difference between the conditional and unconditional event in question, if they have the same probability could you please explain? I obviously would have not written my above explanation if I knew that the two event were actually the same. Please clarify this last point, since it seems to be the whole reason that this question even exists.

You put the ships in some $5$ squares on the board.  The conditional probability  that the ships are sunk, given your choice, is the probability that the opponent chooses those $5$ squares plus any $3$ other squares, and that is ${11 \choose 3}/{16 \choose 8}$.  Since this is the same no matter which choice you make,
it is also the (unconditional) probability that your ships will be sunk.

EDIT:
Now a different (and maybe more interesting) question is whether the opponent has a better strategy than a random choice of the $8$ squares.  The answer is certainly yes, because many of her random choices involve wasted shots that can't possibly contribute to sinking both ships.  For example, it's clearly wasteful to shoot at a square without shooting at any of its neighbours.

Suppose the ships could be broken up into individual squares, so you have 11 possible squares you could hit and still miss the ships. However, you only have eight shots, so you can only have $11!/(8!*3!)$ possible ways. There is a number $11 \choose 3$ ways that this happens.

Surprisingly, the answer is still the same if the ships CAN'T be broken up. (Why?)


Show the roots of the quadratic equation $z^2 +bz+ c = 0$ lie in or on the unit circle So I need a little help with the following:
Considering separately the cases of real and complex roots show that the roots of the quadratic equation  $z^2 +bz+ c = 0$ lie in or on the unit circle (i.e. $|z_{i}|\leq 1$) if and only if $|c|\leq1$ and $|b|\leq 1+c$, where $b$ and $c$ are real coefficients.

I showed both sides of the relation for real roots, but now I am stuck on the complex case. Any ideas?

Since, roots are complex $b^2 \leq4c$. Hence, $c\geq0$. The roots are $$z_1,_2=(-b\pm i \sqrt{(4c-b^2)})/2$$We first assume roots lie in unit circle. Hence,$|z|^2\leq1$ which implies $$(b^2+(4c-b^2))/4\leq1\implies c\leq1, i.e, |c|\leq1$$ Also, $(1-c)^2\geq0\implies(1-c)^2+4c\geq4c\implies(1+c)^2\geq4c\implies(1+c)^2\geq b^2\implies|b|\leq 1+c$

Now, let's prove the other direction. Assume the conditions hold. Then,$$|z|^2=(b^2+(4c-b^2))/4=c\leq1$$ $$\implies |z|\leq1$$

We can consider that $c\geq 0$, because if $c<0$ then the equation has real roots. Now you have that

$$z=\cfrac{-b\pm i\sqrt{4c-b^2}}{2}$$

and so

$$|z|=\sqrt{\cfrac{b^2}{4}+\cfrac{4c-b^2}{4}}=\sqrt{c}\leq 1\Leftrightarrow c\leq 1$$


Find Big Theta $\Theta$ of generating functions Consider the generating function:
$$F(x) = \frac{x^{2}}{(x^{2}-9x+14)(x^{2}+2x-3)}-\frac{x^{1}}{(x^{2}-9x+14)(x^{2}+2x-3)} $$
I am looking to find a $\Theta$ approximation of this sequence. Any help would be appreciated!

I think you can say that $F(x)$ is equal to $x²/(x-2)(x-7)(x+3)(x-1)$ so you take the smallest roots and you say that $F(x)$ is big theta of $1$ (constant).
Hope it will be ok for Rudiger ^^


Show that there is no integer n with $\phi(n)$ = 14 I did the following proof and I was wondering if its valid. It feels wrong because I didn't actually test the case when purportedly $n$ is not prime, but please feel free to correct me.

Assume there exists $n$ such that $\phi(n) = 14$. Assume $n$ is prime. Then $\phi(n) = n-1$. Then here, n-1 = 14, so n = 15.
We know since Euler's totient function is multiplicative that $\phi(xy)$ = $\phi(x)\phi(y)$, so $\phi(15) = \phi(3)\phi(5)$, but alas $\phi(3)\phi(5) = 2\cdot4 = 8 \ne 14$. If $n$ is not prime a similar argument follows since we know then that $n$ must be composed of prime numbers by the prime factorization theorem.

If a prime $p\mid n$, then $p-1\mid\phi(n)$. If $\phi(n)=14$, then, since the divisors of $14$ are $\{1,2,7,14\}$, $p\in\{2,3\}$. Thus, $n=2^a3^b$ and $\phi(n)$ is of the form $2^j3^k$. However, there is no factor of $7$ in $2^j3^k$.

This does not hold. What kind of similar argument are you then talking about?

You can use the fact that $\phi$ is multiplicative. Assume $n = p_1^{a_1}p_2^{a_2}...p_t^{a_t}$, then $\phi(p_1^{a_1}p_2^{a_2}...p_t^{a_t})$ $\phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_t^{a_t}) = 2 \cdot 7 = 1 \cdot 14$

Use this to arrive at a contradiction.


Mathematical odds of picking letters What are the odds of picking two pre-selected non-sequential letters in order out of a $26$ letter alphabet, i.e. $D$ then $S$, not $S$ then $D$? One chance only.

if I understand the question correctly, what's the probability that you select a two letters from the English alphabet, such that the second one comes after the first. Use the law of total probability:
$$
P(X) = \sum_{k=1}^{26}P(X|Y=k)P(Y=k) = \frac{25}{26} \cdot P(X=A) + \frac{24}{26} \cdot P(X=B) +\ldots
$$

of course $P(X=j) = \frac{1}{26}$. Can you handle from here?

EDIT: you may want ot use the identity $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$

First are the selection of the two letters the same event? Or separate, and are you done selecting letters, or will you continue to select letters. If you continue to select letters that needs to be specified or the answer would assume you selected wrong (1/26)(1/26), or 1/26^2 but that wouldn't be correct for your scenario is suggesting either two separate events (like above) however selecting from a different amount of letters than 26. What exactly do you mean sequential? Picking D before the next event of selecting letters? That's wouldn't be 1/26 as mentioned by others because selecting any that come before S and is correct is what I believe you are asking? If that's what you mean by sequential (picking D then picking another letter in the same event (so d is taken out of selections) However does the person know, or aware that the letter is sequential and after D?) If they know the letter is after D then 1/22 for the second guess if they are in the same event (or turn picking letters). Also do they know it is sequential, that makes a difference on the first guess, because you could not guess Z, so the first guess witch was D would have to be 1/25 and then knowing it was after the letter D and guessing 1/22 so with that knowledge (knowing the second letter is after in the alphabet or sequential).

1/25*1/22

That only works if they know that the second letter is sequential. If they are picking as two separate events and after combining them and deeming them sequential it is just 1/26^2. This is just the rate of guessing the correct letter and then doing it again.

If your looking for all sequential possibilities and guessing the correct pair, that is a lot, especially because they are not even letters that are adjacent to each other or one after the other, they seem to have very random placement. That's would be something like 1/26^26*26 * 1/IDK Someone else can figure that out. I probably started it wrong.

(Edit) Oops I meant to just make this a comment. So I'll add some thought above.The letters "D" and "S" make no difference, it could be any letter, or even numbers for that matter as long as your using 26.  @David


Does $\int_E f = 0$ implies $f = 0$ a.e.? I know that for nonnegative $f$ and a measurable set $E$, $$\int_E f$$ (Lebesgue integral) is identically zero iff $f = 0$ a.e. How can I show this property holds for any arbitrary $f$ (not necessarily nonnegative)? Assume $f$ is continuous everywhere.

You can't. For example, let $f$ be the identity map on $\mathbb{R}$ and let $E = [-1, 1]$. $\int_E fdm = 0$ but $f \not= 0$.

What I would do is see how you defined the f? Most books defined it as two non-negatives right $f= f^+-f^-$. Then you also said the integral is additive. Thus if you show it for non-negative you are done!


Prove $A_1, A_2, \ldots,A_{\ell-1}, A_{\ell+1}\ldots \ldots, A_{m} $ in $\mathbb R^m$ are linearly independent viewed as vectors in $\mathbb R^{m-1}$? Suppose I have linearly independent vectors $A_1, A_2, \ldots, A_m$ in $\mathbb R^m$

Consider the matrix $B = [A_1, A_2, \ldots  A_m]$ consisting of these vectors and suppose $B^{-1}[A_1, A_2, \ldots,A_{\ell-1}, A_{\ell+1}\ldots \ldots, A_{m}]$ has the $\ell$-row consisting only of $0$'s.

Is it then neccesarily true that $A_1, A_2, \ldots,A_{\ell-1}, A_{\ell+1}\ldots \ldots, A_{m}$ are linearly independent in $\mathbb R^{m-1}$ considered as vectors with the $\ell$-component removed ?

I've tried to prove that $A_1, A_2, \ldots,A_{\ell-1}, A_{\ell+1}\ldots \ldots, A_{m}$, with the $\ell$-component removed, span $\mathbb R^{m-1}$ or are linearly independent, however I've not yet come to a final result.

This is not true. Let $m=3$ and $A_1=(0,2,3),~ A_2=(1,1,1),~ A_3=(0,1,1)$. Then

\begin{align}
\det(A_1,A_2,A_3)=\begin{vmatrix}
0 & 1 & 0\\
2 & 1 & 1\\
3 & 1 & 1
\end{vmatrix}
=-1\neq 0.
\end{align}
If we delete the first components of $A_2$ and $A_3$ the system $\{A_2,A_3\}$ wont be linearly independent in $\mathbb R^2$

Let $A_1=(1,2,3),~A_2=(0,1,1),~A_3=(-1,1,1)$. Then
$$B=\begin{bmatrix}
1&0&-1\\ 2&1&1\\ 3&1&1
\end{bmatrix}\quad \text{and}\quad
B^{-1}=\begin{bmatrix}
0&-1&1\\ 1&4&-3\\ -1&-1&1
\end{bmatrix}.$$
The first row of the matrix $B^{-1}[A_2,A_3]$ is only 0 and the system $\{A_2,A_3\}$ after deleted the first components is not linearly independent.

It is necessary that any subset is linearly independent so that a set is linearly independent (by definition).


A prime $p$ splits in $K$ if and only if $P(x)$ splits into distinct linear factors modulo $p$. In this answer, one can read:

  Let $P \in \Bbb Z[X]$.
  Let $K$ be the splitting field of $P(x)$. A prime $p$ splits in $K$ if and only if$^1$ $P(x)$ splits into distinct linear factors modulo $p$.

  1 With finitely many exceptions, related to the fact that the ring of integers in $K$ may not be $\mathbb{Z}[x]/P(x)$.

Question:
I would like to know the precise statement of this claim (e.g. what are these "finitely many exceptions"), and how to prove this statement.

I am aware of Dedekind's factorization theorem, stated here :

  Let $K$ be  a  number   field  and $a \in O_K$ such  that $K=\Bbb Q(a)$.
  Let $f(T)$ be  the  minimal  polynomial  of $a$ in $\Bbb Z[T]$.  For  any  prime $p$ not  dividing $[O_K:\Bbb Z[a]]$,write
  $$f(T) = \pi_1(T)^{e_1}\cdots \pi_r(T)^{e_r} \pmod p,$$ where  the $\pi(T)$'s  are  distinct  monic  irreducibles  in $\Bbb Fp[T]$.   Then $(p) =pO_K$ factors  into prime ideals as
  $$(p) = P_1^{e_1}\cdots P_r^{e_r},$$ where there is a bijection between the $P_i$'s and $\pi(T)$'s such that $N(P_i)=p^{deg(\pi_i)}$.

In order to prove $\Longleftarrow$ in the statement above, I would like to apply Dedekind's factorization theorem. But I don't know how I could take $P(T)=f(T)$, i.e. $P$ is the minimal polynomial of an element $a \in O_K$ such that $K=\Bbb Q(a)$ (only knowing that the roots of $P$ are $r_1,\dots,r_n$ such that $K=\Bbb Q(r_1,\dots,r_n)$).

Moreover, I don't see how to get "$\implies$".

Here are some related questions: (1), (2), (3), (4).

Apply the Dedekind theorem to $\mathbb{Q}(r_i)$ and use the fact that if a prime splits in a several fields then it splits in their composite.


Existence of continous functional over infinite dimensional space without global minimum The Weierstrass theorem says that any continuous function over compact set attains it extreme value within the set. Since compact means closed and bounded only for finite dimensional spaces, my guess is that the theorem does not necessarily hold for infinite dimensional spaces. For example the unit sphere in an infinite dimensional space is not compact even though it is closed and bounded (from converse of Reisz's Lemma, which I do not profess to fully understand - last paragraph of question).

So to show the theorem wrong, I am trying to construct an explicit example of a continuous functional $J: A \subseteq V \to \mathbb{R}$ where $V$ is a function space and $A$ is a closed and bounded subset of $V$ such that the global minimum of $J$ over $A$ does not exist.

To this end, are there any limitations on the norm or metric I choose to imbue the problem with? As in are there norms, which if I choose, the example I am trying to construct will always fail? Also does anyone know of an example which matches what I am trying to do?

I don't have a strong background in analysis and I am trying to learn what I can for an optimization course that I am taking. So I am not sure where to start off either. If someone could give some pointers, sketches, or references it would be really great.

Though the above answer is satisfactory, I think I have a simpler and less contrived example; please feel free to comment on any holes in the argument. Let $ V = \mathcal{C}\left( {\left[ {0,1} \right],\mathbb{R}} \right)$ and let  $$A = \left\{ {f \in V \mid f\left( 0 \right) = 0,f\left( 1 \right) = 1} \right\} \subset V$$ Let $J = \left\| f \right\| = \int_0^1 {f\left( x \right)dx} $. Then $A$ is bounded above by one under this norm. Note that the functions $ \left\{ {x,{x^2},{x^3}...} \right\} \in A$ and have smaller and smaller values for the functional $J$. However, for any function of the form $ x^n$ the function $x^{n+1}$ will have a smaller value of the functional. In fact the smallest possible value of $J$ under the constraints is achieved by
$$f\left( x \right) = \left\{ {\begin{array}{*{20}{c}}
  {0\quad x \ne 1} \\
  {1\quad x = 1}
\end{array}\quad ,\quad x \in \left[ {0,1} \right]} \right.$$
which does not belong to $V$ (that is it is not sequentially compact, and the Weierstrass theorem does not apply). Hence there is no minimum for $J$ over $A$.

I have left out the part where I need to show $A$ is closed. The idea is to work with the definition of a closed set and the complement of a open set. For example a subset of the complement of $A$ can be defined as,
$$ B = \left\{ {f \in V|f\left( 0 \right) = 0,f\left( 1 \right) \ne 1} \right\} \subset {A^C} \subset V $$
Then for any $ \bar f \in B$ arbitrarily close to 1 at  $\bar f\left( 1 \right)$ there exists a $ \hat f \in B$ that is closer. Thus $B$ is open. Similar argument can be made by relaxing the other end point or even both at the same time and so $A^C$ is open. Therefore its complement $A$ must be closed.

For the last answer, the function $$f\left( x \right) = \left\{ {\begin{array}{*{20}{c}}
  {0\quad x \ne 1} \\
  {1\quad x = 1}
\end{array}\quad ,\quad x \in \left[ {0,1} \right]} \right.$$ is the limit point of $x^n$. And it is not in the set so A should not be closed right ? (I apologize for putting it here since I am new to the website and can not comment.) I came up with the following argument. Please comment if you find any loopholes/errors.

Consider $V= L^p(E)$ where  $E$ is of finite measure. Then $L^q(E)\subset L^p(E)$ for any $p<q<\infty$. Let $A = L^q(E)$ equipped with $L^q$ norm. Since $L^q$ is complete, we have closedness. Boundedness is obtained by definition. Consider the functional defined on $A$ as follows:
$$J = \frac{1}{\int_0^1 |f(x)|^2 dx}$$
Then $\inf J =0$ and is not achieved $\forall f$ $\in$ $A$.


Priority of the 3 axioms of groups In my book about Abstract Algebra, it is stated that

A group $\langle G,*\rangle$ is a set $G$, closed under a binary operation $*$, such that these 3 axioms are satisfied:

$g_1$: For  all $a,b,c\in G$, $$(a*b)*c=a*(b*c) $$
$g_2$: There  is an element $e$ in $G$ such that for all $x\in G$, $$e*x=x*e=e$$
$g_3$: Corresponding to $a\in G$, there is an element $a'$ such that $$a*a'=a'*a=e$$

The book stated  that among the 6 orders of $g_1,g_2,g_3$, only $3$ are correct orders of defining a group. But I have no idea about it. Can someone give me some hint?

The author of your book is unnecessarly  delving into what order of stating axioms are useful.  A dictionary should simply list what are the words of that language.

Listing a cacaphony of letters that are not words of that language, even if logically correct, does not serve any useful purpose.


Understanding formula components for Complex exponential sequence I am trying to understand how all components within the complex exponential sequence function fit together, I have been reading from the following slide

it is the line below 'then we can express' that confuses me. so far I have deduced the following (which may be incorrect):

My confusion lies in two areas:

1) The part of the function used for magnitude looks awfully similar to what I would expect to see for rotation in the complex plane, how has this been used for magnitude?

2) The part of the function used to denote the base, has been converted into another form of which I do not understand.

If anyone could shed any light on either of these point it would be very much appreciated. If it is able to be explained intuitively as opposed to algebraically this would be much better as I have found the visualisation of the components working together allow for a better overall understanding.

The context of "sequence" suggest that $n$ should be an integer in
$$
x[n]=A\alpha^n.\tag{0}
$$

Your slide says if we write
$$
\alpha=e^{\sigma_0+j\omega_0},\quad A=|A|e^{j\phi},\tag{1}
$$
then
$$
x[n]=A\alpha^n=(|A|e^{j\phi})\cdot (e^{\sigma_0+j\omega_0})^n
=|A|e^{j\phi}e^{(\sigma_0+j\omega_0)n}.\tag{2}
$$
This is nothing but substitution (1) into (0).

For your second question, check Euler's formula.

(1) They haven't used $e^{j\phi}$ to represent magnitude. They also didn't make any such claim elsewhere. You're the one somehow mistaking this for magnitude. This is a complex number, not a magnitude.

(2) I don't really understand what you mean here, but if you meant the expression for $\alpha,$ then it's not much different from the expression for $A.$ Here, we've simply expressed $\alpha$ in exponential form (this may be uniquely done for any nonzero complex number). That is, we write it in the form $e^{a+ib}=e^ae^{ib}=R(\cos b+i\sin b),$ where $R=|\alpha|$ is a positive real number. So this is still of the form $|\alpha|e^{i\psi}$ for suitable $\psi.$


Finding intervals containing solutions to a equation, without using a graph How can I find all intervals containing solutions to the equation $4x^2-e^x=0$, without using a graph? I know how to solve this problem, but not without a graph. Thanks.

HINT:

Find the derivative of the function $f(x) = 4x^2 - e^x$ and set it to $0$ to find it's local minimum or maximum.  You can solve the new equation using Lambert W function.

Then use the second derivative test to check if the point is maxima or minima. You should be able to obtain 1 local minima and 1 local maxima. First we have a minima, so that means that the function is strictrly decresing in that interval, now plug the minima into your equation to find if the value of the function is smaller than 0. Yes, it is and that means that there's one zero in that interval. Then check the interval between the minima and the maxima, if they are on different sides of the x-axis, the we have another zero. And at last check if the maxima is bigger than $0$, because in the interval $(maxima, \infty)$, the function is decreasing. So if for the maxima, function has value bigger than $0$, we have another zero in that interval.

So in the end there are 3 zeros of the function. And we have one in each of the intervals:
$(-\infty,minima), (minima,maxima), (maxima,\infty)$

If you plug in values randomly for $f(x)$ and you're able to get $f(a).f(b)<0$ then $(a,b)$ is the interval in which roots of the equation would lie.


What's the best way to measure mathematical ability? Very soft question I admit, but it's something that's been bothering me for a while.

I've been thinking that being self taught has the problem of accreditation.  You can't evaluate a mathematician in a vacuum.  You need an accredited mathematician to decide whether or not someone else is also a mathematician worthy of accreditation.  Well, who evaluated the other mathematician?  Other accredited mathematicians.  It's sort of like becoming a member of an exclusive club.

We put the job of accreditation on our universities.  But what if some person was discovered, off-the-grid so to speak, who had taught themselves mathematics from library textbooks.

How could such a person evaluate themselves?  How do you know if you're making progress when you study?

It's tricky.  It's like language learning.  Do I speak German more fluently now than I did yesterday?  I've no idea.  Who can say?

It's like playing with Lego.  How do you know if you're getting better with Legos?  You build more complicated things.  But who's to say one person's Lego helicopter is better than another's Lego Enterprise?  What's the goal with Legos?  Is there one?  Should there be one?

I know already that this question will be deleted almost immediately, but I think these are important questions and many people visiting this site are in fact self-taught and I'm sure these questions show up as massive roadblocks.

Thanks for reading.

Your question is philosophical. As far as I know, there is no normed linear space of all possible mathematicians on which we have a metric to compare elements in the space!

My personal opinion is that there is an infinite amount of mathematics. If there isn't, then it is extremely large. This means any knowledge you have will be woefully less than what is possible to know. (Put some measure on the infinite set of all possible mathematics?)

Additionally, you will always find a person, either from the past or present, and possibly the future, who knows more mathematics or knows more about some particular branch of mathematics. While it is true that you can make comparisons with other people's mathematical abilities, that is often demoralizing. For most people, anyways, they aren't "at the top".

Of course, there is a threshold I am assuming one is beyond. There is clearly a difference between the majority of calculus students and math PhD students. Here, yes, you should be comparing yourself to see if you can master undergraduate and graduate material to know if you can, say for instance, do research in mathematics.

But all that aside, it is somewhat pointless and self-serving if you do mathematics merely for status. You should enjoy doing it as you should enjoy doing anything difficult. And mathematics is genuinely beautiful. I suggest you are doing well if you continually are surprised at what you learn, if you are able to find satisfaction in meeting non-trivial personal goals, and if you surprise yourself by going beyond your expectations.

In particular, improve your ability to solve problems, improve your ability to propose problems, and improve your ability to explain mathematics.

If you work on a difficult problem and you solve it, then you've surpassed your expectations! Otherwise it would not have been a difficult problem--the doubt of solving it makes it difficult. If you can propose new problems, you can enjoy the excitement of the novelty of new (to you at least) mathematics. If you can visualize the structure of mathematics and express it clearly to others, you can appreciate the beauty of mathematics and in fact share it as well.

In order to do any of this, you do need to know what you don't know. Otherwise you can't envision any improvement. There is some value in making your own personal maps of what the mathematical landscape looks like. This is very much in line with the saying that the wise man knows what he does not know.

That's my 2 cents.

Take an exam. It is objective and unbiased (usually).


Gödel's Proof as a proof strategy for P = NP or P != NP I have had this thought for quite a while. Gödel proved the incompleteness of arithmetic by creating a one-to-one correspondence with a number and certain numerical relationships to create a statement that says, in effect, "I cannot be proven."

My question is: has there been any attempt to go the other direction? That is, has anyone succeeded in showing that an arbitrary statement -- such as P=NP -- Is a statement that says of itself that it has no proof? In order for this to happen, a one-to-one relationship needs to be shown between what that means in the mathematics of it and its "meta meaning". In short, Gödel went from meta-meaning ("this statement cannot be proven") and constructed a number that, in effect, stated this meta-meaning. Has there been attempts to show that statements already in existence have a meta meaning stating that they cannot be proven? if so, has anybody used this strategy to prove or disprove P=NP's provability? It may be a simple question, but it has been bothering me for a while. Thanks for reading :)

My thoughts on the subject, which must be taken with a grain of salt as I'm far from being an expert on this subject (or any subject, to that matter):

This idea was mentioned in Douglas Hofstadter's "Godel, Escher, Bach", but I never saw it seriously discussed. As far as I know, no independence proof (e.g. the independence of the Continuum hypothesis) has ever used such a technique, and it's hard to see why P=NP will be different.

It is worth remembering that Godel's statement is difficult to build. In effect, you can think of it as a logical encoding of a small computer program which knows how to decode Godel's numbering and knows how to check proofs (in an effective system, i.e. one in which proof checking is computable), and to top it all, it also contains an encoding of itself using a smart diagonalization trick. This is not something you stumble upon; it is a very delicate construct.

I see no reason to assume that a statement such as P=NP, which deals with a class of Turing machines, can be re-interpreted as discussing itself. If such a far-fetched interpretation can be made for P=NP, why can't it also be done for, say, IP=PSPACE (which is well known to be true)?

So although this idea is quite fascinating, I see no reason to believe it is true; however, it might be explored by taking some toy independent statements and trying to see if they can be re-interpreted in a way they talk about themselves (I think it will already prove immensely difficult because of the complexity of making a statement talk about itself). I would start there, not attack P=NP directly.

It is also worth mentioning that there is no apparent reason why P=NP is undecidable. There are many indications that it is undecidable using standard methods (e.g. diagonalization - see Baker-Gill-Solovay) but many other complexity-theory problems had a similar difficulties and were laid to rest using a clever new formulation or point of view (IP=PSPACE being a nice example).

I am far from an expert also, but every independent statement can be interpreted as saying 'I am not provable', thats what it means to be undecidable. And every theorem says 'I am provable'.


Intuition for regression to the norm So for regression to the norm it says if someone has a high score on a test (relative to the average) then they are likely to score lower and lower on each following test? This seems very counter intuitive.

As with all probability problems the setup is very important, perhaps you heard of the problem of 3 coin flips, if we know 2 of them are heads what is the probability the third is heads? Which has probability 1/4 This is because the third coin to fall heads is not fixed.
Likewise consider if you were to pick a high score from the class. For any given person they are much more likely to be picked if they did relatively well for themselves on the test rather than relatively poorly (with respect to their own average). Another way of thinking about this is consider a class with 10001 people 10000 average 70 on tests which we call group B and 1 that averages 90 which we call group A. You pick a paper with grade 80 is it more likely it came from group A or B?. Of course B is the natural answer which means that this person is likely to score lower than 80 on the next test.

They would score lower and lower, and then higher and higher, and then lower and lower, etc. such that the mean is realized over large $n$. If a higher score is indicative of some real improvement in the student's average ability (as you suggest) you would need to alter the mean to reflect this.


Determine the magnitude and the direction of the velocity of the aircraft. An aircraft A is flying in a vertical plane containing two tracking stations P and Q which are 15km apart. At a cetain instant θ (measured anticlockqise from horizontal line PQ to the line PA) is 60° and the $ \dot \theta $ (angular velocity) is -0.025rad/s. At the same time, α (measured anticlockqise from extended horizontal line PQ to the line QA) is 150° and the $\dot \alpha$ is -0.02rad/s. Determine the magnitude and the direction of the velocity of the aircraft.

I used the radial and transverse components of the velocities relative to P and Q and calculated the resultant.

Relative to P, radial component = $$\frac{d(PA)}{dt}= \frac{d(15000Cos(\theta))}{dt} = -15000Sin(\theta) \dot \theta $$

The transverse component = $$r \dot \theta =-(PA)0.025$$

The components of velocity relative to Q could be obtained in the same way but I'm not sure about what to do next. Is taking the resultant of them correct? I took the resultant and got the following answers.

Magnitude - 15133m/s

Direction - 88.89° north of east

Consider the triangle $\Delta PQA$. Denote the measure of angle $\angle APQ$ as $\theta$ and note $\theta=\pi/3\;\text{rad}$, the measure of angle $\angle AQP$ as $\beta$ and note $\beta=\pi-\alpha$ where $\alpha$ is the measure of the angle between the extended line $QP$ and segment $AQ$. Since $\alpha=5\pi/6\;\text{rad}$ we know $\beta=\pi/6\;\text{rad}$. We know that $\theta' = -0.025\;\text{rad/s}$ and that $\alpha' = -0.02\;\text{rad/s}$. This implies that $\beta' = 0.02\;\text{rad/s}$.

Define our coordinates centered at point $P$ with the $x$ direction along segment $PQ$ and the $y$ direction perpendicular to segment $PQ$.

Let point $A=(x,y)$. The velocity of point $A$ (denoted $V_A$) is $(x',y')$. The magnitude of the velocity is $\sqrt{x'^2 + y'^2}$ and the direction (relative to the horizontal $PQ$) is $\tan{y'/x'}$. It's easy to show that $A=(x,y)=(3.75\;\text{km},6.495\;\text{km})$.

Denote the point $B$ as the vertical projection (perpendicular to $PQ$) of point $A$ onto segment $PQ$. Consider the triangle $\Delta PBA$. The triangle is a right triangle with a vertical side of length $y$ and a horizontal side of length $x$. Note that

$$\tan\theta = \frac{y}{x}$$

which can be derived to produce the line

$$y'=(\tan\theta) x' + x(\sec^2{\theta})\theta'$$

where all but $x'$ and $y'$ are known. Substituting all known values reduces the line to

$$y'=1.732x'-0.375\;\text{km/s}$$

Now consider triangle $\Delta QBA$. Again note that this is a right triangle with a vertical side of length $y$ and a horizontal side of length $15-x$. Again note that

$$\tan{\beta}=\frac{y}{15-x}$$

which can be derived to produce the line

$$y'=-(\tan{\beta})x'+(15-x)(\sec^2{\beta})\beta'$$

where again, all is known except for $x'$ and $y'$. Substituting in the known values reduces the line to

$$y' = -0.5774x'+0.3\;\text{km/s}$$

The intersection of these two lines will provide us with the velocity vector

$$(x',y')=(0.292\;\text{km/s},0.131\;\text{km/s})$$

The magnitude, as described above is, $320\;\text{m/s}$ and the direction is $0.418\;\text{rad}=23.9^o$ above the horizontal. To be even more clear we will say that the ground projection of the plane is heading toward $Q$ and away from $P$.

$$OA = OPtan(\theta)$$
$$d(OA) = d(OP)tan(\theta) + OPsec^{2}(\theta)d\theta ......(1)$$

Similarly,

$$OA = OQtan(\alpha)$$
$$d(OA) = d(OQ)tan(\alpha) + OQsec^{2}(\alpha)d\alpha  ........(2)$$

OQ = 15000-OP

$$\frac{OA}{OP} = tan(60)$$

$$\frac{OA}{OQ} = tan(30) = \frac{OA}{15-OP} = tan(30)$$

Solving these two :  You will find that $OP = 3.75$$

$$ \frac{d(OA)}{dt} = \frac{d(OP)}{dt}tan(\theta) +OPsec^{2}(\theta)\frac{d\theta}{dt}...(3)$$ $$ \frac{d(OA)}{dt} = \frac{d(OQ)}{dt}tan(\alpha)+ OQsec^{2}(\alpha)\frac{d\alpha}{dt}.....(4)$$

$$\frac{d\theta}{dt} = \theta^{o}$$
$$\frac{d\alpha}{dt} = \alpha^{o}$$

Substituting the values of $\theta, \alpha,\theta^{o},\alpha^{o}, OP, OQ$,

we get,  and solving (3) and (4) we get the y component $\frac{d(OA)}{dt} $ and the x component $\frac{d(OP)}{dt}$ and take the magnitude $\sqrt{x^2+y^2}$ou will get

$$ v = 320$$m/sec and the angle will be the $tan^{-}(\frac{y}{x}) = 23.9$ degrees.


A logic problem about set theory In a group of n people, subgroups with common interest are formed (football,tennis,snooker). The number of subgroups equals $2^{n-1}$. Any 3 subgroups have a common member. Prove that there is a person who is a member of all the subgroups.

proof by contradiction seems like a good fit here, but I can't seem to get the details right.

Denote the set by $S,$ and let $X$ be the collection of subsets of $S$ as given in the problem. First note that $A\in X$ iff $A^{C}\notin X$ since we have exactly $1/2$ of the total number of subsets. From this we deduce that if $A, B\in X,$ then $A\cap B \in X,$ since $(A\cap B)^{C} \cap A\cap B = \emptyset.$ Now, if $\{x\} \in X$ for some singleton, then we're immediately done, so suppose this isn't true. Then every set of the form $S-\{x\}$ is in $X.$ Taking the intersection of two of these gives a set of the form $S-\{x, y\},$ and we clearly get all such sets. Continuing in this manner gives that every set is in $X,$ a contradiction, so we're done.

Alternatively you can just do this by induction on the intersection of $k$ sets, with the base case being $k=2$ proven above.

Given a finite set $N$ of size $n$, let $O_n$ be a family of subsets of $N$ such that any three elements of $O_n$ have non-empty intersection. Given that $|O_n| = 2^{n-1}$ you want to show that $\exists x \in N \forall o \in O_n : x \in o$.

When forming an $O_n$, the maximum number of subsets of $N$ that can be chosen of a specific size $k$ is exactly the number of choices from $N$ where one element is fixed; this is exactly $\binom{n-1}{k-1}$. Fixing one choice ensures that all the subsets of size $k$ obey the requirement at any three subsets share an element.

Notice that enumerating the maximum choices for each $k \le n$ forms a row in Pascal's Triangle, and the sum of all the maximum counts for each $k$ is equal to $2^{n-1}$. Therefore, in order to form an $O_n$ whose cardinality is exactly $2^{n-1}$, the maximum number of each size $k$ subset must be chosen. This includes one singleton subset (if no singletons are chosen, then one more set must be chosen to reach the appropriate size, but one more choice from any other size subset would violate the maximum for that size). Thus, in order for $O_n$ to satisfy the requirement that any three subsets share an element, the fixed choice in each size $k$ subset must be the element of $N$ in the singleton.

Therefore the singleton choice is the $x$ that satisfies $\exists x \in N \forall o \in O_n : x \in o$


How to show that the following function is continuous at 0? Define a function $f$ as

$$ f(x) =
\begin{cases}
\frac{p}{q^2},  & \text{if $x \in \Bbb Q,$ $p,q\in \Bbb Z $ $p$ and $q$ are relatively prime} \\
x^2, & \text{if $x \notin \Bbb Q$}
\end{cases}$$

Is $f$ continues at $x=0$ ?

I understand that I have to prove or disprove that the limit exists at $0$, i.e. prove or disprove that for any $\epsilon>0$ there exists $\delta>0$ so that if $0<|x−0|<δ$ then $|f(x)−f(0)|<ϵ$. I am confused as to how I can actually go about this proof.

Notice that $f(0)=0$, so we need to prove that for all $\epsilon$, there exists a $\delta$ such that $|x|<\delta\Rightarrow |f(x)|<\epsilon$. Since for $x<1$, $f(x)<x$, we see that setting $\delta=\min\{1,\epsilon\}$ gives us the desired result, as when $|x|<\epsilon$, we immediately get $|f(x)|<|x|<\epsilon$ and when $\epsilon>1$, $|x|<1\Rightarrow |f(x)|<1<\epsilon$

Let $\epsilon \in (0,1), \delta = \epsilon < \sqrt\epsilon$. $\forall x $ such that $0\le|x|\le\delta$,

If $x \in \Bbb Q$, $|f(x)-f(0)| = |\frac{p}{q^2}-0|\le |\frac{p}{q}| \le |x| \le \delta=\epsilon$
If $x \notin \Bbb Q$, $|f(x)-f(0)| = |x^2 - 0| \le \delta^2 \le \epsilon$.

Hence $f$ is continuous at $x = 0$.


Proving the sum of the first $n$ natural numbers by induction I am currently studying proving by induction but I am faced with a problem.

I need to solve by induction the following question.

$$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$

for all $n > 1$.

Any help on how to solve this would be appreciated.

This is what I have done so far.

Show truth for $N = 1$

Left Hand Side = 1

Right Hand Side = $\frac{1}{2} (1) (1+1) = 1$

Suppose truth for $N = k$

$$1 + 2 + 3 + ... + k = \frac{1}{2} k(k+1)$$

Proof that the equation is true for $N = k + 1$

$$1 + 2 + 3 + ... + k + (k + 1)$$

Which is Equal To

$$\frac{1}{2} k (k + 1) + (k + 1)$$

This is where I'm stuck, I don't know what else to do. The answer should be:

$$\frac{1}{2} (k+1) (k+1+1)$$

Which is equal to:

$$\frac{1}{2} (k+1) (k+2)$$

Right?

By the way sorry about the formatting, I'm still new.

Basic algebra is what's causing the problems: you reached the point

$$\frac{1}{2}K\color{red}{(K+1)}+\color{red}{(K+1)}\;\;\;\:(**)$$

Now just factor out the red terms:

$$(**)\;\;\;=\color{red}{(K+1)}\left(\frac{1}{2}K+1\right)=\color{red}{(K+1)}\left(\frac{K+2}{2}\right)=\frac{1}{2}(K+1)(K+2)$$

Think of pairing up the numbers in the series. The 1st and last (1 + n) the 2nd and the next to last (2 + (n - 1)) and think about what happens in the cases where n is odd and n is even.

If it's even you end up with n/2 pairs whose sum is (n + 1) (or 1/2 * n * (n +1) total)

If it's odd you end up with (n-1)/2 pairs whose sum is (n + 1) and one odd element equal to (n-1)/2 + 1 ( or 1/2 * (n - 1) * (n + 1) + (n - 1)/2 + 1 which comes out the same with a little algebra).


Ambiguity of Context Free Grammar There is a theorem related to CFGs that
" There exists no algorithm which can decide whether a grammar is ambiguous or not."

I have developed an algorithm which can decide the ambiguity of a cfg.

But the proof of the above theorem is based on Post Correspondence Problem (PCP). Please tell me if I publish the algorithm would that mean that this theorem is not correct.

Note: Please also post some ambiguous cfgs. I want to test my algo.

A good heuristic is: "If you think you have disproved previously proved result X, you are more likely wrong."

I am not sure how many people have worked on PCP over the years. It is most likely a lot, and they have most likely been competent computer scientists and mathematicians.

I would tend to trust a group like that to reason mathematically, more than I would trust myself.

Your algorithm is most likely wrong (there is a probability $\varepsilon > 0 $ that it is correct and all these mathematicians are wrong, for an almost arbitrarily small $\varepsilon$).

It is well known that the grammar of the programming language C++ is ambiguous when expressed as a CFG.

Also, try to present a counterexample for your algorithm. You designed it, you should know when it breaks.

Thanks for sharing your views. But you have not given me my answer. The answer would be a YES or a NO.

I would simply like to know that if I present an algorithm which can decide the ambiguity of a CFG, would this dis-proves the theorem

OR

Even I have to present a theoretical proof.

Please don't consider it rude. I'm no scientist rather a researcher.

Thanks.