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
50 views

Prove by induction that… $1+3+5+7+…+(2n+1)=(n+1)^2$ for every $n \in \mathbb N$

I'm not too sure exactly how to approach this question. Would anyone be able to give me any helpful advice or some sort of direction? I have a little problem with induction. Prove by induction that: ...
0
votes
0answers
20 views

Questions on logic behind “proof by contradiction”

I'm trying to understand the logic behind "proof by contradiction" and hoping that I can clear up a few things in this post. First of all, suppose I have a proposition $P$ and from this I can imply ...
0
votes
1answer
29 views

How can I show that a and b are odd in this contradiction proof?

Statement: suppose a,b belongs to Z (integers). If 4/(a^2+b^2) then a and b are not both odd. By proof of contradiction I assume that a and b are both odd. If a^2 and b^2 is odd then by definition a ...
1
vote
1answer
28 views

Proving a Problem involving Fibonacci numbers

I'm working on proving the problem that states $\text {The sequence}$ {$F_n$} $\text {is defined by the} \ F_1=F_2=1, F_{n+2}=F_{n+1}+F_n \ \text {for} \ n \ge 1.$ $\text {For any natural number m, ...
0
votes
2answers
20 views

Proving of Inequalities

How to prove: If $a>0$ and $b>0$, and $a^2>b^2$, then $a>b.$ I've tried different methods but I really can't prove this one. Thank you for your help!
1
vote
3answers
38 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
1
vote
2answers
48 views

Is this proof by induction for a sum of odd squares correct?

Statement: $1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = (n/3)*(2n-1)*(2n+1)$ Proof by induction -Base case: when $n = 1$ $1^2 = 1/3 * (2 * 1 -1) * (2 * 1 +1) = 1$ $1=1$ hence statement holds for $n = 1$ ...
0
votes
2answers
35 views

Is this contradiction proof correct?

Statement : suppose $a,b$ belongs to $\mathbb{Z}$ (integers). If $4/ (a^2 + b^2)$ then $a$ and $b$ are not both odd. Proof by contradiction: Assume that if $4/(a^2 + b^2)$ then a and b are both odd. ...
1
vote
1answer
30 views

Proof of big-O notation

Prove the following: If f is a polynomial of degree $d$, then $f(n)=O(n^{d})$. For every $d \in N, n^{d} = O(e^{n})$ Intuitively, it makes sense to me that for the first one, growth order depends ...
10
votes
1answer
99 views

Prove that $a < b\sqrt{3}$ under conditions given

There are integers $a$ and $b$ such that: 1) $a > b > 1$ 2) $ab+1$ is divisible by $a+b$ and $ab-1$ is divisible by $a-b$. Prove that $a < b\sqrt{3}$. It's really hard, do you see a ...
0
votes
1answer
35 views

Proving a sequence is increasing and converging as $n\to \infty$.

Suppose that $x_0 \in (-1,0)$ and $x_n=\sqrt{x_{n-1}+1}-1$ for $n \in \mathbb N$. Prove that $x_n \uparrow 0$ as $n\to \infty$. What happens when $x_0 \in [-1,0]$? Before this, the problems I did had ...
0
votes
0answers
15 views

If $a,b,c$ are the vertices of a triangle in the complex plane, prove that the area of a triangle is $\frac{1}{2}|b-c|^2|Im\frac{c-a}{c-b}|$

I have trouble with this proof. I can get as far as the fact that we must position the vertex $c$ on the origin and then rotate by a factor of $|b-c|$. But then this gives: \begin{align*} ...
0
votes
2answers
23 views

Contrapositive proof question, is this a valid way

Definition: $a\in \Bbb Z$ is a perfect square if there is a $b\in\Bbb Z$ and $a = b^2$ To prove: if $m$ and $n$ are perfect squares, then $mn$ is a perfect square. I know that this can most easily ...
0
votes
1answer
34 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...
1
vote
1answer
27 views

Suppose n is an integer. Use a proof by contrapositive to show if n^3 is even, then n is even

So, we assume that n is not even. Then, $n$ is odd, so $n= 2k+1$ for some integer $k$. Then, $(2k+1)^3 = 8x^3+12k^2+6k+1$. Would it be legal, then, for me to say $(8k^3+12k^2+6k)+1 = ...
-1
votes
2answers
25 views

Suppose that x is an integer. Use a proof by contrapositive to prove that if 5x+7 is even, then x is odd.

I know that we assume x is even. So, as x is even, x = 2k for some integer k. Then, that would make for 5(2k)+7 = 10k + 7. And this is where I'm stuck. I know that it isn't complete at 10k+7 to ...
0
votes
0answers
62 views

How do I prove that $f(n) + O(f(n)) = \Theta(f(n))$?

Here's what I have so far: $f(n) = \Theta(f(n))$ $C_1 f(n) < f(n) < C_2 f(n)$ $C_1f(n) + O(f(n)) < f(n) + O(f(n)) < C_2f(n) + O(f(n)) $ And then I run out of gas. The equal to sign ...
2
votes
2answers
47 views

Where should I place the notorious '+c'?

Consider the following proof - $$I=\int \sin (\ln x)dx\\\iff I=\sin(\ln x)x-\int\frac{ \cos (\ln x) }{x}\cdot {x} dx \\\iff I=x\sin (\ln x)-\int\cos(\ln x)dx\\\iff I=x\sin(\ln x )-[x\cos(\ln ...
1
vote
1answer
23 views

Is this correct structural induction (subsets)?

The last question (which is always the hardest) of my Induction Exercises goes like this: Let S be the subset of $\mathbb{Z}$ defined by: -12,20 $\in$ S if x,y $\in$ S, then x+y $\in$ S We use ...
0
votes
0answers
10 views

Cartesian product proof with counterexample

I was asked to disprove the following statement by counterexample: Let A, B and C be sets. If A x C = B x C then A = B I was under the impression that: (x1, y1) = (x2, y2) if and only if x1 = x2 and ...
0
votes
2answers
24 views

Understanding and writing limit proofs

I got this question : Consider $a_n,\:b_{n\:}$ sequences such that for every n , $0\le a_n\le \:b_{n\:}$. Let $\lim _{n\to \infty }\left(\frac{b_n}{a_n}\right)\:=\:1$, and $a_n$ is a ...
0
votes
0answers
20 views

Given $A\in Tn(R)$ show thast A is a scalar matrix if $e_{ij}=Ar_{ij}$, where $a\le i\le j\le n$

Given $A\in Tn(R)$ show thast A is a scalar matrix if $e_{ij}=Ar_{ij}$, where $a\le i\le j\le n$ Prove for $1: e_{ii}A=Ae_{ii}$ and for $2: e_{ij}A=Ae_{ij}$ where $i\le j$ Now for 1, I understand ...
0
votes
1answer
14 views

Proving order of magnitude

Generally how much proof must be given to prove a statement of order-of-magnitude? for example: $n^2 + 2 log (n) = O(n^2)$ $2 log (n)$ has a lower order of magnitude than $n^2$ so it can be argued ...
0
votes
6answers
67 views

Proof that every number has at least one prime factor

Prove that for $ n \geq 2$, n has at least one prime factor. I'm trying to use induction. For n = 2, 2 = 1 x 2. For n > 2, n = n x 1, where 1 is a prime factor. Is this sufficient to prove the ...
0
votes
2answers
26 views

Finding counterexamples and proving a transformation is linear

Can someone please explain instances where $ f^{-1} (f (A)) \not = A $ and $f (f^{-1}(B)) \not = B$ if $ f:X \rightarrow Y $ and $ A$is a subset of X and B is a subset of Y? I can't think of when this ...
2
votes
1answer
22 views

Congruence modulo proof

Statement: a = 1 (mod 5) then a^2 = 1 (mod 5) Direct proof (we also have the option of proving by contraposition): let a = 5m + 1 then a^2 = (5m+1)^2 = 25m^2 + 10m + 1 = 5m(5m + 2) + 1 hence a^2 ...
1
vote
2answers
37 views

Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
0
votes
0answers
28 views

Proving that a value is a multiple of 11

I need to prove that 12**n - 1 is a multiple of 11 for every value of n (part of N). This is clearly a proof-by-induction problem. My base case is 0, where I assume n = 0 will give a resulting 0 ...
0
votes
2answers
53 views

Using induction to prove a formula for $\sin x+\sin 3x+\dots+\sin (2n-1)x$

I'm working from the text "Intro To Real Analysis" by William Trench. Here is what I have thus far. I will prove using Mathematical Induction that $\sin x+\sin 3x+...+\sin (2n-1)x=\frac{1-\cos ...
0
votes
0answers
29 views

How to write a formal proof of the statement: For all integers p, m, n, if p|m and p|n then p|(m+n)

Prove: For all integers $p$, $m$, $n$, if $p|m$ and $p|n$ then $p|(m+n)$ Proof: Let $p,m,n \in \mathbb{Z}$. Suppose $p|m$ and $p|n$. Then $\exists x,y\in \mathbb{Z}$ such that $m = px$ and $n = ...
1
vote
3answers
40 views

Correctly negating “there exists a subset of $S$ that is a basis for $V$”

I would like to prove the following by contradiction: "Let $V$ be a vector space having dimension $n$, and let $S$ be a subset of $V$ that generates $V$. Prove that there is a subset of $S$ that is ...
0
votes
1answer
50 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
0
votes
4answers
46 views

Prove that $2|(x^4-3) <=> 4|(x^2+3)$

Prove that $2|(x^4-3) <=> 4|(x^2+3)$ What i have right now is: Consider the case (=>): Since $x^4-3$ divides $2$ then, there must exist n belongs to integer, such that $n = \frac{x^4-3}{2}$ I ...
0
votes
2answers
24 views

Limit of |x-2| as x approaches -2

I believe that it equals -4. In the epsilon-delta definition, we can set delta equal epsilon and I become this satisfies the definition. The problem is I can't seem to prove based on this that 0 less ...
0
votes
1answer
30 views

Prove there's always a larger element

We have a number $ 0 < x < 1 $. We also have the function $1-\dfrac{1}{n}$ with $n \in \mathbb{N}$. How can I prove that for any $x \in \mathbb{R}$, there exists an $n \in \mathbb{N}$ such that ...
0
votes
0answers
33 views

Correctness of proof based on nested interval theorem

I am given that for positive integer n, let $a_n=1-(1/n)$ and $b_n=1+(1/n)$. $I_n=[a_n,b_n]$. I am to show that 1) the hypothesis of the nested interval theorem are satisfied, 2) find the point of ...
1
vote
1answer
65 views

Proof that arithmetic and geometric mean converge

I need some help with understanding a part of this proof and also writing it up correctly. Given $a_n\geq a_{n+1}\geq b_{n+1} \geq b_n$ with $a_1=a$ and $b_1=b$. I am also given that ...
0
votes
3answers
50 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
0
votes
4answers
42 views

How to write a formal proof of the statement: For all integers n, if n is a multiple of 5 then 3n is a multiple of 5.

Prove: For all integers $n$, if $n$ is a multiple of $5$ then $3n$ is a multiple of $5$. Proof: Assume $n$ is a multiple of $5$. Then $n$ must have the form $5k$ where $k \in \mathbb{Z}$. We have ...
2
votes
1answer
34 views

Proof Check - Linear Algebra

I'm new to more formal mathematics and I was wondering if I could write my attempt at a small proof here and see what others thought and if you could point out any fatal flaws or just offer some tips? ...
0
votes
3answers
33 views

Proofing implication

I am asked to prove if a and b are positive, then $a^2(b+1) + b^2(a+1) >=4ab$ This makes me really confused. I don't know where I can start the proof. Any hints?
1
vote
2answers
83 views

Can the proof of Theorem 1.20 (b) in the book, The Principles of Mathematical Analysis by Walter Rudin, 3rd ed., be improved?

I'm reading Walter Rudin's PRINCIPLES OF MATHEMATICAL ANALYSIS, third edition, and am at Theorem 1.20(b), where he states and proves that between any to real numbers, there is a rational; that is, if ...
1
vote
1answer
28 views

How do I prove (scalar1 + vector1) * scalar2 is not equal to scalar1 * scalar2 + scalar2 * vector1?

I am taking a Linear Algebra course and have been stumped on a homework question for a few hours. How do I prove for two scalars, $c_1$ and $c_2$, and a vector $v$: $(c_1 + v)c_2 \neq c_1c_2 + c_2v$ ...
0
votes
1answer
91 views

Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
1
vote
2answers
53 views

How to write a formal proof of the statement: if $x<3$ then $10-2x>4$?

Prove: For all real numbers $x$, if $x<3$ then $10-2x>4$. Proof: Let $x \in \mathbb{R}$, such that $x<3$. We have the following sequence of implications: $10-2x>4 \Rightarrow -2x>4 ...
0
votes
2answers
56 views

Suppose $x$ is a limit point of $A \subset X$, then if $f: A \to Y$ is continuous, is it true that $f(x)$ is a limit point of $f(A)$?

So I already know that a counterexample is $f(x) = c$ for $c$ is a constant, but I can't seem to prove this statement by contradiction, all I did was go back and forth. "Proof": If $f(x)$ ...
0
votes
2answers
49 views

Prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ using natural deduction

I want to prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ where $x \notin FV(\psi)$ using natural deduction method. I was able to prove implication from left to ...
1
vote
4answers
54 views

Prove this by induction?

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly: So obviously, the ...
2
votes
2answers
68 views

If all mappings $f: A\to B$ are many-to-one, does there exist surjective $g: A\to B$?

Suppose sets $A$ and $B$ are such that all mappings $f: A\to B$ are many-to-one (i.e. not injective). Can we prove that there must exist a surjective $g: A\to B$? Ideally, I am hoping to be able to ...
0
votes
2answers
57 views

Proving formally $\lim_{x \to -\infty}\mathrm{Pr}( \left \lfloor{x}\right \rfloor \le X < x) = 0$ (Proof check)

we have $$\lim_{x \to -\infty}\mathrm{Pr}( \left \lfloor{x}\right \rfloor \le X < x) $$ where X is a real random variable, and $x \in R$. My idea of a proof would be by contradiction: Assume ...