0
votes
2answers
29 views

Proof by induction sum $2^j = 2^{n+1} - 1$

I am trying to solve a previous test for an exam, and there are no solutions. The problem I am trying to solve is If $n$ is a natural number, then $1 + 2 + 2^2 + 2+3 + ... + 2^n = 2^{n+1} -1$ ...
-1
votes
2answers
38 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 ...
0
votes
2answers
23 views

How to quantify this statement

How do I quantify this statement? Let $x \in \mathbb{R}$. $1 \le x \le 2$ if and only if $1 \le x \le 1+ 1/n$ for some $n \in \mathbb{N}$. When I am trying to prove this, I am led (in the course of ...
2
votes
2answers
34 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
1
vote
1answer
38 views

Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

I'm trying to study for a quiz. I think I'm on the right track with this problem, however, I'm having a difficult time formalizing it. Prove that if graph $G$ is a 3-connected planar graph then its ...
0
votes
0answers
8 views

prove where $f(x,y) = \sqrt{|x| + |y|}$ is differentiable and is not differentiable [duplicate]

Classify where $f(x,y) = \sqrt{|x| + |y|}$ is differentiable -- where it's not, prove it, and where it is, prove it. For $x\neq 0$ and $y\neq 0$, we can just treat it as $f(a,b) = \sqrt{a+b}$ (where ...
-2
votes
1answer
28 views
0
votes
1answer
34 views

Suppose that the sequence of prices{$p_k$} converges to a limiting price $\bar p$. What must $\bar p$ be?

We let $Q_k$ denote the supply of commodity, $D_k$ the demand for the commodity, and $p_k$ the price at $k$-th time. The demand depends on the current price, $D_k = a + b p_k$ and the supply depends ...
0
votes
1answer
41 views

General conceptual confusion relating to vacuous proofs and quantifier help

I need to prove the statement: Let $x \in \mathbb{R}$. Prove that $1 \le x \le 2$ if and only if $1 \le x \le 1+ 1/n$ for some $n \in \mathbb{N}$. So I start with the forward implication: If $1 ≤ ...
0
votes
0answers
64 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
1answer
18 views

basic conditional probability proof

I having trouble with the following proof: $$P((A \cap B) \mid B) = P(A\mid B).$$ I get that $P(A\mid B) = P(A \cap B) / P (B)$, but I am unsure of how to proceed.
0
votes
2answers
45 views

Sum of the eigenvalues

if $V$ is a finite-dimensional vector space and $t \in \mathcal L (V,V) $is such that $t^2 = id_V$ prove that the sum of eigenvalues of t is an integer. I started the prove as such: Let $\lambda_1 ...
0
votes
4answers
47 views

Help with a certain proof

For all $x,y \in \mathbb{R} - \{0\}$, $(xy)^{-1}=x^{-1}y^{-1}$. I was wondering how I could solve this.
0
votes
3answers
35 views

Let $x,y \in \mathbb{R}_{>0}$. If $x<y$ then $0<1/y<1/x$.

I came across a proof in my textbook and was wondering how to solve it: Let $x,y \in \mathbb{R}_{>0}$. If $x<y$ then $0<1/y<1/x$.
0
votes
0answers
25 views

Equal fields and dimension

Let $K \subseteq L$ be fields. Show that K=L if and only if $dim_k L=1$ I know that I will have to show both directions of the implication. I'm very new to the topic of fields so I'm still ...
0
votes
3answers
39 views

Proof that $X^C \cap Y^C= \;(X \cup Y)^c$

Proof that if $X \subset S,\; Y\subset S,\;$ then $\;X^C \cap Y^C= \;(X \cup Y)^c:$ It must be shown that the two sets have the same elements, that each element of the set on the left is an element ...
2
votes
2answers
59 views

Could this linear algebra proof be done without computation?

From page 95 of Hoffman & Kunze's Linear algebra: Let $T$ be the linear operator on $\mathbb{R}^2$ defined by $T(x_1,x_2)=(-x_2,x_1)$ Prove that if $B$ is any ordered basis ...
0
votes
3answers
35 views

What is this problem stating? And how to prove this?

$$\exists! x : A(x) \Rightarrow \exists x : A(x)$$ Assuming that $A(x)$ is an open sentence. I'm new to abstract mathematics and proofs, so I came here to ask for some simplification. Thanks
0
votes
0answers
14 views

Field Extensions Identities

I'm working on proving some identities but I need some help clarifying the notation and what exactly each statement is saying. Prove the following identities. (a) $K(A) = QF (K[A])$ (b) $R[A_1 ...
1
vote
1answer
32 views

Divisors of prime factorizations

Let $f,g,h \in F[x]$, with $f(x)$ and $g(x)$ relatively prime. If $f(x)$ divides $h(x)$ and $g(x)$ divides $h(x)$ prove that $f(x)g(x)$ divides $h(x)$. My thoughts: there are certain properties that ...
0
votes
1answer
25 views

Greatest common divisor of ring elements

Consider the ring $\mathbb Q[x]$. (a) Suppose that $a(x) = (x+1)^3(x-1)^4(x+2)$ and $b(x) = (x+1)^2(x+2)^3(x-3)^4$. What is the $\gcd (a(x),b(x))$? (b) Suppose that $c(x) = (x^2-1)^4(x^2+3x+2)$. ...
1
vote
0answers
12 views

Splitting Fields Proof

Let $K\subseteq L$ be fields and $ f \in K[X] \setminus K$. Prove that the following are equivalent. (a) $L$ is a splitting field for $f$ over $K$ (b) $f$ splits over $L$ and $L=K(a_1,\ldots,a_n)$ ...
0
votes
2answers
42 views

Help with a proof I came across

I came across this in my textbook and was wondering how it could be proven. If $a\mid m$ and $b\mid m$ and $gcd(a,m) = 1$, then $ab\mid m$. It's near some Euclid and Extended Euclid proofs so I ...
2
votes
2answers
158 views

Help with graph induction proof

I'm trying to prove : Given a simple graph G with n vertices, where n is even, prove that if every vertex has degree n/2 + 1, then G must contain a (simple) 3-cycle. A (simple) 3-cycle is a set of 3 ...
0
votes
1answer
26 views

Proof for a graph distance

For Graph $G$, there are several $(x, y)$-paths; the shortest among them have length $2$. Thus $d(x, y) = 2$. Prove that graph distance satisfies the triangle inequality. That is, if $x,y,z$ are ...
0
votes
0answers
25 views

Linearly Independent and Span Proof

Let R be a field, M be an R-module, $X \subseteq M$. Show that $X$ is linearly independent if and only if $x$ not $\in$ span (X\ {x}) for each $x \in X$ (I'm not sure how to write the symbol for ...
0
votes
1answer
27 views

Span and Smallest Submodule Proof

Let R be a ring, M a R-module, and $X \subseteq M$ Show that span$(X)$ is the smallest submodule of R containing X. My ideas: Every submodule is contained in its span so $X \subseteq$ span$(X)$ and ...
0
votes
0answers
17 views

2 column proof of The Tangent-Chord Angle Corollary

I need to prove 12.23 on this section (http://i.imgur.com/M5iev9K.png) I can use any of the theorems or corollaries before 12.23 but not the ones after it. This is a list ...
1
vote
1answer
60 views

Using Pigeonhole Principle for a graph proof

Using the Pigeonhole Principle, prove that in any graph with two or more vertices there must exist two vertices that have the same degree. (Note: the problem does not assume that the graph is ...
0
votes
1answer
14 views

Proving the Division Algorithm using induction

Let $n \in \mathbb{N}$. For every $m \in \mathbb{Z}$, there exist unique $q, r \in \mathbb{Z}$ such that $ m = qn+r$ and $0 \le r \le n-1$. We call $q$ the quotient and $r$ the remainder when dividing ...
1
vote
2answers
33 views

Ring with special rules for add and mult

$R$ is a ring of integers with special rules for multiplication and addition. Suppose that $f: \mathbb Z \to R$ is an isomorphism that is defined by $f(x) = x-2$. What integer in the ring $R$ is ...
1
vote
0answers
24 views

Show that the field Q[sqrt2] cannot be ordered using the defined relation

The complete questions states: On $\mathbb Q\:$[$\sqrt2 $] we define the relation: $\mathbb a+b\sqrt2 < a'+b'\sqrt2$ if $\mathbb a<a'$ and $\mathbb b<b'$ then show that the field $\mathbb ...
0
votes
1answer
25 views

GCD of polynomials

In $\mathbb{Z}/5\mathbb{Z}[x]$ use the Euclidean Algorithm to find the GCD of $x^4+x^2$ and $x^4+x^3+3x$. My thoughts: I am getting to the point where I need to use a fraction to get further in ...
0
votes
0answers
15 views

Question regarding a surjective function

The function $f :\mathbb{Z}_{12} \longrightarrow \mathbb{Z}_4$ is defined by $f(x)=3x$. I am asked given any $a,b \in \mathbb{Z}_{12}$ if preservation of addition and multiplication occur. I proved ...
0
votes
0answers
49 views

Let {$p_n$} be a sequence of points in the $\mathbb{R}^2$. Use the notion of convergence to solve the following

A) Define what it means for a point p $\in$ $\mathbb{R}^2$ to be a limit point of {$p_n$}. B) Prove that p is a limit point of {$p_n$} if and only if {$p_n$} has a subsequence which converges to p. ...
1
vote
4answers
45 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
2answers
23 views

Question with this proof

The integer $m$ is odd if and only if there exists q $\in \mathbb{Z}$ such that $m=2q+1$ I know that $m$ is even if 2|n, and $n$ is odd if $n$ is not even. I also know the division algorithm, which ...
0
votes
0answers
12 views

Writing a proof that a certain algorithm generates the correct transition matrix for a quantum walk?

Regarding quantum walks, I have a transition matrix $M$ and a particle vector $P$ and I have determined that the elements of $M$ have to be positioned in a certain way so that the position of the ...
1
vote
2answers
46 views

Prove for a simple graph that $n-1 \leq m \leq \frac{n(n-1)}{2}$

For a given simple (that is neither loops nor multiple edges are allowed) undirected graph, where $m$ is the number of edges and $n$ is the number of vertices that the following inequality holds. ...
3
votes
0answers
49 views

Proof for the form of characteristic polynomial

I'd like to proof: The caracteristic polynomial of $A \in M(n\times n, K)$ has the form: $P_A(\lambda) = (-1)^n \lambda^n + (-1)^{n-1} \operatorname{tr}(A)\lambda^{n-1} +\dots +\det(A)$ My proof ...
0
votes
1answer
15 views

Are these Cartesian Product equalities true?

Let $A, B, C, D$ be sets. (i): (A x B) $\cup$ (C x D) = (A $\cup$ C) x (B $\cup$ D) (ii): (A x B) $\cap$ (C x D) = (A $\cap$ C) x (B $\cap$ D) I have to prove these later for homework if true, and ...
0
votes
1answer
23 views

If f(n)∈Ω(n) how do I prove or disprove f(n)∈O(n)

If f(n)∈Ω(n) how do I prove f(n)∈O(n) I feel it is true, but not sure how to show it the way I see it c1*n =< f(n) =< c2*n holds, but so confused on how to show it
0
votes
0answers
21 views

GCD and LCM Property

Let D = $\mathbb R + X\mathbb C[X]$ Show that $GCD(X, iX) = \mathbb R^\times$ and $LCM(X, iX) = \emptyset$ I have an outline of what to do but don't exactly know who to show all of it... First, ...
0
votes
0answers
10 views

Domain GCD Property

Let D be a domain and $\emptyset \subset A \subseteq D^*$ $d \in GCD(A)$ if and only if (d) is a minimum among the principal ideals containing (A) If $d \in GCD(A)$ then d|a for all $a \in A$ and ...
0
votes
1answer
49 views

Proof for a function $m:2^S\to R$

Let $S$ be a finite, non-empty set and $m:2^S\to R$ a function with the following properties $M1$: $\forall A\in2^S, m(A)\ge0$ $M2$: $\forall A, B\in 2^S, A\cap B=\varnothing\Longrightarrow m(A\cup ...
0
votes
1answer
17 views

Property of GCD in ring

Let D be a domain and $\emptyset \subset A \subseteq D^*$ Show that CD(A)={$d\in D$ | $(A)\subseteq (d)$} I know that I'll need to show both containments to show that the two statements are ...
0
votes
0answers
33 views

Big-O and Big-Omega Proof

Trying to refresh my memory on proofs, I got a feeling this is true but can't remember how to prove it: If f(n)∈Ω(n) how do I prove f(n)∈O(n) Thanks for help (I do remember definitions of big omega, ...
0
votes
2answers
69 views

Combinatorics proof of “sum of (k choose m) with k from m up to n is equal to n+1 choose m+1”

I've already proved this statement algrebraically. I'm asked to prove it with combinatorics. So far I came up with, LHS= # ways to choose m apples from a total of m,m+1,...,n RHS= # ways to choose ...
0
votes
1answer
39 views

GCD Domain Proof

Let $D = \mathbb{R} + X \mathbb{C}[X]$ Show that $\gcd_D(X^2,iX^2)=\emptyset $ Here is my plan so far... (and my questions) Suppose $f \in \gcd_D(X^2,iX^2) $. How do I show that because X is ...
0
votes
0answers
28 views

Prove that $s \not= \emptyset $ by showing that at least one of $|a|$ or $|b|$ is an element of $S$.

. I'm trying to show an alternative proof to Bezout's Lemma (let $a, b \in \mathbb{Z}$, then there exists $x,y \in \mathbb{Z}$ such that $gcd(a, b) = ax + by$). Heres one of the steps in proving it: ...