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

0
votes
1answer
15 views

queuing problem, related to marriage algorithm

Say we have an nxn matrix and for every entry a_{ij}, it equals 1 if flight j starts after flight i ends. Otherwise it is 0. Suppose the largest matching contains M marriages (i.e. 1's in nxn matrix ...
0
votes
1answer
26 views

Proof by contradiction or contrapositive sets help

so I'm having difficulties proving the following Theorem, through either proof by contradiction or contrapositive. Can someone please help me? The problem is as follows: Prove that for any two sets, ...
0
votes
0answers
29 views

Prove that $Z(S_n)$ is trivial for $n \geq 3$ [duplicate]

Hi I am trying to solve this question I don't know where to begin but I have an idea so we have $$Z(G) = \{x \in G \space |\space xy = yx \space\forall y \in G\}$$ We must show that for all ...
-1
votes
0answers
31 views

Prove if true, counterexample if false

I'm not too sure where to start with this problem, any help is appreciated. For every function f from nonnegative integers into nonnegative reals, o(f) = O(f) - Theta(F). (Set difference: A - B ...
0
votes
1answer
20 views

Iterating proof step

Many books proves theorems by performing one proof step and using this step as a scheme they say by repeating this step $l$ times we prove that... I wonder whether there is some formal meta-theorem ...
2
votes
1answer
32 views

Prove that $n(r) < 2\pi \sqrt[3]{r^{2}}$

Suppose that $n(r)$ denotes the numbers of points with integer coordinates on a circle of radius $r > 1$. Prove that $$ n(r) < 2\pi \sqrt[3]{r^{2}} $$ What process would you use to resolve ...
0
votes
0answers
15 views

Mixed strategies as LP problem

A row player is playing against a column player and his yield table is -, C1, C2, C3 R1, -3, 2, -1 R2, 0, -2, 1 R3, -1, 3, -5 Is it then correct to ...
0
votes
0answers
12 views

how to prove a non-negative integer n to be divisible by positive integer d is n mod d = 0

I'm not sure how to prove that, a necessary and sufficient condition for a non-negative integer n to be divisible by a positive integer d is that n mod d = 0. I get that I have to prove the cases of ...
-1
votes
1answer
19 views

Mathematical Induction Proof Question dealing with functions [on hold]

How would you use mathematical induction to prove: Let $f$ be a function of two positive integer variables with $f(1,1) = 2$ and $f(m + 1, n) = f(m,n) + 2(m + n)$ $f(m, n + 1) = f(m,n) + ...
0
votes
3answers
32 views

Mathematical Induction Proof Question dealing with integers

How would you use mathematical induction to prove that $1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \dots + n \cdot (n + 1) \cdot (n + 2) = \frac{n(n + 1)(n + 2)(n + 3)}{4}$ I tried proving the base ...
1
vote
0answers
20 views

Proof that this specific function is measurable

Here there is the setup of my problem: measurable $\ g: X \to Y$; the image measure $$\hat{g} : (\Delta (X), \Sigma_X) \to (\Delta (Y), \Sigma_Y)\hspace{0.5cm} \text{such that} \hspace{0.5cm} ...
0
votes
1answer
26 views

Proof approach: A 7x7 matrix with 15 ones can allow at least three marriages

This is quite difficult to prove imho with regards to Hall's Marriage Algorithm I can visualize a number of scenarios that work (i.e. put ones from the first entry to the fifteenth, or across ...
1
vote
1answer
40 views

Existence of functions $g$ such that 1. $f\circ g(1) =2$; 2. $g \circ f(1) = 2$, for all $f$ [on hold]

Let $S = \{1,2,3,4\}$. Let $F$ be the sets of all functions from $S$ to $S$. a) Prove or disprove the statement: "For all $f \in F$, there exists $g \in F$ so that $(f \circ g)(1) = 2$" b) Prove or ...
2
votes
3answers
49 views

Trouble with eigenvalue proof

Hello I am having a lot of trouble trying to prove a statement in linear algebra, il post it and what I have tried etc, Let $A \in \mathbb M_{nxn}$ and let $\lambda_1,...,\lambda_r$ be distinct ...
0
votes
0answers
11 views

Deducing a Recursion formula for Vandermonde Matrix

Vandermonde matrix, $V_n(a_1, \dots, a_n)$ = $\left|\begin{array}{cccc}1 & a_1 & a^2_1 & ... & a^{n-1}_1 \\... & ... & ... & ... \\1 & a_n & a_n^2 & ... & ...
2
votes
0answers
23 views

Proof that $\mathbb E[X]=\sum_{\omega \in \Omega}X(w)P(\{w\})$

The question is inspired by a theorem about the expected value of a discrete random variable: $$\mathbb E[X]=\sum_{x}xp(x)$$ if the series converges absolutely. The theorem says that $\mathbb ...
1
vote
2answers
27 views

Characteristic Polynomial Property

I am trying to prove a more simple analog of a determinant property. The main one being that if $A$ is an $n \times n$ square matrix with characteristic polynomial $\Delta (t) = ...
0
votes
1answer
33 views

Let $A, B$ and $X$ be sets. Prove that if $A ∪ B ⊆ X$ then $A ⊆ X$.

I have just started learning set theory and I've been trying to learn how to do proofs, however I really can't figure out I've been trying to answer a simple one: Let $A, B$ and $X$ be sets. Prove ...
1
vote
3answers
56 views

If M,N are finite dimensional vector spaces with same dimension ,then if M is subset of N ,then M=N

If M,N are finite dimensiona;l vector spaces with same dimension then if M is subset of N ,then M=N I think i need to show that both vector spaces are spanned by same bases in order to do this or to ...
2
votes
1answer
46 views

Let $a,b,c$ be the nonnegative real numbers such that $a+b+c=1$. Prove that $\sqrt{a+\frac{(b-c)^2}4}+\sqrt b+\sqrt c\le\sqrt3$

Let $a,b,c$ be the nonnegative real numbers such that $a+b+c=1$. Prove that $$\sqrt{a+\frac{(b-c)^2}4}+\sqrt b+\sqrt c\le\sqrt3$$ I first wrote $a$ as $1-b-c$ and substituted it in main ...
1
vote
0answers
63 views

How to determine if a number is product of exactly two primes? [on hold]

Suppose $X = p_1p_2$ where $p_1$ and $p_2$ are (not necessarily consecutive) prime numbers. Given $X$, what are the different ways to prove or determine that $X$ is a product of two primes? We ...
0
votes
1answer
11 views

Prove line joining midpoints of non-parallel sides of trapezoid is parallel to the parallel sides of the trapezoid

If I have a trapezoid with two sides parallel, and a line going through the midpoints of the other two sides, how do I prove that this line is also parallel to the two parallel sides of the trapezoid? ...
2
votes
1answer
40 views

Rank of a symmetric matrix. (ISI Sample Paper)

Here, $\langle v,w\rangle=v^tw$ is the usual dot product. Let $A$ be an $n \times n$ symmetric matrix. Let $l_1, l_2, \ldots , l_{r+s}$ be $(r + s)$ linearly independent $n\times 1$ vectors such ...
1
vote
2answers
22 views

Proving associativity of product of two formal sums $\sum_{n = 1}^{\infty} \frac{a_n}{n^x}$

Let $R$ be the set of all formal sums $\sum_{n = 1}^{\infty} \frac{a_n}{n^x}$ where $a_n \in \Bbb{Q}$, where two sums $a, b$ are equal iff $a_i = b_i \ \forall i$. It is indeed a ring with addition ...
1
vote
0answers
22 views

Proof subtraction is not forward stable

I've been taught that the "subtraction operation" is not accurate/forward stable as the relative error can be arbitrary large. I tried to prove it formally but I end up with a contradiction. What ...
0
votes
1answer
20 views

Proof regarding convex sets

A set of points is said to be convex provided that every pair of points in the set can be joined by a line segment that lies entirely within the set. Show that, if $ | ∇f(x)| ≤ M \space \space ...
0
votes
2answers
47 views

Using induction to prove a sequence is always less than a given number

Let $f(1)=2$ and $f(n+1)=\sqrt{3+f(n)}$. Prove that $f(n)<2.4$ for all $n\ge 1$. I established a base case when $n=1$ and then moved on to the inductive step by assuming the statement is true ...
2
votes
1answer
61 views

For which values of $n$ can $x^n+y^n$ be a perfect square?

Let $x, y$ and $n$ be positive integers. Using Fermat's Last Theorem we can show that $x^n+y^n$ can't be a perfect square if $n$ is divisible by $4$, but when $n=3$ we have some simple solutions like ...
1
vote
2answers
39 views

Showing a complex function is constant

If I know that a function $f$ is entire and $f(z)=f(z+1)=f(z+i)$ for all $z \in \mathbb{C}$, how do I show that $f(z)$ is constant? I feel like this needs use of the uniqueness/identity theorem to ...
1
vote
3answers
61 views

Proving $2^n\leq 2^{n+1}-2^{n-1}-1$ for all $n\geq 1$ by induction

I am trying to prove that for every element of $\mathbb{N}$, that $2^n \leq 2^{n+1} - 2^{n-1} - 1.$ I started by showing that initial case, of $n=1$, is true. Then I proceed to the ...
0
votes
3answers
32 views

Let $a, b, c, d$ be integers s.t $a|bc$ and $d=gcd(a,b)$. Prove $a|cd$.

From the assumption I was able to gather the following: $bc= ak_1$. Let $p=gcd(a,b)$ thus $p=dk_2$. Well since $p|a$ and $p|b$ I have the following, $a= pr_1$ and $b=pr_2$. I have been trying to ...
1
vote
0answers
34 views

Proof by contradiction to prove an inequality does not hold

I am trying to prove that there is no positive integer x such that $2x < x^2 < 3x$. I started by assuming that this statement is true. I then subtracted 3x from each part of the inequality to ...
2
votes
2answers
38 views

Proving injectivity by contradiction

Define the function $g:\mathbb N \rightarrow \mathbb N$ with $g(d)= d^2 + d + 1$ I started out by assuming that if two arbitrary elements of $\mathbb N$, $x$ and $y$,where $x>y$ without loss of ...
2
votes
0answers
13 views

Proof $X\backslash\bigcap \limits_{i\in\Lambda} A_i = \bigcup\limits_{i\in\Lambda} (X\backslash A_i)$ [duplicate]

Let $X$ be a universe. Let $\{A_i\}_{i\in\Lambda}$ be a family of sets in $X$, where $\Lambda$ is a set of index. I want to prove: $$X\backslash\bigcap \limits_{i\in\Lambda} A_i = ...
0
votes
0answers
11 views

Proof of Strictly Increasing Functions

For real numbers c, d with c$<$d we denote the open interval in R by (c,d)=x$\in$R: c$<$x$<$d. Recall that a function f:R-->R is strictly increasing if for all x,y in domain of f, whenever ...
0
votes
2answers
39 views

How to proof $f_{n+1}(x) = x f_n(x) - f_{n-1} (x),\quad n \geqslant 1$ by induction?

Let $$ f_n (x) = \det \begin{bmatrix} x & 1 & 0 & \cdots & 0 \\ 1 & x & 1 & 0 & 0 \\ 0 & 1 & x & 1 & \vdots \\ \vdots & & & \ddots & 1 ...
-3
votes
1answer
24 views

Proof of positive semidefinite projection [on hold]

How to show the sol. of $\min \limits_{X \in \mathbb{S}^+}||X-C||_F^2$ is $U \hat \Lambda U^T$ where $\hat \Lambda = diag(max(0,\lambda_1), ... , max(0,\lambda_N))$, $C = U\Lambda U^T$ and $\Lambda ...
0
votes
0answers
26 views

How should prove that a function is onto?

This is what is done to prove that a function is onto: For functions given by formulas we proceed along the following lines. Step 1: Let y be any element of the codomain and x an element of the ...
1
vote
2answers
27 views
1
vote
2answers
34 views

If a, b, q, r $\in Z$ s.t $a= bq + r$. Prove $gcd(a,b) = gcd(b, r).$

Here's what I have so far, I let $d_1$ divide $a$ and $b$ so I could write $a$ and $b$ as $a= d_1k$ and $b=d_1j$. After manipulation, I was able to achieve that $d_1|r$ after substituting values for ...
0
votes
2answers
38 views

How to start proof of triangular inequality? [duplicate]

$$\left| {\left| a \right| - \left| b \right|} \right| \le \left| {a \pm b} \right| \le \left| a \right| + \left| b \right| $$
1
vote
2answers
43 views

Prove by induction on $n$ that when $x \gt 0$, $ (1+x)^n \ge 1+nx+\frac{n(n-1)}{2}x^2 \text{ for all positive integers } n. $

Here's the problem: Prove by induction on $n$ that when $x \gt 0$ $$ (1+x)^n \ge 1+nx+\frac{n(n-1)}{2}x^2 \text{ for all positive integers } n. $$ So, clearly the base case is true. Here's how far ...
-4
votes
1answer
29 views

Use induction to prove a couple of questions [closed]

(a) Let f(x) = e^(-1/x^2), x > 0. Use mathematical induction to prove that, for every n ≥ 1, the n’th derivative f^(n)(x) is of the form Pn(1/x)· e^(-1/x^2) for some polynomial Pn (depending on n) b) ...
2
votes
4answers
81 views

proving that for every integer $x$, if $x$ is odd, then $x + 1$ is even (induction)

So I have to write a proof that "for every integer $x$, if $x$ is odd, then $x + 1$ is even". I understand what I have to do but I always get stuck at the last step which is prove that it's true for ...
0
votes
1answer
28 views

can someone explain the proof of russels paradox (barber)?

So I understand Russels paradox (barber) but I do not understand the proof, I've looked everywhere online and youtube videos but it doesn't seem to make sense. Please note, I have compensated ...
0
votes
2answers
16 views

Prove an existential quantifier goal by assuming there exists an arbitrary value that makes the expression true.

I'm trying to prove the following: Suppose { A$_{i}$ | i $\in$ I } is an indexed family of sets and I $\neq$ $\emptyset$. Prove that $\cap$$_{i \in I}$A$_{i}$ $\in$ $\cap$$_{i \in ...
3
votes
0answers
17 views

for a given $f$, $f$ is measurable iff $f^{-1} (${$-\infty$}$) \in \mathcal{M}$ , $f^{-1} (${$\infty$}$) \in \mathcal{M}$ and f is measurable on $Y$.

Let $f : X \rightarrow \bar{\mathbb{R}}$ and $Y = f^{-1}(\mathbb{R})$ then f is measurable iff $f^{-1} (${$-\infty$}$) \in \mathcal{M}$ , $f^{-1} (${$\infty$}$) \in \mathcal{M}$ and f is measurable on ...
0
votes
2answers
67 views

Solutions of $\arctan x = 1 - x$. Proofs?

In this question, we examine the equation $\arctan x = 1 - x$. You may assume without proof that $\arctan x$ is continuous on $R$. a) Prove that there is a solution to the equation in the interval ...
0
votes
0answers
21 views

Order statistics difficult problem

The $n+1$ random variables $X_i$ ($1\le i\le n+1$) are independent and identically distributed with cummulative distribution $F$. Let $Y_k$the order statistics of $X_1,...,X_n$ and let $Z_k$ the order ...
1
vote
2answers
74 views

Prove there exists a unique continuous function

suppose that $f:A\to\mathbb R$ is uniformly continuous on $A$. Let $\overline{A}$ be the closure of $A$. Assuming that there exists a continuous extension of $f$, $g:\overline{A}\to \mathbb R$ ...