Dynamic Programming Recursive Algorithm - Series of coin tosses I have this programming prompt where I have been asked to find the number of permutations of a 32 coin toss sequence that do not have three consecutive heads in a row.

I have been tasked to find this with dynamic programming and I am having a hell of a time trying to figure out the recursive algorithm.

I have tried a two variable approach where I try and keep track of whether the previous two flips were heads or tails and then incrementing based upon that. I have also tried breaking it into sub-problems where I start with a singular toss and then work my way up the full 32 tosses.

And I'm having a hard time visualizing how to approach this and figuring out how to keep track of everything as the algorithm commences.

Any help would be greatly appreciated.

Let $x(n)$ be the number of $n$-terms sequences of heads and tails, avoiding three consecutive heads.

The goal is to compute $x(32)$ via dynamic programming.

I'll do it in two different ways . . .

Method $(1)$:$\;1$-variable recursion.

By direct calculation,
$$x(0)=1,\;\;x(1)=2,\;\;x(2)=4$$
and for $n \ge 3$, we get
$$x(n)=x(n-1)+x(n-2)+x(n-3)$$
Explanation:

Call a sequence of heads and tails "qualifying" if it avoids three consecutive heads.

Assuming $n \ge 3$, an $n$-term sequence of heads and tails is qualifying if and only if it has one of the forms
\begin{align*}
&Ts'\\[4pt]
&HTs''\\[4pt]
&HHTs'''\\[4pt]
\end{align*}
where $s',s'',s'''$ are qualifying sequences of lengths $n-1,n-2,n-3$, respectively.

Based on the above recursion, we get the following dynamic program, expressed as pseudocode . . .

function x(n):
    if n \le 2, return 2^n
    a,b,c= 1,2,4
    i = 0
    loop begin
        d=a+b+c
        i = i + 1
        if i = n then break
        a,b,c=b,c,d
    loop end
    return d
end function

Method $(2)$:$\;2$-variable recursion.

We have $x(n) = f(0,n)$, where $f(h,n)$ is the number of qualifying $n$-term sequences, assuming $h$ consecutive heads are already in progress.

Then $f(h,n)$ satisfies the recursion
\begin{align*}
&\text{if}\;h \ge 3,\;\text{then}\\[4pt]
&\;\;\;\;f(h,n) = 0\\[4pt]
&\text{else if}\;n = 0,\;\text{then}\\[4pt]
&\;\;\;\;f(h,n) = 1\\[4pt]
&\text{else}\\[4pt]
&\;\;\;\;f(h,n) = f(0,n-1)+f(h+1,n-1)\\[4pt]
&\text{end if}\\[4pt]
\end{align*}
Explanation:

If there are $3$ consecutive heads in progress, there are no qualifying sequences.$\\[4pt]$
Else if there are no tosses remaining, the empty sequence qualifies.$\\[4pt]$
Else a tail resets $h$ to zero, a head increases $h$ by $1$, and either way, $n$ decreases by $1$.$\\[4pt]$

Based on the above recursion, we get the following dynamic program, expressed as pseudocode . . .

function x(n):
    if n = 0, return 1
    a0,a1,a2 = 1,1,1
    i = 0
    loop begin
        b0 = a0 + a1
        b1 = a0 + a2
        b2 = a0
        i = i + 1
        if i = n then break
        a0,a1,a2 = b0,b1,b2
    loop end
    return b0
end function

With either of the two methods, we get $x(32) = 334745777$.

I asked my calculus professor this questions and he said it can be solved using a geometric series.  So in a handful of lines of code.  The answer he gave me was still roughly 4.1 billion possibilities where you do not have heads 3 times.  The series simplified to this:
2^32 - 2^28 + 1
Any thoughts?


Can a rational Bézier curve take exactly the same shape as a part of the sine function? I'm wondering whether a rational Bézier curve could take exactly the same shape as a part of the sine function. The best way to check this seems like this:

Find a part of the sine function such that there is no symmetry anymore in this part, e.g. from $\sin(0)$ to $\sin({\pi \over 2})$.
In that case, the control points for a quadratic Bézier curve follow from the sine function. Because a Bézier curve is tangent to the control polygon at the first and last points, this results in the points $(0,0)$, $(1,1)$ and $({\pi \over 2}, 1)$. The second point $(1,1)$ is the intersection of the two tangent lines.

When plotting the above:

Which is pretty close, but I'm looking for an exact representation (if possible). Therefore, the next step is to look to a rational Bézier curve:

In this case I used the weights [1, 1.4, 1]. It is now a very close approximation for this part of the sine function, but it is not exact.

What would be a systematic way to do this? And if it fails for a quadratic rational Bézier curve, could it work for a cubic, quartic, quintic, ... curve?

I don't think it would be meaningful to look into Uniform Rational B-Splines (or Non-Uniform ones, NURBS) since they are just piecewise rational Bézier curves, right?

In a Bézier curve, $x$ and $y$ are polynomials in the parameter $t$. Note that you can't just have "a part of the sine function": if $y(t) = \sin(x(t))$ for $t$ in some interval, since both sides of that equation are analytic functions on the complex plane the equation would be true for all complex numbers $t$. Since $y(t)$ is a polynomial, for any given value of $y$ (unless $y$ is constant) there are only finitely many $t$ and thus finitely many $x$.  But this is not the case for the sine function: $\sin(n \pi) = 0$ for all integers $n$.  So the sine curve can't be given exactly by a  Bézier curve of any degree.

Since a Bezier curve has only finitely many nonzero derivatives and a sine has infinitely many, they can not coincide on any interval in their domains containing more than one point.


Is every matrix in $F[x]^{n\times n}$ is row-equivalent to an upper-triangular matrix? I'm trying to solve this problem, but I don't have any idea of what I should do..

  True or false? Every matrix in $F[x]^{n\times n}$ is row-equivalent to an upper-triangular matrix.

This is a question in the section 7.4 of the book of linear algebra of Hoffman-Kunze.

See carefully the proof of Theorem 6. Do the same thing, then we get an upper triangular matrix which is row-equivalent to the original matrix.
(Only different thing is that we do not assume (ii), so the entries of the main diagonal may not be 1.)

I think I have an counter example; we know that $M_{3 \times 3}(\mathbb{R})\subseteq F[x]^{3 \times 3}$. The matrix:

$$ \left[
  \begin{array}{ c c c}
     0 & 0 & -1 \\
     1 & 0 & -3 \\
     0 & 1 & -8
  \end{array} \right]
$$

Because it's minimal polynomial is $x^3+8x^2+3x+1$, whose companion matrix is not row-equivalent to an upper-triangular matrix. is this right?


Switching the order of differential operators A function $f(x,y)$ is transformed to variables $(u,v)$ with $x=uv$ and $y=\dfrac{u}{v}$ so the first partial derivative with respect to $u$ is $$\frac{\partial f}{\partial u}=v\frac{\partial f}{\partial x}+\frac1v\frac{\partial f}{\partial y}\tag{1}$$ Show that the second partial derivative with respect to $u$ can be written as $$\frac{\partial^2 f}{\partial u^2}=v\left[v\frac{\partial^2 f}{\partial x^2}+\frac{1}{v}\frac{\partial^2 f}{\partial x \,\partial y}\right]+\frac{1}{v}\left[v\frac{\partial^2 f}{\partial y \,\partial x}+\frac{1}{v}\frac{\partial^2 f}{\partial y^2}\right]$$

My working:

\begin{align*}\frac{\partial^2 f}{\partial u^2}&=\frac{\partial}{\partial u}\frac{\partial f}{\partial u}\\&=\frac{\partial}{\partial u}\left(v\frac{\partial f}{\partial x}+\frac1v\frac{\partial f}{\partial y}\right)\,\qquad\text{By substituting equation (1)}\\&=\fbox{$v\frac{\partial}{\color{red}{\partial u}}\frac{\partial f}{\color{blue}{\partial x}}+\frac1v\frac{\partial}{\color{red}{\partial u}}\frac{\partial f}{\color{blue}{\partial y}}$}\qquad\text{Distributed then changed order of operators}\\&=\fbox{${v\frac{\partial}{\color{blue}{\partial x}}\frac{\partial f}{\color{red}{\partial u}}+\frac1v\frac{\partial}{\color{blue}{\partial y}}\frac{\partial f}{\color{red}{\partial u}}}$}\,\qquad{\text{Switched the order of the denominators}}\\&=v\frac{\partial}{\partial x}\left(v\frac{\partial f}{\partial x}+\frac1v\frac{\partial f}{\partial y}\right)+\frac1v\frac{\partial}{\partial y}\left(v\frac{\partial f}{\partial x}+\frac1v\frac{\partial f}{\partial y}\right)\\&=v\left[v\frac{\partial^2 f}{\partial x^2}+\frac{1}{v}\frac{\partial^2 f}{\partial x \,\partial y}\right]+\frac{1}{v}\left[v\frac{\partial^2 f}{\partial y \,\partial x}+\frac{1}{v}\frac{\partial^2 f}{\partial y^2}\right]\end{align*}$\fbox{}$

I am asking this question because I know that differential operators in general do not commute. But I cannot find a way to solve the problem without switching the order of the operators.

Therefore my doubt is whether or not the boxed expressions are valid.

I did manage to reach the desired result, but is the proof correct?

I think that this proof is wrong but I am unable to find a correct proof.

Could someone please either explain or give hints on what the correct proof should look like or point out and explain my errors?

Many thanks.

Here we look at first at the general situation and develop the second partial derivative by consequently applying the chain rule. This way we can better see  symmetries which is helpful when calculating the special case.

  We consider the functions

  \begin{align*}
x&=x(u,v)=u\cdot    v\\
y&=y(u,v)=\frac{u}{v}\qquad&\text{and}\quad\qquad
f=f(x,y)=f(x(u,v),y(u,v))
\end{align*}

First partial derivative:$\quad\frac{\partial f}{\partial u}$

  We obtain by applying the chain rule
  \begin{align*}
\frac{\partial f}{\partial u}=\frac{\partial f}{\partial x}\cdot\frac{\partial x}{\partial u}
+\frac{\partial f}{\partial y}\cdot \frac{\partial y}{\partial u}\tag{1}
\end{align*}

Second partial derivative:$\quad\frac{\partial^2 f}{\partial u^2}$

  We obtain by applying $\frac{\partial}{\partial u}$ to (1) using the chain rule again as well as the product rule of derivatives
  \begin{align*}
\frac{\partial^2 f}{\partial u^2}
&=\frac{\partial }{\partial u}
\left(\frac{\partial f}{\partial x}\cdot\frac{\partial x}{\partial u}
+\frac{\partial f}{\partial y}\cdot \frac{\partial y}{\partial u}\right)\tag{2}\\
&=\frac{\partial }{\partial u}
\left(\frac{\partial f}{\partial x}\cdot\frac{\partial x}{\partial u}\right)
+\frac{\partial }{\partial u}\left(\frac{\partial f}{\partial y}\cdot \frac{\partial y}{\partial u}\right)\tag{3}\\
&=\frac{\partial }{\partial u}\color{red}{\left(\frac{\partial f}{\partial x}\right)}\cdot\frac{\partial x}{\partial u}
+\frac{\partial f}{\partial x}\cdot\frac{\partial }{\partial u}\left(\frac{\partial x}{\partial u}\right)\\
&\qquad+\frac{\partial }{\partial u}\color{blue}{\left(\frac{\partial f}{\partial y}\right)}\cdot\frac{\partial y}{\partial u}
+\frac{\partial f}{\partial y}\cdot\frac{\partial }{\partial u}\left(\frac{\partial y}{\partial u}\right)\tag{4}\\
&=\left(\frac{\partial^2 f}{\partial x^2}\cdot\frac{\partial x}{\partial u}
+\frac{\partial^2 f}{\partial y\partial x}\cdot \frac{\partial y}{\partial u}\right)\cdot\frac{\partial x}{\partial u}
+\frac{\partial f}{\partial x}\cdot\frac{\partial^2 x}{\partial u^2}\\
&\qquad+\left(\frac{\partial^2 f}{\partial x\partial y}\cdot\frac{\partial x}{\partial u}
+\frac{\partial^2 f}{\partial y^2}\cdot \frac{\partial y}{\partial u}\right)\cdot\frac{\partial y}{\partial u}
+\frac{\partial f}{\partial y}\cdot\frac{\partial^2 y}{\partial u^2}\tag{5}\\
&=\frac{\partial^2 f}{\partial x^2}\cdot\left(\frac{\partial x}{\partial u}\right)^2
+\frac{\partial^2 f}{\partial y\partial x}\cdot \frac{\partial x}{\partial u}\cdot\frac{\partial y}{\partial u}
+\frac{\partial f}{\partial x}\cdot\frac{\partial^2 x}{\partial u^2}\\
&\qquad\frac{\partial^2 f}{\partial y^2}\cdot \left(\frac{\partial y}{\partial u}\right)^2
+\frac{\partial^2 f}{\partial x\partial y}\cdot\frac{\partial x}{\partial u}
\cdot\frac{\partial y}{\partial u}
+\frac{\partial f}{\partial y}\cdot\frac{\partial^2 y}{\partial u^2}\tag{6}
\end{align*}

Comment: This is for presentation issues a rather lengthy calculation. Usually we would skip (3) and (4) and obtain (5) directly from (2).

In (2) we apply the chain rule as we did in (1)
In (3) we use the linearity of the differential operator
In (4) we apply  the product rule
In (5) we apply the chain rule again
In (6) we multiply out and do a few rearrangements

  Special case: $x(u,v)=u\cdot v, y(u,v)=\frac{u}{v}$

  The partial derivatives of the special case give
  \begin{align*}
&x(u,v)=u\cdot v&&\frac{\partial}{\partial u}x(u,v)=v&&\frac{\partial^2}{\partial u^2}x(u,v)=0\\
&y(u,v)=\frac{u}{v}&&\frac{\partial}{\partial u}y(u,v)=\frac{1}{v}&&\frac{\partial^2}{\partial u^2}y(u,v)=0
\end{align*}

  Putting these results in (6) we finally obtain
  \begin{align*}
\frac{\partial^2 }{\partial u^2}&f(x(u,v),y(u,v))=\frac{\partial^2 }{\partial u^2}f(u\cdot v,\frac{u}{v})\\
&=\frac{\partial^2 f}{\partial x^2}\cdot v^2
+\frac{\partial^2 f}{\partial y\partial x}\cdot v\cdot\frac{1}{v}
+\frac{\partial f}{\partial x}\cdot 0\\
&\qquad\frac{\partial^2 f}{\partial y^2}\cdot \frac{1}{v^2}
+\frac{\partial^2 f}{\partial x\partial y}\cdot v
\cdot\frac{1}{v}
+\frac{\partial f}{\partial y}\cdot0\\
&=v^2\cdot\frac{\partial^2 f}{\partial x^2}
+\frac{\partial^2 f}{\partial y\partial x}+\frac{\partial^2 f}{\partial x\partial y}
+\frac{1}{v^2}\cdot\frac{\partial^2 f}{\partial y^2}\tag{7}
\end{align*}

  according to OPs formula.

$$ $$

  [Add-on 2016-10-24]: According to OPs comment some more details regarding (4) and (5).

  We consider bivariate functions

  \begin{align*}
x&=x(u,v)\\
y&=y(u,v)\qquad&\text{and}\quad\qquad
g=g(x,y)=g(x(u,v),y(u,v))
\end{align*}

  which are sufficiently often differentiable in both variables. The following is valid according to (1)

  \begin{align*}
\frac{\partial }{\partial u}g(x(u,v),y(u,v))
=\frac{\partial }{\partial x}g(x,y)\cdot\frac{\partial }{\partial u}x(u,v)
+\frac{\partial }{\partial y}g(x,y)\cdot\frac{\partial }{\partial u}y(u,v)\tag{8}
\end{align*}

$$ $$

  Setting $g=f$ we obtain from (8)

  \begin{align*}
\frac{\partial }{\partial u}f(u(x,y),v(x,y))
=\frac{\partial }{\partial x}f(x,y)\cdot\frac{\partial }{\partial u}x(u,v)
+\frac{\partial }{\partial y}f(x,y)\cdot\frac{\partial }{\partial u}y(u,v)
\end{align*}

  or using a more compact notation

  \begin{align*}
\frac{\partial f}{\partial u}
=\frac{\partial f}{\partial x}\cdot\frac{\partial x}{\partial u}
+\frac{\partial f}{\partial y}\cdot\frac{\partial y}{\partial u}
\end{align*}

  which corresponds to (1).

$$ $$

  Setting $g=\frac{\partial }{\partial x}f$ we obtain from (8)

  \begin{align*}
\frac{\partial }{\partial u}\left(\frac{\partial }{\partial x}f(u(x,y),v(x,y))\right)
&=\frac{\partial }{\partial x}\left(\frac{\partial }{\partial x}f(x,y)\right)\cdot\frac{\partial }{\partial u}x(u,v)\\
&\qquad+\frac{\partial }{\partial y}\left(\frac{\partial }{\partial x}f(x,y)\right)\cdot\frac{\partial }{\partial u}y(u,v)
\end{align*}

  or using a more compact notation

  \begin{align*}
\frac{\partial}{\partial u}\left(\frac{\partial f}{\partial x}\right)
=\frac{\partial^2 f}{\partial x^2}\cdot\frac{\partial x}{\partial u}
+\frac{\partial^2 f}{\partial y\partial x}\cdot\frac{\partial y}{\partial u}
\end{align*}

  which corresponds to (5).

Basically, you are asking whether
\begin{align}
\left[\frac{\partial}{\partial u}, \frac{\partial}{\partial x} \right]=0
\end{align}
where
\begin{align}
\frac{\partial}{\partial u } = \sqrt{\frac{x}{y}}\frac{\partial}{\partial x} + \sqrt{\frac{y}{x}}\frac{\partial}{\partial y}.
\end{align}
Observe
\begin{align}
\frac{\partial }{\partial u}\frac{\partial}{\partial x} = \sqrt{\frac{x}{y}}\frac{\partial^2}{\partial x^2} + \sqrt{\frac{y}{x}}\frac{\partial^2}{\partial y \partial x}
\end{align}
but
\begin{align}
\frac{\partial }{\partial x}\frac{\partial}{\partial u}=&\  \frac{\partial}{\partial x}\left( \sqrt{\frac{x}{y}}\frac{\partial}{\partial x} + \sqrt{\frac{y}{x}}\frac{\partial}{\partial y}\right)\\
=&\ \frac{1}{2\sqrt{xy}}\frac{\partial}{\partial x} -\frac{1}{2} \sqrt{\frac{y}{x^3}}\frac{\partial}{\partial y}+\sqrt{\frac{x}{y}}\frac{\partial^2}{\partial x^2} + \sqrt{\frac{y}{x}}\frac{\partial^2}{\partial y \partial x}.
\end{align}
Hence
\begin{align}
\left[\frac{\partial}{\partial u}, \frac{\partial}{\partial x} \right]\neq 0.
\end{align}

However, as an exercise, you should still check whether the two boxed quantities are equivalent since cancellation is possible.


Is the any math function that change the power of denominator of an input fraction? I'm seeking for a function that gets a fraction as input and change its denominator power in the log function like follow:

$f(\frac{a}{b}) = log(\frac{a}{b^k})$

Is it possible to find a function like f?

p.s: The input of function is not a and b, it's $\frac{a}{b}$ and I need the definition of function, like $f(r) = r^2$.

You can define a function as follows.  Let $f(a/b) := \log(a/b^2)$ where $a$ and $b$ are relatively prime positive integers.  The function $f$ "maps" positive rational numbers (i.e. fractions) to real numbers.  Note that $f$ is not smooth or continuous.

Many functions (taking $a$ and $b$ as inputs) can be manufactured. How about $$f(a,b) = log(\frac{a}{b})+ \sum_{n=1}^{k-1}log(\frac{1}{b})$$


Conditional Expected Value $E[(X-Y)^2] < \infty $ Given

$E[|X|]<\infty$, $E[|Y|]<\infty$, $E[X|\sigma(Y)]=Y$, $E[Y|\sigma(X)]=X$,

I need to show that out of $E[X^2]<\infty$ and $E[Y^2]<\infty$ follows also $E[(X-Y)^2]<\infty$.

I started with using the linearity of the expected value to my advantage like this:

$E[(X-Y)^2]=E[X^2-2XY+Y^2]=E[X^2]+E[Y^2]-2E[XY]$

Here is where I'm getting stuck. I know the first two terms are smaller than infinity, but how do I show that $2E[XY]<\infty$?

I also thought of using the formula for conditional expected value and replacing the $Y$ in $2E[XY]$ with $E[X|\sigma(Y)]$ but I'm struggling with continuing.

Can anyone help me with the proof or at least give some hint?

By tower property,
$E[XY]=E[E[XY|Y]]=E[YE[X|Y]]=E[Y^2]$

You can also use Cauchy-Schwarz inequality.


CLT for random variables with varying distributions The following is not a homework problem. Here it is:

Suppose $\{X_k\}_{k=1}^{\infty}$ is a sequence of independent random variables such that
$$
P(X_k=1)=P(X_k=-1)=\frac{1}{2}-\frac{1}{2k^2}
$$

$$
P(X_k=k)=P(X_k=-k)=\frac{1}{2k^2}.
$$
Find the limiting distribution of $\frac{1}{\sqrt{n}} \sum\limits_{k=1}^n X_k$.

Now, I am guessing that the given probabilities are for $k\geq 2$, since $k=1$ would yield an inconsistent definition. Furthermore, I am assuming the case $k=1$ corresponds to only the second line.

The first sign of trouble comes from the fact that these random variables are not identically distributed (otherwise, we could just use CLT). One thing I noticed is that $\mathbb{E}(X_k)=0$ for each $k$. Also, it appears as though the limit of the sequence is a random variable $X$ with $P(X=1)=P(X=-1)=\frac{1}{2} \hspace{2mm}$  (not that this result is necessarily of much help).

I'd very much appreciate any suggestions on how to approach this problem. Thanks!

Let $Y_k=\mathrm{sgn}(X_k)$, then $(Y_k)$ is a centered i.i.d. Bernoulli sequence hence, by the most usual CLT, $T_n=\frac1{\sqrt{n}}\sum\limits_{k=1}^nY_k$ converges in distribution to a standard normal random variable $T$. By Borel-Cantelli lemma, the random set $\{n\geqslant1\mid X_n\ne Y_n\}$ is almost surely finite hence there exists some almost surely finite random variable $Z$ such that $\left|\sum\limits_{k=1}^nX_k-\sum\limits_{k=1}^nY_k\right|\leqslant Z$ for every $n$. In particular $R_n-T_n\to0$ almost surely, where $R_n=\frac1{\sqrt{n}}\sum\limits_{k=1}^nX_k$.

Now it is a general fact that if $T_n\to T$ in distribution and if $R_n-T_n\to0$ almost surely then $R_n\to T$ in distribution. Thus, CLT holds for $(X_n)$ as well.

Suppose $\{X_k\}_{k=1}^{\infty}$ is a sequence of independent random
variables such that $$ P(X_k=1)=P(X_k=-1)=\frac{1}{2}-\frac{1}{2k^2}
$$

$$ P(X_k=k)=P(X_k=-k)=\frac{1}{2k^2}. $$ Find the limiting distribution of $\frac{1}{\sqrt{n}} \sum\limits_{k=1}^n X_k$.
The characteristic function of $X_k$ is
$$\phi_k(\xi)=(\frac{1}{2}-\frac{1}{2k^2})e^{i\xi}+(\frac{1}{2}-\frac{1}{2k^2})e^{-i\xi}+\frac{1}{2k^2}e^{ik\xi}+\frac{1}{2k^2}e^{-ik\xi}$$
$$=(1-\frac{1}{k^2})\cos \xi +\frac{1}{k^2}\cos k\xi = \cos \xi +\frac{1}{k^2}(\cos k\xi-\cos\xi)$$
Then the characteristic function of $X_k/\sqrt{n}$ is
$$Ee^{i\xi X_k/\sqrt{n}}=\cos \frac{\xi}{\sqrt{n}} +\frac{1}{k^2}(\cos \frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}})$$
and
$$Ee^{i\xi(\sum_{k=1}^n X_k)/\sqrt{n}}=\prod_{k=1}^n\left(\cos \frac{\xi}{\sqrt{n}} +\frac{1}{k^2}(\cos \frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}})\right)$$
$$=\exp\left[\log \sum_{k=1}^n\left(1-(1-\cos \frac{\xi}{\sqrt{n}} -\frac{1}{k^2}(\cos
\frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}}))\right)\right]$$
Then
$$\log \sum_{k=1}^n\left(1-(1-\cos \frac{\xi}{\sqrt{n}} -\frac{1}{k^2}(\cos
\frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}}))\right)$$
$$\sim -\sum_{k=1}^n(1-\cos \frac{\xi}{\sqrt{n}}-\frac{1}{k^2}(\cos \frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}}))$$
$$\sim -\sum_{k=1}^n(1-\cos \frac{\xi}{\sqrt{n}})+\sum_{k=1}^n\frac{1}{k^2}(\cos \frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}})=S_1+S_2$$
For $S_1$ we have
$$S_1=-n(1-\cos\frac{\xi}{\sqrt{n}})=-2n
\sin^2\frac{\xi}{\sqrt{n}}=-2n\frac{\sin^2\frac{\xi}{\sqrt{n}}}{\frac{\xi^2}{n}}\times\frac{\xi^2}{n}
\to -2\xi^2 , \ \ n \to \infty.$$
$$S_2=\sum_{k=1}^n\frac{1}{k^2}(\cos
\frac{k\xi}{\sqrt{n}}-\cos\frac{\xi}{\sqrt{n}})=-2\sum_{k=1}^n\frac{1}{k^2}\sin\frac{(k+1)\xi}{2\sqrt{n}}\sin\frac{(k-1)\xi}{2\sqrt{n}}$$
$$=-2\sum_{k=1}^n\frac{1}{k^2}\frac{(k^2-1)\xi^2}{n}\frac{\sin\frac{(k+1)\xi}{2\sqrt{n}}}{\frac{(k+1)\xi}{2\sqrt{n}}}\frac{\sin\frac{(k-1)\xi}{2\sqrt{n}}}{\frac{(k-1)\xi}{2\sqrt{n}} }$$
$$=-2\sum_{k=1}^n\frac{\xi^2}{n}\frac{\sin\frac{(k+1)\xi}{2\sqrt{n}}}{\frac{(k+1)\xi}{2\sqrt{n}}}\frac{\sin\frac{(k-1)\xi}{2\sqrt{n}}}{\frac{(k-1)\xi}{2\sqrt{n}} }+
2\sum_{k=1}^n\frac{1}{k^2}\frac{\xi^2}{n}\frac{\sin\frac{(k+1)\xi}{2\sqrt{n}}}{\frac{(k+1)\xi}{2\sqrt{n}}}\frac{\sin\frac{(k-1)\xi}{2\sqrt{n}}}{\frac{(k-1)\xi}{2\sqrt{n}} }$$
$$=S_{21}+S_{22}.$$

Now it is clear that $S_{21} \to -2\xi^2$ and $S_{22} \to 0$ as $n \to \infty$.
Therefore
$$Ee^{i\xi(\sum_{k=1}^n X_k)/\sqrt{n}} \to e^{-4\xi^2}, \ \ n \to \infty.$$
This is the characteristic function of r.v. $X=2Z \sim N(0,4)$.


Help understanding how to factor completely $x^3-x^2-x+1$ I need someone to help explain the steps to completely factor the problem $x^3-x^2-x+1$.

Here is what I have done so far:

  $x^3-x^2-x+1$

  to

  $x^3-x^2+-1(x+1)$

  Since there is a negative I changed $-x+1$ to $-1(x+1)$

  to

  $x^2(x-1)+-1(x+1)$

  to

  $(x^2-1)(x-1)(x+1)$.

Is this correct? If not please explain what I did wrong and what I should do. If it is then thank you for saying so, if not, thank you for helping me to understand.


$.99999...=1$: What is the proof that we can multiply an infinite series by something to shift it? I wanted to prove to myself that $.9999... = 1$ so I wanted to show that:

$N = 9/10 + 9/100 + 9/1000 + 9/100000 + ...$

or more formally, $N = 9S$ where

$S = \sum_{k=1}^{\infty} \frac{1}{10^k}$

Then multplying by $10$ I get

$10S = \sum_{k=1}^{\infty} \frac{1}{10^{k-1}} = \sum_{k=0}^{\infty} \frac{1}{10^{k}}$

Subtracting I get

$10S - S = \sum_{k=0}^{\infty} \frac{1}{10^k} -  \sum_{k=1}^{\infty} \frac{1}{10^{k}} = \frac{1}{10^0} = 1$

So if $9S = 1$, then $S = 1/9$, and $N = 9S = 1$, proof completed.

Is this proof correct?
What is it exactly that allows me to multiply an infinite series by $10$ and have it be a valid transformation? To my "ignorant intuition" this seems like taking something infinite and making it $10$ times infinity, which I don't know what that really means.
What is it that allows me to shift indexes like I did to move $k$ down from $1$ to $0$? Similar to question 2 above. We shift and yet do not have to touch or manipulate the upper bound of infinity at all. I know that "infinity minus one" is sort of a weird notion but I don't understand what it means or why we can default it back to infinity, whereas in any other context when we change bounds we change them on both lower and upper.

The manipulations you did are valid for convergent series. Therefore your proof is incomplete because you didn't prove that the series is actually convergent.

Fortunately the convergence in this case is easy to show: The sequence of partial sums is strictly increasing (all terms of the series are positive), and each of the terms of that sequence is less than $1$. A strictly increasing sequence that is bound from above converges.

Here's a proof that shows that the partial sums are bounded by $1$ without knowledge of the result, by virtue of manipulations analogue to the manipulations you did in the infinite series:

  Be $s_n = \sum_{k=1}^n \frac{9}{10^k}$ the $n$-th partial sum. Clearly, $s_1=\frac{9}{10}<1$. Furthermore, it is easy to check that $s_{n+1} = (s_n + 9)/10$, thus if $s_n<1$ then $s_{n+1} < (1+9)/10 = 1$. Therefore by induction, all $s_n<1$.

To see why establishing convergence is important, consider the following series:
$$S = 1 + 1 + 1 + 1 + \ldots$$
Obviously,
$$S = 0 + S = 0 + 1 + 1 + 1 + \ldots$$
But then,
\begin{aligned}
0 &= S - S\\
  &= (1-0) + (1-1) + (1-1) + (1-1) + \ldots\\
  &= 1 + 0 + 0 + 0 + \ldots\\
  &= 1
\end{aligned}

So why can you multiply the terms of the series by $10$ (or actually any number $c$) and get $10$ times the result?

Well, the usual definition of convergence of a series is as follows:

  $\sum_{k=0}^{\infty} a_k = a$ if for every $\epsilon > 0$ you can find an $N_\epsilon$, so that for each $n>N_\epsilon$ you have $\left|\sum_{k=0}^n a_k - a\right| < \epsilon$.

So now to prove that $\sum_{k=0}^{\infty} ca_k = ca$, you have to find an $N'_\epsilon$, so that for each $n>N'_\epsilon$ you have $\left|\sum_{k=0}^n ca_k - ca\right| < \epsilon$. However note that the latter is now a finite product, and thus you can move the factor $c$ out of the sum. For $c=0$, the statement is obviously true, so we only have to consider $c\ne 0$. But then, we can reformulate the condition as $\left|\sum_{k=0}^n a_k - a\right| < \epsilon/\left|c\right|$, and since $\sum a_k$ converges to $a$, and thus we see that $N'_\epsilon = N_{\epsilon/\left|c\right|}$ works.

The case of the shift is even easier: You effectively have replaced the series
$$a_0 + a_1 + a_2 + \ldots$$
by the series
$$0 + a_0 + a_1 + a_2 + \ldots$$
Adding $0$ obviously doesn't change the finite sum, and then we see that $N'_\epsilon = N_\epsilon+1$ covers the exact same terms for the modified sequence.

You've also used a third operation which you didn't specifically mention: You subtracted the two series element-wise. The proof that this is allowed is similar to the previous ones, but slightly more complicated because you've now got two series. But again, you use the fact that you can do the manipulation for finite sums, and the fact that both series individually converge.

More simple, you have
$$0.999\cdots = 0.999\cdots$$
then you multiply by ten on both sides

$$ 10 \times 0.999\cdots = 9.999\cdots=9+0.999\cdots$$
then substract $0.999\cdots$ from both sides

$$10 \times 0.9999\cdots-0.9999\cdots=(10-1)\times 0.999\cdots = 9$$
but $10-1=9$ so simplify $9$ from both sides and you get the equality $0.999\cdots=1$


Determine the minimum possible amount of distinct prime divisors of $19^{4n}+4$ Determine the minimum possible amount of distinct prime divisors of $19^{4n}+4$, for a positive integer $n$

My works:

By the Sophie Germain factorization, we have
$$19^{4n}+4=(19^{2n}-2\cdot 19^n+2)(19^{2n}+2\cdot 19^n+2)$$

this problem answer is $3$,can you help?

$19^{4n}+4$ has at least 3 prime factors:

Write $19^{4n}+4=xy$ using your factorization. Observe that $x,y$ are relatively prime, since they are both odd and their difference is $4\cdot 19^n$. Moreover, modulo 5 we have $19^{4n}=(-1)^{4n}=1$, so $5\ | \ 19^{4n}+4$. Since neither factor is a power of 5 (see below), the result follows.

Taking $n=1$ yields $19^4+4=5^2\cdot 13\cdot 401$ has 3 distinct prime factors, attaining the minimum.

Silly short proof that neither factor is a power of 5:

Both factors are one more than a perfect square, so by Mihailescu's Theorem they are not powers of 5.


Do we have $\int f dxdy = \int fdydx$ or $\int f dxdy = -\int f dydx$? If $f : \mathbb R^2 \to \mathbb R$ is an integrable function, then do we have
$$
 \int f dxdy = \int f dydx
$$
or
$$
 \int f dxdy = -\int f dydx?
$$
(I am leaving the domain of integration as it does not matter for the question, but suppose we have some compactum $[a,b]\times[c,d]$ as this make integration theory easier).

To give some context. I am currently reading about differential forms and integration, and if we have a $2$-form $\omega = f\cdot (dx \wedge dy)$, then
$$
 \int f dx\wedge dy = -\int f dy \wedge dx
$$
and the notation $\int f dx \wedge dy$ could be understood as shorthand for $\int f dxdy$. So then the second interpretation would be true.

On the other side, the "ordinary" integral as interpreted as the Riemann-integral where $dx$ and $dy$ are sometimes understood as the "infinitesimal" sides of the rectangles in which the domain of integrations gets partitioned. But then $dxdy = dydx$, or $\Delta x \cdot \Delta y = \Delta y \cdot \Delta x$. I know this language is a little bit "hand-wavy" as it is not clear what infinitesimal objects are, and so some authors leave them out of the integral expression and just write $\int f$, but at least this is the intuitive way and in some way resembles what is done in Riemann integration.

Also, another argument in favour of the first (i.e. interchanging does not changes sign) is the Fubini theorem and multiple integrals (see wikipedia), i.e. if Fubini applies we have
$$
 \int f dxdy = \int \left(\int f dx\right) dy
$$
and
$$
 \int \left(\int f dx \right) dy = \int \left(\int f dy\right) dx
$$
which would yield $\int f dxdy = \int f dydx$ by comparing those expressions.

So there are arguments to support both interpretations, but what is the right interpretation?

As far as i know $\int f dx \wedge dy$ is shorthand for something like $\int f\circ g * (\frac{\partial g}{\partial x}-\frac{\partial g}{\partial y})dxdy$ where g is a parametrisation of the integrationdomain. This makes $dx\wedge dy$ alternating, so $dx\wedge dy=-dy\wedge dx$.


Prove that $a \equiv b \pmod{1008}$ Suppose that the positive integers $a$ and $b$ satisfy the equation $$a^b-b^a = 1008.$$ Prove that $a \equiv b \pmod{1008}$.

Taking the equation modulo $1008$ we get $a^b \equiv b^a \pmod{1008}$, but I didn't see how to use this to get that $a \equiv b \pmod{1008}$.

Suppose
$a^b-b^a = n$
with all variables
positive integers.
If $n=1$,
this is Catalan's problem
for which the only solution is
$a=3, b=2$.
Assume
$n \ge 2$.

I will show that there
at most a finite number of solutions
and give bounds for
$a$ and $b$
in terms of $n$.

For $n=1008$,
the only solution is
$a=n+1, b=1$.

If $b=1$,
then
$a-1 = n$,
so $a = n+1$.
Then
$a-b = n
\equiv 0 \bmod n$.

If $b=2$,
then
$a^2-2^a = n$.
Since
$a^2 \le 2^a$
for
$a\le 2$
and
$a \ge 4$,
we must have
$a=3$
so the only $n$ that works
is
$n =3^2-2^3 = 1$.

If
$b \ge 3$,
if
$a > b$
then
$b^a > a^b$
(since
$b^{1/b} > a^{1/a}$
)
so no solution.
Therefore
if $b \ge 3$
then $a < b$.

We can't have $a=1$.

If $a=2$
then
$2^b-b^2 = n$.
Since the left side
is increasing for
$b \ge 4$,
there is at most one solution.
For $n=1008$,
there is no solution.

If $a=3$
then
$3^b-b^3 = n$.
Since the left side
is increasing for
$b \ge 3$,
there is at most one solution.
For $n=1008$,
there is no solution.

Suppose
$a \ge 4$
so $b \ge 5$.

Let $b = a+c$
where $c \ge 1$.
Then,
since
$(1+1/x)^x < e$
and
$u^r - v^r
\ge (u-v)v^{r-1}
$
if
$u > v > 1$
and
$r > 1$,

$\begin{array}\\
n
&=a^{a+c}-(a+c)^a\\
&=a^a(a^{c}-(1+c/a)^a)\\
&\gt a^a(a^{c}-e^c)\\
&\gt a^a(a^{c}-(a-2)^c)\\
&\gt 2a^ac(a-2)^{c-1}\\
&\ge 2a^a\\
\end{array}
$

This gives a
finite number of
possible values for $a$.

If
$n=1008$,
the only possibility is
$a=4$
(since
$4^4 = 256$
and
$5^5 = 3125$).
If $a=4$,
this is
$n
\gt 2\cdot 256c2^{c-1}
\ge 512c
$
so the only possibility is
$c=1$
so $b= 5$.

This does not work
(to see without computation:
$4^5-5^4$ is odd).

We have $1008 = 2^4 \cdot 3^2 \cdot 7$. First note that $a \equiv b \pmod{2}$ since $1008$ is even. Note that $2 \nmid a,b$ since if $2 \mid a,b$ then $a,b \leq 5$. Therefore, $a^b \equiv a \pmod{8}$ and $b^a \equiv b \pmod{8}$, so $a \equiv b \pmod{8}$. Then since $a^4 \equiv 1 \pmod{16}$, we have $a^b \equiv a^a \pmod{16}$ and so $a^a \equiv b^a \pmod{16}$. If $a \equiv 1 \pmod{4}$, then $a \equiv b \pmod{16}$. If $a \equiv 3 \pmod{4}$, then $a^3 \equiv b^3 \pmod{16}$ gives $a \equiv b \pmod{16}$.

We have $a^b \equiv a \pmod{3}$ and $b^a \equiv b \pmod{3}$ since $a$ and $b$ are both odd. Thus $a \equiv b \pmod{3}$. If $a \equiv b \equiv 1 \pmod{6}$, then $a^b \equiv a \pmod{9}$ and $b^a \equiv b \pmod{9}$ by Euler's Totient Theorem since $\varphi(9) = 6$. Thus $a \equiv b \pmod{9}$ in this case. If $a \equiv b \equiv 5 \pmod{6}$, then $a^b \equiv a^5 \pmod{9}$ and $a^5 \equiv b^5 \pmod{9}$. Thus $a \equiv b \pmod{9}$.

Similarly since $\varphi(7) = 6$ we get taking the cases $a \equiv b \equiv 1 \pmod{6}$ and $a \equiv b \equiv 5 \pmod{6}$ again that $a \equiv b \pmod{7}$.


Selecting cards to form a fair game Background

  In an old card game we draw 2 cards from a pile of 2 red and 2 black cards without replacement. If the two cards have the same color (for instance red and red) you win. However, if the cards have opposite color you lose.

This is a rich problem, especially if we instead look at the broader problem of drawing $2$ cards from a pile of $(n,m)$ cards, where we now have $n$ red and $m$ blue cards. After sorting out the information one can show that any solution must satisfy

$$(n-m)^2 = n + m$$

from which it is not hard to deduce that every solution must be a pair of consecutive triangular numbers.

$$(1,3), \ (3,6), \ (6,10), \ (10,15), \ldots$$

In other words we have

$$T_2(n) = T_2(n-1) + n, \qquad T(n)=0, n\leq 1$$

Which of course also can be expressed as $T_2(n) = n(n+1)/2$. So
$\bigl(T_2(n), T_2(n+1)\bigl)$ forms every solution.

My question is if similar beautiful patterns appear when we increase the number of cards we draw.

Main statement

  Assume we have a pile of $(n,m)$ cards, where $n$ of the cards are red and $m$ are black and we draw $c$ cards from the pile (where $c \leq n + m$). Fix $n$, how do we have to choose $m$ to obtain a fair game? E.g. a game where the probability of drawing a pile of cards of similar colors (red, red ..., red or black, black, ..., black) equals the probability of drawing cards of opposite color (any combination of red and black cards)

For $c = 3$ it seems we have to find integer solutions to

$$n(n-1)(n-2) + m(m-1)(m-2) = 3mn(n+m-2)$$

and this seems really hard. However, it seems $(1,5,3)$ is a solution. After an extensive computer search it seems

$$(1,5), \ (5,20), \ (20,76), \ (76,285), \ (285,1065), \ (1065,3976), \ \ldots$$

Are the first few solutions when drawing three cards. It seems these satisfy
$$
 T_3(u) = 5 T_3(u-1) - 5 T_3(u-2) + T_3(u-3) \ \text{with} \ T_3(1) = 1 \ \text{and} \ T_3(u) = 0 \ \text{if} \ u \leq 0.
$$

EDIT: Seems to boiling down to finding all integer pair such that

$$     \binom{m}{c}\binom{n}{0} \Bigl/\binom{m+n}{c}\Bigr.
    + \binom{m}{0}\binom{n}{c} \Bigl/\binom{m+n}{c}\Bigr. = \frac{1}{2}, $$
Where again $c \in \mathbb{N}_{\geq 2}$ and $c \leq n < m$. The expression above can be "simplified" to
$$\prod_{i=0}^{n-1} \frac{m+n-k-i}{m+n-i} + \prod_{i=0}^{m-1} \frac{n+m-k-i}{n+m-i} = \frac{1}{2}$$
and can be quite easily be numerically approximated. However, it does not lead me closer to finding every solution for every $c$.

EDIT 2: While I thought all solutions would be on the form $(a,b)$, $(b,c)$, $(c,d), \ldots$ this does not seem to be the case.
In particular for $c = 6$ we
$$T_6(1) = (1,11), \qquad T_6(2) = (2,19)$$
interesting!

Problems

Let $T_c(n)$ be the $n$'th solution when drawing $c$ cards.

Is it true that $T_c(1) = 2c - 1$ for every $c\geq 2$?
Is there a general recurrence relation for $T_c(n)$? Is there a closed expression for $T_c(n)?$
Given a particular $c$ how can we find all pairs $(n,m)$ that form a fair game?

This is a partial answer.

  Is it true that $T_c(1) = 2c - 1$ for every $c\geq 2$?

Yes, it is.

Since$$\begin{align}\frac{1}{2}\binom{m+1}{c}-\binom mc&=\frac 12\cdot\frac{(m+1)!}{(m+1-c)!c!}-\frac{m!}{(m-c)!c!}
\\\\&=\frac{m!}{c!(m+1-c)!}\bigg(\frac{m+1}{2}-(m+1-c)\bigg)
\\\\&=\frac{m!}{c!(m+1-c)!}\cdot\frac{2c-1-m}{2}\end{align}$$
we have$$\frac{1}{2}\binom{m+1}{c}-\binom mc=0\iff m=2c-1$$

So, we can say that

If $m\lt 2c-1$, then $\frac{1}{2}\binom{m+1}{c}\not=\binom mc$.
If $m=2c-1$, then $\frac{1}{2}\binom{m+1}{c}=\binom mc$.

Therefore, it follows that $(1,2c-1)$ is the first solution for every $c\ge 2$.

  Is there a general recurrence relation for $T_c(n)$? Is there a closed expression for $T_c(n)?$

For $c=3$, as you noticed, it seems that we have
$$T_3(u) = 5 T_3(u-1) - 5 T_3(u-2) + T_3(u-3)\qquad (u\ge 4)$$
$$T_3(1)=1,\qquad T_3(2)=5,\qquad T_3(3)=20$$
Since $x^3-5x^2+5x-1=(x-1)(x-(2-\sqrt 3))(x-(2+\sqrt 3))$, we get
$$T_3(u)=\frac{1}{12}\bigg((3 - \sqrt 3)(2 - \sqrt 3)^u+ (3 + \sqrt 3)(2 + \sqrt 3)^u-6\bigg)$$

For $c=4$, it seems that $(1,7)$ is the only solution.

Let $m+n-2=t\ (\ge 3)$. Then, the equation
$$\binom m4+\binom n4=\frac 12\binom{m+n}{4}$$
can be written as
$$(2m^2-2mt-4m+2t^2-t+1)^2=3t^4-6t^3+6t^2+1$$So, $t\ (\ge 3)$ has to be an integer such that $3t^4-6t^3+6t^2+1$ is a perfect square.

Though it seems that $t=6$ is the only such integer, no proof can be obtained. If this is true, then we can say that $(1,7)$ is the only solution.

For $c=5$, it seems that $(1,9)$ is the only solution.

Let $m+n=k\ (\ge 6)$. Then, the equation
$$\binom m5+\binom n5=\frac 12\binom{m+n}{5}$$
can be written as
$$(2m^2-2mk+k^2-4k+5)^2=\frac{3k^4-28k^3+108k^2-188k+125}{5}$$So, $k\ (\ge 6)$ has to be an integer such that $\frac{3k^4-28k^3+108k^2-188k+125}{5}$ is a perfect square.

Though it seems that $k=10$ is the only such integer, no proof can be obtained. If this is true, then we can say that $(1,9)$ is the only solution.

"n an old card game we draw 2 cards from a pile of 2 red and 2 black cards without replacement. If the two cards have the same color (for instance red and red) you win. However, if the cards have opposite color you lose.
This is a rich problem, especially if we instead look at the broader problem of drawing cards from a pile of (n,m)
cards, where we now have n red and m blue cards."

Actually, there is no problem here! What do you want to find?  The probability of winning?

If so drawing two cards, blue or red, leads to four possible results, BB, BR, RB, of RR (B stands for "blue" and R stands for "red").  If there are m blue and n red cards, the probability of "BB" is $\frac{m}{m+ n}\frac{m-1}{m+n-1}$ and the probability of "RR" is $\frac{n}{m+ n}\frac{n-1}{m+n-1}$.  The probability of winning, getting either "BB" or "RR" is the sum of those two.


Is it necessary $A^TA =I$ if $AA^T=I$ where A is a square matrix? Suppose if $AA^T=I$ where $A$ is a square matrix, is it necessary that $A^TA=I$?

I tried to google it but didn't find anything confirmatory.

In the same way if $AA^{-1}=I$, is it necessary that $A^{-1}A=I$?

My attempt it as follows:-

$$A=\begin{bmatrix}
a&b&c\\
d&e&f\\
g&h&i
\end{bmatrix}$$

$$AA^T=\begin{bmatrix}
a&b&c\\
d&e&f\\
g&h&i
\end{bmatrix}\begin{bmatrix}
a&d&g\\
b&e&h\\
c&f&i
\end{bmatrix}$$

$$AA^T=\begin{bmatrix}
a^2+b^2+c^2&ad+be+cf&ag+bh+ci\\
da+eb+fc&d^2+e^2+f^2&dg+eh+fi\\
ga+hb+ic&gd+he+if&g^2+h^2+i^2
\end{bmatrix}$$

$$a^2+b^2+c^2=1$$
$$d^2+e^2+f^2=1$$
$$g^2+h^2+i^2=1$$
$$ad+be+cf=0$$
$$ag+bh+ci=0$$
$$da+eb+fc=0$$
$$dg+eh+fi=0$$
$$ga+hb+ic=0$$
$$gd+he+if=0$$

Now if we calculate $A^TA$, it would be

$$A^TA=\begin{bmatrix}
a^2+d^2+g^2&ab+de+gh&agc+df+gi\\
ba+ed+hg&b^2+e^2+h^2&bc+ef+hi\\
ca+fd+ig&cb+ef+ih&c^2+f^2+i^2
\end{bmatrix}$$

Now can one say $a^2+d^2+g^2=1$ from the previous equations? I think not necessary. So by this exercise I doubt $A^TA=I$

I am not getting any idea for $AA^{-1}=I$

In addition to all this $I=I^T=(AA^T)^T =A^T(A^T)^T=A^TA $.


Confused about square root So i have this equation $$-\sqrt{C_1-y^2}=x+C_2$$

I want to get rid of radical by squaring both sides, the negative sign in front of the first term will become positive right?

I know this is a silly question but i need to make sure, my background at algebra is terrible.

Yes it is, and your question is not very terrible since after your calculation, you will reach weird things.

  $$C_1-y^2=(x+C_2)^2$$

You can of course change the subject and get a nice equation.

  $$y^2=-(x+C_2)^2+C_1$$

Even though the equation seems nice, we need to remember that criteria from the equations are $C_1-y^2\geq 0$ and $x+C_2\leq 0$ since square root always take positive root, and things inside positive should be positive (I assume you are working with real variables.

So that's it.  You can erase the negative sign (by squaring both sides), but the negative sign does play a role when you try to draw the curve out.


check workings for polynomial function from graph The diagram shows a curve with equation of the form $y = kx(x + a)^2$,
which passes through $(-2, 0)$, $(0, 0)$ and $(1, 3)$.
What are the values of $a$ and $k$.

To find $k$, I would set $f(x) = 1$.
$f(1) = k(x + 2)(x + 0)(x - 1)$
$3 = k(1 + 2)(x + 1)(1 - 1)$
$3 = k(3)(1)(0)$
This would make $k = 0$ which does not appear to be right.

$$y=kx(x+a)^2\quad \quad \quad (-2, 0),(0, 0) , (1, 3)$$

$$\text{for} (0,0):\quad \quad \quad f(0)=0=0\\
\text{for}(1,3):\quad \quad \quad f(1)=k(1+a)^2=3\\
\text{for}(-2,0):\quad \quad \quad f(-2)=-2k(-2+a)^2=0$$

so you have two equations with two variables:

$$\begin{cases}k(1+2a+a^2)=3\\
-2k(4-4a+a^2)=0\end{cases}$$

$$\begin{cases}k+2ak+ka^2=3\\
-8k+8ka-2ka^2=0\end{cases}$$

Solve, you should get $\color{red}{a=2,k=\frac 1 3}$

The equation is satisfied by $(-2,0)$ and $(1,3)$
Putting $(-2,0)$ in the equation we obtain:
$$0 = k(-2)(-2+a)^2 $$
Therefore, $(a-2)=0$ as $k \ne 0$
$$\implies a=2$$
Similarly, putting $(1,3)$ in the equation we obtain:
$$3 = k*1*(1+2)$$
Therefore $k=1$


Find values $f(0)=p$ to make $f(x)=e^{\frac{-1}{|x|}}$ continuous at $x=0$ Given a function $f(x)=e^{\frac{-1}{|x|}}$ when $x \neq 0$ and $f(x)=p$ if $x=0$. I need to find the values for $p$, such that the function becomes continuous at $x=0$. In order to be continuous at $x=0$, it needs to be defined at that point (which is clearly the case), also the limit $\lim_{x\rightarrow 0} f(x) $ must exist and $\lim_{x\rightarrow 0} f(x) = f(0)=p$ must hold.

So far as I see it, the limit does not depend on the value I take for $p$, so it must be unique, since $\lim_{x\rightarrow 0} f(x) $ can only take one value. However the question clearly states that I have to find valueS for $p$ (quoting: "Find the values of $p$ that make $f$ continuous at $0$.").

Am I wrong or is the question malformed?

The question is well formed, and you already found one part of the answer: there is only one possible value $p$ for which $f$ will be continuous.

I have encountered this type of question quite often, and usually, the use of the plural does not mean that there need to be several answers. Plural is used to denote that it is not clear how many answers there are (and there could also be no answer at all!)

The question is well-posed. In mathematical texts the wording with plural s in a question about some solution set usually does not imply any assumption about it's size. It has this answer:
$$
\lim_{x\to 0} e^{-1/|x|} = 0 = p \Rightarrow S = \{ 0 \}
$$


Partial derivatives vs. Total Derivatives for chain rule. If I had a function $f(x,y)$ where $x=x(s,t)$ and $y=y(s,t)$ then

$$ \frac{df}{dt} = \frac{\partial f}{\partial x} \frac{\partial x}{\partial t} + \frac{\partial f}{\partial y} \frac{\partial y}{\partial t}. $$

I have been reading this and have spotted in case 2 that

$$ \frac{\partial f}{\partial t} = \frac{\partial f}{\partial x} \frac{\partial x}{\partial t} + \frac{\partial f}{\partial y} \frac{\partial y}{\partial t}. $$

$f$ has no explicit $t$ dependence so how can this be correct? How can I have a chain rule for partial derivatives? A chain rule implies that there is no explicit dependence on the variable that we are differentiating with respect to, and I thought partial derivatives only deal with explicit dependencies and not implicit? Thanks

In case $2$, it's not $\frac{\partial f}{\partial t}$, it's $\frac{\partial z}{\partial t}$, and $z$ is not independent of $t$.

An ordinary derivative--such as that of $f$ with respect to $t$, in your example is only valid if all the dependencies of $f$, all the dependencies of those dependencies, all the dependencies of those dependencies, and so on, can be shown to have a single common dependency $t$, explicit or otherwise. In all other cases, only a partial derivative applies, since $f$ then only depends partially on $t$.

That is why a partial derivative is used in Case 2; $t$ is not a common dependency of the system $(f,x,y,s,t)$, as $s$ is in no way dependent upon $t$.


Value of expression $\sum\limits^{10}_{r=2}\binom{r}{2}\cdot \binom{10}{r}$ The value of expression $\displaystyle \sum\limits^{10}_{r=2}\binom{r}{2}\cdot \binom{10}{r}=$

What I tried:

$$\sum^{10}_{r=2}\frac{r!}{2!\cdot (r-2)!}\times \frac{10!}{r!\cdot (10-r)!}$$

$$\frac{10!}{2!}\sum^{10}_{r=2}\frac{1}{(r-2)!\times (10-r)!}$$

How do I solve it?


$A^TJA = J$ $ \rightarrow \det(A) = 1$ Why is this true? I cant seem to understand why the $\det(A) = 1$ for this to hold?

It is not indeed the case. We might have $$\det (A)=-1$$ since $$\det(A^TJA)=\det(J)$$yields to $$\det(A^T)\det(J)\det(A)=\det(J)$$and if $J$ is invertible (i.e. the determinant is non-zero) we conclude $$\det(A)^2=1$$if $J$ is singuler ($\det(J)=0$) we cannot determine $\det (A)$

It is not true in full generality. For instance, if you are dealing with $1×1$ matrices, then matrix multiplication boils down to ordinary multiplication and the equation would be $A\cdot A\cdot J = J$, so assuming we are working over the rationals (though this can be generalized), we have $J=0$ or $A=1$ or $A=-1$.
In fact, this example can be generalized by applying the determinant to both sides of the equation and noting that $\det (A^T)=\det(A)$. This gives $\det(A)^2 \times \det(J) = \det(J)$, so if $\det(J)$ is not zero, then $\det(A)=1$ or $\det(A)=-1$.


Minimum value of $\frac{4}{x}+2x+10+\frac{3+x}{4x^2+1}$ If the minimum value of $\frac{4}{x}+2x+10+\frac{3+x}{4x^2+1}$ when $x>0$ is $\frac{p}{q}$ where $p,q\in N$ then find the least value of $(p+q).$

I can find the minimum value of $\frac{4}{x}+2x$ using $AM- GM$ inequality but that too comes irrational and when i tried to find the minimum value of $\frac{3+x}{4x^2+1}$ using first derivative test,i am facing difficulty.Please help me in solving this problem.

While the answers that have been proposed already are great, I think that rather than trying to find the positive roots of the following polynomial :

\begin{align}
32x^6-52x^4-24x^3-29x^2-4&=0,
\end{align}

your problem could be solved more easily by using the rational root theorem.

  Rational root theorem :
  Let $P(x)=\sum\limits_{k=0}^n a_kx^k$ where every $a_k$ is an integer and $a_n\neq0$. If $\alpha$ is a rational root of $P(x)$, then $\alpha=\frac{p}{q}$ where :

  $p$ divides $a_0$,
  $q$ divides $a_n$,
  $\gcd(p,q)=\pm1$.

In your case, you are looking for a positive rational root hence we can narrow the possible values to $4$, $2$, $1$, $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{16}$, $\frac{1}{32}$.

As none of these values is a root of our polynomial, you can conclude that the minimum of your function is not reached at a positive rational.

HINT: There is another approach using calculus

let $$y=\frac{4}{x}+2x+10+\frac{3+x}{4x^2+1}$$
$$\frac{dy}{dx}=-\frac{4}{x^2}+2+\frac{(4x^2+1)(1)-(3+x)(8x)}{(4x^2+1)^2}$$
Now, for maxima or minima, put $$\frac{dy}{dx}=0$$
$$\frac{(4x^2+1)(1)-(3+x)(8x)}{(4x^2+1)^2}-\frac{4}{x^2}+2=0$$
Since, $x>0$ then find the positive roots of the equation for minima & proceed


How to show that $u-Ku=f$? Let $X \subset C(\mathbb R;\mathbb R)$ be the space of all continuous functions $u: \mathbb R \to \mathbb R$ where

$$\lim_{x \to \pm \infty} u(x)=0$$

provided with the $\sup$-norm. Let $k \in L^1(\mathbb R)$, $u \in X$ and

$$(Ku)(x) := \int_\mathbb R k(x-y)u(y)\,dy, \,\,\,x \in \mathbb R.$$

Furthermore $$\int_\mathbb R |k(s)|\, ds <1$$

How can I show that for every $f \in X$ there exists exactly one $u \in X$ such that $$u-Ku=f\,\,?
$$

Fix $f\in X$ and consider the mapping $\varphi:X\rightarrow X$ defined by
$$\varphi(u)=Ku+f$$
We apply the Banach-fixed point theorem on $\varphi$. To do so we need to check three conditions:

$X$ is complete (enough to show that is closed in the Banach space of bounded continuous functions).
The functional $K$ (and hence $\varphi$) maps $X$ to $X$.
We have $||\varphi(u)-\varphi(v)||_{\infty}\leq C||u-v||_{\infty}$ for every $u,v\in X$ where $C<1$.

If these conditions hold, then $\varphi$ has a unique fixed point in $X$ that is, there exists a unique $u\in X$ such that
$$Ku+f=u\Leftrightarrow u-Ku=f$$

$K$ is a bounded linear operator with

$||K||=\int_\mathbb R |k(s)|\, ds <1$.

Hence (Neumann seies !) $I-K$ is invertible.


Subspace spanned by two standard basis vectors and its intersection with other subspaces Let $\mathcal{V}$ be a subspace of $\mathbb{R}^n$ with $dim\mathcal{V}=n-1$ where $n>3$.

For any integer pairs $i$ and $j$ satisfying $1\leq i < j \leq n$, let
$\mathcal{W}_{ij}$ be a subspace of $\mathbb{R}^n$ spanned by two vectors $\mathbf{e}_i$ and $\mathbf{e}_j$ that are the $i^\mathrm{th}$ and $j^\mathrm{th}$ column in the $n\times n$ identity matrix.

Clearly, $\mathcal{V}\cap\mathcal{W}_{ij}$ is not empty for any $i$ and $j$. But I'm wondering whether I can claim something stronger.

  For any subspace $\mathcal{V}$ of $\mathbb{R}^n$ with $dim\mathcal{V}=n-1$ where $n>3$, there always exist integers $i$ and $j$ satisfying $\mathcal{V} \supset \mathcal{W}_{ij}=span(\mathbf{e}_i,\mathbf{e}_j)$.

Is this statement true?

Since $n>3$ this implies that $dimV > 2$. Now the dimension of the subspace is one less than the whole vector space so there must exist two vectors from the standard basis in the subspace.

For suppose not then there exists two $e_i,e_j$ such that  $span(e_i,e_j)\cap V=\{0\}$. To see this note that $V$ must contain one memeber of the standard basis or else it is the zero space, since it must contain one there is at least two other members not in the space by the hypothesis that $n>3$ and the assumption being made. This means they are a direct sum implying that there dimension is $dim(V\oplus span(e_i,e_j))=dim(V)+dim(span(e_i,e_j))=n-1+2=n+1$.

Certainly, the direct sum of these subspaces is itself a subspace of $R^n$. But this a contradiction since the dimension of a subspace is always less than or equal to the vector space.

Therefore the assertion is indeed true.

In fact, I suspect there may be even a stronger condition which you may assert but will I leave that to you to explore.


How to find location of a point for a rectangle I have a circle with a line that is drawn through it at two points. I have the coordinate for the center of the circle, the two coordinates where it intersects the circle and the radius as well. I want to put the two rectangles around the two pieces from the circle, as shown by the green marking. My question is how can I get the coordinates of the rectangle? Any help would be appreciated

One of the things i considered using was the midpoint formula to find the middle coordinate between the intercepting points and then I can find the distance.

Assuming the center to be the origin, compute $r-\Big\Vert \frac{A+B}2 \Big\Vert$. This is the amount of offset needed. The direction is given by $\frac{A+B}2$, so the complete formula is
$$O = \frac{r-\left\Vert\frac{A+B}2\right\Vert}{\left\Vert\frac{A+B}2\right\Vert} \frac{A+B}2 = \frac{2r - \Vert A+B\Vert}{2\Vert A+B\Vert} (A+B)$$

Find equation of the blue line and that of the circle(shift origin here or it will get a bit nasty) and add an arbitrary constant to it and put in equation of circle retaining only x terms.

You will get a quadratic equation. Set discriminant to be 0 as you want only 1 point of contact with circle(tangent)

Knowing this point, You can find its equation and equation of other lines as you know their slopes/points. You will get 2 values of arbitrary constants up there corresponding to 2 rectangles.


Show that $\varphi(\langle n, k\rangle) = \frac{1}{2}(n+k+1)(n+k)+n $ is injective How to show that the following function is an injective function?

$ \varphi : \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N} \\
\varphi(\langle n, k\rangle) = \frac{1}{2}(n+k+1)(n+k)+n$

I'm starting with $ \frac{1}{2}(a+b+1)(a+b)+a = \frac{1}{2}(c+d+1)(c+d)+c$, but how am I supposed to show from this equality that $\langle a, b\rangle = \langle c, d\rangle$, where $\langle a, b\rangle \in \mathbb{N}\times \mathbb{N}$ ?

Here are two arguments.  The first should make the statement "visually obvious" while the second is more formal.

Construct a grid displaying the value of $\phi(n,k)$ for each value of $n$ and $k$:
$$\begin{matrix}
  \color{red}{\phantom{k={}}4}&14\cr
  \color{red}{\phantom{k={}}3}&9&13\cr
  \color{red}{\phantom{k={}}2}&5&8&12\cr
  \color{red}{\phantom{k={}}1}&2&4&7&11\cr
  \color{red}{n=0}&0&1&3&6&10\phantom{=n}\cr
  &\color{blue}{0}&\color{blue}{1}&\color{blue}{2}&\color{blue}{3}&\color{blue}{\!\!\!\!\!\!\!\!4\rlap{{}=k}}
\end{matrix}$$
This should make it pretty clear what is going on.  A formal proof could be as follows.

First, suppose that $n_1+k_1>n_2+k_2$.  Since we are talking about integers, this means that $n_1+k_1\ge n_2+k_2+1$ and we have
$$\eqalign{\phi(n_1,k_1)
  &=\tfrac12(n_1+k_1+1)(n_1+k_1)+n_1\cr
  &\ge\tfrac12(n_2+k_2+2)(n_2+k_2+1)+n_1\cr
  &=\tfrac12(n_2+k_2+1)(n_2+k_2)+n_2+k_2+1+n_1\cr
  &>\phi(n_2,k_2)\ .\cr}$$
Now suppose that $\phi(n_1,k_1)=\phi(n_2,k_2)$.  By the above argument we cannot have $n_1+k_1>n_2+k_2$, by a symmetrical argument we cannot have $n_2+k_2>n_1+k_1$, therefore $n_1+k_1=n_2+k_2$.  Hence
$$\eqalign{\phi(n_1,k_1)=\phi(n_2,k_2)\
  &\Rightarrow\ \tfrac12(n_1+k_1+1)(n_1+k_1)+n_1=\tfrac12(n_2+k_2+1)(n_2+k_2)+n_2\cr
  &\Rightarrow\ \tfrac12(n_1+k_1+1)(n_1+k_1)+n_1=\tfrac12(n_1+k_1+1)(n_1+k_1)+n_2\cr
  &\Rightarrow\ n_1=n_2\ ,\cr}$$
and so $k_1=k_2$.  Thus $\phi$ is injective.

It might be easier to start by letting $(n, k)$ be such that $\varphi( \langle n, k\rangle ) = 0$. Then, $(n + k + 1)(n+k) + 2n = 0$, and since $n, k \in \mathbb{N}$, $(n + k + 1)(n + k), 2n \ge 0$, so $2n = n = 0$, so $k = 0$, and since $(n, k) = (0, 0)$, $\varphi$ is injective.


Looking at nature for answers to math problems I recently watched a video about the Gömböc, a shape with one stable and one unstable point of equilibrium. Dr. Gábor Domokos proved the existence of this shape. Domokos originally looked at pebbles when trying to find the shape, although this approach was ultimately unsuccessful. Later on, some turtles were found to have a similar shape to the Gömböc.
I am looking for some other examples of when researchers have drawn inspiration (or completely copied) from nature in order to find solutions to math/engineering problems. To clarify, I am not looking for examples of explaining nature using math, as there are many examples of that (e.g. the Fibonacci spiral, arrangement of electrons in atoms/molecules, normal distribution, etc), but instead for examples of explaining math/engineering using nature.
I wasn't able to come up with or find any more examples myself, only the Gömböc.
Edit: I feel like there must have been some instance of when researchers have used the natural positioning of electrons to model something else, but I can't think of anything off the top of my head.

I remember reading about a research paper in which the researchers used an amoeba to gain approximate solutions to the traveling salesman problem. Although that is a computer science problem, it is not entirely irrelevant to mathematics.

Amoeba finds approximate solutions to NP-hard problem in linear time.
In the new study, the researchers found that an amoeba can find
reasonable (nearly optimal) solutions to the TSP in an amount of time
that grows only linearly as the number of cities increases from four
to eight.

I also found the following book that might be of interest to you. A look at the table of contents will provide you with a lot of interesting examples.
Nature-Inspired Optimization Algorithms by Xin-She Yang.
Hope this helps.

This is a cool question. One example I know of is that of the wholeness axiom of Paul Corazza. Roughly, the axiom is a large cardinal axiom which states something about the reflection properties of the universe $V$ by way of large cardinals. Paul Corazza is said to have had access to this axiom after meditating. Not exactly looking at nature, but I guess looking inside oneself.
https://en.wikipedia.org/wiki/Wholeness_axiom
More corny is the classical story of Newton and the apple.


Convert Sums of absolute values in Linear program Ihave the following problem and it needs to be converted into LP form.
\begin{align}
 \max\> & z = c^T x\\
      & Ax \leq B \\
      & \sum_{i=1}^{n}|x_i|=1
\end{align}
I know that $c^Tx$ and $Ax \leq B$ are matrix dot products.
My question is, How can I convert $\sum_{i=1}^{n}|x_i|=1$ into LP form.
I have read online that if you only have a finite amount of $x$'s, you can simply do one equation for the positive and another one for the negative. For instance, if we have $|x_1| = 1$, the equation will be transformed to $x_1 = 1$ and $-x_1 = 1$. How can we do it for the summation?
I think we need to take the combinations of all the possible $x$'s as maybe $x_1$ is positive and all the rest are negative.
Thanks!

Use auxiliary variables. Let $u_i \geq 0, v_i \geq 0$. Then we can write $x_i = u_i - v_i$ and $\vert x_i \vert = u_i + v_i$.


Example of how to use intermediate value theorem when given the range of c. Theorem: Let $f$ be continuous on $[a,\,b]$ and assume $f(a)\not=f(b)$. Then for every $\lambda$ such that $f(a)<\lambda<f(b)$, there exists a $c\in(a,\,b)$ such that $f(c)=\lambda$.

  Question:

Suppose that $f : [0,1] \rightarrow [0,2]$ is continuous. Use the Intermediate Value Theorem to prove that their exists $c \in [0,1]$ such that:

$$f(c)=2c^2$$

  Attempt:

  I know that when we have the condition were $f : [a,b] \rightarrow [a,b]$, the method to prove that c exits, is the same method you would use to prove the fixed point theorem.

Unfortunately I don't have an example in my notes when we have $f : [a,b] \rightarrow [a,y]$. How would I use the IVT to answer the original question?

Hint:

Consider the function $g(x)=f(x)-2x^2$.

Some details:

$g(0)=f(0)\ge 0$ since the range of $f$ is contained in $[0,2]$. Similarly, $g(1)=f(1)-2\le 0$. Furthermore, $g$ is continuous since $f$ is. Now, either $g(0)$ or $g(1)==0$, and  there's nothing to prove. Or $g(0)>0$, $g(1)<0$. The Intermediate value theorem assures there exists $c\in (0,1)$ such that $g(c)=0$.

First note: $\exists x_0, x_1$ such that $f(x_0) = 0$, $f(x_1) = 2$. Both x are somewhere in the interval $[0,1]$.

Second note: $0 < 2c^2 < 2$ for $ c \in (0,1)$.

So we have:
f is continious on $[x_0, x_1] \subset [0, 1]$, $f(x_0) \neq f(x_1)$ and $f(x_0) < 2c^2 < f(x_1)$. By IVT there must exist $c \in (x_0, x_1)$ so that $f(c) = 2c^2$.


If $A$ is normal show that $A+A^*$ bijective implies $A$ is bijective Suppose $A$ is a normal ($||Ax||=||A^*x||$ for all $x \in H$ ) bounded linear operator on a Hilbert space $H$. We want to show that if $A+A^*$ is a bijection then so is $A$.
A is injective is very easy since $kerA=kerA^*$ we have that  if $Ax=0$ then $x \in ker(A)\cap ker(A^*)$ so $x \in ker(A+A^*)$ so $x=0_H$.
I'm stuck on surjective. My hint is to use the open mapping theorem (so $A+A^*$ is open); but I can't see how this helps me at all.
I thought maybe I could prove $Im(A)$ was dense and closed but I can't relate either to $A+A^*$.
EDIT
In

Since $A$ and $A^\ast$ commute, we have
$$
\frac 1 4(A+A^\ast)^2-\frac 14(A-A^\ast)^2=A^\ast A.
$$
Since $A+A^\ast$ and $i(A-A^\ast)$ are self-adjoint operators, it follows that
\begin{align*}
\|A x\|^2&=\langle A^\ast Ax,x\rangle\\
&=\frac 1 4\langle (A+A^\ast)^2x,x\rangle-\frac 1 4\langle (A-A^\ast)^2x,x\rangle\\
&=\frac 1 4\|(A+A^\ast)x\|^2+\frac 1 4 \|i(A-A^\ast)x\|^2.
\end{align*}
By the open mapping theorem (or the bounded inverse theorem if youlike), there exists a constant $c>0$ such that $\|(A+A^\ast)x\|\geq c\|x\|$. Thus
$$
\|Ax\|\geq \frac{c}{2}\|x\|.
$$
Thus $A$ is a bijective operator from $H$ to $\operatorname{im}A$ with bounded inverse. In particular, $\operatorname{im}A$ is closed. Finally, if $y\perp\operatorname{im}A$, then
$$
0=\langle y,AA^\ast y\rangle=\|A^\ast y\|^2,
$$
hence $y\in \ker A^\ast=\{0\}$. Therefore, $\operatorname{im}A$ is also dense in $H$.
Here is a shorter answer that requires a little more technology: By the spectral theorem, the unital $C^\ast$-algebra generated by $A$ is $\ast$-isomorphic to $C(K)$ for some compact $K$, so this question boils down to the invertibility of $f\in C(K)$ under the assumption that $\operatorname{Re}f$ is invertible. Of course, an element of $C(K)$ is invertible if and only if it has no zero. Furthermore, the zeros of $f$ coincide with the zeros of $|f|$. Now all we have to do is to notice that
$$
|f|^2=(\operatorname{Re}f)^2+(\operatorname{Im}f)^2\geq (\operatorname{Re}f)^2>0.
$$

For finite dimensions:
Isnt $A$ and $A^H$ simulataneously diagonalizable by unitary matrix cant u use that to prove this by simply saying $A+A^H = U (D+D^H) U^H$ and hence bijective iff $\lambda_i+conj(\lambda_i) \neq 0$ and hence $\lambda_i \neq 0$ and hence $A$ is bijective .


Why is $|x|$ not differentiable at $x=0$? The definition of a derivative is the slope of a function tangent to a point. It is also defined as $$\lim_{h\to0} \frac{f(x+h)-f(x)}{h}$$
If we apply this to $f(x)= |x|$, we get that it is $\lim\limits_{h\to 0} \dfrac{|h|}{h}$, which is undefined. However, if we look at the graph of $|x|$, we see that there can exist a tangent line at x=0, with slope 0. So why is the derivative undefined instead of 0?

Let $f(x) = |x|$. For $x > 0$, the gradient is $1$, whereas for $x < 0$, the gradient is $-1$. At $x = 0$, you have infinitely many lines,  which are represented by the subgradient $[-1,1]$.

If you draw the graph of the equation, you will get a v-shaped configuration with the vertex located at x=0, y=0.

If you try to put a tangent at that vertex point, you will see that the line can take on one of innumerable slopes and still be "touching at one point". It's undefined.


Differentiability implies continuity - A question about the proof I have a question, to aid my understanding, about the proof that differentiability implies continutity.$\mathstrut$

Differentiability Definition

When we say a function is differentiable at $x_0$, we mean that the limit:

$$f^{\prime} (x) = \lim_{x\to x_0} \frac{f(x) - f(x_0)}{x-x_0}$$ exists.

Continuity Definition

When we say a function is continuous at $x_0$, we mean that:
$$\lim_{x\to x_0} f(x) - f(x_0) = 0$$

Theorem: Differentiability implies Continuity: If $f$ is a differentiable function at $x_0$, then it is continuous at $x_0$.

Proof:

Let us suppose that $f$ is differentiable at $x_0$. Then
$$ \lim_{x\to x_0} \frac{f(x) - f(x_0)}{x-x_0} =  f^{\prime} (x) $$

and hence

$$ \lim_{x\to x_0} f(x) - f(x_0) = \lim_{x\to x_0} \left[ \frac{f(x) - f(x_0)}{x-x_0} \right] \cdot \lim_{x\to x_0} (x-x_0) = 0$$

We have therefore shown that, using the definition of continuous, if the function is differentiable at $x_0$, it must also be continuous.

My Question

The proof seems to execute the following steps:

Assume the function is continuous at $x_0$
Show that, with little algebra, we can change this into an equivalent question about differentiability at $x_0$. With this little bit of algebra, we can show that if a function is differentiable at $x_0$ it is also continuous.

What I am slightly unsure about is the apparent circularity. In my mind it seems to say, if a function is continuous, we can show that if it is also differentiable, then it is continuous. Rather than what I was expecting, namely, if a function is differentiable, we can show it must be continuous.

Hopefully my confusion is clear. Any help will be greatly appreciated.

Technically, there is an implicit issue of existence of limits which is being swept under the rug in the presentation you have given. The assumption of differentiability at $x_0$ says that the limit

$$\lim_{x \to x_0} \frac{f(x) - f(x_0)}{x-x_0}$$

exists as a finite number. The limit $\lim_{x \to x_0} x-x_0$ exists and is zero regardless of our assumptions. Then the product rule for limits tells us both that $\lim_{x \to x_0} f(x)-f(x_0)$ exists, and that it is the product of the two limits above, which means it must be zero. Because the product rule also tells us that the limit exists, we do not have to assume continuity first.

Conceptually, if a function is differentiable at x=a, that means the function is changing gradually at that point. If the function is discontinuous at x=a for any reason (it is undefined, jumps, or has a cusp at x=a), then the function is not changing gradually at that point and is not differentiable.


Solve $\sqrt{3x}+\sqrt{2x}=17$ This is what I did:
$$\sqrt{3x}+\sqrt{2x}=17$$
$$\implies\sqrt{3x}+\sqrt{2x}=17$$
$$\implies\sqrt{3}\sqrt{x}+\sqrt{2}\sqrt{x}=17$$
$$\implies\sqrt{x}(\sqrt{3}+\sqrt{2})=17$$
$$\implies x(5+2\sqrt{6})=289$$
I don't know how to continue. And when I went to wolfram alpha, I got:
$$x=-289(2\sqrt{6}-5)$$
Could you show me the steps to get the final result?
Thank you.

I think $$x = \left( \frac{17}{\sqrt{3} + \sqrt{2}} \right)^2$$ is a perfectly fine solution, absent any contextual reason to rationalize the denominator.


Prove equilateral triangle in another triangle We got triangle $ABC$ ($AC = BC$). ∠$ACB = 120^\circ$. $AM = MN = NB = \frac 13AB$.

Prove that CNM is equilateral triangle.
Any ideas how to do that? I'd be grateful if someone helps me!

P.S.I am sorry that the drawing is not very accurate!

Since $∠ACB = 120°$ and $AC=BC$ then $∠CAB=∠CBA=30°$ and let be $CH$ the altitude of triangle $ABC$ and $AB=3l$.

$\tan(∠CAB=30°)=\sqrt{3}/3=CH/AH=CH/(l+l/2) \Rightarrow CH=l\sqrt{3}/2$. But $CH$ is also the altitude of the triangle $CMN$ and then

$\tan(∠CMN=∠CNM)=CH/MH=\frac{l\sqrt{3}/2}{l/2}=\sqrt{3} \Rightarrow ∠CMN=∠CNM=60°$

given

3AM=3MN=3NB=AB
$\angle ACM$=$\angle MCN$=$\angle NCB$(from 1)

So,  $\angle ACM$=$\angle MCN$=$\angle NCB$=60 ($\angle ACB=\angle ACM$+$\angle MCN$+$\angle NCB$)

also given

$\angle ACB=120$

SINCE it is equilateral triangle,

$\angle CAB$=$\angle CBA$=30(using sum of all $ang$ of $\triangle$ is 180)
ALSO
$\angle MCN$=$\angle CMN$=$\angle CMN$=60
(By solving triangle ACM and BCN).


Is angle $EBA$ is a right angle? I am having trouble analyzing this image to identify the statement as true or false:

The statements are:

angle $EBA$ is a right angle. - I think it's false, but I can't think of a theorem or postulate that will justify my answer.
$\overleftrightarrow{FG}$ is perpendicular to plane $H$. - I think this is wrong because $\overleftrightarrow{FG}\subseteq{H}$

please help. thank you

I think there are two mutually perpendicular planes intersecting along ABC in the 3D figure I have redrawn. It is assumed ABC is perpen to the bigger plane on which the union is mounted.From the picture assuming BE is is parallel to the plane shown and ABC is perpendicular to it..then

it is correct EBA is a right triangle.

FG is perpendicular to plane K, the piercing point is C.


Eliminating unwanted branches of algebraic curves related to triangle centres Lately I have become fascinated with triangle centres. To that end, I have written a small Python module that can compute explicit positions of centres for arbitrary triangles in the plane to arbitrary precision, based on the trilinear and barycentric coordinates in Kimberling's Encyclopedia of Triangle Centers (ETC).

For certain combinations of triangles and centres, the sum of barycentric coordinates evaluates to $0$ and I have a point at infinity. To study those cases where a triangle centre leaves the friendly confines of the Euclidean plane for the line at infinity, I invented the notion of infinity curves.

  The infinity curve $\infty_n$ associated with the Kimberling triangle centre $X_n$ is the locus of points $(x,y)$ with $y\ne0$ and $(x,y)\ne(0,\pm\sqrt3)$ where the centre $X_n$ of the triangle with vertices $(-1,0),(1,0),(x,y)$ is a point at infinity. $\infty_n$ may be empty; I will ignore these cases here, as well as points that always lie on the line at infinity such as $X_{30}$.

For algebraic centres, which make up the vast majority of centres in the ETC, the associated infinity curves are also algebraic, and the problem then is to find an exact bivariate polynomial describing them. They can be derived by setting the sum of barycentric coordinates equal to zero, then expanding, simplifying and factoring. For example, the Exeter point $X_{22}$ has triangle centre function $a(b^4+c^4-a^4)$, from which I derived
$$\infty_{22}(x,y):3x^4 + 2x^2y^2 - 6x^2 - y^4 - 6y^2 + 3=0$$
Infinity curves can be visualised (or determined not to exist) for a given centre by making a complex plot of the centre's location for the triangles $(-1,0),(1,0),(x,y)$ with varying $z=x+yi$. Here is such a plot for $X_{22}$; the infinity curve is white and marks discontinuities in the hue.

The file infcurves has polynomials describing infinity curves up to $X_{70}$ (also the upper limit of the centres that can be computed by the Python module at the time of posting this question). However, I have been unable to fully reduce some of the polynomials to match the real appearance of their corresponding curves, and this is why I ask this question.

Take for example $X_{29}$ with centre function $\frac{\sec A}{\cos B+\cos C}$. Its complex plot looks like this, the infinity curve being a simple W-shape on the upper half-plane:

The polynomial I have computed as $\infty_{29}$, on the other hand, produces that and more:
$$27 x^{16} + 144 x^{14} y^{2} - 216 x^{14} + 306 x^{12} y^{4} - 864 x^{12} y^{2} + 756 x^{12} + 324 x^{10} y^{6} - 1404 x^{10} y^{4} + 2160 x^{10} y^{2} - 1512 x^{10} + 171 x^{8} y^{8} - 1180 x^{8} y^{6} + 2430 x^{8} y^{4} - 2880 x^{8} y^{2} + 1890 x^{8} + 36 x^{6} y^{10} - 540 x^{6} y^{8} + 1480 x^{6} y^{6} - 1800 x^{6} y^{4} + 2160 x^{6} y^{2} - 1512 x^{6} - 132 x^{4} y^{10} + 530 x^{4} y^{8} - 600 x^{4} y^{6} + 270 x^{4} y^{4} - 864 x^{4} y^{2} + 756 x^{4} - 16 x^{2} y^{12} + 92 x^{2} y^{10} - 124 x^{2} y^{8} - 140 x^{2} y^{6} + 324 x^{2} y^{4} + 144 x^{2} y^{2} - 216 x^{2} + 4 y^{10} - 37 y^{8} + 116 y^{6} - 126 y^{4} + 27=0$$

This curve appears to be decomposable into four parts, one of which is the one I want. The problem is that the polynomial is absolutely irreducible, something I have checked with my implementation of Gao's factorisation algorithm (one of whose steps I inquired about in this question). I want to eliminate the unwanted branches of this curve, but factoring does not seem to be the way.

  Given an irreducible algebraic curve with several distinct branches like $\infty_{29}$ above, how can I select a specific branch and remove the others?

In general if you are given an explicit formula for a polynomial $f(x,y):=\sum_{(i,j)} a_{i,j}x^iy^j \in k[x,y]$ where $k$ is a subfield of the field $\mathbb{C}$ of complex numbers, it is difficult to determine if $f$ is an irreducible polynomial in $k[x,y]$.
If the ideal $I:=(f)\subseteq k[x,y]$ is non-prime, it is difficult to calculate the irreducible components $f=f_1\cdots f_k$ of $f$. I dont think there are any "general methods". How do you check that the polynomial is "absolutely irreducible" on a computer?
Note: A computer has "finite memory", hence when you calculate on a computer you calculate in a finite field with large characteristic. So if you have an algorithm on your computer that claims to "prove a polynomial is irreducible", this algorithm proves it is irreducible in a polynomial ring over a finite field.
Example: Let $A:=\mathbb{Z}[x_1,..,x_n]$ be the polynomial ring in $n$ variables over the integers and assume $p>0$ is the largest prime expressible on your computer. Let $k:=\mathbb{Z}/p\mathbb{Z}$.
Assume $F(x_1,..,x_n):=f_1(x_i)\cdots f_k(x_i)+pf(x_i)\in A$ is an irreducible polynomial. Your computer is working in the polynomial ring $B:=k[x_1,..,x_n]$ and in this ring (when reducing $F$ modulo the prime $p$) you get the polynomial
$$ \overline{F}=\overline{f_1}(x_i)\cdots \overline{f_k}(x_j),$$
and the polynomial $\overline{F}$ is not irreducible in $B$. Hence the original polynomial $F$ is irreducible in $A$ but your computer does not detect this since it is working with the polynomial ring $B$.
Comment: "This curve appears to be decomposable into four parts, one of which is the one I want. The problem is that the polynomial is absolutely irreducible, something I have checked with my implementation of Gao's factorisation algorithm (one of whose steps I inquired about in this question). I want to eliminate the unwanted branches of this curve, but factoring does not seem to be the way."
In general: A computer cannot detect if a polynomial is irreducble in $\mathbb{Z}[x_i]$ or $\mathbb{Q}[x_i]$ because it has "finite memory" and is working with polynomials in a polynomial ring over a finite field.
Example: Let $p>0$ be a prime number and consider the polynomial $$f(x):=x^2+p\in A:=\mathbb{Q}[x].$$
Let $p$ be the largest prime expressible on your computer.
You can yourself verify that $f(x)$ is irreducible in $A$ but your computer believes there is an equality $f(x)=x^2$ which is a reducible polynomial, since your computer calculates in the field $\mathbb{F}_p:=\mathbb{Z}/p\mathbb{Z}$ and the polynomial ring $\mathbb{F}_p[x]$.
Here is a post on the problem of studying the number of solutions to polynomial equations and computer algebra:
When does a system of polynomial equations have infinitely many solutions?


Why is this not a linear transformation from P2 to P3? $L(p(x)) = x^2 + p(x)$

I haven't gotten any homework problems that aren't a linear transformation, so I found a problem where this isn't the case. I know the two rules needed to prove it is a linear transformation, and I tried them here:

$L(a(p(x)) = ax^2 + ap(x)$ = $a(x^2 + p(x))$ = $aL(p(x))$

$L(p(x) + q(x))$ = $x^2 + (p(x) + q(x))$ = $x^2 + p(x) + q(x)$

$L(p(x)) + L(q(x))$ = $2x^2 + p(x) + q(x)$, so it is not equal to the above expression and therefore it is not a linear transformation.

Did I work this out right?

The equation $L(ap(x))=ax^2+ap(x)$ isn't right.  To compute $L(ap(x))$, you look at the formula for $L(p(x))$ and plug in "$ap(x)$" for "$p(x)$", so you get $L(ap(x))=x^2+ap(x)$.  Your computation for addition is correct, however.

To show that $L$ is not linear, you need to show that it is not true that $L(p(x)+q(x))=L(p(x))+L(q(x))$ for all $p$ and $q$ (or the corresponding statement for scalar multiplication).   To show this, you need to actually produce a counterexample.  That is, can you write down any specific polynomials $p(x)$ and $q(x)$ such that $L(p(x)+q(x))\neq L(p(x))+L(q(x))$?  (This shouldn't be hard from what you've done so far!)

In a linear function (transformation) the standard projections  are of the 1st degree...here you have a quadratic !


How do I find the partial sum of this So I have a sum defined below:

$$
\sum_{m=1}^n 2^{-m}
$$

I know the partial sum equals

$$
\frac{1}{2^n}(2^n - 1)\
$$

But how do you go from one to the other?

Let
$$S=\sum_{k=1}^n 2^{-k}=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots +\frac{1}{2^n}.\tag{1}$$
Then
$$2S=1+\frac{1}{2}+\frac{1}{2^2}+\cdots+\frac{1}{2^{n-1}}.\tag{2}$$
From (1) and (2), by subtraction we obtain
$$S=1-\frac{1}{2^n}$$
(note the massive amount of cancellation). Now we are almost at the desired expression.


Probability of stepping on n-th field in game where you move using dice We play a game where in each round we roll a six-sided dice and move the appropriate number of squares. How likely are we to step on the $n$-th field during the game, if we started with the number $0$?
The answer is sufficient in the form of a recurrent formula, which refers to a constant number of values for the lower one. Can you use only $2$ values for lower?

I am kinda lost here. I did bit know how even approach this.
Thanks to anyone who can help me guide to right direction
I made this:
| 1 | 1                                             |
| 2 | 1+1,2                                         |
| 3 | 1+1+1, 2+1, 3                                 |
| 4 | 1+1+1+1, 1+1+2, 1+3, 2+2, 4                   |
| 5 | 1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 1+4, 2+3, 5 |

But I can not see any pattern or how I can calculate probability from it. Does order of numbers matter ?

For $n=1\dots 6$ we have:
$$
p_n=\frac16+\frac16\sum_{k=1}^{n-1}p_{n-k}\implies p_n=\frac16\left(\frac76\right)^{n-1}\tag1
$$
Indeed (1) obviously holds for $p_1$ and by induction:
$$
p_n=\frac16+\frac1{6}\sum_{k=1}^{n-1}\frac1{6}\left(\frac76\right)^{k-1}
=\frac16+\frac1{36}\frac{\left(\frac76\right)^{n-1}-1}{\frac76-1}=
\frac16\left(\frac76\right)^{n-1}.
$$
For $n>6$ the probabilities can be computed by the following formula:
$$
p_n=\frac16\sum_{k=1}^{6}p_{n-k}=\frac{7p_{n-1}-p_{n-7}}6.\tag2
$$
The rightmost expression in $(2)$ is valid for $n>7$. It can be used for $n=7$ with the convention $p_0=1$.

For large $n$:

For $n$ that is large enough, each field have the same probability
to be landed.
The expected value for a 6-sided dice is $3.5$

Thus, the probability to land on $n$ in the limit is
$$\lim_{n \to \infty} p_n=\frac{1}{3.5}= 0.285$$
I am not an expert, so take my solution with a grain of salt.


mean square convergence vs almost sure convergence I saw a few examples that show that almost sure convergence doesn't imply convergence in mean square. Can anyone find an example of a random series that converges in mean square but doesn't converge almost surely?

Look at

X[n,w]=exp(-n^2*(w-1/n)) where w is in [0,1] (set of all out comes) and n is the time index.

Only for w=0 it does not converge so it almost surely converges (prob 1). But when it does not converge (i.e. w=0) the sequence goes to infinity exponentially fast making it not converging in mean square sense.


Riemann hypothesis and prime distribution What exactly does the Riemann hypothesis imply for the prime numbers?
Since the explicit formula is independent of the Riemann hypothesis, what would it actually mean for the primes if all the nontrivial zeros of the zeta function had real part 0.5? Is there some sort of a "simple" explanation for that?

The Riemann hypothesis says that for any real number $x$ the number of prime numbers less than $x$ is
approximately $\mathrm{Li}(x)$ and this approximation is essentially square root
accurate. More precisely,
$$
\pi(x)=\mathrm{Li}(x)+O(\sqrt{x}\log(x)).
$$
"Von Koch (1901) proved that the Riemann hypothesis implies the "best possible" bound for the error of the prime number theorem."
References at this site:
How related is the distribution of primes to the Riemann Hypothesis?
What is the link between Primes and zeroes of Riemann zeta function?

Thanks Dietrich Burde, I've checked the links you mentioned and in the first response to the first link (How related is the distribution of primes to the Riemann Hypothesis?) it says: "Knowledge of the real part of the location of the zeta zeros translates into knowledge of the distribution of primes." Is it possible to clarify that "knowledge"? What do I know if I assume RH? And how exactly do I gain this knowledge?


Help to solve this integral :) $$ g(t) = A \int_{-\infty}^{+\infty} h(\omega) f(t-\omega) d\omega$$

$$h(t) = \left\{\begin{array}{ll} A & 0\leq t\leq {T\over2}\\ 0 & \mbox{otherwise} \end{array}\right.     $$

$$f(t) = \left\{\begin{array}{ll} A & {T\over2}\leq t\leq T \\ 0 & \mbox{otherwise} \end{array}\right.     $$

I didn't find a way to solve it :(, please help

The given expression is the convolution between $h(t)$ and $f(t)$

$$
 g(t) = \left\{
\begin{array}{ll} 0 & t\leq {T\over2}  \ \mbox{or}\  t\geq {3T\over2}\\
A^3\left(t-{T\over2}\right) & {T\over2}\leq t\leq {T}\\
A^3\left({3T\over2}-t\right) & {T}\leq t\leq {3T\over2} \end{array} \right.
$$

A correct result has already been given; the following just examines some of the calculations in detail.

The expression $f(t - \omega)$ in the integrand is non-zero precisely when
$$\frac T 2 \le t - \omega \le T.$$
Multiplying each part by $-1$ reverses the direction of the inequalities:
$$-T \le \omega - t \le -\frac T 2,$$
so
$$t - T \le \omega \le t - \frac T 2.$$

So this part of the integrand is non-zero just when $\omega$ is in the interval
$\left[t - T, t - \frac T 2\right].$
The other part of the integrand is non-zero when $\omega$ is in
$\left[0, \frac T 2\right].$
The three cases arise from whether one interval overlaps the other on the left, on the right, or not at all.


Does e = limit as x tends to negative infinity hold true? Does $$e=\displaystyle\lim_{x \to -\infty}\left(1+\frac{1}{x}\right)^x\qquad\quad?$$

...or, in other words, rewrite the expression as
$$
\lim_{y \to \infty} \frac{1}{\bigg(1-\frac{1}{y}\bigg)^y}
$$

if base tends to 1 after taking its separate limit and power tends to infinity
then use below formula this type of questions ...

       lim         (base-1)(power)
      x->infinity
    e


Why do people use "it is easy to prove"? Math is not generally what I am doing, but I have to read some literature and articles in dynamic systems and complexity theory. What I noticed is that authors tend to use (quite frequently) the phrase "it is easy to see/prove/verify/..." in the manuscripts. But to me, it is usually not easy at all; maybe because I haven't spent much time in the field, maybe not.

My question is: why do people use the phrase "it is easy" in their proofs?

P.S. I hope this question is not too subjective, and has some value for the community.

Use of "it is easy to see that" is common and traditional in mathematical writing, but it is not exactly a proud tradition: really good mathematical exposition uses this and similar locutions very sparingly.

To be more specific, I think it is bad writing to say "It is easy to see that X is true" and say no more about how to prove X.  If this occurs in formal mathematical writing and all else is as it should be, then no information is being conveyed.  In other words, what other reason is there to assert that X is true and say no more about the proof except that the author expects the reader to be able to supply the details unassisted?  If you are skipping the proof for any other reason, you had better say something!

[And of course some of the harm is psychological.  If you're carefully reading a text or paper that asserts X is true and says nothing else about it, you know you need to stop and think about how to prove X.  If "it is easy to see X" then after every minute or so part of your brain will quit thinking about how to prove X and think, "They said it was easy to see this, and I can't see it at all.  What am I, stupid?"  I definitely remember thinking this way when I started out reading "serious" math books.]

When I referee papers I often suggest that authors suppress their "it is easy to see that"'s.  As others have said in the comments, as a careful, skeptical reader, you also need to stop and be sure that indeed you can supply the proof yourself, and it is notorious among mathematicians that such phrases are likely places to find gaps in mathematical arguments.  But it is just as easy -- in fact, easier -- to have a gap in the argument where you don't have any text at all, so writing "it is easy to see that" is not really the guilty party but rather a possible piece of incriminating evidence.

So if it's not so good to write this, why do people write this way?  And they certainly do: I happened to be editing my commutative algebra notes when I read this question, so out of curiosity I searched for "easy" and found about ten instances of "it is easy to see that" in 265 pages of notes.  About half of them I simply took out.  The other half I thought were okay because I didn't just say "it is easy to see that": I went on to explain why it was easy!  So having caught myself doing what I said not to, I can reflect on some causes:

1) Tradition/habit.

I have read "it is easy to see that" thousands of times, so it is in my vocabulary whether I like it or not.  Most mathematicians know that they have funny phrases which appear ubiquitously in mathematical writing but not in the rest of their lives: one of the very first questions I answered on this site was about the meaning and use of "in the sequel".  In the year or so since then I have observed it in my own writing: it just fits in there.  You have to really actively dislike some of these standard locutions in order to avoid writing them yourself.  For instance, I have more than a thousand pages of mathematical writings available online and I challenge anyone to find "by inspection" anywhere in these.  "By inspection" is the deformed cousin of "it is easy to see that": whereas at least it is easy to see what "it is easy to see that" means, even the meaning of "by inspection" is obscure.

2) A conflation of formal writing and informal writing / speaking / teaching.

The way you speak mathematics to someone else is very different from the way you write it: it is much more temporal.  If you are teaching someone new mathematics then most often they cannot verify / process / understand every single mathematical statement you make, in real time, so they have to make choices about exactly what to think about as you're talking to them.  In spoken conversation it's extremely useful to say "this is easy": by saying it, you're cueing the listener that it's safe to direct her attention elsewhere.  Also, because when you talk -- or write informally --  you don't give anywhere near as complete information as you do in formal mathematical writing, commentary on what you're skipping becomes more important.  For instance, in an intermediate level graduate course I may prove approximately 2/3 of the theorems I state in class.  If I'm skipping something, it's probably because it's too easy or too hard.  I had better say which it is!

3) Immaturity/Laziness.

Certainly when you're reading your own writing and you find "it is easy to see that", you need to stop short and make sure you know exactly what you omitted.  If it's not easy for you to see what you wrote it was easy to see, you may have a serious problem: indeed, you may be papering over a gap in your argument.  To do this intentionally is a sign of great mathematical immaturity -- someone who hides (in plain sight!) what they don't know in this way is not going to make it very far in this profession -- but even doing it unintentionally is something that most mathematicians largely grow out of with experience.

I know of at least one case where someone did this with the intention of intimidating the referees away from calling them on their claim. "It's easy to prove that..." i.e. "I dare you, referee, to say this isn't true! I will make you look like an idiot!"


Different methods to compute $\sum\limits_{k=1}^\infty \frac{1}{k^2}$ (Basel problem) As I have heard people did not trust Euler when he first discovered the formula (solution of the Basel problem)
$$\zeta(2)=\sum_{k=1}^\infty \frac{1}{k^2}=\frac{\pi^2}{6}.$$
However, Euler was Euler and he gave other proofs.

I believe many of you know some nice proofs of this, can you please share it with us?

OK, here's my favorite. I thought of this after reading a proof from the book "Proofs from the book" by Aigner & Ziegler, but later I found more or less the same proof as mine in a paper published a few years earlier by Josef Hofbauer. On Robin's list, the proof most similar to this is number 9
(EDIT: ...which is actually the proof that I read in Aigner & Ziegler).

When $0 < x < \pi/2$ we have $0<\sin x < x < \tan x$ and thus
$$\frac{1}{\tan^2 x} < \frac{1}{x^2} < \frac{1}{\sin^2 x}.$$
Note that $1/\tan^2 x = 1/\sin^2 x - 1$.
Split the interval $(0,\pi/2)$ into $2^n$ equal parts, and sum
the inequality over the (inner) "gridpoints" $x_k=(\pi/2) \cdot (k/2^n)$:
$$\sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k} - \sum_{k=1}^{2^n-1} 1 < \sum_{k=1}^{2^n-1} \frac{1}{x_k^2} < \sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k}.$$
Denoting the sum on the right-hand side by $S_n$, we can write this as
$$S_n - (2^n - 1) < \sum_{k=1}^{2^n-1} \left( \frac{2 \cdot 2^n}{\pi} \right)^2 \frac{1}{k^2} < S_n.$$

Although $S_n$ looks like a complicated sum, it can actually be computed fairly easily. To begin with,
$$\frac{1}{\sin^2 x} + \frac{1}{\sin^2 (\frac{\pi}{2}-x)} = \frac{\cos^2 x + \sin^2 x}{\cos^2 x \cdot \sin^2 x} = \frac{4}{\sin^2 2x}.$$
Therefore, if we pair up the terms in the sum $S_n$ except the midpoint $\pi/4$ (take the point $x_k$ in the left half of the interval $(0,\pi/2)$ together with the point $\pi/2-x_k$ in the right half) we get 4 times a sum of the same form, but taking twice as big steps so that we only sum over every other gridpoint; that is, over those gridpoints that correspond to splitting the interval into $2^{n-1}$ parts. And the midpoint $\pi/4$ contributes with $1/\sin^2(\pi/4)=2$ to the sum. In short,
$$S_n = 4 S_{n-1} + 2.$$
Since $S_1=2$, the solution of this recurrence is
$$S_n = \frac{2(4^n-1)}{3}.$$
(For example like this: the particular (constant) solution $(S_p)_n = -2/3$ plus the general solution to the homogeneous equation $(S_h)_n = A \cdot 4^n$, with the constant $A$ determined by the initial condition $S_1=(S_p)_1+(S_h)_1=2$.)

We now have
$$ \frac{2(4^n-1)}{3} - (2^n-1) \leq  \frac{4^{n+1}}{\pi^2} \sum_{k=1}^{2^n-1} \frac{1}{k^2}  \leq \frac{2(4^n-1)}{3}.$$
Multiply by $\pi^2/4^{n+1}$ and let $n\to\infty$. This squeezes the partial sums between two sequences both tending to $\pi^2/6$. Voilà!

The following proof is by Khalaf Ruhemi ( he is not a MSE member)
By partial fraction decomposition, we have
$$\frac{y}{(1+y^2)(y^2+x^2)}=\frac{1}{x^2-1}\left(\frac{y}{1+y^2}-\frac{y}{y^2+x^2}\right).$$
Integrate both sides from $y=0$ to $y=\infty$,
\begin{gather*}
\int_0^\infty\frac{y}{(1+y^2)(y^2+x^2)}\mathrm{d}y=\frac{1}{x^2-1}\int_0^\infty\left[\frac{y}{1+y^2}-\frac{y}{y^2+x^2}\right]\mathrm{d}y\\
=\frac{1}{x^2-1}\left[\frac12\ln(1+y^2)-\frac12\ln(y^2+x^2)\right]_0^\infty=\frac{1}{2(x^2-1)}\left[\ln\left(\frac{1+y^2}{y^2+x^2}\right)\right]_0^\infty\\
=\frac{1}{2(x^2-1)}\left[\ln(1)-\ln\left(\frac{1}{x^2}\right)\right]=\frac{1}{2(x^2-1)}\left[2\ln(x)\right]=\frac{\ln(x)}{x^2-1}.
\end{gather*}
Next, integrate both sides from $x=0$ to $x=\infty$
\begin{gather*}
\int_0^\infty\frac{\ln(x)}{x^2-1}\mathrm{d}x=\int_0^\infty\int_0^\infty\frac{y}{(1+y^2)(y^2+x^2)}\mathrm{d}y\,\mathrm{d}x\\
\{\text{change the order of integration}\}\\
=\int_0^\infty\frac{1}{1+y^2}\left[\int_0^\infty\frac{y\,\mathrm{d}y}{y^2+x^2}\right]\mathrm{d}y\\
=\int_0^\infty\frac{1}{1+y^2}\left[\arctan\left(\frac{x}{y}\right)\right]_0^\infty dy=\int_0^\infty\frac{1}{1+y^2}\left[\frac{\pi}{2}-0\right] \mathrm{d}y\\
=\frac{\pi}{2}\int_0^\infty\frac{1}{1+y^2} dy=\frac{\pi}{2}\arctan(y)\bigg|_0^\infty=\frac{\pi}{2}\cdot\frac{\pi}{2}=\frac{\pi^2}{4}.
\end{gather*}
Thus,
\begin{gather*}
\frac{\pi^2}{4}=\int_0^\infty\frac{\ln(x)}{x^2-1}\mathrm{d}x=\left(\int_0^1+\int_1^\infty\right)\frac{\ln(x)}{x^2-1}\mathrm{d}x\\
=\int_0^1\frac{\ln(x)}{x^2-1}\mathrm{d}x+\underbrace{\int_1^\infty\frac{\ln(x)}{x^2-1}\mathrm{d}x}_{x\to1/x}\\
=2\int_0^1\frac{\ln(x)}{x^2-1}\mathrm{d}x=-\int_0^1\frac{\ln(x)}{1-x}\mathrm{d}x-\int_0^1\frac{\ln(x)}{1+x}\mathrm{d}x\\
\left\{\text{use $\frac{1}{1+x}=\frac{1}{1-x}-\frac{2x}{1-x^2}$ in the second integral}\right\}\\
=-2\int_0^1\frac{\ln(x)}{1-x}\mathrm{d}x+2\underbrace{\int_0^1\frac{x\ln(x)}{1-x^2}\mathrm{d}x}_{x^2\to x}\\
=-2\int_0^1\frac{\ln(x)}{1-x}\mathrm{d}x+\frac12\int_0^1\frac{\ln(x)}{1-x}\mathrm{d}x\\
=-\frac32\int_0^1\frac{\ln(x)}{1-x}\mathrm{d}x\overset{1-x\to y}{=}-\frac32\int_0^1\frac{\ln(1-y)}{y}\mathrm{d}y\\
\{\text{expand $\ln(1-y)$ in series}\}\\
=\frac32\sum_{n=1}^\infty \frac{1}{n}\int_0^1 y^{n-1}\mathrm{d}y=\frac32\sum_{n=1}^\infty\frac{1}{n^2}=\frac{3}{2}\zeta(2).
\end{gather*}
So we have
$$\frac{\pi^2}{4}=\frac{3}{2}\zeta(2)\Longrightarrow \zeta(2)=\frac{\pi^2}{6}.$$


Solve recurrence equation: $a_{n}=(n-1)(a_{n-1}+a_{n-2})$ Find and solve recurrence equation $a_{n}$, where $a_{n}$ is the number of derangement in permutation $\pi\in S_{n}$, and $\forall_{i\in \mathbb{N}_{n}}\pi(i)\ne i$.
I managed to find the equation:
$$
a_{n} =
\begin{cases}
1,  & \text{if $n$ = 0} \\
0, & \text{if $n$ = 1}  \\
(n-1)(a_{n-1}+a_{n-2}), & \text{if $n\ge2$}
\end{cases},
$$
but I don't know how to solve it. Only managed to get to this:
$A(x) = 1+\sum^\infty_{n=0}{(n+1)a_{n+1}x^{n+2}}+\sum^\infty_{n=0}{(n+1)a_{n}x^{n+2}}$.

the solution is given by the Gamma-function, $$a(n)=\frac{\Gamma (n+1,-1)-\Gamma
   (2,-1) \Gamma (n+1)}{e-\Gamma
   (2,-1)}$$


Prove that $f(x_n^+)-f({x_n}^-)=2^{-n}$ Let $x_n$ be an enumeration of $\Bbb Q\cap (0,1)$.

Let $\Omega_x=\{n: x_n<x\}$.

Let $$f:(0,1)\to \Bbb R\\f(x)=\sum_{n\in\Omega_x}2^{-n}$$

Prove that $\lim\limits_{x\to x_n^+} f(x)-\lim\limits_{x\to x_n^-}f(x)=2^{-n}$. I've been trying useless stuff such as writing the limits as $f(x+h), h\to 0$, trying to rewrite the sets in any useful manner, but there's no case, I couldn't solve this.

Could anyone give me some hints to head for the right direction?

Note that $f$ is an increasing function, so the limits are well-defined.

Fix $n\in \mathbb N$.

Let  $m\in \mathbb N$ be arbitrary.

Note that  $\displaystyle f(x_n+\frac1m)-f(x_n-\frac1m)=\sum_{k\in \Omega_{x_n+\frac1m}\setminus\Omega_{x_n-\frac1m}} 2^{-k}$.

Let $A_m=\Omega_{x_n+\frac1m}\setminus\Omega_{x_n-\frac1m}=\{k, x_k\in \mathbb Q\cap [x_n-\frac1m, x_n+\frac1m(\}$.

Note that $A_m$ is a decreasing sequence, and $\bigcap_mA_m=\{n\}$

Rewriting things a little, we have  $\displaystyle \sum_{k\in \Omega_{x_n+\frac1m}\setminus\Omega_{x_n-\frac1m}} 2^{-k}=2^{-n}+\sum_{k\in A_m\setminus \{n\}}2^{-k}$.

Hence $\displaystyle f(x_n+\frac1m)-f(x_n-\frac1m)=2^{-n}+\sum_{k\in A_m\setminus \{n\}}2^{-k}$.

It remains to prove that $\displaystyle \lim_{m\to \infty}\sum_{k\in A_m\setminus \{n\}}2^{-k}=0$ and we're done.

Since the sets  $A_m\setminus\{n\}$ are decreasing, the sequence $\displaystyle s_m:=\left(\sum_{k\in A_m\setminus \{n\}}2^{-k}\right)_m$ is decreasing, but also bounded below by $0$, hence convergent.

Now, consider the sequence $a_m=\min(A_m\setminus \{n\})$.

Since $\displaystyle \bigcap_m\left(A_m\setminus \{n\}\right)=\emptyset$ it must be that $\forall k, \exists N, \forall l\geq N, a_l\neq a_k$.

Therefore, $a_m$ is not bounded (otherwise it takes finitely many different values, and one of those values occur infinitely many times, contradicting the previous line).

Consequently, $a_m$ has a monotonic subsequence that goes to $\infty$, say $ a_{m_{p}}\to \infty$.

Finally, notice that $\displaystyle 0\leq s_{m_{p}}\leq  \sum_{k\geq a_{m_{p}} }2^{-k}$.

The sum on the right goes to $0$ as $p\to \infty$ (since it is a subsequence of the sequence $(\sum_{k\geq p} 2^{-k})_p)$.

Therefore, $s_m$ is convergent and $s_m$ has a subsequence that goes to $0$. Hence $s_m$ converges to $0$.

This function $f(x)$ snaps to a value as $x$ hits one of the values in the enumeration, holds that value until we hit the successive value of the enumeration.  So lets focus in on a particular $x_n$ and  pick $h>0$ so that is smaller than the difference between the $n-1$ and $n$ terms AND $n$ and $n+1 $terms :
$$
x_{n}+h < x_{n+1}    \quad    (x_n,x_n+h,x_{n+1})\\
x_{n-1}+ h < x_n - h\quad      (x_{n-1}, x_{n-1} - h, ,x_n )
$$
So we can easily calculate what $f$ is for values over this range.

Now pick $k_1,k_2$ such that  $0< k_1,k_2 < h$.

Then we have for any such $k_1,k_2$, the difference between the value of the functions is just the last term of the summation $\frac 1 {2^n}$.

$$f(x_n-k_1) - f(x_n+k_2) = \frac 1 {2^n}$$

hence the result .


Different method to take limit gives different results? Question:

  $$\lim_{x\to0}\frac{\sin(3x^2)}{\log\cos(2x^2-x)}=?$$

My method:

Apply L-H rule, since the form is $\frac 00$:

$$\lim_{x\to0}-\frac{6x\cos(3x^2)\cos(2x^2-x)}{\sin(2x^2-x)\cdot(4x-1)}$$
Putting in the value for the determinate terms we get:
$$\lim_{x\to0}\frac{6x}{\sin(2x^2-x)}$$
Apply L-H rule again to get:
$$\lim_{x\to0}\frac{6}{4x\cos(2x^2-x)}$$

Now, the numerator is $\not\to0$ and the denominator is $\to 0$, thus the limit is undefined! But, the correct answer is not undefined. I don't want to know the correct solution, but I wish to know where I went wrong.

The problem is that after$$\lim_{x\to0}\frac{6x}{\sin(2x^2-x)},$$you should have obtained$$\lim_{x\to0}\frac6{(2x-1)\cos(2x^2-x)}=-6.$$


Number of permutations in which a integer appears before other Two integers $x$, and $y$ are fixed such that $1 \le x < y \le n$.
I am trying to count the number of permutations of {$1,2,3,4,...,n$}
($n \ge 2$) were $x$ appears to the left of $y$.

I think I should use product rule in this case but I am not sure.

Hint:

To answer how many of these will have $x$ to the left of $y$,

think about how many of these will have $x$ to the right of $y$.

Are these numbers related?

  There are exactly as many permutations with $x$ to the left of $y$ as there are having $x$ to the right of $y$.  See if you can explain why using a bijective function between them.

What does this imply about the total number of permutations in relation to the number of permutations with $x$ to the left of $y$?

For a direct counting argument instead of a combinatorial argument, first pick which two spaces the pair $x,y$ will occupy.  Whichever two spaces you picked, put $x$ in the left space and $y$ in the right.  From there, fill in the remaining spaces however you prefer (left to right or smallest to largest, etc...).

  There are then $\binom{n}{2}$ ways of picking which two spaces $x$ and $y$ collectively occupy and $(n-2)!$ number of ways of picking the arrangement of the remaining numbers.  Apply multiplication rule.

Take the position of $y$ and make this partition of the set:

$$\{1,2,...,n\}=\{1,...,i\}\cup\{y\}\cup\{j,...,n\}$$

Now count when $x \in\{1,...,i\}$.

This is the canonical way to solve this kind of permutations, how it appear in textbooks (by example Bijective combinatorics if I remember correctly).

It works for a lot of words with order restrictions. In this case it is very easy cause there is only one restriction, i.e. $x<y$ and the answer is "trivialy" $n!/2$ (just by symmetry).