Tag Info

Hot answers tagged

8

Take your claim But since $\forall x \in A: x \in B$ and $\forall x \in B: x \in C$ by the statement above, every $x \in A$ must also be in C. That's already a proof of your result! So packaging that proof inside a longer argument which starts off by assuming the opposite of what you want to establish, and then aims for a contradiction, is just ...


5

Use the induction method: First, take $n=3$, $3! = 6$ and $3^3 =27$, $3! < 3^3$. Second, assume the inequality holds for $n = K$, $K \in \mathbb{N}$, $K>3$, i.e. $K! < K^K$. Then consider $n= K+1$, $(K+1)! = (K+1) K! < (K+1) K^K < (K+1) (K+1)^K = (K+1)^{K+1} $, which is $(K+1)! < (K+1)^{K+1}$. Proved.


4

Observe that: $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$. Thus: $\displaystyle \sum_{k=1}^{n+1} k\binom{n+1}{k} = \displaystyle \sum_{k=1}^{n+1} k\binom{n}{k} + \displaystyle \sum_{k=1}^{n+1} k\binom{n}{k-1} = \displaystyle \sum_{k=1}^n k\binom{n}{k} + \displaystyle \sum_{k=0}^n (k+1)\binom{n}{k} = 2\displaystyle \sum_{k=1}^n k\binom{n}{k} + ...


3

We know that $n$ and $m$ divide both $k$ and $q$. Since $k$ is the lowest common multiple, $k \leq q$. If $k = q$ then the result is obvious. Let's assume that $k < q$ Then we can do the integer division between $k$ and $q$: $q = t·k + r$ so that $0 \leq r < k$. Since $n$ and $m$ divide $q$ and $k$ then they divide $q - t·k = r$. Therefore $n$ ...


3

Via induction it's a bit tiresome but Base case $n=2$, $2!=2<4=2^2$ is pretty straightforward. Then multiplying both sides by $n+1$ gives $$(n+1)!< (n+1)n^n$$ Considering $$(n+1)n^n < (n+1)(n+1)^n=(n+1)^{n+1}$$ so by induction we are done. Again, a direct proof is infinitely easier, for $n\ge 2$, so I include it for comparison's sake. ...


3

If $x > 1 \quad \Rightarrow \quad x^2 > x \quad \Rightarrow x^3 > x^2 \ \ldots$. By induction, $x^{n+1} > x^n$. Thus, $x^m \geq x^{n+1} > x^n$.


2

It is okay. You could also do it directly: Take $x \in A$. Since $A \subseteq B$, we get $x \in B$. But $B \subseteq C$ implies that $x \in C$. So we conclude that $A \subseteq C$.


2

Inductive hypothesis: For $n = k$, $$\color{blue}{2^k \geq k^2},\quad k \geq 4.$$ $$2^{k+1} = 2\cdot \color{blue}{2^k} \geq 2(\color{blue}{k^2}) \geq k^2 + k^2 \geq k^2 + 2k + 1 \overset{\large k>2} = (k+1)^2$$


2

Edited: I see why this is false but in general, why every closed subset of a compact set is compact? Another proof: Let $S \subset T$ be a closed set, where $T$ is compact. Let $\{\mathcal{U}_\alpha\}$ be an open cover of $S$. Then $\{\mathcal{U}_\alpha\} \cup \{S^c\}$, where $S^c$ is the complement of $S$ w.r.t. to $X$, covers $T$. Since $T$ is ...


2

Lemma: If $0<a<1$ I claim for any $b>0$ that $0<ab<b$ Proof: $b(1-a)$ is a product of positive numbers hence is positive. Corollary: $a^n<1\implies a^{n+1}<1$ when $0<a<1$ Proof: By induction, the base case being given, then let $b=a^n$ in the lemma. Alternatively, a direct proof: Write $$a^n-1=(a-1)(a^{n-1}+a^{n-2}+\ldots ...


2

Yes, you want to show that given $a^n\le 1$, then $a^{n+1}\le 1$. Well since $a>0$, we know that $a^{n+1}\le a$. But $a<1$. So we have $a^{n+1}\le a\le1$ as desired. This proof would clearly not work if $a$ were not less than $1$.


2

You are very close. For brevity, denote $R$ composed with $R$ by $R\circ R$. By the definition of composition, the pair $(a,c)$ is in $R\circ R$ if and only if there exists a $b$ such that $(a,b)$ and $(b,c)$ are both in $R$. But if there is such a $b$, then by transitivity $(a,c)$ is in $R$. Thus if $(a,c)$ is in $R\circ R$, then $(a,c)$ is in $R$. ...


2

You can simplify your argument. You should look at $g(i)$ compared to $g(i_0)$, which reduced the number of cases to 2: if $g(i_1)=g(i_2)=g(i)<i_0$, then $i<i_0$ as $g$ is strictly increasing. Then you know that $i_1=g(i_1)=g(i_2)=i_2$. same goes for $g(i_1)=g(i_2)=g(i)>i_0$ $i_1+1=g(i_1)=g(i_2)=i_2+1$. there is no case $g(i_0)=i_0$ by definition ...


1

Here is a way to derive this result. By the binomial theorem, $$(1+x)^n =\sum^{n}_{k=0}\binom{n}{k}x^k$$ Differentiate both sides. $$n(1+x)^{n-1} =\sum^{n}_{k=0} k\binom{n}{k}x^{k-1}$$ Substitute $x=1$ $$n2^{n-1} =\sum^{n}_{k=0} k\binom{n}{k} =\sum^{n}_{k=1} k\binom{n}{k} $$


1

The first thing you need to do is to get the definitions absolutely clear. A (binary) relation $R$ on a set $A$ is not a subset of $A$, it is a subset of $A\times A$. In other words, $R$ does not consist of elements of $A$, it consists of pairs of elements of $A$. A relation $R$ on a set $A$ is transitive means: for all $a,b,c\in A$, if $(a,b)\in R$ and ...


1

$0 < a < 1 \ \Rightarrow \ 1 = a + x$ with $x > 0$. Thus, $$ 1 = 1^n = (a + x)^n = a^n + \sum_{k=0}^{n-1}{n \choose k}a^kx^{n-k} \geq a^n \quad \Rightarrow \quad a^n \leq 1 $$


1

Let's take a look at what we're trying to prove: $$ \forall \epsilon > 0 \; \exists N \in \mathbb{N} : \lvert a_n + c - (a_\infty + c) \rvert < \epsilon \; \forall n \ge N \tag{1} $$ Now let's take a look at what we know: Since $a_n \to a_\infty$ we have $$ \forall \epsilon > 0 \; \exists N \in \mathbb{N} : \lvert a_n - a_\infty \rvert < ...


1

It is a matter of doing things in an orderly manner. Yes, this covers all cases: either the image is contained in $[k]$, or it maps to $k+1$. Induction is made over $k$; not $m$. Careful. This is wrong. Induction is being made over $k$, and your induction hypothesis is that if $[m]\to [k]$ is an injection, $m\leqslant k$. You don't know anything about ...


1

Basically you want to show that $f(x) = c^x > 1$ when $c>1$ for all $x>0$. Consider $\frac{d}{dx}f(x)$ to show that $f$ is a strictly increasing function, and evaluate $f(0)$.


1

To show $g \circ f$ is continuous, you need to show it satisfies the property of continuity that you stated. So, you need to prove if $V \in \tau_{3}$, then $(g \circ f)^{-1}(V) \in \tau_{1}$. (Note that $(g \circ f)^{-1}(V) = f^{-1}(g^{-1}(V)).)$ Here is a hint: Use the fact that both $f$ and $g$ are continuous. Start with $g$. If we have $V \in ...


1

We know that $n!<n^n$ for some $n$, via our inductive hypothesis. We want to show that $(n+1)!<(n+1)^{n+1}$. Your first step is good, multiplying both sides of our inductive hypothesis by $n+1$ to get $(n+1)!<(n+1)n^n$. But $n^n<(n+1)^n$ (we can assume this, if not, it is very easy to prove), so $(n+1)(n^n)<(n+1)(n+1)^n$ and we have that ...


1

Think of it this way. You know the inequality $|x-2| \cdot |x+2| < |x-2| \cdot 5$ is true. You are trying to show that the inequality $|x-2| \cdot |x+2| < \epsilon$ is true. By the transitive property of inequality, you will have successfully shown that inequality to be true if you are able to show that $|x-2| \cdot 5 < \epsilon$. This is ...


1

The sum $w$ covers the first $m$ terms, where the two sums agree. What is left over is the sum from the $m$th term on. We have $\alpha_m = 0$ so we can write $$x = w + \sum_{i=m+1}^\infty \frac{\alpha(i)}{3^i}$$ But of course since $\alpha(i)$ is either $0$ or $2$, $\alpha(i) \leq 2$ $$x \leq w + \sum_{i=m+1}^\infty \frac{2}{3^i}$$ The infinite part of ...


1

I like your idea that if $U(n)$ has an element of even order, then the order of $U(n)$ is even by Lagrange's Theorem. On the other hand, for $n>2$, the order of $n-1$ in $U(n)$ is 2. Another approach to this problem is to work with properties of the Euler phi function since $o(U(n))=\varphi(n)$.



Only top voted, non community-wiki answers of a minimum length are eligible