Prove that isomorphisms are symmetric Prove that isomorphisms are symmetric

Now if $(G, *)$ and $(H, \circ)$ are two groups. A map $\gamma : G \to H$ such that $\gamma (x * y) = \gamma(x) \circ \gamma(y)$ for all $x, y \in G$ is a homomorphism, and a bijective homomorphism is an isomorphism, and we notationally put $G \cong H$ if a isomorphism exists between $G$ and $H$.

I need to prove that $G \cong H \implies H \cong G$.

Now we know that $\gamma : G \to H$ is an isomorphism, and it seems like $\gamma^{-1} : H \to G$ should be an isomorphism as well. Proving that $\gamma^{-1}$ is bijective is trivial, however proving that it is an homomorphism doesn't seem to be as easy, since $\gamma^{-1}(\gamma(x * y)) = \gamma^{-1}(\gamma(x) \circ \gamma(y)) \implies (x * y) = \gamma^{-1}(\gamma(x) \circ \gamma(y))$ and since we have no idea how $\circ$ affects $\gamma^{-1}$ we can't deduce anything further. (please correct me if I'm wrong)

However I found a proof online, that I'm not so sure about

In the proof above how do we know that $$s_1 \circ s_2 = \phi^{-1}(t_1) \circ \phi^{-1}(t_2) \ \ \ \ \ \ \ \ (1)$$ and how do we know that the $t_1$ and $t_2$ in $(1)$ above is the same as $t_1$ and $t_2$ in equality $(2)$ below? $$\phi^{-1}(t_1 * t_2) = s_1 \circ s_2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$$

What we would like to show, based on what we know already, is that for any $h_1,h_2 \in H$, that:

$\gamma^{-1}(h_1 \circ h_2) = \gamma^{-1}(h_1) \ast \gamma^{-1}(h_2)$.

Now, since $\gamma$ is bijective, we know there exists unique $g_1,g_2 \in G$ with:

$\gamma(g_1) = h_1, \gamma(g_2) = h_2$.

So:

$\gamma^{-1}(h_1 \circ h_2) = \gamma^{-1}(\gamma(g_1) \circ \gamma(g_2))$

and since $\gamma$ is a homomorphism, $\gamma(g_1) \circ \gamma(g_2) = \gamma(g_1\ast g_2)$, thus:

$\gamma^{-1}(h_1 \circ h_2) = \gamma^{-1}(\gamma(g_1) \circ \gamma(g_2)) = \gamma^{-1}(\gamma(g_1\ast g_2)) = g_1 \ast g_2.$

Now, from $\gamma(g_1) = h_1, \gamma(g_2) = h_2$, applying $\gamma^{-1}$ to both these equations gives:

$g_1 = \gamma^{-1}(\gamma(g_1)) = \gamma^{-1}(h_1)$, and:

$g_2 = \gamma^{-1}(\gamma(g_2)) = \gamma^{-1}(h_2).$

So, finally, we have: $\gamma^{-1}(h_1 \circ h_2) = g_1 \ast g_2 = \gamma^{-1}(h_1) \ast \gamma^{-1}(h_2)$, which is what we sought to prove.

I can't see the image but I'll try to guess the proof enouncement. Let guess $\phi:H\rightarrow G$ is an isomorphism and let prove $\phi^{-1}$ is also. Its easy to see that $\phi^{-1}$ is bijective. As we know $\phi$ is bijective, given $t_1,t_2\in G$ take $s_i=\phi^{-1}(t_i)$, so $t_i=\phi(s_i)$, which results in $(1)$. We know that $\phi(s_1\circ s_2 )=t_1*t_2$ as $\phi$ is homomorphism, so taking $\phi^{-1}$ we get $(2)$. Joining $(1)$ and $(2)$ proves that $\phi^{-1}$ is homomorphism


$\cos(x)$ strictly increasing on $(-\pi,0)$ How can one show that $f(x) =\cos(x)$ is strictly increasing on $(-\pi,0)$? That is, how can one show that $\sin(x)<0$ for all $x \in (-\pi,0)$ (as $f'(x)=-\sin(x)$) rigorously? Although I know that the image of $\sin$ on this interval is $(-1,0)$ and this should suffice, I'm not sure how to prove that this is the image.

(continuing from the other answerer's post having gotten to the question of how to show $\sin(x)$ is postive on the interval $(0,\pi)$)

Using the complex analysis definition of $\sin$ and power series expansions of $e^u$,

Let $x\in(0,\pi)$

Then $\sin(x) = \dfrac{e^{ix}-e^{-ix}}{2i} = \sum\limits_{n=0}^\infty\dfrac{(-1)^n}{(2n+1)!}x^{2n+1} = x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+c_9(x)~~$ where $c_9(x)\in(-.09,.09)$.  Expand further if you wish to make the error range smaller.  The error range $c_n$ is $O(\frac{1}{n!})$.

For whatever $x$ you pick in the range, you will be able to find an $n$ such that the error range is smaller than the partial sum up to that point, showing that it is in fact positive on the entire interval.


Proving sequence is bounded below? I have the function:
$$
a_{n}=\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\ldots +\frac{1}{\sqrt{n}}-2\sqrt{n}
$$

How could I go about proving that this sequence is bounded from below? When plotting it, I can see it converges to around -1.45, but I can't figure out how to try and prove it's bounded arithmetically. I was trying to figure out how to manipulate it to use the arithmetic/geometric mean inequality, but had no such luck.

Thanks!

hint: $\dfrac{1}{\sqrt{k}}= \dfrac{2}{2\sqrt{k}} \ge \dfrac{2}{\sqrt{k+1}+\sqrt{k}}= 2\sqrt{k+1}- 2\sqrt{k}$, and take the sum for $k$ runs from $1$ to $n-1$.

If
$a_{n}=\sum_{k=1}^n \frac1{\sqrt{k}}-2\sqrt{n}
$,
then

$\begin{array}\\
d(n)
&=a_{n+1}-a_n\\
&=\dfrac1{\sqrt{n+1}}-2(\sqrt{n+1}-\sqrt{n})\\
&=\dfrac1{\sqrt{n+1}}-2(\sqrt{n+1}-\sqrt{n})\dfrac{\sqrt{n+1}+\sqrt{n}}{\sqrt{n+1}+\sqrt{n}}\\
&=\dfrac1{\sqrt{n+1}}-2\dfrac{1}{\sqrt{n+1}+\sqrt{n}}\\
&<\dfrac1{\sqrt{n+1}}-2\dfrac{1}{2\sqrt{n+1}}\\
&=0\\
\text{and}\\
d(n)
&>\dfrac1{\sqrt{n+1}}-2\dfrac{1}{2\sqrt{n}}\\
&=\dfrac1{\sqrt{n+1}}-\dfrac{1}{\sqrt{n}}\\
&=\dfrac{\sqrt{n}-\sqrt{n+1}}{\sqrt{n}\sqrt{n+1}}\\
&=\dfrac{\sqrt{n}-\sqrt{n+1}}{\sqrt{n}\sqrt{n+1}}\dfrac{\sqrt{n}+\sqrt{n+1}}{\sqrt{n}+\sqrt{n+1}}\\
&=\dfrac{-1}{\sqrt{n}\sqrt{n+1}(\sqrt{n}+\sqrt{n+1})}\\
&>\dfrac{-1}{2n\sqrt{n}}\\
\text{so}\\
a_{n+k}-a_n
&=\sum_{j=1}^k (a(n+j)-a(n+j-1))\\
&< 0\\
\text{and}\\
a_{n+k}-a_n
&=\sum_{j=1}^k (a(n+j)-a(n+j-1))\\
&>\sum_{j=1}^k \dfrac{-1}{2(n+j-1)\sqrt{n+j-1}}\\
\end{array}
$

Therefore
$a_n$ is a decreasing sequence
which is bounded below
since
$\sum \dfrac1{n^{3/2}}
$
converges.

For an explicit bound,
since
$\dfrac1{x^{3/2}}
$
is decreasing for
$x \ge 1$,
$\dfrac1{x^{3/2}}
\lt \int_{x-1}^x \dfrac{dt}{t^{3/2}}
$
so

$\begin{array}\\
\sum_{j=1}^k \dfrac{1}{(n+j-1)\sqrt{n+j-1}}
&\lt\sum_{j=1}^k \int_{n+j-2}^{n+j-1} \dfrac{dt}{t^{3/2}}\\
&\lt\int_{n-1}^{n+k-1} \dfrac{dt}{t^{3/2}}\\
&\lt\int_{n-1}^{\infty} \dfrac{dt}{t^{3/2}}\\
&\lt\dfrac{2}{\sqrt{n-1}}\\
\end{array}
$

so

$\begin{array}\\
a_{n+k}-a_n
&>\sum_{j=1}^k \dfrac{-1}{2(n+j-1)\sqrt{n+j-1}}\\
&\gt\dfrac{-1}{\sqrt{n-1}}\\
\text{or}\\
a_{n+k}
&>a_n-\dfrac{1}{\sqrt{n-1}}\\
\end{array}
$

As is often the case,
nothing here is original
and I worked it out
as I went along.


Minimum ceiling height to move a closet to upright position I brought a closet today. It has dimension $a\times b\times c$ where $c$ is the height and $a\leq b \leq c$. To assemble it, I have to lay it out on the ground, then move it to upright position. I realized if I just move it in the way in this picture, then it would require the height of the ceiling to be $\sqrt{c^2+a^2}$.

Is this height required if we consider all possible ways to move the closet? Or is there a smart way to use less height?

This is a image from IKEA's instruction that comes with the closet.

We are asked to prove that a minimum clearance of $\sqrt{a^2 + c^2}$ is required to move the assembled closet (box) from a "prone" position in the hallway floor to an upright position.

Let $V$ be the vertical height of the box, defined as the difference between the heights of the uppermost and lowest corners of the box in whatever position.  This value is invariant with translation and with rotation about a vertical axis.  In the upright position $V = c$, and depending on which face the box is lying on its prone position, the vertical height there is either $V = a$ or $V = b$.

To restate what is to be shown, in going from the prone to the upright position, the vertical height $V$ must at some intermediate position equal $\sqrt{a^2 + c^2}$, and that (as already shown by the OP's diagram), the upright position may be reached without exceeding that vertical height.

Using the above mentioned symmetries (translation and rotation about a vertical "z-axis"), we can maintain the center of the box in a fixed location and keep the long axis of the box (having length $c$) confined to a plane perpendicular to the (horizontal) width of the hall (assuming for the sake of generality that hallway width and length are arbitrarily great, so allowing movement of the box restricted only by the height of the hallway ceiling).

The leaves two degrees of freedom: the angle $\theta$ the box's long axis makes with respect to horizontal, and the angle $\phi$ around that axis which the box is rotated.  For specificity let's say $\phi = 0$ designates an orientation in which the $b$ length edges are horizontal.

By standard trigonmetric arguments, it suffices to consider quarter rotations $0 \le \theta \le \pi/2$ and $0 \le \phi \le \pi/2$, for which:

$$ V(\theta,\phi) = c \sin \theta + (b \sin \phi + a \cos \phi) \cos \theta $$

For fixed angle $\theta$ the angle $\phi$ which minimizes $V$ is zero, so:

$$ V(\theta,\phi) \ge V(\theta, 0) = c \sin \theta + a \cos \theta $$

Thus when $\theta = \tan^{-1} c/a$, $V(\theta,\phi) \ge \sqrt{a^2 + c^2}$, and it follows that $\theta$ cannot reach upright angle $\pi/2$ without $V$ reaching at least $\sqrt{a^2 + c^2}$, and also that if $\phi = 0$ is maintained, then the upright position may be reached without $V$ exceeding that threshold.

If you're treating the box as a rigid body (you can't chop it, squish it, burn it, etc.), then we can make the following statements:

The box starts with a rotation angle of $\theta = 0$, and you want to rotate it to get $\theta = 90^\circ = \pi/2$.
Because the box is rigid, it cannot be deformed; thus, its angle $\theta(t)$ must be
continuous.
By the Intermediate Value Theorem, the box must pass through every angle between $0$ and $90^\circ = \pi/2$.
Thus, the box must pass through the angle where the required height is $\sqrt {a^2 + b^2}$. There is no way to "do any kind of movement to the box" such that we could "stand it up [using] less than that height."


put 4 red, blue and green triangles in a row How many ways are there to put 4 red, 4 blue and 4 green triangles in a row so that no blue triangles would lie next to each other.

I got an answer, there are 126*56=7056 combinations. Could you check please, if the answer is right/wrong?

HINT: Do the problem in two steps.

First determine in how many ways the red and green triangles can be arranged in a row.
Each of those ways is a row of eight triangles; counting the spaces at the beginning and end of the row, there are nine slots into which you can insert a blue triangle. Since you’re not allowed to have two blue triangles in a row, you can put at most one blue triangle into a slot. How many ways are there to choose four of the nine slots to be filled with blue triangles?

Now what must you do with the answers to (1) and (2) to answer your problem?

total there are $\frac{12!}{(4!)^3}$ combination no.of combination and  the blue triangle will lie next to each other =$\frac{11!}{3!4!4!}$ in conclusion there will be 23100


is the trace of inverse of positive, positive definite matrix decreasing? Let $A, B$ be non-negative, and symmetric positive definite matrices.
If $A\le B$, i.e., all the entries of $B-A$ are non-negative, is it true that $\mbox{trace}(A^{-1}) \ge \mbox{trace}(B^{-1})$?

No. Let $A=I\le B=\pmatrix{1+\frac1t&1\\ 1&1}$ with $t>0$. Then $B^{-1}=\pmatrix{t&-t\\ -t&1+t}$ and hence $\operatorname{tr}(A^{-1})=2<1+2t=\operatorname{tr}(B^{-1})$ when $t$ is sufficiently large.

By $A \le B $, taking $a_{ij}\le b_{ij}$,
we have $A=PDP^{-1}$ and $B=QMQ^{-1}$, $ Tr(A)=Tr(D)$ and $Tr(B)=Tr(D)$, $Tr(A^{-1})=Tr(D^{-1})$, so $Tr(D^{-1})$ is sum of reciprocals of the diagonal entries of D. If the diagonal elements of D are all greater than or equal to one then $Tr(D)\ge Tr(D^{-1})$

$A\le B$

$Tr(A) \le Tr(B)$

$Tr(A^{-1}) \ge Tr(B^{-1})$


Integration by parts for Riemann integrable fucntion Suppose $f$ is Riemann integrable on $[a,b]$ and $g$ be continuously differentiable on $[a,b]$.

Define $$F(x):= \int_a ^x f(t) dt,\ \ \forall x\in[a,b]$$

We know $F$ is continuous hence Riemann integrable.
Is the following true?
$$\int_c^dg(t)f(t)dt = [g(d)F(d)-g(c)F(c)]- \int_c^d g'(t)F(t)dt\\for\ \ d,c\in[a,b]$$
i.e. can I use some "sort" of integration by parts?
Thanks in advance.

p.s.
I have no exposure to measure theory.

Strong sufficient conditions for integration-by-parts found in calculus books are $F$ and $g$ have continuous derivatives.  If $f$ is continuous we can be sure that $F' = f$ and it follows that for Riemann integrals

$$\tag{*}\int_c^dg(t) f(t) \, dt = g(d)F(d) - g(c)F(c) - \int_c^d F(t) g'(t) \, dt.$$

Weaker conditions for Lebesgue integrals are that $F$ and $g$  are absolutely continuous in which case (*) is true for Lebesgue integrals.

Assuming you want to work with Riemann integrals, the result is also true with your conditions.  We have to be careful because the assumption is only that $f$ is Riemann integrable.

Here is a way to prove this using Riemann-Stieltjes integration and the more general integration-by-parts result for such integrals.  Since $F$ has bounded variation and $g$ is continuous we have that $g$ is R-S integrable with respect to $F$ and

$$\tag{**}\int_c^d g(t) f(t) \, dt = \int_c^dg dF = g(d)F(d) - g(c) F(c) - \int_c^d F \, dg.$$

Since $g$ is continuously differentiable your result follows. Using the mean value theorem of differential calculus it can be shown that

$$\int_c^dF\, dg = \int_c^d F(t) g'(t) \, dt.$$

A bit more work is needed to justify all of the steps.  The first equality in (**) can be proved using Riemann-Stieltjes sums.  The second equality is integration-by-parts for R-S integrals.

Try integration by parts:

$$\int_c^d g(t)f(t)dt $$
$$=\int_a^d g(t)f(t)dt - \int_a^c g(t)f(t)dt$$
$$=\left.\left[g(t)\int f(t)dt - \int g'(t)\left\{\int f(t) dt\right\} \right]\right|_a^d - \left.\left[g(t)\int f(t)dt - \int g'(t)\left\{\int f(t) dt\right\} \right]\right|_a^c$$
$$\ldots \ldots$$
$$\ldots \ldots$$
$$= [g(d)F(d)-g(c)F(c)]- \int_c^d g'(t)F(t)dt$$

Try to fill up the gaps. Its easy.

Hope this helps you.


Recursively defining the set of bit strings set having more zeros than ones Question:

Recursively define the set of bit strings that have more zeros than ones.

I tried it this way:

$\Sigma\subset \{0,1\}^*$

Basis step: $0 \in \Sigma$

Recursive step: For any $x\in \Sigma$, $00x1\in L$

Is it a valid answer?

Denote by $\Sigma$ the set of all finite binary strings, including the empty string $\oslash$. In the follwing $x$, $y$, $\ldots$ are variables for strings, and juxtaposition denotes concatenation.

Strings containing more zeros than ones  are called admissible. The language $L$ consisting of all admissible strings can be recursively generated as follows:

(i)$\quad 0\in L$,

(ii)$\quad x\,y\in L\ \rightarrow\ x\,0\,y,\ x\,0\,1\,y,\ x\,1\,0\,y\in L$.

Note that in (ii) $x$ or $y$ may be $=\oslash$. – It is obvious that all strings so generated are admissible. Conversely: The admissible strings of length $\leq2$ are $0$ and $0\,0$, and are indeed produced by (i) and (ii). Assume now that all admissible strings of length $\leq n$ are produced by (i) and (ii). If an admissible string $z$ has length $n+1$ and does not consist solely of zeros it contains $0\,1$ or $1\,0$ as a substring. It then can  be produced using (ii) and an admissible string $x\,y$ of length $n-1$.

To expand on your recursive step, I believe you'll need:

$0x \in S$, $x0 \in S, 01x\in S, 10x\in S, 1x0\in S, 0x1\in S, x01\in S, x10\in S$, for any $x \in \Sigma$

And your $\Sigma$ should really denote the set you're trying to define, that is the set of bit strings having more zeros than ones.


Solve $T(n) = (T(\frac{n}{2}))^3 , T(1) = 2$ Solve $T(n) = (T(\frac{n}{2}))^3 , T(1) = 2$

Well, I'm not sure how to approach this properly. can anyone help me out?

I've tried $T(1) = (T(0.5))^3 = 2$

But that doesn't help me much.

Find: $\Theta$ of the function.

Your equations only define what $T(2^k)$ is equal to for $k\in\mathbb Z$, since

$$\begin{align}T(2)&=T(1)^3=8\\
T(4)&=T(2)^3=8^3=512\\
T(8)&=T(4)^3=512^3\\
\vdots&\end{align}$$

For $x\notin\{2^k| k\in \mathbb Z\}=A$, you cannot (from the given data) calculate $T(x)$.

For example, you can define $T(x)=0$ on all $x\notin A$, and the condition is satisfied, but you can also define $T(x)=1$, and the condition will still be satisfied.


solve the following first order but not of first degree ordinary differential equation $$x = y\frac{dy}{dx}-\left(\frac{dy}{dx}\right)^2$$
I think it can be converted into a Clairaut. form but not able to do it

$x=y\dfrac{dy}{dx}-\left(\dfrac{dy}{dx}\right)^2$

$\left(\dfrac{dy}{dx}\right)^2-y\dfrac{dy}{dx}+x=0$

Apply the method in http://www.ae.illinois.edu/lndvl/Publications/2002_IJND.pdf#page=2:

Let $F(x,y,t)=t^2-yt+x~,$

Then $\dfrac{dy}{dt}=-\dfrac{t\dfrac{\partial F}{\partial t}}{\dfrac{\partial F}{\partial x}+t\dfrac{\partial F}{\partial y}}=-\dfrac{t(2t-y)}{1+t(-t)}=\dfrac{2t^2}{t^2-1}-\dfrac{ty}{t^2-1}$

$\dfrac{dy}{dt}+\dfrac{ty}{t^2-1}=\dfrac{2t^2}{t^2-1}$

$y=t+\dfrac{\ln(t+\sqrt{t^2-1})+C_1}{\sqrt{t^2-1}}$

$\therefore\dfrac{dx}{dt}=-\dfrac{\dfrac{\partial F}{\partial t}}{\dfrac{\partial F}{\partial x}+t\dfrac{\partial F}{\partial y}}=-\dfrac{2t-y}{1+t(-t)}=\dfrac{2t}{t^2-1}-\dfrac{y}{t^2-1}=\dfrac{t}{t^2-1}-\dfrac{\ln(t+\sqrt{t^2-1})+C_1}{(t^2-1)^\frac{3}{2}}$

$x=\int\biggl(\dfrac{t}{t^2-1}-\dfrac{\ln(t+\sqrt{t^2-1})+C_1}{(t^2-1)^\frac{3}{2}}\biggr)dt=\dfrac{t(\ln(t+\sqrt{t^2-1})+C_1)}{\sqrt{t^2-1}}+C_2$

Hence $\begin{cases}x=\dfrac{t(\ln(t+\sqrt{t^2-1})+C_1)}{\sqrt{t^2-1}}+C_2\\y=t+\dfrac{\ln(t+\sqrt{t^2-1})+C_1}{\sqrt{t^2-1}}\end{cases}$


What is the difference between "Polynomial" and "Multinomial" in two or more variables? What is the difference between "Polynomial" and "Multinomial" in two or more variables?
Since, by definition:

Multinomial:
An algebraic expression having two or more (unlike) terms is called a Multinomial.

For example:
$5x^2 - 2x$ is a multinomial having $2$ terms,
$5x^3- 2xy + 7y^2$ is a multinomial having $3$ terms,
$7xy - 9yz + 6zx - 7$ is a multinomial having $4$ terms.

Polynomials in two or more variables:
An algebraic expression in two or more variables is called a Polynomial if the Power of every variable in each term is a whole number.

Some books say "Multinomial" is one of the types of "Polynomial", and the other discuss it in particular.
Is the function $f$ cross "Polynomial" or "Multinomial"? Why?
$$f(x, y)=x y + y^2 + 2 x y^2 + y^3 - 3 x y^3 + x y^4,$$

Under many definitions, polynomials and multinomials are synonyms (as commented above). Under any definition, your $f(x,y)$ is both a polynomial and a multinomial. A monomial is not a polynomial nor a multinomial. Poly $\to$ many, multi $\to$ multiple; neither multiple nor many can refer to one.
Polynomial is used more commonly though my experience is that multinomial is more commonly used when referring to plotted distributions. Whereas in describing a function polynomial is used almost exclusively.

A multinomial is not a type of polynomial.
Polynomials are limited to positive integer powers of variables.
A multinomial can contain, say, square roots of a variable.  Or other irrational functions of variables.


Convergence of $\sum_n a_nb_n$ for all $b_n\searrow 0$ implies convergence of $\sum_n a_n$ I need a hint for a practice problem:

Let $a_n \geq 0$. Show that if $\displaystyle\sum_{n=1}^\infty a_nb_n$ converges for every monotonically decreasing sequence $b_n \to 0$, then $\displaystyle\sum_{n=1}^\infty a_n$ converges.

I've been trying to use the fact that $\sum\limits_{n=1}^\infty a_n r^n \leq M < \infty$ for all $r \in [0,1)$ iff $\displaystyle\sum_{n=1}^\infty a_n$ converges, but I can't seem to get it, so I'm not sure that's the right way to go about it.

Thanks in advance!

(Contraposition.) Suppose that $a_n\geq 0$ for each $n$ and $\sum\limits_{n=1}^\infty a_n=+\infty$.  Define $n_1<n_2<n_3<\cdots$ such that $\sum\limits_{n=n_{k}}^{n_{k+1}-1}a_n>1$ for each $k$ (with $n_0=1$).  Define $b_n=\frac{1}{k}$ for $n_{k-1}\leq n<n_k$.  Then $\sum\limits_{n=1}^\infty a_nb_n$ diverges.

$\sum a_nb_n$ converges for every $b_n$ which goes monotonically to 0.  Let $b_n$ be such a sequence such that $\sum b_n$ diverges. If $ \sum a_n b_n$ is to converge, then "on average" the {$a_n$}  < the {$b_n$}, even though for any particular n it could be that $a_n > b_n$.  One way to write this is

$ \sum_{1}^n a_n$ < $\sum_{1}^n b_n$ for "most" n.  More precisely as $n \rightarrow \infty$ we have $\sum a_n$ < $ \sum b_n$.  That is,  $\sum a_n$ is strictly less than $\sum b_n$ whenever b is divergent.

We can define a series {$b_n$} as being divergent in this way:  that for any number R > 0 there exists a number $N_R$ such that $ \sum_{n =1}^{N_R} b_n> R$.

Let {$b_n$} be a divergent series and pick R.  The $N_R$ that works for {$b_n$} will not work for {$a_n$}. The reason is that for every positive integer k, $\sum_{n=1}^\infty a_n$ < $ \frac{1}{k} \sum _{n=1}^\infty b_n$ ,(which is divergent) and there is always a k such that the chosen $N_R$ is too small, unless $\sum a_n$ converges to a number > R.

Since $ \frac{1}{k} \sum _{n+1}^\infty b_n$  does diverge, there is a new $N_{R,k}$ which works for this series, and if we take k large enough  we have  $N_{R,k}$ > $N_R$ where the inequality is strict.

However, no matter what k we pick $N_{R,k}$ if $\sum a_n$ does not converge to a number > R it is not large enough that  $\sum_{n = 1}^{N_{R,k}} a_n> R$, because there is always a larger k, thus a smaller divergent series, and thus a bigger $N_{R,k}$ for that series.

If for any R there can be no  ${N_R}$ for $\sum a_n$ then that sum cannot be divergent. If it is not divergent, it must converge.


Poisson process expected value Let {${N(t), t \geq0}$} be a Poisson process with rate $\lambda$. Let $S_n$ denote the time of the $nth$ event. What is $E[N(4)-N(2)|N(1)=3]$?

(Note: $E[X]$ is the expected value or mean).

I know that generally $E[N(t)]= \lambda t$, where $t$ is time. Since this is a Poisson process, wouldn't it not matter that $N(1)=3$ since the increments are independent? If so, then would it be correct to claim that $E[N(4)-N(2)|N(1)=3]$= $E[N(4)-N(2)]$=$2 \lambda$?

I don't feel I can contribute any more by writing out an answer, except:

yes you are correct. It follows from independent increment. that $N(4)-N(2)$ is independent of $N(1)-N(0)=N(1)$. therefore, is is just $E[N(4)-N(2)]=2\lambda$

Actually, wouldn't the answer be $2\lambda+3$? $2\lambda$ is the expected occurrences from time $2$ to time $4$ $(N(4)-N(2))$ and you are guaranteed $3$ from the condition.


Limit of the geometric sequence $\{r^n\}$, with $|r| < 1$, is $0$? Prove that the $\lim_{n\to \infty} r^n = 0$ for $|r|\lt 1$.

I can't think of a sequence to compare this to that'll work.  L'Hopital's rule doesn't apply.  I know there's some simple way of doing this, but it just isn't coming to me. :(

Let $a_n=|r|^n$ for $n\ge1$,
so $(a_n)$ is a decreasing sequence which is bounded below by zero

and therefore converges, so let $\displaystyle\lim_{n\to\infty}a_n=L$.

Since $a_{n+1}=|r|a_n$, and $(a_{n+1})$ is a subsequence of $(a_n)$, by the theorem that all subsequence of a convergent sequence converge to the same limit$,  \;\;L=|r|L\implies L=0\;\;$ (for $r\ne0$).

Since $\displaystyle\lim_{n\to\infty}|r|^n=0$,  $\displaystyle\lim_{n\to\infty}r^n=0$ also.

This is an answer I had earlier posted.

This is not a rigorous proof but helps in visualisation.

If $$-1<x<1$$ and you raise it to any power $n > 1 $ the value of it decreases.

Eg say$ x = 0.1 , x ^2  = 0.01, x^3 = 0.001$ or $x ^n = 0.1 ^ n = \frac{1}{10^n}$ and as $ n$ keeps getting bigger , the denominator approaches $\infty $ and the numerator approaches $0 $


Randomly vs Sequentially selecting an item out of a box? Say you have $n$ envelopes in a box placed in some order, and one of them is a special envelope. On average, would you have a higher, lower or equal chance of picking the special envelope if you went in sequential order (left to right) versus if you randomly chose an envelope instead (assuming without replacement)? (Or without replacement)

The two probabilities are the same for all values of $n$.

Assuming that the order of the envelopes was determined randomly (ie they were thoroughly shuffled), then drawing sequentially from this randomly-ordered pack is the same as dealing cards from the top of a shuffled deck. This is the same as drawing from random positions without replacement from a shuffled deck. The double randomness in the second method (random shuffle followed by a random draw) does not make the order in which the cards are drawn any more random. A single random shuffle is as good as a thousand.

In both cases each envelope is drawn only once, and the order in which they are drawn is decided at random. After each draw there are the same number of undrawn envelopes remaining. The special envelope is at a random position among the remainder, so it has an equal chance of being at any position among the remaining cards.

as n goes towards infinity, the two probabilities , namely the one you pick randomly and the one you pick in an order will tend towards the same value.

Why? Think about it as a deck of cards, say I want the hearts 6, I first pick a card and pray that it is hearts 6, it is not and I pick again and I continue until I get hearts 6, this chance on the first try might be (1/52), but if I go in an order I would get (1/52)^n.


Distribution of Universal Quantifiers I know that a universal quantifier can be distributed over conjunction and not disjunction, but I'm having a hard time wrap my head around it. Why is this the case? Is there an example of a statement that would demonstrate this principle?

Intuitively, the reason that universal quantification can be distributed over conjunction is that universal quantification can already be viewed as conjunction: $(\forall x)\Phi(x)$ can be viwed as the conjunction of $\Phi(d)$ taken over every element $d$ of the domain.  Viewed this way, $(\forall x)(\Phi(x) \land \Psi(x))$ and $(\forall x)\Phi(x) \land (\forall x)\Psi(x)$ are equivalent because they both represent a giant conjunction of every instance of $\Phi(d)$ along with every instance of $\Psi(d)$. This can be made more precise by looking at Tarski's schema for truth in a structure.

For the same reason, existential quantification can be distributed over disjunction, because $(\exists x)\Phi(x)$ can be viewed as the disjunction of every possible substitution instance of $\Phi$.

In very old literature, people actually used $\bigwedge_x$ for $\forall$ and  $\bigvee_x$ for $\exists$, for this reason.

Now, continuing this informal viewpoint, the reason that $\forall$ cannot be distributed over disjunction is that a certain distributive rule does not hold:
$$
\bigwedge_x\left(\Phi(x) \lor \Psi(x)\right)
$$
is not in general the same as
$$
(\bigwedge_x \Phi(x)) \lor (\bigwedge_x \Psi(x))
$$
Indeed, this rule already fails when there are just two elements in the domain, because the propositional formula
$(P \lor Q) \land (R \lor S)$ is not equivalent to $(P \land R) \lor (Q \land S)$.

Matt E, in his comment, gives two statements. He shows that a universal quantifier cannot be distributed over disjunction, because if it could, a false statement would follow logically from a true one. The statement "A universal quantifier can be distributed over disjunction" is itself a universal statement, and requires only one counterexample to disprove it.

"A universal quantifier can be distributed over conjunction" is also a universal statement. It cannot be proved by giving examples. There might be some counterexample we didn't think of. So how do we know it's true? -- Good question!


Prob. 9, Chap. 6, in Baby Rudin: Which one of these two improper integrals converges absolutely and which one does not? Here are the links to three earlier posts of mine on Prob. 9, Chap. 6, in Baby Rudin here on Math SE.

Prob. 9, Chap. 6, in Baby Rudin: Integration by parts for improper integrals

Prob. 9, Chap. 6, in Baby Rudin: Integration by parts for improper integrals with one infinite limit

Prob. 9, Chap. 6 in Baby Rudin: Integration by parts for an improper integral

Now my question is the following.

  Which one of the integrals $\int_0^\infty \frac{ \cos x }{ 1+x } \ \mathrm{d} x$ and $\int_0^\infty \frac{\sin x}{ (1+x)^2 } \ \mathrm{d} x$ converges absolutely, and which one does not?

My Attempt:

  For any $b > 0$, and  for all $x \in [0, b]$, the following inequality holds:
  $$ \left\lvert \frac{ \sin x }{ (1+x)^2 } \right\rvert  \leq \frac{1}{(1+x)^2},  $$
  which implies (by virtue of Theorem 6.12 (b) in Baby Rudin) that
  $$ \int_0^b \left\lvert \frac{ \sin x }{ (1+x)^2 } \right\rvert \ \mathrm{d} x \leq \int_0^b \frac{1}{(1+x)^2} \ \mathrm{d} x = - \frac{1}{1+b} - \left( - \frac{1}{1+0} \right) = 1 - \frac{1}{1+b}; $$
  moreover,
  $$ \lim_{b \to \infty} \left( 1 - \frac{1}{1+b} \right) = 1. $$
  So we can conclude that
  $$  \int_0^\infty \left\lvert \frac{ \sin x }{ (1+x)^2 } \right\rvert \ \mathrm{d} x = \lim_{ b \to \infty}  \int_0^b \left\lvert \frac{ \sin x }{ (1+x)^2 } \right\rvert \ \mathrm{d} x \leq 1. $$
  That is, the improper integral $\int_0^\infty \left\lvert \frac{ \sin x }{ (1+x)^2 } \right\rvert \ \mathrm{d} x $ converges, which is the same as saying that the integral $\int_0^\infty \frac{ \sin x }{ (1+x)^2 } \ \mathrm{d} x $ converges absolutely.

Am I right?

If so, then, as suggested by Rudin, the other integral does not converge absolutely.

But how to show this directly?

Observe that on any interval of the form $[(k-1/3)\pi, (k+1/3)\pi]$ (where $k \in \mathbb Z$), we have $|\cos(x)| \geq 1/2$. Therefore the integral

$$\int_0^{\infty}\left|\frac{\cos(x)}{1+x}\right|\ dx$$
is at least as large as
$$\sum_{k=1}^{\infty}\int_{(k-1/3)\pi}^{(k+1/3)\pi} \frac{1}{2(1+x)}\ dx$$
As the integrand is monotonically decreasing for positive $x$, it follows that on the interval $[(k-1/3)\pi, (k+1/3)\pi]$ (with $k > 0$) we have
$$\frac{1}{2(1+x)} \geq \frac{1}{2(1 + (k + 1/3)\pi)}$$
and therefore
$$\sum_{k=1}^{\infty}\int_{(k-1/3)\pi}^{(k+1/3)\pi} \frac{1}{2(1+x)}\ dx \geq \sum_{k=1}^{\infty} \frac{\pi}{3(1+(k+1/3)\pi)}$$
which diverges by limit comparison with $\sum 1/(3k)$.

Your proof of convergence is correct.

To show that (a) does not converge, consider that
$$
\int_0^\infty \left| \frac{\cos x}{1+x}\right| \geq \sum_{n=0}^\infty \int_{2n\pi}^{2n\pi+\pi/6} \left| \frac{\cos x}{1+x}\right| \geq
\sum_{n=0}^\infty \int_{2n\pi}^{2n\pi+\pi/6} \left| \frac{1/2 }{1+x}\right|
\\ \geq \frac{\pi}{12} \sum_{n=0}\frac{1}{1+x}
$$
and the last sum diverges.


About Utterly odd numbers. Consider the following sequence defined here https://oeis.org/A079523 of utterly odd numbers: These are numbers such whose binary representation ends in an odd number of ones.

If $n$ is an utterly odd number, then show that $n+64$ is also an utterly odd number. I did some computer experiments and I think that this is true. But I am not sure how to prove it.

For a number to be utterly odd, the number of its binary digits is odd.
For example, we have the number
Converting it into binary:

$$19 = 10011_2$$  where we have total five (odd number) of binary digits

and in the same way, if we see 18,

$$18 = 10010_2$$ It also consists of an odd number of digits in binary.

So, conclusion:

  A number is called an utterly odd number if it consists of an odd number of digits in its binary representation(omitting zeros on the left side if any )

Now, we check the term n+64 if it is utterly odd or not.
64 has 7 binary digits i.e. 1000000
it will remain a 7 digit binary for $$X<64$$
Because at n=64,
the expression becomes,
$$ (64+64) =128 $$
Which in binary consists of 8 digits

For n=1 till 200,
the values of n for which $$(n+64)$$ is an utterly odd number are:

$$[0,63] U [192,448] U [960, 1983]$$

let's check the size of the intervals,

length of the first interval is $$63= 2^6-1$$

Second interval length = $$448-192=2^8$$

and Similarly for the third one,
$$1983-960=1023=2^{10} -1$$

So, the length of the interval k in which we get an utterly odd number is :

$$f(k) = {2^2k -1,    {k = Odd}}$$
and $$f(k) =  {2^2k ,  {k = Even} }$$

So, the final conclusion:

  $$n+64$$ is not an utterly odd number for every n, however, it behaves as an utterly odd number in some intervals


Improper integral of the form $I=\int_{0}^{\infty} \frac{\sin(ax)}{x^2+b^2}dx$ My teacher showed in class that starting with $\int_{-\infty}^{\infty} e^{inx}g(x)dx$ for an even function $g(x)$ we have
$$\int_{0}^{\infty} \cos(nx)g(x)dx=\pi i\sum \operatorname{Res}\left( f(z)\right)$$

and for an odd function $g(x)$:
$$\int_{0}^{\infty} \sin(nx)g(x)dx=\pi \sum \operatorname{Res} \left(f(z)\right)$$

with $n>0$, $f(z)=e^{inz}g(z)$ and $\lim\limits_{z\to\infty}g(z)=0$

However, when he tried to do an example, by mistake he forgot to add an $x$ in the numerator and left it as
$$\int_{0}^{\infty} \frac{\sin(4x)}{x^2+4}dx$$

and added the $x$ later. While

$$\int_{0}^{\infty} \frac{x\sin(4x)}{x^2+4}dx$$

is not that hard to evaluate, many solutions are found here

I tried to do the first one when I got home, but the methods that I learned until now were unsuccessful. Can I get some help on how to evaluate $I=\int_{0}^{\infty} \frac{\sin(4x)}{x^2+4}dx$ please?

If we set $F(a)=\int_{0}^{+\infty}\frac{\sin(ax)}{x^2+1}\,dx$ we have
$$ (\mathcal{L} F)(b) = \int_{0}^{+\infty}\int_{0}^{+\infty}\frac{\sin(ax) e^{-ab}}{x^2+1}\,dx \,da =\int_{0}^{+\infty}\frac{x\,dx}{(x^2+b^2)(x^2+1)}=\frac{\log b}{b^2-1}$$
hence $F(a)$ is given by the inverse Laplace transform of $\frac{\log b}{b^2}+\frac{\log b}{b^4}+\frac{\log b}{b^6}+\ldots$, i.e. by
$$ \sum_{n\geq 0} \frac{a^{2n+1}}{(2n+1)!}\left(H_{2n+1}-\gamma-\log(a)\right) $$
and
$$ \int_{0}^{+\infty}\frac{\sin x}{x^2+1}\,dx = \sum_{n\geq 0}\frac{H_{2n+1}-\gamma}{(2n+1)!} $$
is rather non-elementary (related to the exponential integral) but pretty simple to approximate numerically.

Some hints:
What is Fourier transform of $e^{-a|t|}$?

Do you know about connection between reverse Fourier transform of function and the function exact?

What about $\int_{0}^{\infty} e^{-at} \sin(bt)$?

Another attempt : you may consider $F(a) = \int_{0}^{\infty} \frac{\cos(ax)}{x^{2}+4}$. Then find a first derivation with respect to $a$. But you should prove uniform convergence of first integral on $E = [1,\infty)$.


Hydrogen atom in partial differential equations For the hydrogen atom, if
$$\int |u|^2 ~dx = 1,$$
at $t = 0$,
I am trying to show that this is true at all later times.

What I need help is with differentiating the integral with respect to $t$, and taking care about the solution being complex valued. Except that my notation is getting me mixed up. I think this might get me there.

Following Ben's hint, here is what I have:

Change $|u|^ 2$   into $u^* u$.
Bring the derivative inside the integral.
Apply the product rule.
Apply the Schrödinger equation and try to show that the result is zero.

$$\int u^* u ~dx = 1 $$

and to bring the derivative inside the integral, isn't $dx$ already inside?

From Schrödinger equation I have:

$$-i\hslash u_t = \sum_{i=1}^n \frac{\hslash^2}{2m_i}(u_{x_i x_i} + u_{y_i y_i} + u_{z_i z_i}) + V(x_1,\ldots,z_n)u$$

for $n$ particles and the potential would $V$ depend on all of the $3n$ coordinates.

I'm not sure how to extend it to even 2 dimensions with the notation below

I will do for you the case of one particle in one dimension. See if you can do the many particles in three dimension case yourself.

It suffices to show $$ \frac{d}{dt} \int u^*u \mathrm{d}x = 0 $$

Bringing the derivative inside the integral sign you need to compute
$$ \int \partial_t(u^*) u + u^* \partial_t u \mathrm{d}x \tag{1}$$
Now we plug in Schroedinger's equation
$$ \partial_t(u) = \frac{i \hbar}{2m} u_{xx} + \frac{i}{\hbar} V u $$
which implies, by taking the complex conjugate (we assume that $V$ is a real valued potential; otherwise the conservation law may not be true)
$$ \partial_t (u^*) = - \frac{i \hbar}{2m} u^*_{xx} - \frac{i}{\hbar} V u^* $$
So expression (1) can be rewritten as
$$ \int \frac{i}{\hbar}\left( V |u|^2 - V |u^2|\right) + \frac{i \hbar}{2m} \left(u^* u_{xx} - u^*_{xx} u\right) \mathrm{d}x \tag{2}$$
The terms inside the first set of parentheses clearly cancel. We treat the second set of parentheses by integration by parts. This shows that the terms inside the second parentheses cancel each other. From which we conclude that
$$ (1) = (2) = 0 $$
as desired.

Now, one quick word on the idea behind the computation above: the magic all sits behind the $i$ factor in the $i\partial_t$ of Schroedinger's equation. Observe the right hand side is given by some real valued function times the wave-function $u$ itself (okay, there is also the Laplacian term; we need that the Laplacian is "self-adjoint", which means that as an operator it is "real-valued"). If we divide the $i$ over the the right hand side, the equation is schematically
$$ \partial_t u = i \times \text{something real} \times u $$
Now using our elementary complex analysis, we know that "$i$ times a complex number $z$ is orthogonal to $z$ itself", and this is what, when all is said and done, allows you to say that the $L^2$ norm of $u$ is conserved under the Schroedinger flow.

Wave function and time: With a potential (V is the potential) that does not depend on time, a general technique is to see what one gets when one writes the wave function as a product of a function only dependent on time, and another function only dependent on place. The Schrodinger equation then gives the result that the complex conjugate of the time-dependent part (up to a constant) equals the reciprocal. One needs to know what the derivative of the exponential function is.


Problem with intuition regarding continuous functions? Suppose we have as a topological space $X$ the  figure eight space. Let $A \subset X$ be one of the circles, then evidently one has a continuous map $f: X \rightarrow A$ by mapping the other circle to the point of intersection. Often, when I visualize continuous functions, I consider them as if they are "deformations" of the space (I do NOT mean the real topological notion of 'deformation', but the one you find in the dictionary).

However, this has some complications: for this to make sense (as highlighted by my example) I would always need some ambient space in which I can visualise this deformation. In my case, this is evident: just use the Euclidean space, then the 'continuous deformation' is the one collapsing the circle to said point.

However, I don't feel comfortable with just embedding everything into the Euclidean space, or some other bigger ambient topological space. My question is then: is this intuition bad? If yes, what is a better intuition to know if a map is 'continuous'? (I mean this broadly, I know that we can't always embed it into an Euclidean space, but this doesn't take away the fact that I can look at continuous maps as 'deformations' of the topological space)

Topology is not about form, geometry is about form, topology is a way to deform the properties of the space, not the space itself, at least in my point of view.


Normal Distribution website I dont know if this is allowed to be asked but I'm trying to teach myself probability and statistics. I've moved onto Normal distriibuton and cumulative distribution functions and I can't find any great websites that have basic ways of describing how formulas work. I'm just wondering if there are any great websites you know of I could teach myself with? Thanks

Khan Academy has already been mentioned but i have to add this: there you usually won't find great explanations of how formulas work. I'm a Statistics major and i have used Khan Academy and, when it concerns explanations of how formulas work, you will find only a good video or 2 about the Poisson process.

Undergrad level books and Khan Academy aren't strong on proofs for the formulas that you are looking for, because those proofs require fancier math than the necessary to use them. I think you will find what you are looking for only in sophisticated books.

See this one:

http://stattrek.com/tutorials/statistics-tutorial.aspx

http://stattrek.com/probability-distributions/normal.aspx?Tutorial=Stat

Here is another:

http://www.intmath.com/counting-probability/11-probability-distributions-concepts.php

And if you google

https://www.google.com.br/?gws_rd=ssl#q=probability+distribution+examples+pdf&*&spf=109

you will find a lot of information.


Is there a calculator out there that shows the full answer instead of shortening it? I'm looking for a calculator that shows a full answer regardless of it's length.

For example the assignment 2^1000 will output: 1,07150860718626732094842504906e+301.
Windows calculator shows me that amount because else it won't fit the display.

So the question is:
Is there a calculator out there that shows the full answer instead of shortening it?

You can try Python console. Python can work with large numbers, and you can use it as calculator


find a $n\times n$ real matrix whose minimal polynomial is $x^{n-1}$ I need to find a $n\times n$ real matrix whose minimal polynomial is $x^{n-1}$. I know this transformation with respect to the basis $\{v_1,\dots,v_n\}$ $$T(v_1)=v_2$$ $$T(v_2)=v_3$$ $$\dots\dots$$ $$T(v_{n-1})=v_n$$ $$T(v_n)=0$$ is nilpotent with characteristic polynomial $X^n$.

Could any one help to how to solve the above one?

For $n=1$ there is no solution (the only matrix with minimal polynomial $1$ is the $0\times 0$ matrix). Otherwise there is a solution, but not the $T$ in your question, which has $T^{n-1}\neq0$. Instead, you need the kernel of $T$ to be $2$-dimensional, which you can achieve for instance by changing the definition to have $T(v_1)=0$. The matrix of $T$ on the basis $v_1,\ldots,v_n$ then becomes
$$
\begin{pmatrix} 0&0&0&\ldots&0&0\\0&0&0&\ldots&0&0\\
0&1&0&\ldots&0&0\\0&0&1&\ldots&0&0\\\vdots&\vdots&\ddots&\ddots&0&0\\
0&0&0&\ldots&1&0\\
\end{pmatrix}.
$$
Another (equivalent) soultion is to define $T(v_{n-2})=0$ instead. In either case there is a vector $v_i$ with $T^{n-2}(v_i)\neq0$, but $T^{n-1}=0$.

To see that you must have $\dim(\ker T)=2$, consider the sequence $\dim(\ker T^i)$ for $i=0,1,\ldots,n-1$; it is weakly increasing, starts with $0$ and must end with numbers $d,n$ where $d<n$ (since $T^{n-2}\neq0$). Moreover, as a general fact, the "derived" sequence of its increments is weakly decreasing. It then follows that this derived sequence is $2,1,1,\ldots,1$ and the original sequence $0,2,3,4,\ldots,n-1,n$, in particular $\dim(\ker T^1)=2$.

The fact that the derived sequence is weakly decreasing follows because $T$ induces a map $\ker(T^{i+2})/\ker(T^{i+1})\to\ker(T^{i+1})/\ker(T^i)$ that can be checked to be always injective.


Is there an equation that represents the nth row in Pascal's triangle? I'm doing binomial expansion and I'm rather confused at how people can find a certain coefficient of certain rows.

For example, if a problem was $(2x - 10y)^{54}$, and I were to figure out the $32^{\text{nd}}$ element in that expansion, how would I figure out?

Would I have to look at or draw out a Pascal's triangle, then go 1 by 1 until I hit row 54?    Is there an equation that would tell me what the xth element of the nth row is by plugging in numbers?

The $n^{th}$ row reads

$$1,n,\frac{n(n-1)}2,\frac{n(n-1)(n-2)}{2\cdot3},\frac{n(n-1)(n-2)(n-3)}{2\cdot3\cdot4}\cdots$$

This is computed by recurrence very efficiently, like

$$1,54,\frac{54\cdot53}2=1431,\frac{1431\cdot52}3=24804,\frac{24804\cdot51}4=316251\cdots$$

Using symmetry, only the first half needs to be evaluated. Compared to the factorial formula, this is less prone to overflows.

Looking at the first few lines of the triangle you will see that they are powers of 11 ie the 3rd line (121) can be expressed as 11 to the power of 2. This works till the 5th line which is 11 to the power of 4 (14641).

An equation to determine what the nth line of Pascal's triangle could therefore be n = 11 to the power of n-1

This works till you get to the 6th line. Using the above formula you would get 161051. The 6th line of the triangle is
1 5 10 10 5 1. Both numbers are the same. By inspection you will see that 161051 expressed in base 11 is in fact
1 5 10 10 5 1.

The equation could therefore be refined as:

n (base 11) = 11 to the power of n-1


$n=13$ is a counter example for claim 2.

Claim 1 is vaccuously true, since given any $n$, $a_{n}\in\mathbb{Z}$.

It also looks like n=14 is a counterexample to claim 2.

Proof:
$3-14=-11$ and $2(-11)+5=-17$ has positive divisors $1$ and $17$ only.


System of linear equations in C Find all solutions for matrix depending on the parametres a,b ∈ C...

With the usage of elementary row operations we can get to the reduced matrix
Now, what is the appropriate way of the parametrical solution and how do parametres a,b affect our solutions (existece, values, # of solutions...)?

thought it was obvious from the first matrix.. the columns represent variables x1, x2, x3 plus we have the parameters a, b.
The system would look like this:

-ix1 + ax2 + (2-4i)x3 = 0
x1 + 2ix2 + bx3 = 0
ix1 - x2 + ix3 = 1


Find the closure of A∩B I have  two sets, $A= \{1,2\}$ and $B=\{2,3\}$. $A \cap B = \{2 \}$. The definition of closure states, the closure of any set A is the smallest set that contains A. So I do not know how to use this to determine the closure of (A∩B)

According to your defnition the closure of a set $A$ $cl(A)$ is the smallest closed set $B$ which contains $A$.
Now a singleton set is closed. Therefore $\{2\}$ is smallest closed set which contains $\{2\}$.Hence $cl\{2\}=\{2\}$

Closure is the set $\overline{A}$ such that $\forall a\in \overline{A}$: $a\cap A$ is not empty.

The closure of a single point would be that point itself, as it is the only point that always has a nonzero intersect with set described by that point!


Prove) Suppose $x_n\to\infty$. Then every subsequence $x_{n_k}\to\infty$. I don't think this statement is true. What if the sequence $x_n = 1$ for all even numbers but $x_n$ is a strictly monotone sequence when $n$ is odd? Then the sequence $x_n$ is a divergent sequence but still has a convergent subsequence, by making $n_k$ a sequence of even numbers.

Is my counterexample valid?

Let $(x_{\phi (n)}) $ be a subsequence of $(x_n) $ with $x_n\to +\infty $.

for $A>0$, there exist $N>0$ such that

$$n>N\implies x_n>A $$

but $$\phi (n)\ge n $$ thus

$$n>N\implies \phi (n)>N$$
$$\implies x_{\phi (n)}>A $$

$$\implies \lim_{n\to+\infty}x_{\phi (n)}=+\infty .$$

Your counterexample is not good cause
$\lim x_n $ doesn't exist.

How do the even terms $x_n =1$ get larger and larger? For example $x_n \to \infty$ requires that from some $N$ onward (meaning all $n>N$) $x_n$ mus be greater than, say, $2345$. Surely there are even $n$ which are $> N$.


an isomorphism to product ring $\mathbb{C}\times \mathbb{C}$ Examine whether there is a polynomial $f(X)\in \mathbb{R}[X]$ such that $\frac{\mathbb{R}[X]}{(f(X))}$ is isomorphic to the product ring $\mathbb{C}\times \mathbb{C}$.

I have found a particular example if the polynomial ring would be of two variable, e.g. $\frac{\mathbb{R}[X,Y]}{(X^2+1,Y^2+1)}$ which is isomorphic to $\mathbb{C}\times \mathbb{C}$, or if we allow the ring over $\mathbb{C}$, e.g. $\frac{\mathbb{C}[X]}{X^2+1}$. I think it is not possible to find such $f$ over $\mathbb{R}[X]$ but I am unable to provide a justification there. All I have figured out that $\mathbb{C}\times \mathbb{C}$ is neither an integral domain nor a field, hence $(f(X))$ is neither prime nor maximal ideal. So $f(X)$ has to be a reducible polynomial over $\mathbb{R}[X]$, if it exists. Can we conclude something from here?

Hint: something similar $\mathbb{Z}/6\mathbb{Z}\cong \mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/3\mathbb{Z}$ can happen over polynomial rings.

Note that $(x^2+1)^2$ won't work, similar to $\mathbb{Z}/4\mathbb{Z}\not\cong\mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/2\mathbb{Z}$. However, unlike with $\mathbb{Z}$, it is possible to quotient $\mathbb{R}[x]$ by different polynomials and get the same quotient ring $\mathbb{C}$.

(If you're familiar with the general form of the Chinese Remainder Theorem for rings, good.)

[My thinking :] As we know that irreducible polynomials in R[x] have degree 1 or 2. If we find any polynomial of degree polynomial of degree 4 that can be reducible into lower degree. So there is no polynomial f(x) in R[x].


Discrete Math - Logic - Implication Problem I am taking a discrete mathematics course, and I am currently studying the logic chapters of the textbook. The problem I am trying to solve at the moment says "Use truth tables to verify the following" which makes me assume that it expects the two compound statements being compared to be logically equivalent. Anyways this is the problem:
$$
(P\implies Q)\land(Q\implies R)\equiv (P\implies R).
$$
When I set up the truth table for this problem, I am getting the answer that thee two statements are not logically equivalent. Perhaps this is right, but this problem has 4 other subproblems (a,b,c,d,....etc.), each of which had statements that were logically equivalent. Maybe I am over-thinking this, but any help, hint, or explanation is appreciated.

You are correct that $$(P \rightarrow Q) \land  (Q \rightarrow R) \not\equiv P\rightarrow R$$

It is true that $$\Big((P\rightarrow Q) \land (Q\rightarrow R)\Big) \rightarrow (P \rightarrow R)$$ (You can confirm that this is a tautology by consulting its truth-table.)

But if $Q$ is false, and P is true, and R is true, the left hand side is false, but the righthand side is true, so the implication is not bidirectional.

The statement above is true, because the implication is false only if the premise is true and the conclusion is false.


Is the set $A$ open in $\ell^2$ Let $A=\{(a_n)\in\ell^2:|a_n|<1\;\forall n\}$. Is the set $A$ open in $\ell^2=\{(a_n):\sum|a_n|^2<\infty\}$? I think it might be, because it has the form of an open ball, but how to check openness with respect to $\ell^2$ norm $||a||=\left(\sum|a_n|^2\right)^{1/2}$?

A set $A$ is open iff for every point $a \in A$ exists $\epsilon > 0$ such that $B(a, \epsilon) \subseteq A$, where $B(a, \epsilon)$ is the $\epsilon$-ball around $a$. I claim in this case that your $A$ is open, and I’ll show this by showing that for any $a \in A$, there exists $\epsilon > 0$ such that if $\| x - a \| < \epsilon$, then $x \in A$, i.e. $B(a, \epsilon) \subseteq A$.

Fix some $a \in A$. Since $(a_n)$ is square-summable, we know in particular that $a_n \to 0$, so the sequence $(|a_n|)$ attains a maximum $M < 1$. Choose $$ \epsilon = (1 - M)/2 .$$

If $\| x - a \| < \epsilon$, where $x \in \ell^2$, then
\begin{align*}
|x_n| & \leq |x_n - a_n| + |a_n| \\
& = \left( |x_n - a_n|^2 \right)^{1/2}+ |a_n| \\
& \leq \left( \sum_n |x_n - a_n|^2 \right)^{1/2} + M \\
& = \| x - a \| + M \\
& < \epsilon + M \\
& < 1.
\end{align*}
Thus $x \in A$. This proves that $A$ is open.

Denote $\|(a_n)\|_\infty = \sup |a_n|.$ Clearly $\|(a_n)\|_\infty \leq \|(a_n)\|$ and it is well-known that $\| \cdot \|_\infty$ is a norm. This implies that the identity is continuous $(\ell^2, \|\cdot\|) \to (\ell^2, \|\cdot\|_\infty),$ a fortiori the inverse image of the $\|\cdot\|_\infty$-ball of radius one, namely $\{(a_n); |a_n| < 1, \ \forall n\},$ is open relative to $\|\cdot\|.$


How many distinct permutations of the string "NADAMADRID" have the word DAM appearing in them? How many distinct permutations of the string "NADAMADRID"  have the word DAM appearing in them?
Normally, under the Mississippi Rule, you would take the total number of characters factorial, then divide by the product of all the characters that repeat factorial. In this case however, they ask how many times a certain word will appear in the permuations of a bigger string. I was confused on how to do this problem, and how i would count these possibilites.

I assume you don't distinguish between the same letters, e.g. $D_1$ and $D_2$ are the same, i.e. they are the same color. In such case, you have $10-3+1=8$ position for DAM. For each such position you have $\binom{7}{2}\binom{5}{2}\binom{3}{1}\binom{2}{1}$ allocations for remaining letters.
If you distinguish between letters as above, you also need to account for selection of 'D' and 'A' for DAM, e.g. D can be selected in $\binom{3}{1}$ ways, etc.

The string "NADAMADRID"  contain exactly total 10 characters.
Now consider DAM  as a single character (Say DAM = X), so the new string of
total 8 characters will be XNAADDRI.
Here we see,

X occurs once
N occurs once
A occurs twice(2)
D occurs twice(2)
R occurs once
6.I occurs once

Hence the permutations of XNAADDRI (i.e "NADAMADRID" have the word DAM ) with repeataion of A and D is 8!/(2! * 2!).


Probability of getting at least one of each balls from an urn Consider an urn containing $4$ red balls, $4$ blue balls, $4$ yellow balls, and $4$ green balls. If 8 balls are randomly drawn from these 16 balls, what is the probability that it will contain at least one ball of each of the four colors?

Attempted Solution:

I think I did this right, but I just wanted to confirm.

P(at least one of each ball)

= $1$ - P(not one of each)

= $1$ - $\frac{12\choose8}{16\choose8}$ = $.9615$

Edit:

Actually, I think I have to choose one group of 4 to not get any selected, i.e. $4\choose1$ and then take

$1$ - $4$$\frac{12\choose8}{16\choose8}$ = $.846$

We can use inclusion-exclusion principle:
Let $A_1,A_2,...,A_4$ denote events that there will be a red, blue, green, yellow ball in our selection respectively.

Then, by symmetry:$$P(A_1^c\cup...\cup A_4^c) = 4P(A_1^c)-6P(A_1^c\cap A_2^c) + 4P(A_1^c\cap A_2^c \cap A_3^c) - P(A_1^c\cap A_2^c \cap A_3^c \cap A_4^c) $$

Noting that $$P(A_1^c) = \frac{\binom{12}{8}}{\binom{16}{8}} \quad \quad P(A_1^c\cap A_2^c) = \frac{\binom{8}{8}}{\binom{16}{8}}$$ and the remaining terms are zeroes.

Thus $$P(A_1 \cap...\cap A_4) = 1-P(A_1^c\cup...\cup A_4^c) = \color{red}{\frac{1816}{2145}}=0.846620...$$

which is different from your proposed answer:
$$1-4\frac{\binom{12}{8}}{\binom{16}{8}} = \frac{11}{13} = 0.846154...$$

OP answer and method is not correct.

still does not count correctly.

this can be easily seen if draws 4 thru 13 are done (the distribution)

(left to the reader of course)

-Inclusion-exclusion method gets it right-

I used this:

(C(16,8)^-1) * sum((-1)^k * C(4,k) * C(4*(4-k),8)) , k=0 to 3

in Wolfram Alpha

returns
1816/2145

or
≈0.84662

pisco125 answer exactly

Sally

added:
using brute force counting in Excel and using some R code (not shown)

I get 85 unique draw results (combinations)
where 31 have at least 1 (complete set) of each color

adding the number of ways for each unique combination...

that fraction is
10896/12870

Excel snapshot

that reduces to 1816/2145
as before


Proof that the trace of a matrix is the sum of its eigenvalues I have looked extensively for a proof on the internet but all of them were too obscure. I would appreciate if someone could lay out a simple proof for this important result. Thank you.

These answers require way too much machinery. By definition, the characteristic polynomial of an $n\times n$ matrix $A$ is given by
$$p(t) = \det(A-tI) = (-1)^n \big(t^n - (\text{tr} A) \,t^{n-1} + \dots + (-1)^n \det A\big)\,.$$
On the other hand, $p(t) = (-1)^n(t-\lambda_1)\dots (t-\lambda_n)$, where the $\lambda_j$ are the eigenvalues of $A$. So, comparing coefficients,  we have $\text{tr}A = \lambda_1 + \dots + \lambda_n$.

By the Schur decomposition, any matrix $A$ is unitarily similar to an upper triangular matrix $T$. Being similar, $A$ and $T$ have the same trace and the same eigenvalues. Moreover, the diagonal entries of $T$ are equal to its eigenvalues (since $T$ is triangular). The stated result follows by calculating the trace of $T$. See https://www.statlect.com/matrix-algebra/properties-of-eigenvalues-and-eigenvectors.


Breaking a larger cube into a smaller one I would appreciate ideas on solving the following problem:

    A solid cube of side 6 is first painted pink and then cut into smaller cubes of side 2.How many of smaller cubes have paint on exactly 2 side ?

Here's my hint: Stare at that for a sufficiently long time, and the solution will come up.

and if that doesn't help, try this:

Imagine a Rubik's cube. There are 6 corners, each 3 colored, then 8 edges that have only 2 colors, and finally there are 6 centre faces that have only one color. So if its all painted the same color then obviously you'll have 8 such cubies...


I have a question about limit supremum and limit infimum. Let $\{x_n\}_{n=1}^{\infty}$ and $\{y_n\}_{n=1}^{\infty}$ be sequences of real numbers. Does the following hold:

$$
\limsup x_n +\liminf y_n \le \limsup\,(x_n+y_n).
$$

This is what I have tried but I am not quite sure if it is correct.
$\text{Fix } K>1. \text{ Let }L=\inf_{1\le i \le k}y_i$. Now
$$
\sup_{1 \le i \le k}(x_i+y_i)\ge \sup_{1\le i \le k}(x_i+L)=L+\sup_{1\le i \le k}(x_i) =
\inf_{1\le i \le k}(y_i)+\sup_{1\le i \le k}(x_i).
$$
Now we take the limit as $k \rightarrow \infty$ and we have the desired result. Does this look OK?

Let $~\limsup x_n=\overline x~$ and $~\liminf y_n=\underline y~,$ then $~\overline x~,~\underline y~\in \mathbb R.$
Let $~\epsilon>0~$ be given.
Then $~\exists~~k\in \mathbb N~$ such that $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~x_n>\overline x-\epsilon~/~2~,~~\forall~~n\ge k~$ and $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y_n>\underline y-\epsilon~/~2~,$ for infinitely many value of $~n~.$
Thus $~x_n+y_n>\overline x+\underline y-\epsilon~,$ for infinitely many value of $~n~.$
Therefore for given $~m\in\mathbb N~,~~\exists~~n_0\ge m~$ such that $$x_{n_0}+y_{n_0}>\overline x+\underline y-\epsilon$$
$$\implies \sup_{n\ge m}\left(x_n+y_n\right)\ge x_{n_0}+y_{n_0}>\overline x+\underline y-\epsilon~,$$ for each $~m\in \mathbb N~.$
Hence $$\overline x+\underline y-\epsilon\le\limsup\,(x_n+y_n)$$
Since $~\epsilon > 0~$ be arbitrary, $$\limsup x_n +\liminf y_n \le \limsup\,(x_n+y_n)~.$$

$$\limsup (x_n+y_n) = \lim_{n\to\infty} \left(\sup_{k>n}(x_k+y_k)\right) \leq  \lim_{n\to\infty}\left(\sup_{k>n}x_k+\sup_{k>n}y_k\right)=\\=\limsup(x_n)+\limsup (y_n)$$

The inequality is because a property of supreme: $\sup (a+b) \leq \sup (a) + \sup (b)$.


Solve the equation $\cos^n(x) - \sin^n(x)=1$ Solve the equation $\cos^n(x) - \sin^n(x)=1,n \in \mathbb{N}-\{0\}$

If $n$ is even then $\cos^n(x) = \sin^n(x)+1$ is only possible if $\sin(x)=0$ therefore the solution is $x=k\pi, k \in \mathbb{Z}$.

I'm having problems with $n$ odd case.

UPDATE

For $n=1$ we have $\cos(x) - \sin(x)=1$ and by squaring we get $sin(x)cos(x)=0$ which leads to $x=k\pi$ or $x=\pm \frac \pi 2 + k\pi$. From these solutions, only $x=2k\pi$ and $x=- \frac \pi 2 + 2k\pi$ are valid.

Also $x=2k\pi$ and $x=- \frac \pi 2 + 2k\pi$ are solutions for all odd $n$

It suffices to investigate the solutions over $[0,2\pi)$, as all solutions will be some integer multiple of $2\pi$ away from a solution in $[0,2\pi)$. Let $f(x) = \cos^n(x)-\sin^n(x)$, with $n$ odd and $n\ge 3$. Then
$$f'(x) = n(\cos^{n-1}(x)(-\sin x) - \sin^{n-1}(x)\cos(x)) = -n\sin(x)\cos(x)(\cos^{n-2}(x)+\sin^{n-2}(x)) $$
It can easily be seen that $f'$ has zeros at $0$, $\frac{\pi}{2}$, $\frac{3\pi}{4}$, $\pi$, $\frac{3\pi}{2}$, and $\frac{7\pi}{4}$, with $f'<0$ on $(0,\frac{\pi}{2})\cup(\frac{3\pi}{4},\pi)\cup(\frac{3\pi}{2},\frac{7\pi}{4})$ and $f'>0$ on $(\frac{\pi}{2},\frac{3\pi}{4})\cup(\pi,\frac{3\pi}{2})\cup(\frac{7\pi}{4},2\pi)$.

Now
\begin{align} f(0) &= 1 \\
f(\frac{\pi}{2}) &= -1 \\
f(\frac{3\pi}{4}) &= -2\left(\frac{1}{\sqrt{2}}\right)^n \\
f(\pi) &= -1 \\
f(\frac{3\pi}{2}) &= 1 \\
f(\frac{7\pi}{4}) &= 2\left(\frac{1}{\sqrt{2}}\right)^n
\end{align}
From this, we see that $0$ and $\frac{3\pi}{2}$ are solutions. Furthermore, since $f'<0$ on $(0,\frac{\pi}{2})$, we have that $f(x) < f(0) = 1$ for $x\in(0,\frac{\pi}{2})$. Similarly, since $f'>0$ on $(\frac{\pi}{2},\frac{3\pi}{4})$, we have that $f(x)<f(\frac{3\pi}{4}) = -2\left(\frac{1}{\sqrt{2}}\right)^n < 1 $ for $x\in(\frac{\pi}{2},\frac{3\pi}{4})$. Applying similar reasoning to the other four intervals, we find that $f(x)<1$ for all $x\in[0,2\pi)$ except $x=0$ and $x=\frac{3\pi}{2}$.

It follows that the only solutions in $[0,2\pi)$ are $x=0$ and $x=\frac{3\pi}{2}$, so the only solutions in $\mathbb{R}$ are $\boxed{x = 2k\pi}$ and $\boxed{x = \frac{3\pi}{2} + 2k\pi}$ for $k\in\mathbb{Z}$.

It will only satisfy at 2kπ where, k is an integer. Because when n is odd then at only even multiples of π theq equation will be satisfied.


Closed form for non-linear recurrence $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.

There is no hope to find an explicit formula for $a_n$, but the asymptotics is clear.

One has $a_n=u(a_{n-1})$ where the function $u:x\mapsto\sqrt{x+6}$ has a unique fixed point $a=3$, hence $a_n-a=u(a_{n-1})-a=u(a_{n-1})-u(a)$ and one can suspect that $a_n\to a$. As a matter of fact, $u(a_n)-a=b_n\,(a_{n-1}-a)$ with $b_n=1/(u(a_{n-1})+a)$ hence $0\lt b_n\lt1/a$ hence $|a_n-a|\leqslant a^{-n}\,|a_0-a|$. Since $a\gt1$, this shows that $a_n\to a$.

More is true: since $b_n\to b=1/(2a)=1/6$, $a_n-a=b^{n+o(n)}$. In other words, since $a_n\gt a$ for every $n$,
$$
\lim\limits_{n\to\infty}\frac{\log(a_n-a)}n=\log(b)=-\log(6),
$$
and a little more work shows that $a_n-a=c\,b^n\,(1+o(1))$, where $c$ depends on $a_0$ and has no simple explicit form.

Edit: The algebraic trick used above to compute $b$ might hide the fact that $b=u'(a)$, where $a=u(a)$ is the fixed point of $u$.

Zegalur: I followed your interesting post but cannot see the final
  closed form. My first question is why to "change direction of element
  index" when the changed recurrence Fn+1=F2n−6 is as hard as the
  original a2n=an−1+6? Has this backward recurrence, say, something to
  do with symmmetries in a further elaboration? Would you please clarify
  a bit?

Strange. I can't write any comments.. so I wrote a new answer.. Anyway...

I take a square of two parts of equation and move $6$ to the left side of equation.
$$
a_n = \sqrt{a_{n-1}+6} \ \ \ => \ \ \ a^2_n - 6 = a_{n-1} \ \ \ => \ \ \ a_{n-1}=a^2_{n} - 6.
$$
If we have $a_0$ we now can find $a_{-1}, a_{-2}, ...$ ($a_{-1}=30$).

I've changed direction of index because it's more native to work with something like this:
$$
F_n = Q(F_{n-1}).
$$
(when the next element of sequence is expressed through previous one).

Now $F_{n} = a_{-n}$. If I will find solution in a closed-form $F_{n} = W(n)$ then I can use it to express solution for $a_n$.
$$
a_n = F_{-n} = W(-n).
$$

It is exactly what I did.

You also write that you can't find a final result. That is because solution is expressed by non elementary function $f(x)$ (see my answer). But you can't even find a Taylor series for it. But that function exist and it is continuous (see for example the plot of it).

Final result is
$$
a_n = F_{-n} = f(X^{2^{-n}})
$$
where $f$ and $X$ are defined in my previous answer.


Show that if n is an integer and 3n+ 2 is even, then n is even using contradiction Show that if $n$ is an integer and $3n+ 2$ is even, then $n$ is even,  using a proof by contradiction.

That's the question. So since we're using contradiction, I need to show that N is odd and prove a contradiction exists, right?

$N = 2k + 1$

$3(2k + 1) + 1=6k + 5\quad$ ?

I think I'm off base, or else I don't know how to proceed.

Use these facts:

$\mbox{odd}\times\mbox{odd}=\mbox{odd}$
$\mbox{odd}+\mbox{even}=\mbox{odd}$

Thus, if $n$ was odd, then:

$3n+2=\mbox{odd}\!\times\!\mbox{odd}+\mbox{even}=\mbox{odd}+\mbox{even}=\mbox{odd}$

But we know that $3n+2$ is even - thus, $n$ can't be odd.

Another way of doing it: Say $n$ is odd. Thus, there exists a $k$ such that $n=2k+1$. Then:

$$3n+2\overset{n=2k+1}=3(2k+1)+2=6k+3+2=6k+5=6k+4+1=2(3k+2)+1$$

Anything of the form $2j+1$ is odd. (In this case, $j=3k+2$.) Thus, we have that $3n+2$ is odd.

But we know that $3n+2$ is even - thus, $n$ can't be odd.

$3n+2=2k$

$n=2k-2n-2$

$n=2(k-n-1)$

$n=2b$

Hence $3n+2$ is even when $n$ is even therefore also odd when $n$ is odd.


Showing that $\ln(b)-\ln(a)=\frac 1x \cdot (b-a)$ has one solution $x \in (\sqrt{ab}, {a+b\over2})$ for $0 < a < b$ For $0<a<b$, show that $\ln(b)-\ln(a)=\frac 1x \cdot (b-a)$ has one solution $x \in (\sqrt{ab}, {a+b\over2})$.

I guess that this is an application of the Lagrange theorem, but I'm unsure how to deal with $a+b\over2$ and $\sqrt{ab}$ since Lagrange's theorem offers a solution $\in (a,b)$.

You could show the relations
$$ \frac{2}{a+b}(b-a) < \log(b)-\log(a) < \frac{1}{\sqrt{ab}}(b-a)$$
directly. (Exactly how does this solve your problem?)

To prove the first inequality, note that it is equivalent to
$$ 2\frac{\frac{b}{a}-1}{\frac{b}{a}+1} < \log\left(\frac{b}{a}\right). $$
Now set $x:= \frac{b}{a}$. We get
$$2(x-1) < x\log(x) + \log(x)$$
or
$$ x\log(x) + \log(x) - 2x < -2,$$
which needs to be true for all $x>1$, since by assumption, $b>a>0$. Let's denote the LHS by $f$. To prove the inequality above, we calculate the derivative of $f$ w.r.t. $x$:
$$f'(x) = \frac{d}{dx}\left(x\log(x)+\log(x) - 2x \right) = \frac{1}{x}-1,$$
which is zero if and only if $x=1$ (where $f'$ also changes sign from $+$ to $-$). Consequently $f$ attains its only maximum at $x=1$, so we get
$$f(x) \leq f(1) = -2 \quad \forall x\in\mathbb{R}^+$$
and the condition $x>1$ makes that inequality strict, as required.

The second inequality can be proven by an analogue approach. I'll leave it up to you to give it a try.


If A and B are denumerable, then A-B is denumerable I am studying for finals and I came across this question:

If $A$ and $B$ are denumerable, then $A-B$ is denumerable.

I saw this had been asked in the past but there was not a concrete answer as to whether this can be proved or not.

I would think $A-B$ would still be denumerable but not sure since denumerable means the set is equivalent to the natural numbers.

Lemma:
A subset of a countable (denumerable) set is countable.

Proof of lemma: Let $A$ be a countable set and $B\subseteq A$. Since A is countable there is an injection $f:A\to \mathbb{Z^+}$. Now the restriction of $f$ to $B$ is an injection from $B$ to $\mathbb{Z^+}$. Hence $B$ is countable. $\Box$

Now it is required to prove that $A-B$ is countable (denumerable). Obviously $A-B\subseteq A$. Since $A$ is countable, by lemma, it follows that $A-B$ is countable. $\Box$


Can an integral domain be embedded in a proper quotient of itself? Does there exist an integral domain $R$ which has a proper ideal $J$ so that there exists an injective ring homomorphism $\phi \colon R \to R/J$?

If yes, what are suitable assumptions on $R$ to exclude such a behaviour? Especially, if $R$ is a finite dimensional complete Noetherian integral domain, can such behaviour occur?

Take the integral domain $R = k[x_1,x_2,\ldots]$ and let $J = (x_1)$. Then $R/J \cong k[x_2,x_3,\ldots]$ which is isomorphic to $R$ because you have infinitely many indeterminates.

    Here are some thoughts for your second question: I think if you throw in the assumption that $R$ is a finitely generated $k$-algebra which is also an integral domain, then there is no non-zero prime ideal $\mathfrak{p}$ such that we have an injection $R \to R/\mathfrak{p}$. Indeed, if $\mathfrak{p}$ is non-zero its height is at least one, so that the formula
    $$\operatorname{ht}(\mathfrak{p}) + \dim R/\mathfrak{p} = \dim R$$
    says $\dim R/\mathfrak{p} < \dim R$ and so you can't have an injection $R \to R/\mathfrak{p}$. For finitely generated $k$-algebras $R,S$ that are domains with $R \subseteq S$, we have $\dim R \leq \dim S$ as pointed out by YACP.

EDIT: The following arguments are incomplete (and thus my response might false) - see the comments.

It is enough to assume that $R$ is a finite dimensional Noetherian integral domain in order to exclude this behaviour. In Eisenbud's book (p.219) one can find the following theorem:

  If $R\subset S$ are Noetherian rings such that $S$ is a finitely generated $R$-module, then $\dim R = \dim S$.

So if $R$ is Noetherian, and $\phi$ is as above, then $R/J$ is a finitely generated $\phi(R)$-module, which thus has the same dimension as $R$.

On the other hand, for any ideal $J$ of $R$ one has

\begin{equation} \dim\  R/J + \operatorname{ht}(J) \le \dim R.\end{equation}

Since any proper ideal has height greater/equal one (here we use the domain assumption), we obtain the contradiction
\begin{equation} \dim R = \dim R/J \le \dim R -1. \end{equation}


Collision detection between two accelerating spheres with no initial velocity? We have two non-touching spheres of radii r1 & r2 are lying in space at rest. Both of them are then given accelerations a1 & a2 respectively at time t=0. Find whether they will ever come in contact. Their initial positions are represented as (x1,y1,z1) & (x2,y2,z2) respectively. Accelerations have respective components in 3D. They are represented as (a1i,a1j,a1k) & (a2i,a2j,a2k) respectively.

What is the mathematical condition for successful collision of spheres?

Note: It would be great if you can give me the satisfying condition in terms of variables mentioned in the question i.e., r1,r2,x1,x2,x3,y1,y2,y3,a1i,a2i,a1j,a2j,a1k and a2k

What I did to solve this problem? (This is wrong attempt)

->

rel_p = [(x1-x2),(y1-y2),(z1-z2)]
rel_a = [(a1i-a2i),(a1j-a2j),(a1k-a2k)]

B = dotproduct(rel_p,rel_a)
C = dot(rel_p,rel_p) - (R1+R2)**2

if C<0:
    ans = True
else:
    if B<0 == True:
       ans = True
    else:
       ans = False
if ans:
    print "YES"
else:
    print "NO"

Find both trajectories. Calculate the distance $d$ between both centers with respect to $t$. Find if there is a solution - such a $t$ that $d=r_1+r_2$.

That's the outline. You got to point out if you got specific problems with some of the steps.

EDIT:
It seems to me that your equations are a bit wrong.

First coordinate of the first sphere will be $x_1+\frac{a_{1i}t^2}{2}$ at moment $t$. So, if I call that $\vec{x}_1=(x_1,y_1,z_1)$ and similarly introduce acceleration vector, the position at $t$ will be given by $\vec{x}_1+\frac{\vec{a}_1t^2}{2}$. You should then write both these vectors and calculate the distance vector between them (just subtract). You must find length of this vector and find if there exists such a $t$ that the length is equal (or less) to $r_1+r_2$.

Rel_p = 1/2 *rel_a *cos(theta)*t^2 ------ 1;
radius(R1+R2) = 1/2*rel_a*sin(theta)*t^2 ----2

rel_a.cos(theta) = dot(rel_a,rel_p) /|rel_p|;

rel_a.sin(theta) = cross(rel_A,rel_p)/|rel_p|;

This will also help in Ad-infinitum ;)


What to take by default in probability: with replacement or without replacement? Question: A bag contains 2 red, 3 green and 2 blue balls. Two balls are drawn at random. What is the probability that none of the balls drawn is blue?

My approach towards the answer is:

I will find the total number of cases: selecting 2 balls out of (2+3+2).

I will find total number of cases which have no blue: selecting 2 balls out of (2 red + 3 green).

Here my question is: in the question no information is given for the replacement.

So what should I take it as: with replacement or without replacement?

Let us assume the above question appears on an exam and the professor has a rule: no questions answered during the exam. How to best interpret the problem as given?

Question : A bag contains 2 red, 3 green and 2 blue balls. Two balls are drawn at random. What is the probability that none of the balls drawn is blue?

We are told that two balls are drawn at random. Since we are not told that the balls were returned to the bag, the simplest interpretation would be that the balls were drawn without replacement and should thus be solved accordingly.

If the instructor then came back and said, "i meant with replacement," then i as a professor of statistics for almost 30 years would say that the question was poorly worded and the student must get the benefit of the doubt. If the instructor did not intentionally set out to trick the student, then the instructor would agree. If the instructor did intend to trick the student, then i would find another instructor.

i hope this reply helps, best.

If you are an Indian student... More specifically CBSE student... You are recommended to assume without replacement if not specified in the question.


Probabilities/Poisson distribution exercise I'm new to this site and I'm having trouble while solving a probability problem.
The question is: We have a regional airport, and the number of planes that arrive on the airport follow a poisson distribution of y=2
What is the probability of at least 3 planes takeoff in at least 3 of 5 days?

I was thinking about hipergeometrical probability, but I really have no idea how to solve this. I'd apreciate a lot if someone could give me a hand on this.

EDIT: The answer is 0,195

We have

Poisson$(\lambda,k)$

$$p(X=k)={\lambda^k\over k!}e^{-\lambda}.$$

The Poisson part tells us via the measurement for one unit of time, that $y=2$.The average of a poisson is $1\over\lambda$, so it's not clear to me whether $\lambda=2$ or ${1\over2}$. Is 2 the average number of planes, or is 2 the decay rate of the distribution? Let's assume there's 2 planes a day so $\lambda={1\over2}$.

Above, it looks like you found $P(k\ge3\text{ planes in one day})$. (It's easier to calculate the complement?)

Let's notate that with a $p$ for success. Then P(at least 3 days)=P(3)+P(4)+P(5) as you say. And

$$P(k)={5\choose k}p^k(1-p)^{5-k}.$$


Maximize $\frac{\sin(2x)}{3-\cos(2x)}$ I want to maximize $\frac{\sin(2x)}{3-\cos(2x)}$. I converted both $\sin$ and $\cos$ to $\tan$ and got answer $$\frac{1}{2\sqrt 2}$$ achieved for example at $x=\operatorname{arccot}(\sqrt2)$. Please give some another approach without using the above conversion formula.

Here is another Approach :

Since a point $(\cos (2t), \sin (2t))$ is on a circle $x^2 + y^2 = 1$,

we can understand $\frac{\sin (2x)}{3-\cos(2x)} = \frac{0-\sin (2x)}{3-\cos(2x)}$ by slope of tangent line between a point $(3, 0)$ and a circle $x^2+y^2=1$.

After calculations, we can get :$$\max\left\{\frac{\sin (2x)}{3-\cos(2x)} \right\} = \frac{1}{2\sqrt{2}} \\
\min\left\{\frac{\sin (2x)}{3-\cos(2x)} \right\} = -\frac{1}{2\sqrt{2}}$$

Hint

Use https://en.m.wikipedia.org/wiki/Tangent_half-angle_substitution#The_substitution
to replace $\sin2x,\cos2x$ with $$\dfrac{2t}{1+t^2},\dfrac{1-t^2}{1+t^2}$$ respectively where $t=\tan x$ to  find

$\dfrac{\sin2x}{3-\cos2x}=\dfrac{2t}{3(1+t^2)-(1-t^2)}=y$(say)

Method$\#1:$

Rearrange the relationship to form a quadratic equation in $t$

As $t$ is real, the discriminant must be $\ge0$

Method$\#2:$

$$y=\dfrac t{1+2t^2}$$

If $t\ge0,$ $$\dfrac{1+2t^2}t\ge2\sqrt{\dfrac1t\cdot2t}=?$$

If $t<0,$ set $t=-u$


Derivation of linear interpolation? Anyone know a good derivation of the linear interpolation:

$$\frac{y-y_0}{x-x_0}=\frac{y_1-y_0}{x_1-x_0}$$

Wikipedia gives one, which I don't understand.

Since it is a linear interpolation, just consider a straight line $y=a+ bx$ which goes through two points $(x_0,y_0)$ and $(x_1,y_1)$. So $$y_0=a+b x_0$$ $$y_1=a+b x_1$$ Solve for $a,b$.

For any two points: $(x_0 ,y_0 )$ and $(x_1 ,y_1 )$

$y_0 =mx_0 +b$  and $y_1 =mx_1 +b$

Solve for $b$ for each equation...

Then set the two equal to each other...

Next solve for $m$

you get: $m=(y_0 -y_1 )/(x_0 -x_1 )$

Since this is true for any two points on the line, its also true for the first point and another point on the line where you may know the $y$ but not the $x$:
say $(x,y_2 )$

so then:
$$m= \frac{y_0 -y_1 }{x_0 -x_1 }=\frac{y_0 -y_2 }{x_0 -x}.$$

There it is!


Linear homogeneous ODE with time dependent matrix I was wondering, if $x'(t)=A(t)x(t)$ where $A(t)$ is a continuos $n\times n$ matrix, how do I show that it has $n$ linearly independent solutions?

Think of $x(t)$ and $A(t)$ as 1-dimensional real functions, then it's a standtard ODE whose solution is $$x(t)=c e^{\int A(t)dt}$$

where $c\in \mathbb R$. This is actually the solution for your case as well, but now $c \in \mathbb R^n$ and all that remains is to know how to compute $e^{\int A(t)dt}$. I bet you already guess how to compute $\int A(t)dt$, all that remains then is to find out how to compute $e^M$ being $M$ a matrix. That is called the matrix exponential, and you can find how to compute it in Wikipedia. In fact, you can compute $f(M)$ for any function $f$

Also, since $A(t)$ is continous, the matrix $\int A(t)dt$ will always exist, and the following relation for the determinant of the matrix $e^{\int A(t)dt}$ will hold $det(e^{\int A(t)dt})=e^{tr(\int A(t)dt)}$ by Jacobi's formula. So you can already compute how the determinant of $e^{\int A(t)dt}$ will vary with time without actually computing the matrix, and as you can see, it will never be $0$, which tells you that the equation will have $n$ independent solutions.


Shorthand notation for infinitesimals and infinite numbers For $r$ is a real number, I can write $r \in \mathbb{R}$.

For $\varepsilon$ is an infinitesimal, I'd like to write something like $\varepsilon \in something$ Is there a symbol for "the set of infinitesimals"? Or alternatively, a commonly used abbreviation for "infinitesimal"?

For $H$ is an infinite (hyperreal) number, I'd like to write something like $H \in \infty$ Is there a symbol for "the set of infinite hyperreals", or a common abbreviation?

In non-standard analysis,
a monad (also called halo) is the set of points infinitesimally close to a given point.

On model for extending real numbers is the hyperreal numbers. The set of hyperreals is usually denoted as ${}^*\mathbb{R}$.
Given $x \in {}^*\mathbb{R}$, the monad of $x$ is the set

$$\mathrm{monad}(x) = \{\; y \in {}^*\mathbb{R} : x - y \text{ is infintesimal }\;\}$$

For those $x$ where $|x| < n$ for $n \in \mathbb{N}$, we call $x$ finite (or limited). For such a $x$, there is a unique real number belongs to the monad of $x$. It will be called the standard part of $x$ (also known as shadow of $x$).

To specify a number $x$ is infinitesimally small, one can use the notation
$x \in \mathrm{monad}(0)$ or  $x \in \mathrm{hal}(0)$.

If one want to go beyond this single use of notations for infinitesimals, I'll suggest one pick a textbook on this topic and stick to it. For example, I use following book as reference

  Lectures on the Hyperreals (an introduction to Nonstandard Analysis) by Robert Goldblatt

It uses following notations

Hyperreal $b$ is infinitely close to hyperreal $c$, denoted by $b \simeq c$ if $b - c$ is infinitesimal. This define an equivalent relations
on ${}^*\mathbb{R}$. The halo of a point $b$ is the $\simeq$-equivalence class
$$\mathrm{hal}(b) = \{ \; c \in {}^*\mathbb{R} : b \simeq c \; \}$$
Hyperreals $b$ and $c$ are of limited distance apart, denoted by $b \sim c$, if $b - c$ is limited (i.e $|b-c| < n$ for some $n \in \mathbb{N}$). The galaxy of $b$ is the $\sim$-equivalent class
$$\mathrm{gal}(b) = \{ \; c \in {}^*\mathbb{R} : b \sim c \; \}$$
The standard part of $x$ is denoted by $\mathrm{sh}(x)$.

Your mileage may vary.

After more research, I have concluded that, as Bye_world suggests, there is no standard notation for the set of infinitesimals. Here are some of the notations I have seen used:

$\mathcal{I}$,
$N$,
$\mathbb{N}$,
$\Delta$.

Also, for "$x$ is an infinitesimal", I have seen the notation $x \approx 0$.


proof by induction for summation This is not a duplicate.  I know my conjecture is right, just need to prove it, using induction(not Gauss Method).
Conjecture formula from following equations, and prove conjecture:
$1=1,\\2+3+4=1+8,\\5+6+7+8+9=8+27,\\10+11+12+13+14+15+16=27+64\\$

$S(n)=\sum_{i=(n-1)^2+1}^{n^2}i=(n-1)^3+n^3$

$S(1)=1=1\\S(2)=2+3+4=1+8\\S(3)=5+6+7+8+9=8+27\\S(4)=10+11+12+13+14+15+16=27+64$

Need to show $S(n+1)=\sum_{i=n^2+1}^{(n+1)^2}i=n^3+(n+1)^3$

It's kind of hairy with the variable in the summation.  Seems like there should be a simpler way to prove it than trying to work out that summation.

Assume $S(n)$ true.  So $S(n+1)=(n-1)^3+n^3+?$

Thanks.

Yes, I am aware that $\sum_{i=k}^ni=\sum_{i=1}^ni-\sum_{i=1}^{k-1}i$ and that $\sum_{i=1}^ni = \frac{n(n+1)}{2}$ and that can be used.


Recursive relation for a characteristic polynomial I need to find a recursive relation for the characteristic polynomial of the $k \times k $ matrix $$\begin{pmatrix} 0 & 1 \\ 1 & 0 & 1 \\ \mbox{ } &  1 & . & . \\ \mbox{ } &\mbox{ } & . & . &. & \mbox{ } \\ \mbox{ } &\mbox{ } &\mbox{ } & . & . & 1 \\ \mbox{ } & \mbox{ } & \mbox{ } & \mbox{ } & 1 & 0\end{pmatrix}$$

I calculate the $3 \times 3$ and $4 \times 4$ case but I couldn't deduce a recursive formula.

The characteristic polynomial of your matrix (say, $A$) is the determinant of the tridiagonal Toeplitz matrix $xI-A$. So, as long as you know how to evaluate the determinant of a tridiagonal matrix recursively (see this question and its answers for examples), you can deduce a recursive formula.


Why is a circle in a plane surrounded by 6 other circles? When you draw a circle in a plane you can perfectly surround it with 6 other circles of the same radius. This works for any radius. What's the significance of 6? Why not some other numbers?

I'm looking for an answer deeper than "there are $6\times60^\circ=360^\circ$  in a circle, so you can picture it".

The short answer is "because they don't work," but that's kind of a copout.  This is actually quite a deep question.  What you're referring to is sphere packing in two dimensions, specifically the kissing number, and sphere packing is actually quite a sophisticated and active field of mathematical research (in arbitrary dimensions).

Here's one answer, which isn't complete but which tells you why $6$ is a meaningful number in two dimensions.  The packing you refer to is a special type of packing called a lattice packing, which means it comes from an arrangement of regularly spaced points; in this case, the hexagonal lattice.  The number $6$ appears here because the hexagonal lattice has $6$-fold symmetry.  So a natural question might be whether one can find lattices in two dimensions with, say $7$-fold or $8$-fold symmetry, since these might correspond to circle packings with more circles around a given circle.  (Intuitively, we expect more symmetric lattices to give rise to denser packings and to packings where each circle has more neighbors.)

The answer is no: $6$-fold symmetry is the best you can do!  This is a consequence of the crystallographic restriction theorem.  The generalization of the theorem to $n$ dimensions says this: it is possible for a lattice to have $d$-fold symmetry only if $\phi(d) \le n$, where $\phi$ is Euler's totient function.

The generalization implies that you still cannot do better than $6$-fold symmetry in $3$ dimensions.  There are two natural lattice packings in $3$ dimensions, which both occur in molecules and crystals in nature and which both have $6$-fold symmetry, and it turns out that these are the densest sphere packings in $3$ dimensions.  It also turns out that they give the correct kissing number in $3$ dimensions, which is $12$ (see the wiki article).

In $4$ dimensions, the kissing number is $24$, and I believe the corresponding packing is a lattice packing coming from a lattice with $8$-fold symmetry, which is possible in $4$ dimensions.  In higher dimensions, only two other kissing numbers are known: $8$ dimensions, where the $E_8$ lattice gives kissing number $240$, and $24$ dimensions, where the Leech lattice gives kissing number $196560$!  These lattices are really mysterious objects and are related to a host of other mysterious objects in mathematics.

A great reference for this stuff, although it is a little dense, is Conway and Sloane's Sphere Packing, Lattices, and Groups (Wayback Machine).  Edit:  And for a very accessible and engaging introduction to symmetry in the plane and in general, I highly recommend Conway, Burgiel, and Goodman-Strauss's The Symmetries of Things.

Im sorry guys to inform u all that the question itself is wrong... the number of circles surrounding a circle of same radius in a plane tangent to the central circle and tangent to each other is 2pi... ie, 2*3.14 = 6.28 circles....


An infinite dictionary: countably infinite or uncountably infinite? This question concerns Ian Stewart's "Hyperwebster", an uncountable dictionary.

Say a publishing company wants to publish every possible permutation (of any length) of the characters A-Z. The dictionary might look like this:

A, AA, AAA, ..., AB, ABA, ABAA, ..., AC, ..., AZ, AZA, ...
B, BA, BAA, ..., BB, BBA, BBAA, ..., BC, ..., BZ, BZA, ...
C, CA, CAA, ..., CB, CBA, CBAA, ..., CC, ..., CZ, CZA, ...
Z, ZA, ZAA, ..., ZB, ZBA, ZBAA, ..., ZC, ..., ZZ, ZZA, ...

The publishing company realizes that the dictionary can be reorganized into 26 volumes, with each volume corresponding to one of the 26 characters:

Volume A: A, AA, AAA, ..., AB, ABA, ABAA, ..., AC, ..., AZ, AZA, ...
Volume B: B, BA, BAA, ..., BB, BBA, BBAA, ..., BC, ..., BZ, BZA, ...
Volume C: C, CA, CAA, ..., CB, CBA, CBAA, ..., CC, ..., CZ, CZA, ...
Volume Z: Z, ZA, ZAA, ..., ZB, ZBA, ZBAA, ..., ZC, ..., ZZ, ZZA, ...

The company can save some ink by dropping the first letter, since it can be inferred from each of the 26 volumes.

Volume A: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...
Volume B: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...
Volume C: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...
Volume Z: A, AA, AAA, ..., B, BA, BAA, ..., C, ..., Z, ZA, ...

Since each volume is now identical, the company decides to publish only the first volume, which is the same as the list we started with.

In the linked article, the author remarks that this is an analogy of the real line. Can someone explain how this dictionary is uncountably infinite? Is it because of the fact that we can keep repeating the above steps, subdividing our dictionary infinitely many times, each time arriving at a set the same size as the one we started with?

The dictionary is countable (as words have finite length). If there is an analogy with the real line it does not extend to the cardinality.

Try matching the letters with countable infinity.
A, AA, AAA, AAAA, AAAAA...
1, 2,  3,   4,    5...
This will extend to an infinite amount of As using up every countably infinite number.
By the time we get to AB, ABAA, ABAA... we will have already run out of natural numbers because they were all used up in the set of infinite As.
Because we cannot match each word to a corresponding natural number. The amount of words must be unaccountably infinite.


Unusual Vector Spaces Hi I am a 2nd year undergraduate student studying Mathematics. I have been given the following question on an example sheet and I've been trying to figure it out for a while now and I can't get my head around it.

Consider the triple $(V, \oplus, \odot)$. With $V=\Re$, $u \oplus v = u + 2v$ and $\lambda \odot u=\lambda u$ for any $u, v \in V$ and any $\lambda \in \Re$.

The question is, does $V$ form a vector space over $\Re$? Giving a reason.

I think that you have to show that $V$ satisfies the 8 properties of vector spaces. However the definition of $\oplus$ is confusing me.

When I try to prove the Associativity of addition property - $\forall u, v, w \in V (u \oplus v) \oplus w = u \oplus (v \oplus w)$

I am not sure how to deal with the introduction of $w$ (with $w \in V$).

Does $(u \oplus v) \oplus w = (u + 2v) + 2w$
or does $= (u+2v) + w$? Either way, I can't see how this property can be satisfied

Any help will be greatly appreciated.
Many thanks

Hint: The first one is correct. Now what happens when you change the association by moving the grouping symbols to the pair in the other $\oplus$? For associativity to hold, the results must be equal for all choices of $u,v,w$. Is that the case?

You can't see how this property can be satisfied because with this definition, no, it can't be satisfied. You have just proved that this thing fails to be a vector space. That is how you do it.


Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s. Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications"

Let P(n) be the number of strings not containg two containing two consecutive zeros or two consecutive ones.

I got the answer
P(n)=P(n-1)+2P(n-2)+2P(n-3)+...+2P(0) +2

but then the book says the sequence also satisfies the recurrence relation
P(n)=2P(n-1)+P(n-2). I am not able to understand this part.

Let,
$F(n)$=the number of such strings with length $n$.

$Z(n)$=the number of such strings with length $n$ starting with $0$.

$W(n)$=the number of such strings with length $n$ starting with $1$.

$T(n)$=the number of such strings with length $n$ starting with $2$.

So, $F(n)=Z(n)+W(n)+T(n)$ ... (I)

But, we can easily notice that

$Z(n)=T(n-1)+W(n-1)$

$W(n)=T(n-1)+Z(n-1)$

$T(n)=T(n-1)+W(n-1)+Z(n-1)$

Putting them in equation (I), we get

$F(n)$

$= T(n-1)+W(n-1)+T(n-1)+Z(n-1)+T(n-1)+W(n-1)+Z(n-1)$

$= ( T(n-1)+W(n-1)+Z(n-1) ) + ( T(n-1)+W(n-1)+Z(n-1) ) + T(n-1)$

$= 2F(n-1) + T(n-1)$       [ From equation (I) ]

But $T(n-1)$ means you have a $2$ in the second place, which means that you can do anything with the rest of the places, in $F(n-2)$ ways. Therefore,

$F(n) = 2F(n-1) + F(n-2)$


Approximating square roots using binomial expansion. Through the binomial expansion of $(1 - 2x)^\frac{1}{2}$, I am required to find an approximation of $\sqrt2$.

  Binomial expansion

  $ (1 + x)^n = 1 + \frac{n}{1}x + \frac{n(n-1)}{1*2}x^2 + ... $

Thus, the expansion of $(1 - 2x)^\frac{1}{2}$: $$
 = 1 - x -\frac{1}{2}x^2 - \frac{1}{2}x^3 + ... $$

The suggested way, is to choose a value for $x$ so that $(1-2x)$ has the form $2*$'a perfect square'. This can be done by taking $x = 0.01$. Thus, $(1 - 2x)=(1-2*0.01) = 0.98 = 2*0.7^2$

And
$$
(1 - 2x)^\frac{1}{2} = 0.98^\frac{1}{2} = 0.7\sqrt2$$
Which is equal to the previously established expansion, so we can now go ahead and find $\sqrt2$. The problem I am facing, is that there was no mention of how the value of $x=0.01$ was arrived at.

Is there an easy way to determine an appropriate value for $x$?

Personally, I wouldn't have done it that way.  So here is how I would've done it:

Method 1:

$$\sqrt2=\sqrt{1+1}=1+\frac12-\frac18+\dots\approx1+\frac12-\frac18=\frac{11}8=1.375$$

which is much clearer to me, since it avoids having to take decimals raised to powers and gives you something you can easily do by hand.

$$1.375^2=1.890625$$

Obviously it approaches the correct value as you take more terms.

Method 2:

This is called fixed-point iteration/Newton's method, and it basically goes like this:

$$x=\sqrt2\implies x^2=2$$

$$2x^2=2+x^2$$

Divide both sides by $2x$ and we get

$$x=\frac{2+x^2}{2x}$$

Now, interestingly, I'm going to call the $x$'s on the left $x_{n+1}$ and the $x$'s on the right $x_n$, so

$$x_{n+1}=\frac{2+(x_n)^2}{2x_n}$$

and with $x_0\approx\sqrt2$, we will then have $x=\lim_{n\to\infty}x_n$.  For example, with $x_0=1$,

$x_0=1$

$x_1=\frac{2+1^2}{2(1)}=\frac32=1.5$

$x_2=\frac{2+(3/2)^2}{2(3/2)}=\frac{17}{12}=1.41666\dots$

$x_3=\dots=\frac{577}{408}=1.414215686$

And one can quickly check that $(x_3)^2=2.000006007\dots$, which is pretty much the square root of $2$.

In fact you can take any two numbers which can be added to get 2 (not nesserly 0.01 but at least you should know the root of one of them

So for example $\sqrt{2} = {(1+1)^{1/2}}$

Know all what you need is to expand it using bio theorem and for 2 terms you ll get 1.5

$1+(0.5)\cdot 1= 1.5 $
Which is not too bad approximation for $\sqrt{2} = 1.4142135624 $


Apparently sometimes $1/2 < 1/4$? My son brought this home today from his 3rd-grade class. It is from an official Montgomery County, Maryland mathematics assessment test:

True or false? $1/2$ is always greater than $1/4$.

Official answer: false

Where has he gone wrong?

Addendum, at the risk of making the post no longer appropriate for this forum:

Questions about context are fair. This seems to have been a one-page (front and back) assessment. Here is the front, notice the date and title:

Based on the title, it seems to me that this is an assessment about the number line in which case my son's picture and written proof are inappropriate and better would have been to locate $1/2$ and $1/4$ on the line and state something like "No matter how many times you check, 1/2 is always to the right of 1/4." However, based on the teacher's response it seems the class has entered into a quagmire and is mixing up numbers with portions.

Simply put this is a travesty. The question asks, what appears to be a simple question about two real numbers, $\frac{1}{2},\frac{1}{4} \in \mathbb{R}.$ In particular, it appears to ask if $\frac{1}{2}>\frac{1}{4}.$ The answer to this question is clearly, under normal construction and ordering of the reals, a resounding YES.

What the question meant to ask is a question about fractions of potentially different quantities. In particular, from the teachers drawing, the question meant to ask if $$\frac{1}{2}\cdot x>\frac{1}{4}\cdot y, \qquad \forall x,y \in \mathbb{R}.$$ The answer to this is again, very obviously no, but this is not what the question asked...

Possibly another way to refute the counterexample given, is to reduce it to a statement that's more clearly untrue. Suppose $\frac{1}{2} < \frac{1}{4}$. Then, multiply both sides by 4 to get $2 < 1$, which is more clearly false.

So at this point point, the teacher either has to say that the multiplication doesn't preserve the inequality, or (less likely) that the resulting statement is false.

(Though I wouldn't be surprised if they try to refute modus ponens, or the law of the excluded middle, or so on)


Expected number of steps I play a game as follows. A bucket contains four red balls and three green balls. At each step, a ball is chosen at random from the bucket, with each of the balls there being equally likely to be chosen. If a red ball is chosen, it is removed from the bucket. If a green ball is chosen, it is returned to the bucket. The game continues until all of the four red balls have been removed from the bucket. What is the expected number of steps before the game ends?

What is the expected number of steps needed for hitting a red ball for the first time? After that you somehow start over with $4-1=3$ red balls and $3$ green balls. Then ask the same question (and repeat that).

Start by drawing a directed weighted graph with the probability of each outcome. For instance, at the first step you have two possible events, R and G, such that P(R) = 4/7 and P(G) = 3/7. If you get G, you're back to square one, hence G points back at the beginning. Instead, if you get R, you move further to the second bifurcation, and so on. Something like this:

Now you can work out a formula for the expected number of steps t:

$$
t = \frac{3}{7}(1+t) + \frac{4}{7}\left ( \frac{1}{2}(1+(t-1)) +\frac{1}{2}\left ( \frac{3}{5}(1+(t-2)) +\frac{2}{5}\left(\frac{3}{4}(1+(t-3))+\frac{1}{4}(4)\right) \right ) \right )
$$

The last "4" in the formula refers to the probability that the game ends in exactly 4 turns.

Solving for t, you get an expected value of 7.


What does "open set" mean in the concept of a topology? Given the following definition of topology, I am confused about the concept of "open sets".

2.2 Topological Space. We use some of the properties of open sets in the case of metric spaces in order to define what is meant in general by a class of open sets and by a topology.
Definition 2.2. Let $X$ be a nonempty set. A topology $\mathcal{T}$ for $X$ is a collection of subsets of $X$ such that $\emptyset,X\in\mathcal{T}$, and $\mathcal{T}$ is closed under arbitrary unions and finite intersections.
    We say $(X,\mathcal{T})$ is a topological space. Members of $\mathcal{T}$ are called open sets.
    If $x\in X$ then a neighbourhood of $x$ is an open set containing $x$.

It seems to me that the definition of an open subset is that subset $A$ of a metric space $X$ is called open if for every point $x \in A$ there exists $r>0$ such that $B_r(x)\subseteq A$. What is the difference of being open in a metric space and being open in a topological space?
Thanks so much.

In an abstract topological space, "open set" has no definition!

You simply decide (as part of making your topological space) which sets you want to call open -- those are the sets you put into $\mathcal T$. Whatever you decide to call open will be called open, as long as your decision meets the condition "$\emptyset, X\in\mathcal T$ and $\mathcal T$ is closed under arbitrary unions and finite intersections".

A metric space becomes a topological space by deciding that the "open sets" in this particular topological space are going to be exactly the ones that are open according to the metric-space definition.

Short answer: It's a generalization of the concept of an open interval on the real line to arbitrary spaces.

You'll see statements that the concept of 'open set' has no special meaning. That's only true in the most abstract sense. Really, it's just a convention.

Point-set topology is usually developed from the concept of 'open set' where a topology is defined by defining what its open sets are, and the topology's properties develop from that. (A metric space, of course, defines its open sets from the metric.)

However, the Kuratowski closure theorems show that we can just as easily start by defining the closed sets. It doesn't gain us anything but it's interesting to know as we go along with convention and proceed by defining the open sets first.

Topology developed as a way to understand problems of real analysis, and of course we always try relate any abstract concept of topology back to the Euclidean topology $E^n$ of $\mathbb{R}^n$ (sometimes called the 'usual topology' to emphasize the abstraction).

What are the open sets in $E$? Collections of open intervals. Everything else proceeds from that.