New answers tagged

0

Well, first of all you mean two maximal $k$-connected subgraphs $G_1$ and $G_2$; as in $G_1$ and $G_2$ are $k$-connected but there is no subgraph $G'_1 \supset G_1$ of $G_1$ nor is there a subgraph $G'_2 \supset G_2$ of $G_2$ that is $k$-connected. The result you want is Claim 1 below: Claim 1: Suppose that $G_1$ and $G_2$ share $k$ or more vertices. Then $...


0

I would try proving this by contradiction. Suppose $V(G_1)\cap V(G_2) \geq k$. Then I would show that $G_1\cup G_2$ is $k$-connected. This would contradict the maximality of $G_1$ and $G_2$. I would look at the proof that any two distinct blocks in a graph contain at most one common vertex for some more help.


1

This is correct - as far as it goes. But your question Why Rudin used $n(y−x)>1$ in the first place? is in a way the crux of the matter. The other steps are the routine part - the framework, as it were. This is the place where you need some actual understanding/intuition about "why" the assertion is correct. That you develop over time, by ...


0

This is merely an attempt to inspire, i was not able to conclude this way. So i think you can procede in this way. $$g_{c,d}(x)=\int_{\frac{1}{2}}^xz^{c-1}\sum_{i=0}^{d-1}{{d-1}\choose{i}}(-z)^{d-i-1}dz=$$ $$=\sum_{i=0}^{d-1}{{d-1}\choose{i}}\int_{\frac{1}{2}}^xz^{c-1}(-z)^{d-i-1}dz=\sum_{i=0}^{d-1}(-1)^{d-i-1}{{d-1}\choose{i}}\int_{\frac{1}{2}}^xz^{c+d-i-2}...


1

For the case of sequences, the $\varepsilon-\delta$ type proof is as follows: Given $\varepsilon>0$, you need to find $N\in\Bbb N$ (depending on $\varepsilon$) such that for all $n\ge N$, it holds that $|s_n-L|<\varepsilon$ (in your case, $|s_n-1|$). For that purpose, observe that $$|s_n-1|=\left|\frac{n}{n+\sqrt n}-1\right|=\left|\frac {n-(n+\sqrt n)...


2

Observe that \begin{align*} \biggl|\frac{n}{n+\sqrt{n}} -1\biggr| = \biggl|\frac{\sqrt{n}}{n+\sqrt{n}}\biggr|\leq \frac{\sqrt{n}}{n}=\frac{1}{\sqrt{n}} \end{align*} Hence you have to choose an $n$ such that $\epsilon >\frac{1}{\sqrt{n}}$ happens.


0

Chebyshev bounds are "loose" bounds and useful when you don't know the distribution. Here you know the distribution of $Z$. Why not directly work with the distribution function? For example, let $y = -\frac{\sqrt{\epsilon}}{\Delta t}(1 + \frac{\epsilon - 1}{\epsilon}\Delta t)$. Then, $$ N(y) = P(Z < y) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{y}e^...


1

Your argument is fine, but you are doing more than you need to do in the first part: you are doing the right thing in the second part showing that $f = g$ as sets of pairs if $f$ and $g$ are functions with the same domain that agree on any element of that domain. For the first part, there isn't really anything to prove: if $f = g$, then any property that ...


2

Your proof is correct. A far shorter proof follows. For $1\le x<kn$, $b^x\ne e$ since $$b^x=(b^k)^{\lfloor x/k\rfloor}b^{x\bmod k}=a^{\lfloor x/k\rfloor}b^{x\bmod k}$$ Either $x\bmod k>0$ and $b^x\not\in\langle a\rangle$ because the first factor is in $\langle a\rangle$ and the second is not, or $x\bmod k=0$ but $\lfloor x/k\rfloor\in[1,n)$ and $b^x=a^{...


0

In logic there are generally two kinds of rules: introduction rules and elimination rules. An introduction rules tells us how to prove something, whereas an elimination rule tells us how to use something as a hypothesis. ($\forall$-introduction) To prove $\forall x.\phi(x)$, you introduce a new variable $x$, and attempt to prove $\phi(x)$. Note the emphasis ...


0

To prove statements like that you have to take an arbitrary $x$, and find a $y$ such that $p(x,y)$ holds. If you can't do this, it means that the statement is false. However, the negation of $\forall x\,\exists y\,p(x,y)$ is not usually what you wrote. It is interpreted as $\exists x\,\forall y\,\neg p(x,y)$. Note that quantifiers do not commute in general.


0

Hint: exploit innate symmetry: $\ \ \underbrace{\overbrace{-a^4 = 1^{\phantom{|}}_{\phantom{.}}\!\!}^{\!\!\!\!\textstyle \color{#0a0}{(-a^3)}a\!=\! 1}}_{\!\!\!\!\!\!\textstyle(\color{#c00}{-a^2})a^2\! =\! 1}\Rightarrow\ (a+\overbrace{a^{-1}}^{\!\!\textstyle \color{#0a0}{-a^3}})^2 = a^2+\underbrace{a^{-2}}_{\!\textstyle \color{#c00}{-a^2}}+ 2\, =\, 2$


1

Assume that the claim is false. Without loss of generality, this implies that there is some $m,n\in\mathbb N$, $m<n$, such that there is an injection $f$ from $[n]\to[m]$ ($[n]$ is notation for $\{1,...,n\}$). Also without loss of generality, we can assume that $n$ is the smallest natural for which this property holds. If $n=1$, the claim is clearly false ...


1

hint Let $ \epsilon>0 $ small enough. Consider the partage $$P=(0,1-\frac{\epsilon}{3},1+\frac{\epsilon}{3},2)$$ then $$U(f,P)-L(f,P)=\frac{2\epsilon}{3}<\epsilon$$ Its integral is given by $$\int_0^1f+\int_1^2f=$$ $$\lim_{n\to+\infty}(\int_0^{1-\frac 1n}dx+\int_{1+\frac 1n}^2dx)=$$ $$\lim_{n\to+\infty}(1-\frac 1n)+(2-1-\frac 1n)=$$ $$\lim_{n\to+\infty}...


1

$n!+n\le n!+n\cdot n!=n!(1+n)=(n+1)!\;$ for all $\;n\in\mathbb{N}\cup\left\{0\right\}.$


2

$\frac{1}{n+1} + \frac{n}{(n+1)!} \leq \frac{1}{n+1} + \frac{n}{(n+1)} = 1$ Therefore since $\frac{1}{n+1} + \frac{n}{(n+1)!}= \frac{n!}{(n+1)!} + \frac{n}{(n+1)!} $ your inequality follows immediately.


1

Also if $n=0$ it is obvious ($1\le 1$), for $n\ge 1$: $$n!+n\le n!+n!=n!2\le (n+1)!$$


3

If $n \ge 1$, this is equivalent to $$ 1 \le n(n-1)! $$ which is clear.


0

If every $n_j=1$ we have $k\ge k^2$, which is FALSE unless $k=1.$ If $n_i\ne n_j$ whenever $i\ne j,$ we can prove it by induction on $k$. It's obvious when $k=1.$ Suppose $A$ is a set of $k+1$ different members of $\Bbb N.$ Let $M=\max A.$ Let $C$ be the sum of the cubes of the other members of $A$. That is, $C=\sum_{a\in A\setminus \{M\}}a^3.$ Let $S$ be ...


3

$$a^8-1\equiv 0 \implies (a^4+1)(a^4-1)\equiv 0 \implies a^4 \equiv -1 \pmod p$$ $$c^2=(a-a^3)^2=a^2-2a^4+a^6=a^2(1+a^4)-2a^4\equiv 2 \pmod p$$ $$d^2=(a+a^3)^2=a^2+2a^4+a^6=a^2(1+a^4)+2a^4\equiv -2 \pmod p$$


1

I don't really get what you mean by simplify it. Anyways, in case the last part of the induction part is required, given your inequality and the induction hipothesys you would have: $$\sum_{j=1}^{n+1}\sqrt[4]{j^5}\ln\biggl(1+\frac{1}{j^2}\biggr)\le 4\sqrt[4]{n}+\sqrt[4]{(n+1)^5}\ln\biggl(1+\frac{1}{(n+1)^2}\biggr)\le$$ $$\le 4\sqrt[4]{n}+4\sqrt[4]{\frac{n+1}{...


1

As regards your final step, just notice that $\ln(1+x)\leq x$.Therefore it suffices to show that $$\sqrt[4]{(n+1)^5}\cdot \frac{1}{(n+1)^2} \leq 4 \sqrt[4]{\frac{n+1}{n}}$$ that is $$\sqrt[4]{n}\leq 4 (n+1)^{\frac{1}{4}+2-\frac{5}{4}}=4(n+1)$$ which trivially holds.


0

For $n_1=\cdots=n_k=m<k$, your inequality is wrong since $$ n_1^3+\cdots+n_k^3=km^3<k^2m^2=(n_1+\cdots+n_k)^2 $$ A different approach for correcting the inequality Let's try to solve it through optimization. We solve the following problem $$ {\min n_1^3+\cdots+n_k^3 \\ s.t.\\n_1+\cdots +n_k=u } $$using the Lagrange's method. Skipping the middle steps, ...


0

A subset B implies #A <= #B. Proof. f:A -> B, x -> x is an injection from A into B.


1

You need to show those intervals "continuously overlap". That is for any $k \in \mathbb N$ we have $\frac 1{2^{k+1}} < \frac 1{2^k} < \frac 3{2^{k+1}} < \frac 3{2^k}$. That follows as $\frac 12 < 1 < \frac 32 < 3$. This means $\cup (\frac 1{2^n},\frac 3{2^n}) = (\lim_{n\to \infty} \frac 1{2^n}, \frac 3{2^1}) = (0, \frac 32)$ ...


1

Let $0<x<1$. Consider the interval $(\frac {\ln (\frac 1 x)} {\ln 2},\frac {\ln (\frac 3 x)} {\ln 2})$. The length of this interval is easily seen to be $\frac {\ln 3} {\ln 2}$. Since any interval of length greater than $1$ contains an integer there exist a positive integer $n$ in this interval. You can now verify that $x \in (\frac 1 {2^{n}},\frac 3 ...


1

I would note that $G_1=(1/2,3/2)$ which covers $(1/2,1)$, and then noting that $$\frac{3}{2^{n+1}} \ge \frac{1}{2^n} \iff \frac{3}{2} \ge 1 \mbox{, for all }n\in \mathbb{N}$$ which is true. This gives us that two consecutive intervals have non-empty intersection so that $$\bigcup_{n\le N}G_{n}=\left(\frac{1}{2^N},1\right) \mbox{, for all } N\in \mathbb{N}$$...


0

For the first question, use https://mathworld.wolfram.com/EulersTotientTheorem.html or https://mathworld.wolfram.com/CarmichaelFunction.html and https://en.m.wikipedia.org/wiki/Proof_by_contradiction For the second, if $p\nmid a\iff(a,p)=1$ $$a^{p-1}\equiv 1\pmod p$$ If $(a,2)=1,$ using Carmichael or Totient function, $$a^{2^{n-1}}\equiv1\pmod{2^n}$$ $$\...


0

So I got stuck at that point with my induction: $$1 + \frac{1}{\sqrt[3]{2}} + ... + \frac{1}{\sqrt[3]{n}} + \frac{1}{\sqrt[3]{n+1}} < \frac{3}{2}\sqrt[3]{(n+1)^2}$$ Then, trying to separate elements on the right hand side I got: $$1 + \frac{1}{\sqrt[3]{2}} + ... + \frac{1}{\sqrt[3]{n}} + \frac{1}{\sqrt[3]{n+1}} < \frac{3}{2}\sqrt[3]{n^2(1 + \frac{2}{n} ...


2

Let $M := M(\epsilon,\Delta t) = \frac{\sqrt{\epsilon}}{\Delta t}\left(1 + \left(1 - \frac{1}{\epsilon}\right)\Delta t\right)$. Recall that for any random variable $X$ with a finite second moment and non-negative number $x$, Chebyshev's inequality states: $$\mathbb{P}(|X| > x) \leq \frac{\mathbb{E}[X^2]}{x^2}.$$ I'm guessing your application of the ...


1

You seek to verify the inequality $\frac{3}{2} \sqrt[3]{n^2} + \frac{1}{\sqrt[3]{n+1}} \overset{?}{<} \frac{3}{2} \sqrt[3]{(n+1)^2}.$ Cubing both sides yields $$n^2 + 3 (2/3) n^{4/3}(n+1)^{-1/3} + 3(2/3)^2 n^{2/3}(n+1)^{-2/3} + (2/3)^3 (n+1)^{-1/3} \overset{?}{<} (n+1)^2$$ $$3 (2/3) n^{4/3}(n+1)^{-1/3} + 3(2/3)^2 n^{2/3}(n+1)^{-2/3} + (2/3)^3 (n+1)^{-...


1

Since $k^{-1/3}=\int_{k-1}^kk^{-1/3}dx<\int_{k-1}^kx^{-1/3}dx$,$$\sum_{k=1}^nk^{-1/3}<\sum_{k=1}^n\int_{k-1}^kx^{-1/3}dx=\int_0^nx^{-1/3}dx=\tfrac32n^{2/3}.$$


2

Hint: the polynomial $\,f(x)\,$ is congruent to $\,2x-1\,$ both mod $p_1$ and $q_1$ by little Fermat, so by CRT it boils down to computing its root $\,x\equiv 1/2\equiv (1\!+\!n)/2\pmod{\!n}\,$ for odd $\,n = p_1 p_2$. i.e. let $\,p_1,p_2 = p,q.\,$ $\,f(x) = x(x^{q-1}\!-\!1)+\!2x\!-\!1\,$ so by Fermat & $\,p\!-\!1\mid q\!-\!1^{\phantom{|^|}}\!\!$ & $...


1

I assume $\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z}$. By the chinese remainder theorem, $\mathbb{Z}_m=\mathbb{Z}_{p_1}\times\mathbb{Z}_{p_2}$. So the problem boils down to proving that there is a unique solution to $x^{p_2}+x-1=0$ on each $\mathbb{Z}_{p_i}$. On $\mathbb{Z}_{p_2}$, note that $x^{p_2}=x$ for each $x$ (Fermat's little theorem) and solve the equation....


1

Your proof is correct (with one inattentiveness in line -2: $f^{-1}(U) = M(a) \cap m(b)$). For a shorter proof see William Elliot's anwer. It sticks out that in the first part you work with the $\varepsilon$-$\delta$-definition of continuity, whereas in the second part you use a theorem about continuity: A function $f$ is not continuous if for some open ...


0

I think the way to think about this is to realize that there's nothing special about any point in $\mathbb P^n$. The same goes for any (n-1)-plane in $\mathbb P^n$. To expand upon @Mummy the turkey's comment: every point in $\mathbb P^n$ is represented by a point $\overline P$ in $\mathbb A^{n+1}$. There is always a linear transformation sending $\overline ...


1

B is a subbase for a space S when { $\cap$F : F finite subset B } is a base for S. Theorem. If f:X -> Y, B is a subbase for Y, and for all U in B, f$^{-1}$(U) is open, then f is continuous. To apply this theorem to your problem, note that { (-$\infty$,x), (x,$\infty$) : x in R } is a subbase for R. The proof of the theorem is straight forward and ...


1

Without induction, the problem would be quite simple since you want to prove that $$\frac{2^n }{\sqrt{\pi }}\Gamma \left(n+\frac{1}{2}\right)<\left( \frac{2n}{e} \right)^{n+1}$$ Taking logarithms and using Stirling approximation $$\log(\text{rhs - lhs})=\left(\log (n)-1+\frac{\log (2)}{2}\right)+\frac{1}{24 n}+O\left(\frac{1}{n^3}\right)$$ $$\text{rhs - ...


1

The first one is what it's saying. In order to satisfy the axiom as presented, one must show: $\langle v, v \rangle \in \Bbb{R}$ for all $v \in V$, $\langle v, v \rangle \ge 0$ for all $v \in V$ (note that $\langle v, v \rangle$ can only be considered $\ge 0$ if it is a real quantity), $\langle v, v \rangle = 0 \implies v = \vec{0}$, $v = \vec{0} \implies \...


1

Just note the notation (even you might know what you are talking about) is not correct $$A \times [(B\land\neg C)\lor (\neg B \land C)]$$ Is this a set or a proposition? If it's a set $$A \times (B\oplus C)=A\times[(B\cap C^c)\cup(B^c\cap C)]$$ If it's a proposition, for $(a,b)\in A \times (B\oplus C)$ have $$a\in A\land b\in[(B\cap C^c)\cup(B^c\cap C)]$$ ...


1

From where you left off, you have $a \in A,b\in B,b\notin C \vee a\in A, b \notin B, b \in C$. Hence, $(a,b) \in (A \times B) \vee (A \times C)$ and $b\in B \Leftrightarrow b\notin C$ so that $(a,b)\in (A \times B) \Leftrightarrow (a,b) \notin (A \times C)$. Therefore $(a,b) \in (A \times B) \oplus (A \times C)$ and $A \times (B\oplus C) \subseteq (A \times ...


1

Suppose that $T$ is the graph of a function, that is, suppose that there exists $g : X \to Y$ such that $T = \{(x,y) \in X \times Y : y = g(x)\}$. Now, take $a \in X$ and observe that $T \cap (\{a\} \times Y)$ is non-empty since $(a,g(a)) \in T \cap (\{a\} \times Y)$. We claim that $T \cap (\{a\} \times Y) = \{(a,g(a))\}$. Indeed, if $(x,y) \in T \cap (\{a\} ...


1

Assuming that binomial coefficients are integers (they are, by a simple combinatorial argument), you can use them with telescoping to write your expression: \begin{align*} &\binom{j_1+\cdots +j_k}{j_1}\cdot \binom{j_2+\cdots +j_k}{j_2}\cdots \binom{j_{k-1}+j_k}{j_{k-1}}\cdot \binom{j_k}{j_k}\\ &= \frac{(j_1+\cdots +j_k)!}{j_1!\cdot (j_2+\cdots +...


2

For induction on $k$, the base step $k=1$ gives a ratio $\tfrac{n!}{n!}=1$. To go from $k=j$ to $k=j+1$ in the inductive step, replace $\tfrac{1}{j_k^\text{old}!}$ with $\frac{1}{j_k^\text{new}!j_{k+1}!}$, wth $j_k^\text{new}=j_k^\text{old}-j_{k+1}$. This multiplies the ratio by $\frac{j_k^\text{old}!}{j_k^\text{new}!j_{k+1}!}=\binom{j_k^\text{old}}{j_{k+1}}$...


3

The given expression counts the number of ways to order $n$ objects, with $j_1$ objects of type $1$, $j_2$ of type $2$ and so on until $j_k$ objects of type $k$, and there are no other objects or types. Thus the expression must be an integer.


2

Write $$\sum_{i=1}^{n}i\times\frac{^{n-1}P_{i-1}}{n^i}=\sum_{i=1}^n\frac {i(n-1)!}{(n-i)!n^i}=\frac1n\sum_{i=0}^n\frac {i(i!)(n!)}{(n-i)!(i!)n^i}=\frac1n\sum_{i=0}^n\frac {i(i!)}{n^i}\binom n i$$ Then refer to Proof Binomial Coefficient Identity: $\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$


0

Let $\pi:\mathbb A^{n+1} \setminus 0 \to \mathbb P^n$ be the projection map, and let $v_0,..., v_n$ be a basis for the vector space structure $V$ induced on affine space by your choice of coordinates downstairs (the spans $\langle v_i \rangle$ are obtained as $$ \langle v_i \rangle = \pi^{-1}(0:\cdots : 0 : \underbrace{1}_{i\text{-th entry}} : 0 : \cdots : 0)...


0

As shown in Baby Rudin we can apply L'Hopital's Rule as long as the denominator tends to $\infty$; it is not necessary that we have $\frac {\infty} {\infty}$ form. So apply the rule to $\lim \frac {f(x)} x$ to show that $f'(x) \to 0$. Hint for proof using MVT: If $f'(x) \ to l >0$ the $f(n+1)-f(n) \geq \frac l 2 $ for all $n$ sufficiently large. Show ...


0

Sketch: 1.$$\lim_{x\to\infty}\frac{e^x f(x)}{e^x}=\lim_{x\to\infty}(f’(x)+f(x))\,,$$ which implies $$L=\lim_{x\to\infty}f’(x)+L\,.$$ 2.$$f(x+h)-f(x)=f’(\xi)h \,,$$ yields $$L-L=\lim_{x\to\infty}f’(x) h\,.$$


3

Hint: \begin{align} |a_{n+2}-a_{n+1}|&\leq \frac{1}{8} |a_{n+1}^2-a_n^2| \\ &=\frac{1}{8}|a_{n+1}+a_n| |a_{n+1}-a_n| \\ &\leq \frac 12 |a_{n+1}-a_n| \end{align} Hence, $|a_{n+k}-a_n|\leq ...$?


Top 50 recent answers are included