0
votes
1answer
64 views

Prove the reflexivity of $\subseteq$.

My professor gave me a list of exercises, I've been able to figure out what mechanism I should exploit to prove them, but I'd like to know if it's good. Until now we've been taught a little logic and ...
1
vote
2answers
33 views

Proof on limit superior and limit inferior of a set

I understand the result intuitively but how can I prove this? For a given integral $n \ge 1$, let $A_n = \left\{\frac mn \mid m \in \mathbb Z\right\}$. Show that $\varlimsup_{n\to\infty} A_n = ...
4
votes
1answer
39 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
2
votes
0answers
15 views

Set with relative complement forms partition

Prove that if $S$ is a set and $ \emptyset \subsetneq A \subsetneq S $ then $\Pi = \{A , S-A \}$ is a partition of $S$. Proposed Solution: Since $ A \subsetneq S$ , we have $S - A \neq ...
2
votes
1answer
42 views

Proof Verification for Discrete Math Class

Prove that $n^2$ is even iff $n$ is even. I proved it like this: Case I: $n$ is even 1) $n = 2a$ $(a\in Z)$ 2) $n^2 = 4a^2 = 2(2a^2)$ 3) $2a^2 = K$ $(K \in Z)$ 4) $n^2 = 2K$ Case II: $n$ is ...
0
votes
3answers
99 views

Find the problem with this proof.

The following attempts to prove that if $n^2$ is even, then $n$ is even. Suppose $n^2$ is even. Then $n^2$ = 2$k$ for some integer $k$. Let $n$ = 2$m$ for some integer $m$. This shows that $n$ is ...
1
vote
1answer
59 views

Proof by contradiction: logarithm

I need to prove by contradiction that $\log_2(3)$ is irrational. I'm really unfamiliar with logs to be honest, it's been awhile since I've done them and I'm unsure of how to approach this. Any help ...
0
votes
3answers
41 views

Proof by contradiction proving both numbers are not odd.

I have to do a proof by contradiction: Suppose $a,b,\in\mathbb{Z}$. If $4| (a^2 + b^2)$ then a and b are not both odd. So far I know that I need to prove that if $4|(a^2+b^2)$ then a and b are both ...
3
votes
0answers
34 views

An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

Research effort: $\rightarrow)$ I think this is relatively easy. $\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can ...
0
votes
1answer
33 views

Proof regarding division with a remainder

Let $a\in\mathbb{Z},n\in\mathbb{N}$. If $a$ has a remainder $r$ when divided by $n$, then $a\equiv r\pmod n$ I've done some of these questions before with modulus and division, but I'm unsure of how ...
2
votes
5answers
67 views

Proof regarding divisibility

if $n\in\mathbb{Z}$, then $4$ does not divide $(n^2 - 3)$ I'm not sure how to approach this question, I know how to do questions that involve proving that it does divide but I'm unsure of how to do ...
0
votes
2answers
24 views

Modulus related proof help

I need to prove this via either direct proof, or contrapositive. Unsure of the best way to approach this. if $a \equiv b\mod n$ and $c \equiv d\mod n$, then $ac \equiv bd\mod n$ So far I have: ...
1
vote
1answer
30 views

Proof about isometries, symmetry and reversing orientation.

Suppose $f:\mathbb{R} \rightarrow \mathbb{R}$ is an isometry of the reals. Prove that $f$ is a symmetry around a point if and only if $f$ reverses orientation of $\mathbb{R}$. The orientation of ...
2
votes
2answers
112 views

Proving the roots of a polynomial are irrational

This is a homework question so I'm just looking for some guidance. Basically we are asked to write a step by step proof in the form of assume/then statements for: $\forall x \in \mathbb{R}, ax^2 + ...
0
votes
1answer
33 views

Proof about symmetry in isometries.

Suppose $f: \Bbb R \rightarrow \Bbb R$ is an isometry of the reals. Prove that $f$ is a symmetry about a point if and only if $f$ has a unique fixed point. Part 1: The assumption is $f$ is a ...
1
vote
3answers
35 views

Proof about isometries

Suppose $f\colon\mathbb R\to\mathbb R$ is an isometry of the reals. Prove $f$ is a non-trivial translation iff $f$ has no fixed points. Assumption: $f$ is a non-trivial translation (trivial ...
2
votes
2answers
90 views

Proof by induction that $(1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2$

I'm sitting with the proof in front of me, but I do not understand it. $$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$ The first step of proof by induction is ...
0
votes
2answers
27 views

How to prove something at Normal distribution

$X\sim N(\mu,\sigma^2)$. $A,B$ are constants and $A\ne0$. How to prove that $AX+B\sim N(A\mu+B,A^2\sigma^2)$ ? Thank you!
3
votes
2answers
83 views

Proof of $ \phi(n) = \sum_{n|d} \mu(d) \cdot\frac nd $

I'd like to prove $\phi(m)=\sum_{m|d}\mu(d)\cdot\frac md$. If I'm right then we have for euler-phi $\phi(n) = \sum_{m \leq n,\gcd(m,n)=1} 1$ Which means: as long as $m$ is less or equal than $n$ ...
2
votes
2answers
37 views

How to prove something at Uniform distribution…

$X\sim U (0,1)$. The point $X$ divides $[0,1]$ to two parts. $Y=\frac{\text{The big part}}{\text{The small part}}$. ($Y$ is the ratio... $Y\ge1$). What is the density function of $Y$? I'd like to ...
0
votes
1answer
26 views

Proof homomorphism between graphs

Given two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, an homomorphism of $G_1$ to $G_2$ is a function $f:V_1 \rightarrow V_2$ such $(v,w) \in E_1 \rightarrow (f(v),f(w)) \in E_2$. We establish that ...
0
votes
1answer
26 views

Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
0
votes
1answer
37 views

Question about the Least squares method

We have $n$ dots: $(x_1,y_1)\cdots (x_n,y_n)$. We know that if we use the Least squares method we will get a line $y=mx+b$ that giving the minimal value for the function $w=\sum_{i=1}^n ...
3
votes
3answers
81 views

If a connected graph has a unique spanning tree, then it is a tree.

Prove if a connected graph has a unique spanning tree, then it is a tree. Edit: This can be shown with proof by contradiction.
2
votes
1answer
36 views

Is this proof by induction correct?

Prove by induction that for all $n\in\mathbb N$, $3\mid n^3+3n^2+2n$. $$P(1) = (1)^3+3(1)^2+2(1) = 6$$ Which is clearly divisble by $3$. Therefore, $P(1)$ is true. Assume $P(1),\ldots,P(n)$ and ...
0
votes
1answer
29 views

Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$

Prove, disprove, or give a counterexample: Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$. Eccentricity - the ...
0
votes
1answer
33 views

If a tree has order 2 or more, then the minimum cut set is 1. [closed]

Prove: If a tree has order 2 or more, then the minimum cut set is 1.
0
votes
1answer
25 views

Suppose $f:X\to Y$ is onto and $A\subseteq Y$. Then $f(f^{-1}(A))=A$.

Prove, disprove, or give a counterexample: Suppose $f:X\to Y$ is onto and $A\subseteq Y$. Then $f(f^{-1}(A))=A$. Edit: Does this work? Suppose $f:X \to Y$ is onto and $A \subseteq Y$. We know ...
0
votes
1answer
35 views

Proof that any self-complementary graph has to have $4k$ or $4k+1$ vertex, for some $k \in \mathbb N$

I've seen looking on previous questions that using this algorithm, I can construct self-complementary graphs. I got confused at this point, because I'm not sure if I should proof that there are no ...
1
vote
2answers
39 views

Finding quantity of vertex of odd degree in a graph

Let $G=(V,X)$. If $G$ has n vertex, such exactly $n-1$ have odd degree, how many vertex of odd degree have $\overline {G}$. ($\overline {G}$ the complement of $G$.) So the first thing I notice is ...
2
votes
1answer
16 views

Proof that in a graph of $2$ or more vertrex, there's at least $2$ of them that have the same degree

That's what I what to prove let $G$ be an undirected graph such it has $2$ or more vertex, there's at least $2$ vertex that have the same degree. I'm almost certain that, supposing that it's possible ...
1
vote
2answers
44 views

What is the proper way to prove this?

First of all, here is the question I am trying to answer for context. I can see that the statement $\forall x \in \mathbb{Z} , \exists y \in \mathbb{Z}((x\leq y ) \wedge (x+y=0)) $ negates to ...
1
vote
1answer
38 views

Permutation cycles

My tasks are the following : Task 1 : Prove that $ \begin{pmatrix} 1 & 2 & \cdots & r-1 & r \end{pmatrix} = \begin{pmatrix} 2 & 3& \cdots & r & 1 \end{pmatrix} ...
1
vote
1answer
32 views

Constant function with maximum modulus [duplicate]

Suppose that $f$ is analytic on a domain $D$, which contains a simple closed curve $\gamma$ and the inside of $\gamma$. If $|f|$ is constant on $\gamma$, then I want to prove that either $f$ is ...
2
votes
0answers
101 views

Finding minimum graph of $k$ disjoints component

Sorry for the english, I tried to make it the most clear possible. Be $G$ a connected graph not directed, I have to find an algorithm that given $n$ the quantity of vertex and $0<k<n$ disjoint ...
0
votes
1answer
36 views

Equivalence relations and power sets.

Let $\mathcal{A}$ be the class of all sets and define the relation $R$ on $\mathcal{A}$ as: $A\space R\space B$ iff there is a bijective function $f:A \to B$. Prove that $R$ is an equivalence relation ...
0
votes
2answers
55 views

Proving the inscribed angle theorem

I need to prove that a circle's inscribed angle is 1/2 of the arc it intercepts. I am given that one of the chords making up the angle is the diameter. I have an entire project to do based off of this ...
1
vote
3answers
112 views

Are truth tables a valid method to prove an iff statement?

I recently had a homework assignment returned to me (for a Differential Geometry course, undergrad level) in which my instructor wrote "You cannot use truth tables to prove an if and only if ...
6
votes
3answers
113 views

Let $a,b \in R$ where $ a < b$. Prove that there exist a rational number $c$ and an irrational number $d$ such that $ a <c<b$ and $ a<d<b$.

Question : Let $a,b \in R$ where $ a < b$. Prove that there exist a rational number $c$ and an irrational number $d$ such that $ a <c<b$ and $ a<d<b$. Hint: consider decimal expansions ...
2
votes
2answers
68 views

Prove that if $y,z \in Q$ then $y^z \in A$

Question : Prove that if $y,z \in Q$ then $y^z \in A$ My attempt: Definition 2.7.8 states that a number s is an algebraic number when there exists some $p \in Z[x]$ such that $p(s) =0$. Let us ...
0
votes
2answers
50 views

Proof that if we add a vector to a linearly dependent set of vectors in a vector space $V$, then the new set of vectors is still linearly dependent

Prove that if $S=\{v_1, v_2, v_3\}$ is a linearly dependent set of vectors in a vector space $V$, and $v_4$ is any vector in $V$ that is not in $S$, then $\{v_1, v_2, v_3, v_4\}$ is also linearly ...
3
votes
6answers
491 views

How do I begin proving this binomial coefficient identity?

This is a homework question. I'm asked to prove the identity: $${n\choose 0} - {n\choose 1} + {n\choose 2} - {n\choose 3} + \dots = 0$$ (The sum ends with ${n\choose n} = 1$, with the sign of the ...
1
vote
1answer
57 views

Proof: Convex set of a quadrilateral is a convex quadrilateral

Prove that $\Box ABCD$ is a convex set whenever $\Box ABCD$ is a convex quadrilateral. Things I know: A set of points $S$ is said to be a convex set if for every pair of points $A$ and $B$ in $S$, ...
2
votes
4answers
149 views

Prove that the vectors $v_1,v_2,\ldots,v_k \operatorname{span}R^n$ if and only if $[v_1]_B,[v_2]_B,\ldots,[v_k]_B \operatorname{span}R^n$.

From section on Change of Basis $\longrightarrow$ Assume the vectors $v_1,v_2,\ldots,v_k\operatorname{span}R^n$, we must show that $[v_1]_B,[v_2]_B,\ldots,[v_k]_B\operatorname{span}R^n$. We can ...
1
vote
1answer
46 views

Prove for all $ n \in N,gcd(2n+1,9n+4)=1$

Question: Prove for all $ n \in N,gcd(2n+1,9n+4)=1$ Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear ...
0
votes
2answers
14 views

Proof that in any base $b$, the result of multipling two numbers of $k$ digits, doesn't recuire more than $2k$ digits

The proof that I came up whit is: Let, $c$ be $b^0 r_0+ b^1 r_1+b^2 r_2+...+b^k r_k$ and $d = b^0 r_0'+ b^1 r_1'+b^2 r_2'+...+b^k r_k'$ then multipling both: $$(b^0 r_0+ b^1 r_1+b^2 r_2+...+b^k ...
0
votes
2answers
19 views

Proof that in any base, the sum of two numbers of fixed precision can't have carry more than 1

The best proof that I came with is, given any base $b$, let $c$ be the greatest number can be written whit $n$ digits. Then the number will be: $$c=b^0(b-1)+b^1(b-1)+\cdots +b^n(b-1)$$ Summing this ...
1
vote
2answers
48 views

fourier series analysis, show that for every integer n, using euler's formulas relating trigonometric and exponential functions

Show that for every integer $n$, $$\int_0^{\pi} \cos nt~\sin t~\mathrm{d}t = \begin{cases} \dfrac{2}{1-n^2} & \text{if } n \text{ is even} \\[10pt] 0 &\text{if } n \text{ is odd} ...
0
votes
0answers
74 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
1
vote
0answers
69 views

Power Set, Bijection Function, Equivalence Relation

Let $S$ be a set and $P(S)$ the power set of $S$. For sets $A,B⊆P(S)$, we say that $A \sim B$ if there exists a bijective function $f: A \rightarrow B$. Show that $\sim $ is an equivalence relation.