combinatorics - An identity for the factorial function

A friend of mine was doodling with numbers arranged somewhat reminiscent of Pascal's Triangle, where the first row was $ 1^{n-1} \ \ 2^{n-1} \ \cdots \ n^{n-1} $ and subsequent rows were computed by taking the difference of adjacent terms. He conjectured that the number we get at the end is $ n! $ but I've not been able to prove or disprove this. The first few computations are given below:
$$
\begin{pmatrix}
1 \\
\end{pmatrix}
$$

$$
\begin{pmatrix}
1 & & 2 \\
& 1 & \\
\end{pmatrix}
$$

$$
\begin{pmatrix}
1 & & 4 & & 9 \\

& 3 & & 5 & \\
& & 2 & & \\
\end{pmatrix}
$$

$$
\begin{pmatrix}
1 & & 8 & & 27 & & 64 \\
& 7 & & 19 & & 37 & \\
& & 12 & & 18 & & \\

& & & 6 & & & \\
\end{pmatrix}
$$

$$
\newcommand\pad[1]{\rlap{#1}\phantom{625}}
\begin{pmatrix}
1 & & 16 & & 81 & & 256 & & 625 \\
& 15 & & 65 & & 175 & & 369 & \\
& & 50 & & 110 & & 194 & & \\

& & & 60 & & 84 & & & \\
& & & & 24 & & & & \\
\end{pmatrix}
$$

I attempted to write down the general term and tried to reduce that to the required form. The general term worked out as
$$
\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} (i+1)^{n}.
$$
I tried applying various identities of the binomial coefficients but I'm barely making any progress. Any help would be appreciated.

Small note: If I instead start with the first row as $ 0^{n} \ \ 1^{n} \ \cdots \ n^{n} $ then I still get $n!$ at the end of the computation, and the general formula in this case works out as
$$
\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} i^{n}.
$$
In fact, we can start with any $n$ consecutive natural numbers, each raised to the $(n-1)$th power, and we still get $n!$ at the end of the computation.

Answer

The top rows are indeed made of the powers $i^n=P_n(i)$, which are polynomials of degree $n$, with the leading coefficient $1$.

On the next row you take the first order difference. By the binomial formula, we have

$$P_{n-1}(i)=P_n(i+1)-P_n(i)=i^n+ni^{n-1}+\cdots-i^n=ni^{n-1}+\cdots$$

which is a polynomial of degree $n-1$ with the leading coefficient $n$.

For the next row, $$P_{n-2}(i)=P_{n-1}(i+1)-P_{n-1}(i)=n(n-1)i^{n-2}+\cdots$$ and so on.

On the last row, we have a polynomial of degree $0$ with the leading coefficient $n!$, and all the rest has vanished.

---

Actually you will make the same observation starting with any polynomial in $i$: the final value is $p_nn!$, where $p_n$ is the initial leading coefficient. And if you enlarge the table to the right, the bottom row remains constant.

E.g.

$$2i^3+i\\\Delta_1=6i^2+6i+3\to2\cdot3\,i^2\\\Delta_2=12i+4\to2\cdot3\cdot2\,i^1\\\Delta_3=12\to2\cdot3\cdot2\cdot1\,i^0.$$

calculus - Contour Integral for Cosine and a rational function

I've been trying to figure out this integral via use of residues:

$$\int_{-\infty}^{\infty} \displaystyle \frac{\cos{5x}}{x^4+1}dx$$

The usual semicircle contour wont work for this guy as the integrated is unbounded.
My idea came from a book I was reading on contour integration, where we let

$$f(z) = \displaystyle\frac{e^{(-5iz)}}{2(z^4+1)}+\displaystyle\frac{e^{(5iz)}}{2(z^4+1)}$$

And do the integral in the complex play as follows:

$\gamma_{1}= \text{The contour taken to be the top half of the circle in the counter clockwise direction}$ This contour uses the second term in $f(z)$

$\gamma_{2}= \text{The contour taken from $-R$ to $R$ on the real axis}$

$\gamma_{3}= \text{The contour taken to be the bottom half of the circle in the clockwise direction}$ This uses the first term in $f(z)$.

In the end, the contours $\gamma_{1}$ and $\gamma_{3}$ are bounded and will tend to $0$ as $R$ goes to infinity, so that we're left with the two integrals that we want.

My issue now is that when computing residues..everything seems to be cancelling out and I'm getting $0$. Should I take different contour? I'm really not sure what I did wrong.

Answer

I've given the skeleton of my work below. Fill in any missing pieces and check your answer against mine.

Using $\gamma=[-R,R]\cup Re^{i[0,\pi]}$ and the simple poles at $\frac{1+i}{\sqrt2}$ and $\frac{-1+i}{\sqrt2}$ inside $\gamma$
$$
\begin{align}
\int_{-\infty}^\infty\frac{\cos(5x)}{x^4+1}\mathrm{d}x
&=\mathrm{Re}\left(\int_\gamma\frac{e^{i5z}}{z^4+1}\mathrm{d}z\right)\\
&=\mathrm{Re}\left(2\pi i\left(\left[\frac{e^{i5z}}{4z^3}\right]_{z=\frac{1+i}{\sqrt2}}

+\left[\frac{e^{i5z}}{4z^3}\right]_{z=\frac{-1+i}{\sqrt2}}\right)\right)\\
&=\mathrm{Re}\left(\frac{\pi}{2i}e^{-5/\sqrt2}\left(\frac{1+i}{\sqrt2}e^{i5/\sqrt2}
-\frac{1-i}{\sqrt2}e^{-i5/\sqrt2}
\right)\right)\\
&=\pi e^{-5/\sqrt2}\mathrm{Im}\left(\frac{1+i}{\sqrt2}e^{i5/\sqrt2}\right)\\
&=\pi e^{-5/\sqrt2}\mathrm{Im}\left(e^{i(5/\sqrt2+\pi/4)}\right)\\
&=\pi e^{-5/\sqrt2}\sin\left(\frac5{\sqrt2}+\frac\pi4\right)
\end{align}
$$
Mathematica 8 agrees numerically, but its closed form involves complex functions and looks nothing like what I have above.

real analysis - Pointwise convergence and uniform convergence of $f_n(x) = x^n(1-x)$

Ok, I am new to this pointwise and uniform convergence so don't mind if I make mistakes here.

Let: $f_n(x) = x^n(1-x), x \in [0,1]$

$f(x) = 0, x \in [0,1].$

1. Prove that $f_n$ converges to $f$ pointwisely on $[0,1]$




2. Prove that $f_n$ converges to $f$ uniformly on $[0,1].$

Attempt: For # 1: I've divided this into three cases.

Case 1. When, $x = 0, \lim_{n \to \infty} x^n(1-x) = 0$

Case 2. When, $x = 1, \lim_{n \to \infty} x^n(1-x) = 0$

Case 3. When, $0

I know in all cases the limit goes to 0, but I just wanted to make sure I don't miss anything.

For # 2: $f_n$ is uniformly converges to $f$ if $\sup_{\{a\leq x\leq b\}}\mid f_n(x) - f(x)\mid \to 0?$ Now what that'd be in this case? $\sup_{x\in[a,b]} f_n(x) = 0 = \sup_{x\in[a,b]} f \Rightarrow \mid 0 - 0\mid \to 0$? Is this what uniformly converges to $f$ mean here? If not, any explanation would be really appreciated. Thanks.

Answer

For #1 your approach is correct, and since $[0,1] = \{0\} \cup ( 0, 1 ) \cup \{ 1\}$ you have had all the possible cases.

In the second case, you do not have $\sup_{x \in [0,1]} f_n(x) = 0$, since for example $f_1\left(\frac{1}{2}\right) = \frac{1}{4}$.
However, you are right that $f_n$ converges uniform to 0 if $\sup_{x \in [0,1] } |f(x) | \to 0$, you can omit the $- f(x)$ since that is $0$. Note that $f_n(x) \ge 0$ for all $x \in [0,1]$, so we can omit the absolute value and just concentrate on the top of $f_n$.

And to find the top of $f_n$, we can differentiate $x^{n}- x^{n+1}$. This yields $nx^{n-1} - (n+1)x^n= x^{n-1}(n - (n+1) x)$. Take this to be $0$, which gives $x=0$ or $x=\frac{n}{n+1}$, note that should also consider $x=1$ since we may have that $f_n$ is strictly increasing on $[0,1]$. However, we have $f_n(0) =f_n(1)=0$, so the supremum of $f_n$ is $f_n \left( \frac{ n }{n+1} \right)= \frac{ n^n}{(n+1)^{n+1}}$, which goes to zero as $n \to \infty$.

linear algebra - Pseudo inverse interpretation

Consider two integers $m$ and $n$, with $m > n$, and $A$, $x$ and $b$ real matrices and vectors. In the case $A x = b$, with $A$ of dimension $m \times n$ (and therefore $x$ of dimension $n \times 1$ and $b$ of dimension $m \times 1$), the pseudo inverse can be interpreted as a projection of $b$ in the column space of $A$, that minimizes the $L^2$ norm.

However, in the case where $A$ is of dimension $n \times m$, (and $A$ has full rank), an infinite number of combinations of the column space vectors can decompose the vector $b$. Applying $A^+$ to b ($A^+$ pseudo inverse of $A$), only gives a single vector among those.

How can the pseudo inverse be interpreted in that case ? What are the properties of the vector $A^+ b$ ?

Answer

If $A$ is a linear mapping between two vector spaces, i.e. $A \,:\, U \to V$, then $$
A^+(v) = u \quad\textrm{iff}\quad u \in (\ker A)^\bot \text{ and } Au = P_{(\textrm{rng } A)}v
$$

Thus, you get $u$ from $v$ by first projecting $v$ orthogonally onto the range of $A$, then finding some $u'$ with $A(u')=v$, and finally projecting that $u'$ onto the orthogonal complement of the kernel of $A$. It doesn't matter which $u'$ you picked, since for two possible choices $u_1$,$u_2$, $u_1-u_2 \in \textrm{ker }A$, and thus $P_{(\ker A)^\bot}(u_1-u_2) = 0$, i.e. they get projected onto the same element $u$ in the end.

You also look at this another way. If you restrict $A$ to $(\ker A)^\bot$, then this restricted $A$ is injective and hence has an inverse (with range $(\ker A)^\bot$). You can then define the pseudo inverse as $$
A^+ := \left(\left.A\right|_{(\ker A)^\bot}\right)^{-1}P_{(\textrm{rng } A)}
$$

Your two cases amount to either $P_{(\ker A)^\bot}$ or $P_{(\textrm{rng } A)}$ being the identity, i.e. to either $\ker A = \emptyset$ or $\textrm{rng }A = V$.

calculus - How do I approach solving this indeterminate limit? $lim_limits{hto 0}frac{1}{h}lnleft(frac{2+h}{2}right)$

Disclaimer: I am a middle aged adult learning Calculus. This is not a student posting his homework assignment. Thank humanity for this great forum!

$$\lim_\limits{h\to 0}\frac{1}{h}\ln\left(\frac{2+h}{2}\right)$$

1) Can't directly sub the h. So, normally you reduce and cancel. Can you point me in the right direction? The directions say "manipulate the expression so L'Hopital's is used" I think L'hopital's is involved. Just not sure how to deal with the $\frac{1}{h}$

$$\lim_\limits{x\to \infty}\frac{x^k}{e^x}$$

2) Also, any tips on the one above? If $k$ is a positive integer, what is the limit above?

Thanks for any guidance.

multivariable calculus - The notation $frac{partial}{partial x}$

In Jost's Riemannian Geometry and Geometric Analysis (Sect. 1.2, Chap. 1), the tangent space at a point $x_0$ in $\mathbb{R}^d$ is defined as
$$T_{x_0}\mathbb R^d=\{x_0\}\times E$$
where $E$ is the vector space spanned by $\frac{\partial}{\partial x^1},\cdots,\frac{\partial}{\partial x^d}$. Then the books says: "Here, $\frac{\partial}{\partial x^1},\cdots,\frac{\partial}{\partial x^d}$ are the partial derivatives at the point $x_0$." This is where I get confused. They are the partial derivatives of what? The only partial derivative I know is that of a function, but no function is given here.

Sure, if one wants to argue that $\frac{\partial}{\partial x^1},\cdots,\frac{\partial}{\partial x^d}$ are just formal notations here that don't mean anything other than a formal basis of $E$, then I can accept that even though I have doubts. But then there comes something that confuses me even more. If $f:\mathbb R^d\to\mathbb R^c$ is a differentiable map, then the derivative of $f$ at $x_0$ is defined to be (Einstein convention is used below)
$$df(x_0):T_{x_0}\mathbb R^d\to T_{x_0}\mathbb{R}^c\\
\quad v^i\frac{\partial}{\partial x^i}\mapsto v^i\frac{\partial f^j}{\partial x^i}\frac{\partial}{\partial f^i}$$

So apparently $\frac{\partial}{\partial f^j}$ here depend on $f$ and are not arbitraily selected, so the notation cannot simply be a formal one, which brings me back to the original question: what does $\frac{\partial}{\partial x^i}$ and $\frac{\partial}{\partial f^j}$ mean?

Answer

The tangent space $T_pM$ can be seen as the space of local linear operators acting on the functions $f: M \rightarrow \mathbb R$. If you have vector $v\in T_pM$ you can define how it acts on a function:
$$ v(f) = \left.\frac{d f(\gamma_v(t))}{dt}\right|_{t=0} $$
where $\gamma_v$ is any curve on $M$ such that $\gamma_v(0) = p$ and $\frac{d\gamma_v}{dt}(0) = v$.

Given a coordinate system $(x_i)$ you can find that there exist vectors in $T_pM$ that act on functions exactly like the partial derivatives $\frac{\partial}{\partial x_i}$, that is $v_i(f) = \frac{\partial f}{\partial x_i}(p)$. They are therefore denoted $v_i = \frac{\partial}{\partial x_i}$. Such vectors form a basis of $T_pM$, so any vector can be written as $$ v = v^i \frac{\partial}{\partial x_i} $$

If the point of differentiation is obvious, the vetor can be denoted as $v_i=\left.\frac{\partial}{\partial x_i}\right|_p$. Sometimes $\frac{\partial}{\partial x_i}$ can also denote the whole vector field, defining a vector at every point of the manifold.

soft question - What's so special about the group axioms?

I've only just begun studying group theory (up to Lagrange) following on from vector spaces and I am still finding them almost frustratingly arbitrary. I'm not sure what exactly it is about the axioms that motivated them defining groups.

My textbook asks you to list 'common features' of vector spaces and then later defines a set of axioms for vector spaces under addition, scalar multiplication and both, noting that the axioms under addition form an Abelian group. So are groups just a generalisation of vector spaces under any binary operation?

My main problem is that the book notes that 'the axioms may seem rather arbitrary' and links groups with vector spaces but doesn't elaborate.

When introducing groups, you are tasked to complete Cayley tables for the symmetries of an equilateral triangle and square. Then, similarly to the delivery of vector spaces, notes that the tables have common properties (Closure, Identity, inverse and association) and defines a group as a set of elements under a binary operation that has these features.

So what's so important about these 4 properties? For example, if 1 or 2 the properties were excluded form the axioms, or we added an extra few properties as axioms how would that cripple the effectiveness of groups?

Are the group axioms ever difficult to work with or do they always work, forgive the crude Littlewood analogy, like a mathematical skeleton key?

What is it about these 4 properties that make groups such a powerful tool in mathematics and physics?

My best guess is that a group is the best way to express our sense of symmetry and what is symmetric mathematically, but I would prefer some elaboration.

Answer

Yes, groups express symmetries of objects. If you want a symmetry to be a way to map an object into itself which preserves some property (say, location of vertices on a square, or distance between points in the plane,) and you want symmetries to be things that you can (a) chain together and (b) undo, then you've got a group. (As long as you also admit the trivial symmetry.) In this picture of symmetries as mappings, you don't really have to specify associativity, as it's a natural aspect of anything that looks like composition of functions (more precisely, of anything which fits into a category.)

You shouldn't think that groups are just generalizations of vector spaces. Anything that's a generalization from one case is a bad generalization! Groups are also generalizations of numbers (under addition and, in some cases, multiplication), symmetries of geometric objects (both discrete ones you mention and continuous ones,) and functions, under not only addition and multiplication but, critically, composition. An important historical example was the group of permutations of roots of a polynomial, which is used in the proof that quintic equations can't be solved in radicals and has led to huge areas of modern math.

As for loosening and strengthening some of the axioms: if you throw out inverses, you get monoids (semigroups, if you also throw out the identity.) These are extremely important objects in their own right, but they're too general to have a nice structure theory. The biggest problem is with quotients: surjective homomorphisms $G\to H$ naturally correspond to "normal subgroups" $K\subset G$, i.e. subgroups with $gKg^{-1}\subset K$ for all $g\in G$. There's no such simple way to characterize quotients $M\to N$ of monoids in terms of submonoids, because there's not necessarily a $g^{-1}$ for every $g$, so the most basic isomorphism theorems, which lay the foundation for everything you're likely to learn in elementary group theory, are no longer true. Thus we like to use groups instead of monoids when we can, and many actual things in the world come as groups, so we do so.

Strengthening the axioms does not "cripple the effectiveness" of groups so much as weakening them does. Various objects subject to axioms extending those of a group include abelian groups, vector spaces, modules, rings and algebras over rings, topological groups, Lie groups, and many more, and all of these are of great importance. But there are groups that are none of these things, (every group is in some sense topological, but we don't always want to think about the topology) so we start with just a plain group and strengthen the axioms in appropriate contexts.

real analysis - Lower semi continuous of $f(x)$ when $g(x)$ is continuous

I'm using the definition of lower semi continuous as :

A function $f:X \to \Bbb R$ is said to be lower semi continuous if for each real $\alpha$ the set $\{x \in X: f(x)\le \alpha\}$ is closed , where $X$ is a metric space. Now consider the following example:

Let , $g:X\to \Bbb R$ be continuous and $x_0\in X$. Define , $f:X\to \Bbb R$ by $$ f(x)=\begin{cases}g(x) &\text{, if $x\not=x_0$}\\g(x_0)-1 &\text{ ,if $x=x_0$}\end{cases}$$

Show that $f$ is lower semi continuous.

Here , $f$ is continuous except $x_0$. So , lower semi continuous in $X\setminus \{x_0\}$. Now I want to show that $f$ is l.s.c. at $x_0$.

Let, $x\in S_{\delta}(x_0)$. Since $g$ is continuous so , $|g(x)-g(x_0)|<\epsilon\implies |f(x)-f(x_0)-1|<\epsilon$. Then, $f(x) - f(x_0) <1-\epsilon=\epsilon_1$(say). So , $f$ is l.s.c. at $x_0$.

Is it correct ?

Answer

Probably you have worked out everything in your mind. Your last inequality says $f(x) > f(x_0) + 1- \varepsilon$ for all $\varepsilon > 0$. This means $f(x) \ge f(x_0) + 1 > f(x_0) $. That is the set $\{x : f(x) > f(x_0)\}$ is open.

Another way is to note since you are in metric spaces, lower semicontinuity at point $x_0$ is equivalent to
\begin{align*}
\liminf_{x \to x_0} \, f(x) \ge f(x_0).
\end{align*}
The conclusion is then obvious.

Actually the inequality holds true for general topological spaces. We need to consider $x \to x_0$ as a net $\langle x_{\lambda} \rangle$ converging to $x_0$.

linear algebra - Intuition behind affine subsets?

I am working through Axler's "Linear Algebra Done Right" and I am having trouble intuiting some of the meaning behind affine subsets. According to 2 exercises in the book we have that

(1) A subset $A$ is affine if and only if for any $v,w\in A$ and any scalar $\lambda$, $\lambda v+(1-\lambda)w\in A$

(2) Given vectors $v_1,...,v_n\in V$ the subset $A$ of $V$ given by $A=\{\sum\lambda_iv_i:\lambda_i\in F,\sum\lambda_i=1\}$ is affine

I more or less understand the definition of affine subsets (they're sort of like subspaces without the identity and they're either disjoint or equal, like equivalence classes) and I more or less understand the mechanics of the proofs of these problems, but I have no intuition for why these conditions imply affine-ness. What's so special about linear combinations the sum of the scalars of which is $1$?

Answer

Remember that the straight line through points $w$ and $v$ is given by

$$\{w + \lambda (v-w): \lambda\in\mathbb R\}$$
Now a bit of algebra shows that
$$w + \lambda(v-w) = w + \lambda v -\lambda w = \lambda v + (1-\lambda) w$$
Or in short, the condition states that a subset is affine if and only if for any two points in that set, the straight line through those two points lies completely in that set.

For example, in three-dimensional space, the affine subsets are the full space (obviously), all planes, all straight lines, the single points (since for $v=w$ we get $\lambda v + (1-\lambda)v = v$) and the empty set.

real analysis - $f$ is linear and continuous at a point $implies f$ should be $f(x) =ax, $ for some $a in mathbb R$

Let $f$ be a real valued function defined on $\mathbb R$ such that $f(x+y)=f(x)+f(y)$.
Suppose there exists at least an element $x_0 \in \mathbb R$ such that $f$ is continuous at $x.$ Then prove that $f(x)=ax,\ \text{for some}\ x \in \mathbb R.$

Hints will be appreciated.

calculus - $limlimits_{xtoinfty } frac{ln x}{sqrt{x},{sin{x}}}$

What a weird function.

I tried to find out: $$\lim_{x\to\infty } \frac{\ln x}{\sqrt{x}\,{\sin{x}}}$$

So, I can't use L'Hopital 'cause there's no actual limit in the denominator. It doesn't exist.

Then, I tried to use Heine's theorem and chose two sequences, but yet I got the same limit.

I believe it does not converge. How can I prove it?

Thanks

Answer

You can consider a sequence $x_n = \pi n - 2^{-n}$. On this sequence your function will become unbounded while this sequence goes to infinity. Hence the limit does not exist.

geometry - Three circles within a larger circle

Let's say that the radius of the bigger circle is R. Every circle inside touches the perimeter of the bigger circle and two other circles. How to find the radius of the smaller circles (all are identical).

To illustrate:

Any tips and ideas would be awesome.

Answer

The middle stanza of Soddy's Kiss Precise gives the formula:

Four circles to the kissing come.
The smaller are the benter.
The bend is just the inverse of
The distance from the center.
Though their intrigue left Euclid dumb
There's now no need for rule of thumb.
Since zero bend's a dead straight line
And concave bends have minus sign,
The sum of the squares of all four bends
Is half the square of their sum.

Applied here it says $$\frac 3{r^2}+\frac 1{R^2}=\frac 12 (\frac 3r-\frac 1R)^2\\\frac 3{r^2}+\frac 1{R^2}=\frac {9}{2r^2}+\frac 1{2R^2}-\frac 3{rR}$$ As all the we can get is the ratio, let $r=1$ and we have $$3+\frac 1{R^2}=\frac 92+\frac 1{2R^2}-\frac 3R\\0=3R^2-6R-1\\R=\frac 16(6\pm\sqrt{48})=\frac 13(3\pm2\sqrt{3})$$ and we want the plus sign.

galois theory - Looking for examples of abelian extensions of $mathbb{Q}$ satisfying a certain condition

The Kronecker-Weber Theorem says that every abelian extension of $\mathbb{Q}$ is contained in some cyclotomic extension. One approach to prove this is via higher ramification groups. In this approach, there is a crucial step, which says

Let $K$ be an abelain extension of $\mathbb{Q}$ such that $[K:\mathbb{Q}]=p^m$ and $p$ is the only prime of $\mathbb{Z}$ which ramifies in $K$. To prove the Kronecker-Weber theorem, it is enough to prove that any such $K$ is contained in a cyclotomic extension.

I am looking for some examples such a $K$. Any help ?

Answer

$\Bbb Q(i), \Bbb Q(\sqrt 2), \Bbb Q(\cos(2\pi/9))$ are some examples among many others.

Formula for all terms in a sequence.

I am looking to find an algorithm for a repeating pattern, in order to solve a programming problem. I need a formula for all terms of the following sequence:

0, 2, 4, ..., 0, 2, 4, ...

The sequence would start at 0, and then increment by 2 until reaching 4 and then repeat itself with 0. I have worked with similar patterns, and they usually involve the modulus operator, and the number of repeating terms. For example, from what I understand I could get a repeating pattern just by applying the modulo to the index by the number of repeating terms.

This seems like it should be simple enough, but is eluding me and I do not have a mathematics background.

Answer

You could simply say that the $i$-th element of the sequence is the remainder of when you divide $2\cdot i$ by $6$.

That is, if you count $0$ as the zero-th element. If it's the first, just replace the $i$ with $(i-1)$.

---

For example:

• $0$ is the remainder when you divide $2\cdot 0$ by $6$


• $2$ is the remainder when you divide $2\cdot 1$ by $6$


• $4$ is the remainder when you divide $2\cdot 2$ by $6$


• $0$ is the remainder when you divide $2\cdot 3$ by $6$


• $2$ is the remainder when you divide $2\cdot 4$ by $6$


• $4$ is the remainder when you divide $2\cdot 5$ by $6$

So, if you want to calculate the $i$-th element in, say, Python, you would calculate it as

i_th_element = (2 * i) % 6

Solve the functional equation $f(xf(y)+x)=xy+f(x)$

Find all $f:\mathbb{R}\rightarrow\mathbb{R}$ so that $f(xf(y)+x)=xy+f(x)$.

If you put $x=1$ it's easy to prove that f is injective.
Now putting $y=0$ you can get that $f(0)=0$.

$y=\frac{-f(x)}{x}$ gives us $f(\frac{-f(x)}{x})=-1$

Answer

Set $x = 1$ and $y = t - f(1)$,

then $f(1+f(t - f(1))) = t$, for all $t \in \mathbb{R}$, hence $f$ is a surjective function.

So, $\exists\, y_1 \in \mathbb{R}$, s.t., $f(y_1) = 0$

Then, $$f(x) = f(x+f(y_1)x) = xy_1+f(x) \implies xy_1 = 0, \forall x \in \mathbb{R} \implies y_1 = 0$$

and $\exists\, y_2 \in \mathbb{R}$, s.t., $f(y_2) = -1$

Then, $$0 = f(0) = f(x+xf(y_2)) = xy_2 + f(x)$$

i.e., $f(x) = -y_2x$ for $x \in \mathbb{R}$.

Plugging it back in the functional equation we may verify $y_2 = \pm 1$.

abstract algebra - How to determine the minimal polynomial of $sqrt{3 + 2sqrt{2}}$ over $mathbb{Q}$?

I first let $\alpha = \sqrt{3 + 2\sqrt{2}}$ and $\alpha^2 - 3 = 2\sqrt{2}$. This gives us $(\alpha^3 - 2)^2 = 8$. Expand the polynomial we obtain that
$x^4 - 6x^2 +1$ has $\sqrt{3 + 2\sqrt{2}}$ as a root. But apparently this polynomial is not an irreducible polynomial over $\mathbb{Q}$. How should we determine the minimal polynomial in the first place? Many thanks!

Answer

Hint A minimal polynomial must be irreducible, but as you say, the polynomial $p$ you produced is not:
$$p(x) = (x^2 + 2 x - 1) (x^2 - 2 x - 1).$$

Since $p(\alpha) = 0$, however, $\alpha$ must divide one of these factors (and since $\alpha \not\in \Bbb Q$, that factor must itself be the irreducible polynomial of $\alpha$).

To see what's going on here, expand $(1 + \sqrt{2})^2$.

set theory - About sets and injections

Let $A,B$ be two sets.

Is there necessarily an injection from $A$ to $B$ or an injection from $B$ to $A$ ?

algebra precalculus - Find the coefficient of $x^{15}y^4$ in the expansion of $(2x – 3y)^{19}$

Not even sure I understand this question or know where to start, I understand the basics of finding coefficients but don't get how it's calculated "in the expansion of" another number. Looking for some sort of explanation as to how to solve this. I understand solving binomial coefficients but I'm not entirely sure how they related in this type of question.

numerical methods - Finding $L_2$ norm given uniform norm

Assume that a continuous function $f(x)$ has uniform norm 5 on the
interval [1,4]. What is the largest possible value of the $L_2$-norm of
$f(x)$ on the intervals [1,4] and on [2,4]?

From what I understand about norms, the $L_2$ norm is greater than the $L_\infty$ norm...and I don't see a bound of sorts. How would I deduce the answers?

Answer

Hint: if the uniform norm of f is 5 on [1,4] then $$\sup_{x\in [1,4]} |f(x)|=5$$

$$\int_{1}^{4}|f(x)|^2 dx \leq \int_{1}^{4} 5^2 dx $$

$$\int_{2}^{4}|f(x)|^2 dx \leq \int_{2}^{4} 5^2 dx $$

I think you might have been confused by the fact that "$L_2$ is greater than the uniform norm". In fact it is true that some norms are greater than others but they can be bounded by a smaller norm up to a constant. For instance in $\mathbb{R^n}$ in general $L_1\geq L_{\infty}$ but $L_1\leq n L_{\infty}$.

integration - Solve an integral $intfrac{cos^3 x}{sin^3 x+cos^3 x}dx$

Solve an integral $$\int\frac{\cos^3 x}{\sin^3 x+\cos^3 x}dx$$

I tried to divide the numerator and denominator by $\cos^4 x$ to get $\sec x$ function but the term ${\sin^3 x}/{\cos^4 x}$ gives $\tan^2 x\sec^2 x\sin x$. How to get rid of $\sin x$ term?

Answer

I wasn't really able to come up with a better (elegant) method other than the following:

$$\int \frac{\cos^3 x}{\sin^3 x + \cos^3 x} \mathrm{d}x = \int \frac{1}{1 + \tan^3 x} \mathrm{d}x$$

Now, using the substitution, $t = \tan x \implies \frac{\mathrm{d}t}{1+t^2} = \mathrm{d}x$, we get

$$= \int \frac{1}{(1 + t^2)(1+t^3)} \mathrm{d}t$$

Decomposing it into partial fraction (copying from W|A):

$$= \int \frac{1}{6(t+1)} + \frac{t+1}{2(t^2+1)} - \frac{2t-1}{3(t^2-t+1)} \mathrm{d}t \\ = \frac 16\ln t + \frac 14\ln (t^2+1) + \frac 12\arctan t - \frac 13 \ln (t^2-t+1) + C$$

Substituting back $t = \tan x$

$$\frac 16 \ln \tan x + \frac 12 \ln \sec x -\frac 13 \ln (\sec^2x - \tan x) + \frac x2 + C$$

trigonometry - How to prove by induction that $|sin(nx)| leq n|sin x|$?

Here $n$ belongs to natural numbers. Firstly, I proved the relation by putting $n = 1$ . Then, taking $$|\sin(mx)| \leq m|\sin x|$$ true, I had to prove $$|\sin(m + 1)x| \leq (m + 1)|\sin x|$$ Now, here I got stuck. How to prove it?? Please help.

Answer

The inductive step: Using the triangle inequality and the fact that $\sin$ and $\cos$ function are bounded by $1$ we get

$$|\sin((n+1)x)|=|\sin(nx)\cos x+\cos(nx)\sin(x)|\le|\sin(nx)|cos(x)|+|\cos(nx)||sin(x)|\\\le|\sin(nx)|+|sin(x)|\le n|\sin(x)|+|\sin(x)|=(n+1)|\sin(x)|$$

multivariable calculus - Trying to evaluate this triple integral?

So I'm trying to evaluate the triple integral $$\displaystyle \iiint \limits_{R} \displaystyle \frac{1}{((x-a)^2+y^2+z^2)^{1/2}} \mathrm dV$$ for $a>1$ over the solid sphere $0 \leq x^2 + y^2 + z^2 \leq 1$.

Apparently, there's an interpretation that I should be able to draw from this to. Not too sure what it is.

So the first thing that came to mind when I saw the integral was to apply spherical coordinates, but this doesn't make the denominator of the integrand any less messy.

Using spherical coordinates, the integrand becomes

$$\displaystyle \iiint \limits_{R} \displaystyle\frac{1}{(\rho^2-2a\rho\sin\phi\cos\theta+a^2)^{1/2} } \rho^2\sin\phi \space\mathrm d\rho\mathrm d\phi\mathrm d\theta$$ (I haven't bothered to add the bounds yet), which doesn't look that much more friendly.

Any support for this question would be appreciated.

combinatorics - Prove $sum_{i=0}^{i=x} {x choose i} {y+i choose x}+sum_{i=0}^{i=x} {x choose i} {y+1+i choose x}$

How to prove that
$$\sum_{i=0}^{i=x} {x \choose i} {y+i \choose x}+\sum_{i=0}^{i=x} {x \choose i} {y+1+i \choose x}=\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}$$ ?

I tried to break the right side of equation down:

$$\sum_{i=0}^{i=x+1} {x+1 \choose i} {y+i \choose x}=\sum_{i=0}^{i=x} {x+1 \choose i} {y+i \choose x}+{x+1 \choose x+1} {y+x+1 \choose x}$$

Then I tried Vandermonde's Identity:
$${y+x+1 \choose x} = \sum_{i=0}^{i=x} {y+1 \choose i}{x \choose x-i}$$

Now I am totally lost. Can someone please tell me how to prove this equation?

Answer

This is very easy to prove using the integral representation of
binomial coefficients. Suppose we are trying to prove that

$$\sum_{k=0}^n {n\choose k} {m+k\choose n}
+ \sum_{k=0}^n {n\choose k} {m+1+k\choose n}
= \sum_{k=0}^{n+1} {n+1\choose k} {m+k\choose n}.$$

Use the two integrals
$${m+k\choose n}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+k}}{z^{n+1}} \; dz$$
and
$${m+k+1\choose n}

= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{m+1+k}}{z^{n+1}} \; dz.$$

This yields for the LHS the following sum consisting of two terms:
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^m}{z^{n+1}}
\sum_{k=0}^n {n\choose k} (1+z)^k\; dz
\\ + \frac{1}{2\pi i}
\int_{|z|=\epsilon}

\frac{(1+z)^{m+1}}{z^{n+1}}
\sum_{k=0}^n {n\choose k} (1+z)^k\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^m}{z^{n+1}} (2+z)^n \; dz
+ \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{m+1}}{z^{n+1}} (2+z)^n \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}

\frac{(1+z)^m}{z^{n+1}} (2+z)^{n+1} \; dz.$$

For the RHS we get the integral
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^m}{z^{n+1}}
\sum_{k=0}^{n+1} {n+1\choose k} (1+z)^k\; dz
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^m}{z^{n+1}} (2+z)^{n+1} \; dz.$$

The integrals on the LHS and on the RHS are the identical,
QED.

A similar calculation is at this
MSE link.

A trace as to when this method appeared on MSE and by whom starts at this

MSE link.

real analysis - Can this function be integrated and, if so, what is its value?

Say I have a piecewise function defined as:

$f(x) =
\begin{cases}
0 & \text{if x is irrational} \\
1/q &\text{if x = $p/q$, where $p,q > 0$ are relatively prime integers} \\
\end{cases}$

over the interval $[0,1]$. I can prove that $f$ is continuous over the irrational numbers and discontinuous at all rational numbers. But, is the function Riemann integrable:

$\int_{0}^{1}f(x)dx$? If so how would I prove it and what would be the value? Intuition suggests that the value would be zero but I'm at a loss for how to proceed. Assuming the function IS Riemann integrable could I split it up into multiple sections at every discontinuity? But, there are infinitely many discontinuities...

Thanks for your help.

Answer

By Lebesgue's Criterion, a function is Reimann integrable iff it is bounded and the set of discontinuities has measure $0$, i.e. countable. In this case, $|f|\leq1$, and the set of discontinuities is $\mathbb{Q}$ which is countable and thus measure $0$. So, the function $f$ is Reimann integrable.

For any function which is Reimann integrable, it is also Lebesgue integrable, and the value of each integral is equivalent. Hence, it suffices to find the Lebesgue integral of $f$. To do this, consider that $f$ is piecewise constant, and nonzero on a set of measure $0$, so it has Lebesgue integral $\int f = 0$, and so the Reimann integral is also $0$.

Every sequence of the real numbers has a monotone subsequence.

I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)

---

We can construct a monotone subsequence given any sequence.

We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.

Consider any sequence $(x_n).$

Start the following process with $n = 1$ (the first element in the sequence).

PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n \leq x_{n'},$ or there does not.

1. If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.




2. If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.

Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.

If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.

Answer

There's a flaw at this part of the argument:

Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.

Consider this sequence for $n\geq2$:

$$\frac{(-1)^n}{n}=\frac12,-\frac13,\frac14,-\frac15,\frac16,-\frac17,\frac18,-\frac19,\ldots$$

There is a monotonically increasing subsequence: $-\frac13,-\frac15,-\frac17,\ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.

I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.

sequences and series - Different methods to compute $sumlimits_{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?

Answer

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à!

number theory - How do I prove divisibility by 3 without induction?

How do I prove that:

1. $3$ divides $4^n-1$, where $n$ is a natural number, and





2. $3$ divides $n^3-n$, where $n$ is a natural number?

All without induction?(only number theory)

Thanks !

elementary number theory - $gcd (ca, cb) = gcd (a, b)c$ if $c > 0$

Let $\gcd (a, b) = d$. So, $ax + by = d$ for some $x, y$. Then $(ca)x + (cb)y = cd$. Thus, $\gcd (ca, cb) = cd = \gcd(a, b)c$.

Does it work?

Answer

No. The problem is that $ax+by = d$ does not imply $\gcd(a,b) = d$.

The statement $\gcd(ca,cb) = c\gcd(a,b)$ is true, however. To see that note that

$\gcd(a,b) \mid a \wedge \gcd(a,b) \mid b \implies c\gcd(a,b) \mid ac \wedge c\gcd(a,b) \mid bc$ so
$$\gcd(ac,bc) \mid c\gcd(a,b)$$

The reverse is a little bit more work (you need $\gcd(ac,bc) \mid c\gcd(a,b)$ to conclude).

matrices - Lights Out with custom rules set

I'm trying to understand how to use linear algebra to solve a custom Lights Out puzzle with the following rules:

There are 8 lights, all the lights are off at the starting point, I need to turn on all of them.
Every button change (on\off) of the lights like that:
(If the light was on, it will turn it off, if it was off, it will turn it on)

1 1 0 1 1 0 0 0

1 1 1 1 0 0 1 1
0 1 1 0 0 0 0 1
1 1 0 1 1 1 1 0
1 0 0 1 1 1 0 0
0 0 0 1 1 1 1 0
0 1 0 1 0 1 1 0
0 1 1 0 0 0 1 1

For example:

Button 1 will change lights 1, 2, 4 and 5

Button 2 will change lights 1, 2, 3, 4, 7 and 8
You got the idea...

We start with

0 0 0 0 0 0 0 0

And we need to get to

1 1 1 1 1 1 1 1

I got no idea how to even start, I tried to solve it with many matrix but I didn't really understand what I was doing, so I failed. Any help will be appreciated.

real analysis - Essential Uniform Convergence Implication

Greetings Mathematics Community. I believe that I am thinking too hard about the following problem and would like some guidance in solving it.

Let $X$ have finite measure and let $f_n:X \to \mathbb{C}$ and $f:X \to \mathbb{C}$ be measurable functions. Show that if $f_n$ converges to $f$ in $L^{\infty}$norm, then $f_n$ also converges to $f$ in $L^1$norm.

The definitions that I am working with are as follows:

We say that $f_n$ converges to $f$ uniformly almost everywhere, essentially uniformly, or in $L^{\infty}$norm if, for every $\epsilon>0$, there exists $N$ such that for every $n \geq N, |f_n(x)-f(x)| \leq \epsilon$ for $\mu-$almost every $x\in X$. The $L^{\infty}$norm $||f||_{L^{\infty}(\mu)}$ of a measurable function $f:X\to \mathbb{C}$ is defined to be the infimum of all the quantities $M\in [0,+\infty]$ that are essential upper bounds for $f$ in the sense that $|f(x)|\leq M$ for almost every $x$. Then $f_n$ converges to $f$ in $L^{\infty}$ norm if and only if $||f_n-f||_{L^{\infty}(\mu)} \to 0$ as $n \to \infty$.

We say that $f_n$ converges to $f$ in $L^1$norm if the quantity $||f_n-f||_{L^1(\mu)} = \int_{X} |f_n(x)-f(x)| d\mu$ converges to 0 as $n \to \infty$.

Here is my attempt at solving this problem:

Since $f_n$ converges to $f$ in $L^{\infty}$ norm, then we have
$||f_n(x)-f(x)||_{\infty} \to 0$ as $n \to \infty$ and by definition, $||f_n(x)-f(x)||_{\infty} = \inf\{M \geq 0 : |f_n(x)-f(x)| \leq M\}$. Then $||f_n(x)-f(x)||_1 = \int |f_n(x)-f(x)|dx$.

Here is where I am stuck: Could I create another function $g$ such that $||g(x)||_1 \leq ||g(x)||_{\infty}$ and somehow include Markov's Inequality to show that the $L^1$ norm converges?

Alternatively, could I simply say that $\int|f_n(x)-f(x)|dx \leq ||f_n(x)-f(x)||_{\infty}$ and since we are given that $f_n$ converges to $f$ in $L^{\infty}$norm, then $\int|f_n(x)-f(x)|dx \leq 0$?

I would be grateful for any advice or guidance. Thanks in advance.

Answer

$$\|f_n-f\|_1=\int_X|f_n-f|d\mu\le\|f_n-f\|_{\infty}\mu(X).$$

elementary number theory - What is an "interesting integer" and are there uninteresting integers?

On a site, someone asked which number is most interesting and I answered, "Every number is interesting. Give me a number and I shall tell you why it is!".

Now not going into philosophical arguments about validity of my answer, I believe in it firmly, as it can be "proved" too. Let uninteresting positive integers exist, then there must be a smallest uninteresting number. But that would be a very interesting number which is a contradiction!

Question: Is this argument valid? Can we really say that every integer is interesting?

Clearly, "interesting" should be defined here. This is somehow a very vague notion, but it seems likely that some people already worked on the problem. This leads to the following question:

Question: Is there a commonly accepted and formalized notion of "interesting integer"?

---

Now, some guy took it literally, and gave me the number $373857714078$ as a challenge!

Anyways, I am having a hard time finding something interesting about it, but I am sure there is something somewhere, but then, I am not Ramanujan either. I know it is a very tough question to ask, but maybe someone can hit it!

Here is a start, Prime factorization of $373857714078=2\times 3\times 62309619013.$

Answer

(Let uninteresting positive integers exist, then there must be a smallest uninteresting number. But that would be a very interesting number which is a contradiction!)

This argument has two problems, one of which is mathematical and one of which is linguistic. The linguistic problem comes from ambiguity in the word "interesting." It's a variant of the Sorites paradox, which can be phrased as follows:

Suppose heaps of sand exist. Then there must be a smallest heap of sand. But if I remove a grain of sand from a heap then it doesn't stop being a heap; contradiction!

The mathematical problem remains even after you try to formalize the definition of "interesting." One possible formalization is the following:

Definition: A number is interesting if it has a short description; more formally, if it has low Kolmogorov complexity relative to its size, meaning that it can be printed by a short computer program.

As a simple example, $2^{1000}$ is interesting because it can be printed by a very short computer program (in fact just a for loop) relative to its size (1001 binary digits). Of course I haven't told you what "short" means, but everything I'm about to say goes through for various values of the word "short"; for example, "short" might mean a program less than a tenth as long as the number of binary digits.

With this definition it's actually quite clear that most numbers are uninteresting, since most numbers can't have short descriptions; this is just a straightforward counting argument. Intuitively, the reason that most numbers are uninteresting is that most numbers are noise: they behave as if they were random strings of digits ("high Kolmogorov complexity" happens to be an excellent definition of what it means for a particular string to be "random"), and don't have any human-comprehensible structure.

Now the original argument becomes a variant of the Berry paradox, which can be phrased as follows:

Suppose there is a smallest positive integer definable in less than eleven words. Then that positive integer is "the smallest positive integer definable in less than eleven words," which is a definition involving ten words; contradiction!

It's good to spend some time thinking about how to resolve this paradox, so let me give you some space to do that before telling you what the answer is.

The resolution of the paradox is that it is a proof by contradiction: what it proves, more or less, is that a formal language for writing down descriptions of positive integers cannot be powerful enough to write down self-referential statements that quantify over its own descriptions of positive integers.

In other words, the problem with "the smallest positive integer definable in less than eleven words" as a definition is that the word "definable" is ambiguous: once you disambiguate it, it necessarily refers to a notion of definition which does not, and in fact cannot, include "the smallest positive integer definable in less than eleven words."

Lebesgue outer measure with open balls

I'm not sure if this has been asked before; if so please redirect me to the appropriate question.

The Lebesgue outer measure of $A \subseteq \mathbb{R}^n$ is defined as $$\mu_*(A) = \inf\left\{ \sum_{i} |R_{i}|: A \subseteq \bigcup_{i \in I} |R_i|, I \,\,\mbox{countable} \right\}$$ where the infimum is taken over open boxes $R_i$.

Now suppose we define a new measure in this exact same manner, except we take the infimum over open balls, defining their volume using the usual formula for the volume of an $n$-sphere. Why is this equivalent to the above definition?

It seems somewhat related to the Vitali covering lemma.

combinatorics - Probability of picking all elements in a set

I was studying the birthday paradox and got curious about a related, but slightly different problem. Lets say I have a set S, that has n unique elements. If I randomly pick k elements from the set (assuming equal probability of picking any element), the probability that I'll have picked all the elements in the set, when k=n is n!/n^n.

Now, what would be the value of k for probability of picking all elements in the set to be > 0.9 (or some constant).

A simpler variation would be - how many times should I flip a coin to have a probability > 0.9 to have thrown heads and tails at least once.

Answer

Your first question is about a famous problem called the
Coupon Collector's Problem.

Look in the Wikipedia write-up, under tail estimates. That will give you enough information to estimate, with reasonable accuracy, the $k$ that gives you a $90$ percent chance of having seen a complete collection of coupons.

summation - Intuition behind the formula for $sum i^{2}$

I've been trying to figure out the intuition behind the closed formula:

$\sum i^{2} = \frac{(n)(n+1)(2n+1)}{6}$

This is not hard to prove via induction, so I'm not interested in the proof that this is true. Rather, I'm more interested in why somebody would even make this guess for an inductive step. What's so confusing to me is that

$\sum i = \frac{(n)(n+1)}{2}$ makes sense using the Gaussian trick of taking the number line and folding it in half and realizing that (1+n) = (2+(n-1)) = (3 +(n-2))... so that you end up with this form.

But, what's the intuition for $i^{2}$? Looking at these two formulas, one realizes very quickly that

$\sum i^{2} = \sum i * \frac{(2n+2)}{3}$

But, why is that true intuitively? What's the intuition for this?

Answer

Since you asked for an intuitive explanation consider a simple case of $1^2+2^2+3^4+4^2$ using a set of children's blocks to build a pyramid-like structure.

First you arrange $16$ blocks in a $4\times4$ square. Next you place on top of this arrangement, $9$ blocks in a $3\times3$ square aligning the blocks of the upper left corner of each square, one above the other. On top of this construction place $4$ blocks in a $2\times2$ square, similarly aligned. Finally crown the upper left corner with a single block for the $1\times1$ square.

The following table represents the number of block in each column of the arrangement viewed from above:

$\begin{array}{cccc}
4&3&2&1\\
3&3&2&1\\
2&2&2&1\\
1&1&1&1
\end{array}$

We can find the total number of blocks in the arrangement by adding the number of columns containing a single block to twice the number of columns containing two blocks then adding three times the number of columns containing three blocks and finally adding four times the one column containing four blocks.

\begin{eqnarray}
\sum_{i=1}^4i^2=1\cdot(4+3)+2\cdot(3+2)+3\cdot(2+1)+4\cdot1
\end{eqnarray}

If we do the same thing with a pyramid of blocks having $n\times n$ blocks on its base then the summation would look like the following:

\begin{eqnarray}

\sum_{i=1}^{n}i^2&=&1\cdot(n+n-1)+2\cdot(n-1+n-2)+3\cdot(n-2+n-3)\\
&+&\cdots+(n-1)\cdot(2+1)+n\cdot1\\
&=&1\cdot(2n-1)+2\cdot(2n-3)+3\cdot(2n-5)+\cdots+(n-1)\cdot3+n\cdot1\\
&=&\sum_{i=1}^{n}i(2n-2i+1)\\
&=&2n\sum_{i=1}^{n}i-2\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}i\\
\sum_{i=1}^{n}i^2&=&(2n+1)\sum_{i=1}^{n}i-2\sum_{i=1}^{n}i^2\\
3\sum_{i=1}^{n}i^2&=&(2n+1)\sum_{i=1}^{n}i\\
&=&\dfrac{n(n+1)(2n+1)}{2}\\
\sum_{i=1}^{n}i^2&=&\dfrac{n(n+1)(2n+1)}{6}
\end{eqnarray}

abstract algebra - Commutative binary operations on $Bbb C$ that distribute over both multiplication and addition

Does there exist a non-trivial commutative binary operation on $\Bbb C$ that distributes over both multiplication and addition?

In other words, if our operation is denoted by $\odot$, then I want the following to hold:

1. $a \odot (b \cdot c) = a \odot b \cdot a \odot c$


2. $a \odot (b + c) = a \odot b + a \odot c$


3. $a \odot b = b \odot a$

All of the things I can find so far distribute over either multiplication or addition, but not both. Alternatively, is there a proof that no such operation can exist?

I wasn't sure if this question was too elementary for MO, so I'm trying here first. This question is obliquely related to the following other questions I've asked on MO and here:

Answer

One such operation is $a\odot b=0$ for all $a,b$. I claim this is the only such operation. Indeed, we have $$a\odot c=a\odot(1\cdot c)=(a\odot 1)\cdot (a\odot c).$$ Taking $c=1$ gives that $a\odot 1$ must be either $0$ or $1$ for each $a$. But if $a\odot 1=1$, then $(a+a)\odot 1=2$, which is impossible. So in fact $a\odot 1=0$ for all $a$, and now the equation above tells us $a\odot c=0$ for all $c$ as well.

This argument uses only the fact that $\odot$ distributes over multiplication on the left and $\odot$ distributes over addition on the right. With slight modification, it applies equally well with $\mathbb{C}$ replaced by any ring in which $2$ is not a zero divisor. Note that in arbitrary rings, there can be other such operations $\odot$. For instance, in a Boolean ring (in which $a\cdot a=a$ for all $a$), $a\odot b=a\cdot b$ is such an operation.

algebra precalculus - How do I find X of this equation?

This question is a branch of my previous question.

I'm trying to reverse an equation. I did everything I thought I was suppose to do, but I reached an impass. I have no idea how to reduce passed initial / X an get to removing the antilog (that too I'm not sure how to remove).

I started with (the values are faked):

10 = 5 + ( 10 / X ) + ( 5 * X ) + ( 10 * log( X ) )

I then tried to remove X from the denominator.

10X = 5X + 10 +( 5X * X^2 ) + ( 10X * log( X )X )

Then I divided the X from the multiplication parenthesis.

10 = 5 + ( 10 / X ) + ( 5 * X )  + ( 10 * log( X ) )

If I did everything correctly, I haven't done anything to this equation. All I can figure out to do is just recurssively add and remove * X to each of these terms. Further once I finally break it down I'm not sure how to remove the log( X ), but that is another question I think.

What am I missing to cancel out the X's?

Answer

Going from the first equation to the second, when you multiply $(5*X)$ by $X$, you should get $(5*X^2)$ instead of $(5X*X^2)$ and when multiplying $(10*\log(X))$ by $X$ you should get $(10X*\log(X))$. Going from the second to the third you reverse the errors.

That said, when you have polynomial terms and logarithmic terms in the same equation, as here, you generally cannot find an algebraic solution unless you like the Lambert W function. You can find a solution numerically.

linear algebra - Matrices for which $mathbf{A}^{-1}=-mathbf{A}$

Consider matrices $\mathbf{A}\in\mathbb{C}^{n\times n}$ (or maybe $A\in\mathbb{R}^{n\times n}$) for which $\mathbf{A}^{-1}=-\mathbf{A}$.

A conical example (and the only one I can come up with) would be $\mathbf{A} = \boldsymbol{i}\mathbf{I},\quad \boldsymbol i^2=-1$.

Now I have a few questions about this class of matrices:

1. Are there more matrices than this example matrix (I guess yes) or can they even be generally constructed somehow?


2. Are there also real matrices for which this holds?


3. Now each matrix that is both skew-Hermitian and unitary fulfills this property. But does it also hold in the other direction, meaning is each matrix for which $\mathbf{A}^{-1}=-\mathbf{A}$ both skew-Hermitian and unitary (maybe this is simple to prove, but I don't know where to start at the moment, but of course I know if one holds the other has to hold, too)?


4. Do such matrices have any practical meaning? For example I know that Hermitian and unitary matrices are reflections (in a general sense), but what about skew-Hermitian and unitary (if 3 holds)?

This is just for personal interrest without any practical application. I just stumbled accross this property by accident and want to know more about its implications and applications.

Answer

Note that the condition is invariant under conjugation, so any conjugate of a matrix satisfying this property also satisfies this property.

It is simpler to write the condition as $A^2 = -I$. Note that taking determinants of both sides gives $(\det A)^2 = (-1)^n$, so if $n$ is odd then $A$ cannot be real. (Another way to see this is to note that, since $x^2 + 1$ is irreducible over $\mathbb{R}$, the characteristic polynomial of $A$ is necessarily $(x^2 + 1)^k$ for some $k$.) lhf's example shows that real examples always exist when $n$ is even.

Because the polynomial $x^2 = -1$ has no repeated roots, $A$ is diagonalizable with eigenvalues $\pm i$ and the converse holds.

It is bad practice to ask whether a matrix is skew-Hermitian or unitary. This is not really a property of a matrix. It is a property of a linear operator on a complex inner product space. It should not be hard to construct examples which are neither skew-Hermitian nor unitary by conjugating a diagonal matrix with entries $\pm i$ by a non-unitary matrix.

proof writing - Proving $mathbb{Z × N}$ is countable.

How would I prove that $\mathbb{Z × N}$ is countable? The hint given was to follow to indicated order. Thanks!

algebra precalculus - How to get the simplest form of this radical expression: $3sqrt[3]{2a} - 6sqrt[3]{2a}$.

How to get the simplest form of this radical expression:
$$3\sqrt[3]{2a} - 6\sqrt[3]{2a}$$

Here is my work:
$$3\sqrt[3]{2a} - 6\sqrt[3]{2a}$$
Since the radicands are the same, we just add the coefficients.
$$-3\sqrt[3]{2a} \sqrt[3]{2a}$$
Since everything is under the same index it becomes:
$$-3\sqrt[3]{2} \sqrt[3]{a}$$

Did I do this correctly, if not can anyone tell me what I should do?
Thanks :-).

Answer

Your middle step is incorrect, it should be $-3\sqrt[3]{2a}$ not $-3\sqrt[3]{2a}\sqrt[3]{2a}$. It should be $$3\sqrt[3]{2a} - 6\sqrt[3]{2a} = 3\times\sqrt[3]{2a} - 6\times\sqrt[3]{2a} = (3 - 6)\times\sqrt[3]{2a} = -3\times\sqrt[3]{2a} = -3\sqrt[3]{2a}.$$ I don't think $-3\sqrt[3]{2}\sqrt[3]{a}$ is any simpler than $-3\sqrt[3]{2a}$, but that's just my opinion.

hypothesis testing - What is the probability that dice are rigged?

We are given a single six-sided die. We produce a sequence of $n$ dice rolls, all of them rolling six. We do not know whether the die is fair or not.

How can we calculate the probability that the die is loaded or rigged given $n$ rolls of six?

In other words, what is the probability $q$ that the null hypothesis is false, given a series of $n$ successful Bernoulli trials?

I heard a non-mathematician say that the probability of one six on a fair die is $\frac{1}{6}$, and so the probability of rolling 4 sixes in a row on a fair die is $\frac{1}{6^4} = \frac{1}{1296}$. So far, so good.

But then, he said that the probability that the die is not loaded is $\frac{1}{1296}$, and so the probability that the die is loaded is $\frac{1295}{1296}$.

This does not add up to me. By the same logic, if I roll the die once and get six, the probability that the die is loaded is $\frac{5}{6}$, which cannot be true. You don't call a person a cheat for rolling a six once.

I think that to answer this question, I have to use the binomial distribution somehow, since:

• the probability of a six, fair or not, remains constant and equal to $p$


• I am only interested in success/failure

At this point, I get lost. The problem is that I only know the probability for the null hypothesis $p_0 = \frac16$, and I don't know what the actual value for $p$ is. I don't know where to go from here.

Am I asking the wrong question? Must I set a confidence level $\alpha$? If so, suppose I set $\alpha = 0.05$? $\alpha = 0.01$? I apologize for any incorrect terminology. I am a computer programmer, not a statistician or mathematician.

Edit: It looks like I have to specify how badly the dice must be loaded before I call them unfair. Suppose I say rolling a six has to be at least $r = 10\%$ more likely than a fair die (i.e. $p \ge p_0\cdot\left(1 + r\right) = \frac{11}{60}$) before I call it rigged?

algebra precalculus - Simplify the expression $binom{n}{0}+binom{n+1}{1}+binom{n+2}{2}+cdots +binom{n+k}{k}$

Simplify the expression $\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k}{k}$

My attempt: Using the formula $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$

$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots \binom{n+k-1}{k-1}+\binom{n+k}{k}$

=$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k-1}{k-1}+(\binom{n+k-1}{k}+\binom{n+k-1}{k-1})$

=$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +2\binom{n+k-1}{k-1}+\binom{n+k-1}{k}$

I can again use the same formula for the term $2\binom{n+k-1}{k-1}$, and in the next to step to the term $3\binom{n+k-2}{k-2}$.

But I don't think this way the expression will get simplified.

Any help is appreciated.

Answer

First show that $\large{n\choose r}={{n-1}\choose {r-1}}+{{n-1}\choose r}$,

from which we get $\large{{n+r+1}\choose r}={{n+r}\choose r}+{{n+r}\choose {r-1}}$

By the same rule, $\large{{n+r}\choose {r-1}}={{n+r-1}\choose {r-1}}+{{n+r-1}\choose {r-2}}$

$\large{{n+r-1}\choose {r-2}}={{n+r-2}\choose {r-2}}+{{n+r-3}\choose {r-3}}$

$..$ $\quad \quad \quad \quad ..$ $ \quad \quad \quad ..$

$..$ $\quad \quad \quad \quad ..$ $ \quad \quad \quad ..$

$..$ $\quad \quad \quad \quad ..$ $ \quad \quad \quad ..$

$\large{{n+3}\choose {2}}={{n+2}\choose {2}}+{{n+2}\choose {1}}$

$\large{{n+2}\choose {1}}={{n+1}\choose {1}}+{{n+1}\choose {0}}$

Adding, we get $\large{n\choose 0}+{{n+1}\choose 1}+...+{{n+r-1}\choose {r-1}}+{{n+r}\choose r}={{n+r+1}\choose r}$

---

Alternatively, we can fix any $r$ of the $(n+r+1)$ objects given. Label them $A_1,A_2,...A_r$. Now our choices of $r$ objects from the $(n+r+1)$ objects may or may not contain any or all of the set $\{A_1,A_2,...,A_r\}$.

Case I: It does not contain $A_1$

This will happen in $\large{{n+r}\choose r}$ ways as the $r$ things have to be chosen from the remaining $(n+r)$ things.

Case II: It contains $A_1$ but does not contain $A_2$.

This will happen in $\large{{n+r-1}\choose {r-1}}$ ways, because having chosen $A_1$ and rejectd $A_2$, we have only $(n+r-1)$ things to choose from and we need only $(r-1)$.

$...$

Case r: It contains $A_1,A_2,...,A_{r-1}$ but does not contain $A_r$.

This will happen in $\large {{n+1}\choose 1}$ ways.

Case $(r+1)$: It contains $A_1,A_2,...,A_r$.

This will happen in $\large{n\choose 0}=1$ way.

Hence, $\displaystyle\sum_{k=0}^{r}{{n+k}\choose k}={{n+r+1}\choose r}$

combinatorics - Probability of winning a prize in a raffle (each person can only win once)

So I'm trying to figure out the odds of winning a prize in a raffle where each person can buy multiple tickets but you can only win once.
My problem is the following:

• There are 2600 tickets sold


• There are 42 winning tickets drawn


• There is no limit on how many tickets you can buy


• I buy 10 tickets


• I know that there are only 600 people who have bought tickets (so all the tickets are distributed over the 600 people)

I have looked at booth of these threads:
Thread 1

Thread 2
and they helped me understand the problem well but I am still wondering if there is some way to calculate the probability better when you know how many people who have bought tickets. You still don't know how many tickets each person bought, but maybe you can calculate an average or something similar? I'm also thinking since the price of the tickets is 10$ each, it must be more unlikely someone bought 1000 tickets than say 1,5 or 10.

Any input or help is greatly appreciated!

*Edit:
All the prizes need to be distributed and if a person wins all the rest of their tickets become invalid. So they keep drawing until they have drawn 42 tickets which correspond to 42 unique individuals.

calculus - How can I prove the integral $ int_{1}^{x} frac{1}{t} , dt $ is $ln x $ with this approach?

I have been trying to find a proof for the integral of $ \int_1^x \dfrac{1}{t} \,dt $ being equal to $ \ln \left|x \right| $ from an approach similar to that of the squeeze theorem.

Is it possible to calculate the area under the curve $ f(x) = \dfrac{1}{x} $ as in the picture shown below? You may notice that both sums of the areas should converge to $\ln(x)$ as the base of the rectangles gets smaller and smaller. We approach from above and from below to get a limiting argument of the form:

Area from below the curve as in the second graph $ \leq \int_a^b \dfrac{1}{x} \,dx \leq$ Area from above the curve as in the first graph

The limiting argument would be to keep calculating and adding the areas of the rectangles which bases get smaller and thus showing that this amount is $\ln(x)$.

How could I proceed in this way?

Prove that the Galois group of $x^n-1$ is abelian over the rationals

If $p(x)=x^n-1$, prove that the Galois group of $p(x)$ over the field of rational numbers is abelian.

Here's what I have so far.

Denote the Galois group $G(K,\mathbb{Q})$, where $K$ is the splitting field for $p(x)$ over $\mathbb{Q}$.

By setting $x^n-1=0$, we find the $n$th roots of unity $\omega, \omega^2,\cdots,\omega^n=1$, where $\omega=e^{2\pi i/n}$. Then, the splitting field $K=\mathbb{Q}(\omega)$.

By a theorem, $K$ is a normal extension of $\mathbb{Q}$. We now wish to examine $G(K,\mathbb{Q})=G(\mathbb{Q}(\omega),\mathbb{Q})$. By defintion, this is the group of automorphisms of $\mathbb{Q}(\omega)$ that keep every element of $\mathbb{Q}$ fixed. In other words, if $a\in \mathbb{Q}$, $\sigma(a)=a$ for all $\sigma\in G(\mathbb{Q}(\omega),\mathbb{Q})$.

Suppose $\sigma,\tau \in G(\mathbb{Q}(\omega), \mathbb{Q})$. We know the group structure is given by composing automorphisms. To show that this group is abelian, we need to show that $(\sigma \circ \tau)(b)=(\tau \circ \sigma)(b)$ for all $b\in \mathbb{Q}(\omega)$.

We know that all elements of $\mathbb{Q}$ are fixed. That is, if $a\in\mathbb{Q}$,

$(\sigma\circ\tau)(a)=\sigma(\tau(a))=\sigma(a)=a$

$(\tau\circ\sigma)(a)=\tau(\sigma(a))=\tau(a)=a$

Now, consider $\sigma(\omega)=\sigma(e^{2\pi i/n})$. We have $(\sigma(e^{2\pi i/n}))^n=\sigma(e^{2\pi i})=\sigma(1)=1$. This implies that $\sigma(e^{2\pi i/n})=$ an $n$th root of unity. Thus, $\sigma$ just permutes roots of unity.

This is where I am confused. If the automorphism permutes roots of unity, it doesn't seem to necessarily be the case that $(\sigma\circ\tau)(\omega)=(\tau\circ\sigma)(\omega)$.

Please let me know where to go from here (or where I've gone wrong in my argument). Thanks.

Answer

Your argument up to the point where you're stuck seems completely correct to me.

To finish it, suppose that $\sigma(\omega) = \omega^j$ and that $\tau(\omega) = \omega^k$ for some $j,k \in \mathbb{N}$. Then just observe that
$$
(\sigma \circ \tau)(\omega) = \sigma(\tau(\omega)) = \sigma(\omega^k) = \sigma(\omega)^k = (\omega^j)^k = \omega^{jk}
$$
and similarly
$$

(\tau \circ \sigma)(\omega) = \tau(\sigma(\omega)) = \sigma(\omega^j) = \tau(\omega)^j = (\omega^k)^j = \omega^{jk}
$$

calculus - Find modulus and argument of $omega = {frac {sin (P + Q) + i (1 - cos (P + Q))} {(cos P + cos Q) + i (sin P - sin Q) }} $

A past examination paper had the following question that I found somewhat difficult. I tried having a go at it but haven't come around with any possible double angle identities. How would one go about tackling it?

Given:

$$\omega = {\frac {\sin (P + Q) + i (1 - \cos (P + Q))} {(\cos P + \cos Q) + i (\sin P - \sin Q) }} $$

To prove:

$$|\omega| = \tan \frac {P + Q} {2} \qquad\text{and}\qquad \arg(\omega) = Q $$

A guideline on how/ which identity to use would be greatly appreciated.

To give an idea how one would start it is by;

Proof:

$$|\omega| = {\frac {\sqrt{\sin^2 (P + Q) + (1 - \cos (P + Q))^2}}
{\sqrt{(\cos P + \cos Q)^2 + (\sin P - \sin Q)^2 }}} $$

I'm still unsure about the above or how the square root come about

Answer

We have
\begin{align}
N
& := \sin^2(P+Q) + (1-\cos(P+Q))^2 = \sin^2(P+Q) + \cos^2(P+Q) + 1 - 2\cos(P+Q) \\
& = 2 (1-\cos(P+Q))

= 2\cdot2\sin^2\frac{P+Q}{2}
= 4\sin^2\frac{P+Q}{2}
\end{align}
and
\begin{align}
D
& = \cos^2P +\cos^2Q + \sin^2P + \sin^2Q + 2(\cos P\cos Q - \sin P \sin Q) \\
&= 2 +2(\cos(P+Q))
= 2(1+\cos(P+Q)) = 4\cos^2\frac{P+Q}{2}
\end{align}

Now, $$|\omega| = \sqrt{\frac{N}{D}} = \tan\frac{P+Q}{2}$$

sequences and series - Weird limit $lim limits_{nmathoptoinfty}frac{1}{e^n}sum limits_{kmathop=0}^nfrac{n^k}{k!} $

$$\lim \limits_{n\mathop\to\infty}\frac{1}{e^n}\sum \limits_{k\mathop=0}^n\frac{n^k}{k!} $$

I thought this limit was obviously $1$ at first but approximations on Mathematica tells me it's $1/2$. Why is this?

Answer

In this answer, it is shown that
$$
\begin{align}
e^{-n}\sum_{k=0}^n\frac{n^k}{k!}
&=\frac{1}{n!}\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t\\

&=\frac12+\frac{2/3}{\sqrt{2\pi n}}+O(n^{-1})
\end{align}
$$

calculus - Evaluate: $int_{0}^{infty}left(x^2-3x+1right)e^{-x}ln^3(x) dx$

$$I=\large \int_{0}^{\infty}\left(x^2-3x+1\right)e^{-x}\ln^3(x)\mathrm dx$$

$$e^{-x}=\sum_{n=0}^{\infty}\frac{(-x)^n}{n!}$$

$$I=\large \sum_{n=0}^{\infty}\frac{(-1)^n}{n!}\int_{0}^{\infty}\left(x^2-3x+1\right)x^n\ln^3(x)\mathrm dx$$

$$J=\int \left(x^2-3x+1\right)x^n\ln^3(x)\mathrm dx$$

We can evaluate $J$ by integration by parts but problem, the limits does not work.

How to evaluate integral $I?$

Answer

Here's a way that only requires the identity $\Gamma'(1) = - \gamma$ , since all derivatives of higher order cancel:
\begin{align}
I &=\int \limits_0^\infty (x^2 - 3x+1) \ln^3 (x) \mathrm{e}^{-x} \, \mathrm{d} x \\
&= \left[\frac{\mathrm{d}^2}{\mathrm{d} t^2} + 3 \frac{\mathrm{d}}{\mathrm{d}t}+1 \right] \int \limits_0^\infty \ln^3 (x) \mathrm{e}^{- t x} \, \mathrm{d} x ~\Bigg\vert_{t=1}\\
&= \left[\frac{\mathrm{d}^2}{\mathrm{d} t^2} + 3 \frac{\mathrm{d}}{\mathrm{d}t}+1 \right] \frac{1}{t} \int \limits_0^\infty \left[\ln^3 (y) - 3 \ln^2(y) \ln(t) + 3 \ln(y) \ln^2(t) - \ln^3 (t)\right] \mathrm{e}^{-y} \, \mathrm{d} y ~\Bigg\vert_{t=1}\\
&= \left[\frac{\mathrm{d}^2}{\mathrm{d} t^2} + 3 \frac{\mathrm{d}}{\mathrm{d}t}+1 \right] \frac{1}{t} \left[\Gamma'''(1) - 3 \Gamma''(1) \ln(t) + 3 \Gamma'(1) \ln^2(t) - \ln^3 (t)\right] ~\Bigg\vert_{t=1} \\

&= 2 \Gamma'''(1) + 6 \Gamma''(1) + 3 \Gamma''(1) + 6 \Gamma'(1) - 3 \Gamma'''(1) - 9 \Gamma''(1) + \Gamma'''(1) \\
&= 6 \Gamma'(1)\\
&= - 6 \gamma \, .
\end{align}

In fact, integration by parts yields the following generalisation:
\begin{align}
\gamma &= \int \limits_0^\infty (-\ln (x)) \mathrm{e}^{-x} \, \mathrm{d} x
= \int \limits_0^\infty \frac{-\ln (x)}{x} x \mathrm{e}^{-x} \, \mathrm{d} x \\
&= \int \limits_0^\infty (-\ln (x))^2 \frac{1-x}{2} \mathrm{e}^{-x} \, \mathrm{d} x \\

&= \int \limits_0^\infty (-\ln (x))^3 \frac{x^2 - 3x +1}{6} \mathrm{e}^{-x} \, \mathrm{d} x \\
&= \dots \, \\
&= \int \limits_0^\infty (-\ln (x))^{n+1} \frac{p_n (x)}{(n+1)!} \mathrm{e}^{-x} \, \mathrm{d} x \, .
\end{align}
The polynomials $p_n$ are defined recursively by $p_0(x) = 1$ and
$$p_n (x) = \mathrm{e}^{x} \frac{\mathrm{d}}{\mathrm{d}x} \left(x p_{n-1} (x) \mathrm{e}^{-x}\right) \, , \, n \in \mathbb{N} \, ,$$
for $x \in \mathbb{R}$ . The exponential generating function
$$ \sum \limits_{n=0}^\infty \frac{p_n(x)}{n!} t^n = \mathrm{e}^{t+x(1-\mathrm{e}^t)}$$
can actually be computed from a PDE and it turns out that the polynomials are given by
$$p_n(x) = \frac{B_{n+1}(-x)}{-x} \, , \, x \in \mathbb{R} \, , \, n \in \mathbb{N}_0 \, , $$

where $(B_k)_{k \in \mathbb{N}_0}$ are the Bell or Touchard polynomials.

geometry - A rectangle of a given aspect ratio inscribed in a hexagon.

I'm trying to find the largest rectangle of a given aspect ratio that can be inscribed in a hexagon.

I'm able to sort of walk through the problem in reverse, i.e. given an x, I can calculate the rectangle and aspect ratio :

1. find the point on AB for x


2. find the point on DE for x



3. find the point on BC across from #1


4. calculate height : distance between #1 & #2


5. calculate width : distance between #1 & #3


6. Aspect ratio is #5 / #4

How would I go about doing this in reverse? Thanks in advance for any guidance!

sequences and series - Find the first term of an arithmetic progression, given the 7th and the 16th terms

I tried to solve this problem by first finding out the common difference by using the formula
$$
\text{common difference} = \frac{T_p-T_q}{p-q}
$$
with $T_7=-1$ and $T_{16}=17$. But now I'm not able to find the first term. I tried out many methods. Please help me out..

calculus - prove that a function whose derivative is bounded also bounded

I got this problem:

Let $f$ be a differentiable function on an open interval $(a,b)$ such that $f'$ (the derivative of $f$) is bounded on $(a,b)$ (meaning there exist $0

I tried to prove it but wasn't able to proceed.

Thanks.

Answer

Fix a point $x_0\in (a,b).$ Assume $x\in(x_0,b).$ By using the Lagrange's theorem there exists $c\in(x_0,x)$ such that $f(x)-f(x_0)=f'(c)(x-x_0).$ Thus

$$|f(x)|=|f(x_0)+f'(c)(x-x_0)|\leq |f(x_0)|+|f'(c)||(x-x_0)|\leq |f(x_0)|+M(b-a).$$ Proceeding in the same way you get the bound for $x\in(a,x_0).$ Thus we have shown that the function is bounded.

analysis - Updated: Constructing a bijection between $left(-frac{pi}{2}, frac{pi}{2}right]$ and $mathbb{R}$

I am supposed to construct a bijective function for the interval:
\begin{align}
I_2=\left(-\frac{\pi}{2} ,\frac{\pi}{2} \right] \longrightarrow \mathbb{R} \tag{Problem}
\end{align}

I first tried the easier case, i.e.
\begin{align}f_1:I_1=\left(-\frac{\pi}{2} ,\frac{\pi}{2} \right) &\longrightarrow \mathbb{R} \\ x& \longmapsto \tan(x)
\end{align}
which is a bijection. Now I know that the composition of bijective functions is still a bijection. Which means that it should be possible to 'make room' for the missing point $\pi/2$. The following function:
\begin{align}\phi : \mathbb{R} &\longrightarrow \mathbb{R \setminus}\lbrace 0 \rbrace \\ x & \longmapsto \begin{cases}x+1 \ \text{if} \ x \in \mathbb{N}_0 \\x \ \text{otherwise} \end{cases}\end{align}
would be bijective, such that the composition $\phi \circ f_1: I_1 \rightarrow \mathbb{R}\setminus \lbrace 0 \rbrace $ is bijective, and as desired it now has room for a point that I can map to.

At this point I am not sure if my approach is correct because I can't find a function that would do the trick. Would I need to come up with another composition or is it enough to define a function that maps to the functions introduced above?

Update (in consideration of the answers given)

If I understand things correctly I can define: \begin{align}f_2: I_2 &\longrightarrow \mathbb{R} \\ x& \longmapsto \begin{cases}\phi(x) \ \text{for} \ x \in I_2 \\0 \ \text{for} \ x=\frac{\pi}{2} \end{cases} \end{align}
Update 2 (Clarification required).

Define a new function to be equal to $\phi f_1$ over $I_1$ and have it map $π/2$ to $0$. As suggested (and upvoted) by @TBrendle.

If I do understand this correctly, then I need to map $x=\frac{\pi}{2}$ to $0$. However in this case it would make no sense to me to include $I_1$ in the domain, because $\pi/2$ is not in the domain, hence I don't see why I should include it in the codomain, however if I define:
\begin{align}w: I_2 &\longrightarrow \mathbb{R} \\ (\phi\circ f_1)(x) & \longmapsto \begin{cases} (\phi \circ f_1) \ \text{if} \ x \in I_2 \\ 0 \ \text{if} \ x= \frac{\pi}{2} \end{cases} \end{align}
This doesn't even look like a legitimate function to me anymore, since at $x=0$ the function evaluates to both $0$ and $1$.

Answer

Your approach is flawless. What were you worried about? Your function will be defined piecewise.

Added details:

Your new function is
$$\psi : \left(-\frac{\pi}{2} \frac{\pi}{2}\right] \to \mathbb{R}$$

given by

$$ \psi(x) =

\begin{cases}
\phi(\tan x), & \text{for }-\frac{\pi}{2} < x< \frac{\pi}{2} \\
0, & \text{for } x=\frac{\pi}{2}\\
\end{cases}
$$
where $\phi$ is as given in the question. You can verify that the function $\psi$ has the specified domain and range and is a bijection.

exponentiation - Complex Exponents

What does it mean to raise a number to a complex exponent, and why? A lot of the explanations that I've seen involve e, why is this?

I'm looking for an intuitive answer describing to how exponentiation works on a number plane (i.e. the complex number plane) rather than just a number line (the real numbers), where I understand exponentiation quite well. I'm not looking for a breakdown of Taylor series - I believe the proofs, I just don't grok them.

For example, if I was asking how sine worked, I'd want this, not this.

Answer

Dear Nate, first, why is $e$ the preferred base for exponentials? Imagine that you have 1 dollar and your bank gives you 100% interest rate. After 1 year, you will have 2 dollars.

Now it offers you to add interests 100 times in a year but the interest is 1% at each moment. How much will you get? You will get
$$ (1+0.01)^{100} \approx 2.704 $$
What if they add you $1/N \times $ 100% at $N$ moments of the year and you send $N$ to infinity? Well, you will have $e\approx 2.71828$ dollars after one year.

In fact, the general exponential - power with the base of $e$ - may be defined by this "repeated small interest" formula as

$$ e^X = \exp(X) = \lim_{N\to \infty} \left(1+\frac {X}{N}\right)^N $$
It only has this simple form if the base is $e$. A more general power may be defined as
$$ Y^X = \exp(X \ln Y) .$$
Here, $\ln$ is the natural logarithm so that $\exp\ln X = X$. If I replaced the base $e$ by another base such as $2$ or $10$, the "repeated small interest" formula above would have to contain $\ln 2$ or $\ln 10$ or other awkward factors at various places. It wouldn't be natural.

So instead of powers $Y^X$ and logarithms with general bases, you should think that in mathematics, only $\exp(X)$ and $\ln(X)$ are really needed, and all the other powers and logarithms may be expressed as composite functions. Also, $\exp(X)$ has the advantage that its derivative is exactly equal to the very same function $\exp(X)$. In particular, the derivative evaluated at $X=0$ is equal to one, very nice and simple. It would be $\ln(Y)$ if you used a different base $Y$ instead of $e$.

Now, what is the exponential of an imaginary exponent? Again, you may write
$$\exp(iX) = \lim_{N\to\infty} \left(1+\frac {iX}{N}\right)^N $$
You multiply $N$ copies of a number that is very close to one. What do you get?

Well, the multiplication by a complex number has the effect of magnifying (or reducing) the plane, and rotating it. In particular, the absolute value of the number $(1+iX/N)$ is essentially one, up to second-order corrections that disappear in the $N\to \infty$ limit. So in the limit, $(1+iX/N)$ is effectively a number whose absolute value equals one.

Multiplying by complex numbers whose absolute value is equal to one looks like a rotation of the complex plane. The angles are preserved - those are some things one should know about the complex numbers. Moreover, it's clear that multiplying by $(1+iX/N)$ is equivalent to the rotation by $X/N$ in radians. If you multiply the same factor $N$ times, you simply get a rotation by $X/N$ in radians.

So the $N$th power of $1+iX/N$, in the limit $N\to\infty$, is the number that you get by rotating $1$ in the counter-clockwise direction by the angle $X$ in radians. Clearly, the answer is
$$ \exp(iX) = \cos (X) + i \sin(X) $$
where the trigonometric functions have arguments in radians, of course. Once again, the mathematically natural unit of an angle is in radians for very similar reasons why the natural base of the powers or exponentials is $e$. Only in radians, it's true that the derivative of $\sin X$ equals $\cos X$ and many other things.

In fact, the previous formula makes it natural to say that $\cos X$ and $\sin X$ are not "independent" functions, either. They may be defined as

$$\cos (X) = \frac 12 ( e^{iX} + e^{-iX} ) $$
$$\sin(X) = \frac{1}{2i} (e^{iX} - e^{-iX} ) $$
You may substitute the last two equations into the previous one or vice versa to check that everything is consistent.

Just to be sure, general complex numbers may also be exponentiated via $\exp(A+iB) = \exp(A)\exp(iB)$ where both factors are known.

Sequences (Mathematical Induction)

Can any one help me with this.

We have
$$
U_n=\frac{n^3}{n^4+1}+\frac{n^3}{n^4+2}...+\frac{n^3}{n^4+n}
$$
How to prove that, for all $n$:
$$
\frac{n^4}{n^4+n}\le U_n\le \frac{n^4}{n^4+1}
$$

and what the limit of the sequence ?

I've proved that for $U_0$ but I couldn't prove that for $n+1.$

Thanks too much

number theory - Prove that product of five divisors is $leq n^4$

Five divisors sum $(n_1+n_2+n_3+n_4+n_5)$ of natural number $n>0$ is prime number. Prove that the product of these five divisors is $\leq n^4$
in math words $n_1\cdot n_2\cdot n_3\cdot n_4\cdot n_5 \leq n^4$.
And that's what I did. Let's say that

$n_1.

Let $n_5$ is biggest divisor of number n $\implies n_5=n$

We want to find other four biggest divisors. It obvious can be $\frac{n}{2},\frac{n}{3},\frac{n}{4},\frac{n}{5}$.

Multiplication of these divisors would be $n\cdot \frac{n}{2}\cdot \frac{n}{3}\cdot \frac{n}{4}\cdot\frac{n}{5}=\frac{n^5}{120}$

Now we have inequality $\frac{n^5}{120}\leq n^4$.

Since $n>0$ so lets divide by $n^4$

$\implies \frac{n}{120}\leq1$ or $n\leq120$

So I got that number $n$ must be smaller than $120$. But how to prove it for bigger numbers? Thanks in advance.

Answer

It's not specific to $5$, it works for every $m \geqslant 2$. If $n$ is a positive integer, and $n_1, \dotsc, n_m$ are — not necessarily distinct — positive divisors of $n$ such that
$$\sum_{k = 1}^m n_k \quad\text{ is prime,} \tag{1}$$
then
$$\prod_{k = 1}^m n_k \leqslant n^{m-1}. \tag{2}$$

Writing $n_k = n/d_k$, i.e. setting $d_k = n/n_k$, for $1 \leqslant k \leqslant m$, the inequality $(2)$ is equivalent to
$$\prod_{k = 1}^m d_k \geqslant n\,. \tag{3}$$

Now, the assumption $(1)$ implies $\gcd(n_1, \dotsc, n_m) = 1$. And
$$\gcd(n_1,\dotsc, n_m) = \gcd\biggl(\frac{n}{d_1},\dotsc, \frac{n}{d_m}\biggr) = \frac{n}{\operatorname{lcm}(d_1,\dotsc, d_m)}\,,$$
so we have
$$n = \operatorname{lcm}(d_1, \dotsc, d_m) \leqslant \prod_{k = 1}^m d_k\,,$$
which is $(3)$.