For questions about the writing of proofs. But instead of focusing the mathematics behind the proof, these questions ask about the details and implementation of the proof.

learn more… | top users | synonyms

0
votes
3answers
112 views

Picking A Certain Number Of Days Proof

The Problem is: Show that at least ten of any 64 days chosen must fall on the same day of the week. I know that in order to prove this, it's best to use a proof by contradiction. So, let's ...
1
vote
2answers
460 views

show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$.

I have to provide a structural proof for this: show that $l(T)$, the number of leaves of a full binary tree $T$, is 1 more than $i(T )$, the number of internal vertices of $T$. I have the following, ...
3
votes
3answers
1k views

Proving that the reciprocal of an irrational is irrational

The question I am working on is: Prove that if x is irrational, then 1/x is irrational. My proof differs from the one given in the answer key; but I still feel that mine is valid. Could someone ...
1
vote
2answers
3k views

Proof By Contradiction With Rational and Irrational Numbers

The question I am working on is: Use a proof by contradiction to prove that the sum of an irrational number and a rational number is irrational. After searching through Google, to see if this ...
0
votes
1answer
93 views

Concluding the convergence of a product of series

Let $a(n)$ be a bounded sequence (not necessarily convergent) and assume $\lim b(n) = 0$. Prove that $\lim a(n)b(n) = 0$. Can we conclude anything about the convergence of $a(n)b(n)$ if $\lim ...
1
vote
1answer
892 views

Proving the absolute value of a sequence converges

Prove that if the sequence $\,\{a_n\}\,$ converges to $A$, then $\,\{|a_n\}|\,$ converges to |A|. Also, is the converse true?
1
vote
6answers
561 views

Proof Regarding Property of Odd Integers [duplicate]

The question I am working on is: "Use a direct proof to show that every odd integer is the difference of two squares." Proof: Let n be an odd integer: $n = 2k + 1$, where $k \in Z$ Let the ...
0
votes
2answers
2k views

Basic proof by Mathematical Induction (Towers of Hanoi)

I am new to proofs and I am trying to learn mathematical induction. I started working out a sample problem, but I am not sure if I am on the right track. I was wondering if someone would be kind ...
3
votes
1answer
61 views

Prove that A $\equiv B$

Suppose, I have to prove that $A\equiv B$. I started out by proving that $¬B \implies ¬A$. This proves $A\implies B$. Next I proved that suppose B is true and A is not and this turns out to be ...
2
votes
1answer
67 views

Is this proof correct and written in a understandable fashion?

Given a function $f(x,y) = \sqrt{(x_{1}-y_{1})^2 + (x_{2}-y_{2})^2 +...+(x_{n}-y_{n})^2}$ where $x,y$ $\in$ $\unicode{x211D}^n$, $f:\unicode{x211D}^n \times \unicode{x211D}^n \rightarrow ...
0
votes
1answer
853 views

Proving Big-$\Theta$ if and only if Big-$O$ and Big-$\Omega$

Given the definitions of Big-$O$ and Big-$\Omega$, I'd like to prove that $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. Here's what I've come up with, but I'm not ...
1
vote
1answer
35 views

Finding specific sets

I'm trying to calculate these particular sets given that: $$A=\{a,c,e,h,k\}$$ $$B=\{a,b,d,e,h,i,k,l\}$$ $$C=\{a,c,e,i,m\}$$ $$A \cap B$$ $$A\cap B \cap C$$ $$A \cup B \cup C$$ $$A-B$$ ...
2
votes
2answers
122 views

Proving that for any odd integer:$\left\lfloor \frac{n^2}{4} \right\rfloor = \frac{(n-1)(n+1)}{4}$

I'm trying to figure out how to prove that for any odd integer, the floor of: $$\left\lfloor \frac{n^2}{4} \right\rfloor = \frac{(n-1)(n+1)}{4}$$ Any help is appreciated to construct this proof! ...
3
votes
3answers
87 views

Proving that for any odd integer: $\large \lceil \frac{N^2}{4} \rceil = \frac{N^2 + 3}{4}$

I'm trying to construct a proof that for any odd integer: the ceiling of $\large \lceil \frac{N^2}{4} \rceil = \frac{N^2 + 3}{4}$. Anyone have a second to show me how this is done? Thanks!
3
votes
3answers
128 views

Proving that $\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3 \cdot 4} +\ldots + \frac{1}{n(n+1)} = \frac{n}{n+1}$

How would we go about proving that $$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3 \cdot 4} +\ldots +\frac{1}{n(n+1)} = \frac{n}{n+1}$$
0
votes
1answer
421 views

Does this count as a proof by structural induction?

Let S be the subset of the set of ordered pairs of integers defined recursively by Basis Step: $(0, 0) \in S$ Recursive Step: If $(a, b) \in S$, then $(a + 2,b + 3) \in S$ and $(a+3,b+2) \in S$. ...
0
votes
2answers
52 views

Congruence relationships.

I need to prove (or disprove but I don't think that's the case) that: if $ab \equiv 0$ (mod $n$), then $ a\equiv 0$ (mod $n$) or $b\equiv0$ (mod $n$) I know that $ab\equiv 0$ (mod $n$) ...
0
votes
1answer
79 views

Undirected Graph Proof for Connection

If I have an undirected graph $G = (V, E)$, where $n = |V|$, and $n$ is even, how can I prove that for all $n \ge 2$ and every $v \in V$ has degree $(v) \ge \frac{n}{2}$, $G$ is necessarily connected. ...
2
votes
1answer
128 views

Binary Connective Proofs [duplicate]

I’m working to understand proofs that involve showing the completeness (or incompleteness) of a set of binary connectives and I have run into some confusion. Alright, so I believe I understand how to ...
0
votes
4answers
47 views

Prove that if $a$ is a prime, $b_i \in \mathbb{Z}_+$ and $a | \prod_{i = 1}^{n} b_i$ then $a | b_i$ for some $b_i$

A key property of the integers is that: if $\gcd(a,b) = 1$ and $a |bc$, then $a|c$. Use this property to prove that: if $a \in\mathbb{Z}_+$ is prime and $b_i \in \mathbb{Z}_+$ for $1 \leq i \leq n$ ...
-2
votes
2answers
85 views

Prove using induction $(A_1 \cap A_2 \cap … \cap A_k) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap … (A_k \cup B)$

Prove that if $A_1, A_2, ... , A_n$ and $B$ are sets, then: $(A_1 \cap A_2 \cap ... \cap A_n) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap ... \cap (A_n \cup B)$ Here's what I have. Could someone ...
1
vote
2answers
66 views

Prove $\bigcup _{j=1}^nA_j \subseteq \bigcup_{j = 1}^n B_j$

Prove using induction that if $A_1, A_2,...,A_n,$ and $B_1, B_2,...,B_n$ are sets such that $A_j \subseteq B_j$ for $j = 1, 2,..., n$ then, $\bigcup _{j=1}^nA_j \subseteq \bigcup_{j = 1}^n B_j$ I ...
2
votes
4answers
286 views

Prove using induction: $n^2 - 7n + 12 \geq 0$, where $n \geq 3$

Does this work as an inductive prood? It feels like of weird, I might be doing the basis step twice unecessarily...
2
votes
4answers
458 views

Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $

I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
2
votes
3answers
160 views

Prove that $(n, n + 1) = 1$ for all $n \gt 0$. [closed]

I was thinking of doing this by contradiction. So by supposing: $$(n, n + 1) \neq 1$$ Then trying to to show that $(n, n + 1) \gt 1$ or $(n, n + 1) \lt 1$. But I'm not sure how I can accomplish ...
4
votes
1answer
588 views

are two consecutive numbers relatively prime?

I have a question. I have been given this proof: "For any $n$ in the integers where $n>2$, show there are at least $2$ elements in $U(n)$ that satisfy $x^2=1$." I have gone through and actually ...
0
votes
1answer
89 views

The 'formal' way to prove equivalence?

In school we were always taught to prove equivalence by splitting an equation into $LHS$ and $RHS$ and working with each side individually until $LHS = RHS$. For example, prove: $$2^{k + 1} - 2 = ...
2
votes
0answers
120 views

Comparing Nash equilibrium and Pareto optimal actions

Suppose that $(x_{i}, x_{j})$ identify actions for two players $(i,j)$. If we define Pareto optimal actions by $$h(x_i) +h(x_j)- \eta[p(x_i)+p(x_j)]=2\gamma$$ and Nash equilibrium actions by ...
5
votes
2answers
125 views

Is this sloppy writing for limits?

Please note that I am not asking you to compute or show me how to do this limit. I am asking how to write out a clean and formal solution that is free of any error, ambiguity, or sloppiness. Given ...
0
votes
2answers
68 views

Help with math induction $S_{n+1}=1+aS_n$

Using mathematical induction I would like to prove the following. $S_0=1$ $S_1=1+a,...,S_n=\sum_{i=0}^n a^i$ Prove that $S_{n+1}=1+aS_n$ where $n \ge 0$.
3
votes
5answers
247 views

H0w t0 prove that periodic decimal numbers are rational? $a_1…a_k(b_1b_2..b_l)={m \over n}$

Given $a_1...a_k(b_1b_2..b_l)={m \over n}$ how can I prove that periodic decimal numbers are rational? Where do I even begin?
0
votes
1answer
20 views

How does one select some $i$ to prove $\exists i$ s.t. $s_i \leq A$ where $A$ is the average of real numbers $(s_1 + s_2 + . . . + s_n) / n$

How does one select some $i$ to prove $\exists i$ s.t. $s_i \leq A$ where $A$ is the average of real numbers $(s_1 + s_2 + . . . + s_n) / n$ It seems like a trivial proof, but writing a proof for ...
5
votes
2answers
244 views

How do you get a paper to be peer reviewed

I have a proof that I want to undergo peer review. I unfortunately am not affiliated with any university. How should I go about getting it reviewed and either rejected or published? Thanks!
5
votes
4answers
5k views

Prove that $1^3 + 2^3 + … + n^3 = (1+ 2 + … + n)^2$

This is what I've been able to do: Base case: $n = 1$ $L.H.S: 1^3 = 1$ $R.H.S: (1)^2 = 1$ Therefore it's true for $n = 1$. I.H.: Assume that, for some $k \in \Bbb N$, $1^3 + 2^3 + ... + k^3 = (1 ...
1
vote
1answer
422 views

Show $\mathbb R^n$ is complete.

Show $\mathbb R^n$ is complete. At this point, I am trying to work through the problem in my textbook, there is one step that I do not understand and would like explained. Here's my proof so far: ...
1
vote
2answers
285 views

Is cancellation of Cartesian product possible? I think so, but am having trouble with the proof…

So, Is a cancellation possible for the Cartesian product? ex. if you have two Cartesian products that are equal to eachother, do the 2nd sets for each product equal eachother? Lets say you have ...
1
vote
1answer
531 views

Proving the sum of the first n natural numbers by induction

I have the Following Proof By Induction Question: $$ (1)(2) + (2)(3) + (3)(4) + \cdots+ (n) (n+1) = \frac{(n)(n+1)(n+2)}{3} $$ Can Anybody Tell Me What I'm Missing. This is where I've Gone So Far. ...
3
votes
3answers
99 views

it is surjective - $f: \mathbb{N} \rightarrow \mathbb{N}: x \rightarrow 2x$

i think, this function is surjective: $$f: \mathbb{N} \rightarrow \mathbb{N}: x \rightarrow 2x$$ but in my textbook it says, it is not surjective. but no proof there. i am really wondering if it is a ...
0
votes
2answers
137 views

math proof: $m\le n<m+1$, $n$ rational and $m$ positive integer. How do we prove $m$ is unique?

Suppose $$m\le n < m+1$$ $n$ rational and $m$ a positive integer. How do we prove $m$ is unique? I realize this is true if $m$ is an integer, so $m$ must be a unique number that is an integer ...
3
votes
4answers
1k views

Proving the sum of the first $n$ natural numbers by induction

I am currently studying proving by induction but I am faced with a problem. I need to solve by induction the following question. $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$ for all $n > 1$. Any ...
1
vote
3answers
611 views

Show that there exists a positive real number $x$ such that $x^3 = 5$.

Here is what I've done so far: [First, want to show $b = 5$ is an upper-bound of $S$.] So, let: $$S = \{x \in \Bbb R : x \gt 0, x^3 \le 5\}, S \neq \emptyset$$ Assume that $b = 5$ is not an ...
2
votes
1answer
63 views

Show that $\exists \epsilon$ such that $f_{\epsilon}:=x+\epsilon g(x)$ is one-to-one where $g$ has bounded derivative

Consider a differentiable function $g : \mathbb{R} \to \mathbb{R}$ with bounded derivative $g'$, i.e. $\exists M>0$ such that $|g'(x)|\leq M$ for all $x\in \mathbb{R}$. Prove that for sufficiently ...
8
votes
1answer
335 views

Is “A and B imply C” equivalent to “For all A such that B, C”?

So I mostly study PDE, harmonic analysis, image processing, and so on, but for whatever reason I decided to be a TA for an undergraduate "introduction to proofs" course this semester. I suppose I ...
1
vote
2answers
122 views

Proof of the Sum of Square Roots

I have a question about a problem I encountered: $\exists$ a,b $\epsilon$ $\mathbb{R}$+ such that $\sqrt{a+b}=\sqrt{a}+\sqrt{b}$ Any tips for going about solving this? I tried: ...
5
votes
5answers
897 views

How does one begin to even write a proof?

I'm in my first proof based class and I'm just having a lot of trouble writing proofs. I mean I know it's not going to come natural and it will take time, but seroiusly, how does someone begin to ...
2
votes
2answers
98 views

$9^n \equiv 1 \mod 8$

I would like someone to check this inductive proof (sketch) The base case is clear. For the inductive step, it follows that $8 \mid 9^{n+1} - 9 = 9(9^n - 1)$ by the indutive hyp. So $9^{n+1} \equiv ...
0
votes
2answers
230 views

Vector span proof

Let $c_1,c_2,c_3,c_4,c_5$ be vectors in $R^4$ I'm trying to show that the set (call it set A) {$c_1,c_2,c_3,c_4,c_5$} spans $R^4$ if and only if the set (say, set B) of vectors ...
1
vote
1answer
121 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
0
votes
2answers
63 views

Proving a language is not regular

If two languages L1 and L2 are regular than so is their intersection. If follows that, for two languages L1 and L2, if L1 intersection L2 is not regular and L1 IS regular than L2 is not regular. I ...
1
vote
1answer
44 views

Counting Card hands with various restrictions

I would like to know if my solutions are correct for the following three combinatorial card questions. In each question, assume we have a standard deck of cards (13 ranks, and 4 suits). How many ...