For questions about approaches and techniques for discovering a proof, as opposed to writing it down clearly (which involves (proof-writing)). Should not be used unless the focus is on the technique of the proof instead of the solution.

learn more… | top users | synonyms

5
votes
2answers
903 views

How to prove a function is not onto?

Let $f : Z\to Z$ be the function defined by $f(x) = 3x + 1$. Prove that $f $ is not onto, using a proof by contradiction. (Choose an integer $n$, and then prove ($\forall m \in Z$)($f(m) ≠ n$) by ...
2
votes
0answers
27 views

Given the sets $X$ and $Y$ in the real numbers with least upper bounds $a$ and $b$ respectively, prove that $a+b$ is the least upper bound for $X + Y$

I've seen this proof done other ways and I wonder if my way is right. It's very similar to the $\epsilon > 0$ approach I've seen elsewhere but uses a contradiction: Let $X$ and $Y$ be sets of real ...
0
votes
2answers
301 views

The boundary of the union of two sets is a subset of the union of boundaries

I'm stuck on trying to get this proof started. I want to prove that $\delta(S_1 \cup S_2)\subset \delta S_1\cup\delta S_2$, where $S$ is some set. I don't need a full proof, just a hint to get ...
1
vote
2answers
37 views

induction for idempotent matrix : $P^n = P$

Given that $P^2 = P$ how do i prove by induction that $P^n = P$? I have tried the following: we know that $P^k = P$ holds for $k = \{1,2\}$. If we now take $k=3$: $$ \begin{align} P^3 &= ...
1
vote
3answers
245 views

prove this inequality with log and positive value “x”

How do I prove that for every positive $x$ , $1-x \le -\log{x}$ Can I use convexity somehow?
0
votes
1answer
179 views

Prove ${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$ [duplicate]

Prove ${2n\choose n}=\sum\limits_{k=0}^n {n\choose k}^2$ My Approach: I will be making use of $$\tag 1\quad{m+n\choose r} = {m\choose 0}{n \choose r} + {m\choose 1}{n\choose r- 1} + ...
0
votes
1answer
178 views

Practice Examples of Proofs by Induction, Direct/Indirect Method

I'm learning about proofs in school, quite a few different sorts (but not geometry ones), but the teacher is teaching by slides mainly, not books. The main ones are proof by ...
0
votes
2answers
84 views

Induction and Maximum Principle

I wish to show that the following two assertions are equivalent: (Principle of Mathematical Induction) Let $S$ be a nonempty subset of the set of non-negative integers satisfying the following two ...
1
vote
1answer
53 views

For any two Ideals $A$ and $B$,$A+B=\langle A \cup B \rangle$

Below is the proof of : Prove that for any two ideals $A$ and $B$ of ring $R$,$A+B=\langle A \cup B~\rangle$ . Proof: By theorem (for any two ideals of a ring $R$ ,then the set $A+B$ is an ...
1
vote
1answer
272 views

When to use weak, strong, or structural induction?

For weak induction, we are wanting to show that a discrete parameter n holds for some property P such that P(n) implies P(n+1). For strong induction, we are wanting to show that a discrete parameter ...
1
vote
1answer
91 views

Analytic Proof Of ${n\choose r}={n-1\choose r-1}+{n-1\choose r}$

Analytic Proof Of ${n\choose r}={n-1\choose r-1}+{n-1\choose r}$ My Approach Let $x_k$ be one element in a set of $n$ elements. $n-1\choose r-1$ $=$ the number of unique groups of $r$ containing ...
0
votes
1answer
35 views

Proof with Cartesian coordinates.

Let $S_b := \{(x,y) \in\mathbb R^2 | y = 3x + b\}$ where $b\in\mathbb R$. Give a direct proof that if $(r,s)\in\mathbb R^2$, then there exists a $b\in\mathbb R$ such that $(r,s) \in S_b$. I have ...
1
vote
1answer
40 views
2
votes
5answers
2k views

Is it true that $n^2+3n+13$ is prime for all $n\in\mathbb ℤ^+$?

Prove or disprove the statement: If $n\in\mathbb ℤ^+$, then $n^2+3n+13$ is prime. I am lost here. All I know is that $n$ is greater than or equal to one, since it is a positive integer.
1
vote
0answers
29 views

Proof for the number of leaves for any Binary Search Tree

A property for binary trees is that the number of leaves is the number of full nodes plus 1, in other words, $L = F + 1$ where $L$ is the number of leaves and $F$ is the number of full nodes. What ...
0
votes
3answers
120 views

How would I show that Tn=3^n + 2 is a solution to the recurrence?

Would anyone be able to help me or give me some advice on the following problem: Consider the recurrence with $T_0 = 3$ and $T_{n+1} = 3T_n - 4$ for all $n \in \mathbb{N}$. How would I show that ...
0
votes
1answer
25 views

Boolean algebra proof (a+b) (a+c)' = a'bc'

I have to prove that (a+b) (a+c)' = a'bc' My algebra skills are really rusty and I was wondering what identities are used to solve this so I can get a better understanding
-1
votes
2answers
44 views

Proving a matrix is always symmetric [duplicate]

$B$ is a square matrix of real numbers. Show that the matrix $BB^T$ is always symmetric.
4
votes
2answers
70 views

Prove using the definition of a limit, that $f(x) >$ something if $|x| < \delta$

The function $f (x)$ is defined for $−∞ < x < ∞$. In addition, we have $$\lim_{x \to 0} f(x) = 2$$ (a) Give the $\epsilon$-$δ$-definition of $\lim_{x \to 0} f(x) = 2$. (b) Prove (using this ...
2
votes
2answers
145 views

Suppose A and B are sets. Prove that A ⊆ B if and only if A ∩ B = A.

Here's how I see it being proved. If A and B are sets,and the intersection of A and B is equal to A, then the elements in A are in both the set A and B. Therefore, the set of A is a subset of B since ...
0
votes
3answers
77 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: ...
2
votes
3answers
95 views

Proof: For all integers $x$ and $y$, if $x^2+ y^2= 0$ then $x =0$ and $y =0$

I need help proving the following statement: For all integers $x$ and $y$, if $x^2+ y^2= 0$ then $x =0$ and $y =0$ The statement is true, I just need to know the thought process, or a lead in the ...
2
votes
4answers
94 views

How to prove $C$ from $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$?

How does one prove $C$ from the premises: $A \leftrightarrow (B \leftrightarrow C)$ and $A \leftrightarrow B$ ? I've tried to prove $C$ by contradiction, using a sub-proof which presumes $\neg ...
1
vote
0answers
87 views

Prove that $\{\sqrt[n]{e^{n+1}}\}$ is convergent.

I need to prove that $\{\sqrt[n]{e^{n+1}}\}$ is convergent, and find its limit using this theorem: Let $f:E \to R$ with $x_{0} \in E$ an accumulation point of $E$. Then these are equivalent: 1)$f$ ...
1
vote
1answer
28 views

Verify that $(I−XY)^{(-1)}*X=X*(I−YX)^{(-1)}$ [duplicate]

Verify that $(I_n−XY)^{-1}\cdot X=X\cdot (I_m−YX)^{-1}$ The first $I$ is of order $n$ and the second is of order $m$. $X$ is $n\times m$ $Y$ is $m\times n$
4
votes
4answers
320 views

How to show that these two lines are perpendicular?

Let $\triangle AEE'$ be an isosceles triangle with $\angle EAE'=90^\circ$ such that $AE=AE'$ and such that $A$, $E$ and $E'$ lie on the circle $c_1$. Let $\triangle ADD'$ be an isosceles triangle with ...
2
votes
1answer
113 views

Measuring Unsigned Simple Functions

I was hoping that someone would be able to help me solve this problem regarding simple functions and their measure. This problem is coming straight from Introduction to Measure Theory by Terrence Tao. ...
10
votes
1answer
121 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 ...
1
vote
1answer
179 views

Linear algebra proof regarding matrices

I'd like a hint rather than a full solution. The problem I am considering is the following: $X$ is an $n\times m$ matrix $Y$ is $m\times n$ Show that $(I - XY)^{-1}\cdot X = X\cdot(I - ...
1
vote
1answer
26 views

Boolean Algebra: making a proof assistance

So far i've tried all the identities my teacher gave us and keep getting stuck I have to prove that x'y' + y = x' + xy using boolean algebra identities
3
votes
1answer
56 views

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a.

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a. Any ideas? (Suggested proof by contradiction). Not really sure how to go about this.
0
votes
2answers
29 views

Call a subset A ⊆ ℝ left-infinite if either A = ℝ or A = (a, ∞) for some a ∈ ℝ.

So, as part of some extra credit my professor gave me, I am given this problem: Call a subset $A \subseteq \mathbb R$ left-infinite if either $A =\mathbb R$ or $A=(a,\infty)$ for some $a\in\mathbb ...
3
votes
1answer
42 views

Show by committee selection argument

First post in Stack Exchange and feel bad to be in need of help. But, I'm having a hard time understanding this one or rather showing the argument. $\binom{n}{k} = \binom{n-2}{k-2} + ...
0
votes
1answer
49 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
2answers
31 views

Is this the correct way to prove by induction?

Prove by induction that $$1 + 3 + 5 + 7 + ... + (2n + 1) = (n+ 1)^2 $$ //for every n ∈ $\mathbb N$. $$1+2+3+...+n=\frac{n(n+1)}2$$ Proof: $$3+5+7+\ldots+(2n+1)=$$ ...
0
votes
0answers
30 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
1answer
691 views

Double Complement of a set proof

Question states: Prove the law of double complements for sets: If $A$ is a set and $A^\complement$ is its complement than prove that: $$ (A^\complement)^\complement = A$$ I started with: $$ ...
2
votes
1answer
37 views

Formal proof structure for $\forall n \in \mathbb{N}, P(n) \rightarrow \forall n \in \mathbb{N}, Q(n)$

I'm used to proving universal quantification claims (i.e. $\forall n \in \mathbb{N}, [P(n) \rightarrow Q(n)]$) by: Assuming an arbitrary number in the naturals, assuming the antecdent $P(n)$, doing ...
3
votes
2answers
91 views

If supposing that a statement is false gives rise to a paradox, does this prove that the statement is true?

The title pretty much says it all: If supposing that a statement is false gives rise to a paradox, does this prove that the statement is true? Edit: Let me attempt to be a little more precise: ...
1
vote
2answers
90 views

how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+1})$

we can say that if all $i$ s in the sum were equal to $n$ then the answer to the summation would be $n\cdot n^k$. So $n^{k+1}$ is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$ For ...
1
vote
1answer
61 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}, ...
2
votes
4answers
63 views

Prove $\frac{n}{n+1}<\frac{n+1}{n+2}$

How can we prove the following inequality: $$\frac{n}{n+1} < \frac{n+1}{n+2}$$ I understand how to do proof by inductions and contradictions, but I am getting stuck on this question. My proof ...
1
vote
1answer
37 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
41 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 ...
2
votes
1answer
126 views

Statistics - Show that $\hat{\theta}$ hat is a biased estimator of $\theta$

I'm asked to solve this exercise, but I can't manage to find something satisfying. Any help/hint would be much appreciated. Let $Y_1, Y_2,\dots, Y_n$ denote a random variable sample of size n from a ...
0
votes
1answer
53 views

Characterization of analytic functions by exponential functions

Let $f$ be an analytic function on domain $D$ such that $f(z) \neq 0, \forall z \in D.$ Could anyone advise me how to prove $f= e^{h},$ for some analytic $h$ on $D \ ?$ Thank you.
0
votes
3answers
105 views

Proofs about Matrix Rank

I'm trying to prove the following two statements. I can prove them easily by considering the matrix as a representation of a linear map with a given basis, but I don't know a proof which uses just the ...
0
votes
1answer
23 views

Help understanding proof for: Let $X$ be a set. Then $X \not\approx P(X)$ (where $\approx$ is equivalence relation)

In trying to understand the following proof, I am getting stuck on the chosen definition of $Y = \{ x \in X \mid x \not\in f(x) \}$. How do we know that such a set exists in $P(X)$ when we don't even ...
3
votes
2answers
38 views

We are given $f: X \rightarrow P(X)$, $f(x) = X\backslash\{x\}$, and $X$ is a set. Is the function injective, surjective, bijective?

I am working on this problem in a beginners set theory class. I believe the function is injective but not surjective, thus is it not bijective. We can show it is injective by letting $f(x) = f(x')$. ...
0
votes
1answer
67 views

Field Proofs with Multiplicative Inverses

I've been staring at these two for a while and I can't come up with anything concrete to start. Hints on how to begin would be greatly appreciated, full solutions are not necessary (and preferably ...