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

How to show the inductive step of the strong induction?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 341]. Problem: Use strong induction to show that all dominoes fall in an infinite arrangement of dominoes if ...
0
votes
2answers
49 views

How to get $k^{k + 1} + k^k$ to equate $(k+1)^{k+1}$?

This is a problem from Discrete Mathematics and its Applications Let $P(n)$ be the statement that $n!<n^n$, where $n$ is an integer greater than $1$. $\quad(a)$ What is the ...
1
vote
1answer
33 views

Show that $\binom{1/2}{k} = \frac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}$

The Problem Show that $$\binom{1/2}{k} = \frac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k}$$ My Work $$\begin{align*}\frac{(-1)^{k+1}}{4^k(2k-1)}\binom{2k}{k} &= ...
2
votes
3answers
39 views

How to show no other elements besides $\pm 1$ will be in the kernel of $h: \mathbb Z_p^* \rightarrow \mathbb Z_p^*$; $h(\bar{a}) = \bar{a}^2$.

Let $p$ be a prime and let $h: \mathbb Z_p^* \rightarrow \mathbb Z_p^*$ be defined by $h(\overline{a}) = \overline{a}^2$. Since $h(\overline{xy}) = \overline{xy}^2 = \overline{x}^2 \overline{y}^2 = ...
1
vote
2answers
33 views

How can this be proven (Matrices)

I need to prove why the image on the bottom is true, btw this is on a matrices unit so you know that the order of multiplication does matter
0
votes
1answer
52 views

How do I prove that $\mathbb{Z}[\frac{1+\sqrt{-3}}{2}]$ is a PID?

I'm curious how to prove $\mathbb{Z}[\frac{1+\sqrt{-3}}{2}]$ is a PID. Before I get started proving this, I want to know a correct direction. Is it a good way to prove this by showing that the ring ...
1
vote
1answer
26 views

Using the sequential Criterion, give a proof that $\lim\limits_{x\to 0} f(x)$ does not exist, where: $f(x) = -1$, $x \leq 0$ or $x$, $x>0$

Using the sequential Criterion, give a proof that $\lim\limits_{x \to 0} f(x)$ does not exist, where $$f(x) = \begin{cases}-1 & \text{if } x < 0\\ \ \ \ x & \text{if } x \geq 0 ...
0
votes
2answers
60 views

Reciprocal squares sum inequality [duplicate]

What is the easiest (preferably inductional) way without approximation of the sum_ to prove the following inequality: $\frac{1}{1^2}+\frac{1}{2^2} + \ldots +\frac{1}{n^2} \le 2 - \frac{1}{n}$
1
vote
1answer
43 views

Proving a function is convex

From the Defintion of convex: Theorem to be proven: If $f$ is differentiable and $f'$ is increasing, then $f$ is convex. Use Proof by Contradiction. Consider, $I = (a, b)$ with $a < x < ...
1
vote
1answer
62 views

Cayley transformation of a skew-symmetric matrix is orthogonal?

If $S$ is skew-symmetric ($S^{T} = -S$), how do I show that $Q$ is orthogonal where $$Q = (I + S)(I - S)^{-1}$$ which is the Cayley transformation of $S$.
0
votes
0answers
10 views

Estimation of changes in solution x when A change

Suppose I have system $Ax = b$ where A = [${2}$ $-1$ $1$; $-1$ $10^{-10}$ $10^{-10}$; $1$ $10^{-10}$ $10^{-10}$]; b = [$2(1 + 10^{-10})$; $-10^{-10}$; $-10^{-10}$] and x = [$10^{-10}$; $-1$; $1$] ...
2
votes
1answer
27 views

I cant identify the quantifier

For a simple question like Let x, y ∈ Z. If 3 | x or 3 | y then 3 | x y, Is it alright to assume all x and all y exist in Z? I am trying to negate the statement but since it does not say 'each' ...
0
votes
1answer
34 views

Negate the following statement

“The integer n is even if and only if$$ n^2 + 1$$ is even"" The professor wrote that the negation of this statement is "The integer n is even if and only if $$ n^2 + 1$$is odd." I am pretty sure ...
1
vote
1answer
31 views

Proof in which sup A is related to inf B

Let $A \ne \emptyset$ also $A \subset [1,3].$ Define $B$ to be the set of positive real numbers $x$ such that $\sqrt{x}-1$ is an upper bound of $A.$ Prove that $\inf B = (1 + \sup A)^2.$ Here are my ...
2
votes
1answer
17 views

Proof: Number theory: Prove that if $n$ is composite, then the least $b$ such that $n$ is not $b$-pseudoprime is prime.

I'm looking to prove this, but not too sure how: If $n$ is composite, then the least $b$ such that $n$ is not $b$-psp is prime. Thanks!
0
votes
1answer
21 views

Deduce the Nested Interval Property from MCT?

Let $a_n$ be an increasing sequence, $b_n$ be a decreasing sequence, and assume that $a_n < b_n, \space \forall n \in N$. Show that $\lim(a_n) ≤ \lim(b_n)$, and thereby deduce the Nested Intervals ...
0
votes
1answer
37 views

If $x_n$ and $y_n$ are sequences where $x$ converges to a value other than $0$ and $x_ny_n$ converges, then $y_n$ converges.

Does this make sense? Since $x_n$ converges to a value other than $0$, and $x_ny_n$ converges, then: $$y_n = \frac{x_ny_n}{x_n}$$ also converges.
1
vote
0answers
23 views

Proof: Let $\gcd(a,m)=1$. Then $a^i\equiv a^j\pmod{m}\iff i\equiv j\pmod{\text{ord}_m a}$

Would someone be so kind as to look over my proof for me? $\underline{\implies}$ EDITED Assume $a^i \equiv a^j\pmod m$. Then, $a^{i-j} \equiv 1 \pmod m$. This means that $i-j = k \cdot ...
0
votes
1answer
38 views

Contrapositive of this statement

Suppose $∀x ∈ R, ∃y ∈ R$, s.t. $∀z ∈ R.$ Consider the following statement: $$z > y \implies z > x + y $$ The contrapositive of this statement is: $$z ≤ x+y \implies z ≤ y$$ with the same ...
1
vote
3answers
50 views

Defining prime numbers for proofs

In my discrete mathematics book under existence proofs it has Prove that there exists a prime $p$ such that $2^p -1$ is composite. It then goes on to say by trial and error we find $2^{11}-1$ ...
-1
votes
1answer
53 views

Show that $\lim (\sqrt{n^2+1)}-n) = 0$ [duplicate]

Can't use limit rules as $\sqrt{n^2+1}$ and n are not convergent sequences
1
vote
1answer
26 views

Prove that if $\displaystyle \lim_{n\to \infty} x_n = x$ and if $x > 0$, there exists a natural number $M$ such that $x_n >0$ for all $n > M$.

Prove that if $\displaystyle \lim_{n\to \infty} x_n = x$ and if $ x > 0$, then there exists a natural number $M$ such that $x_n >0$ for all $n > M$. Is this not just a proof of the ...
0
votes
1answer
35 views

Definition of Ordinal (w/ Axiom of Regularity) (problem 37, page 208, Enderton's Elements of Set Theory)

Given the definition of an ordinal to be well-ordered by $\in$ and transitive, I am interested with proving the following: I know and understand the following which easily proves it, but uses the ...
7
votes
4answers
188 views

Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ Source: As was noted in the original post, this problem is from Daniel J. Velleman's book ...
1
vote
1answer
21 views

Let $u,v \in \mathbb{R}^n, A = u\cdot v^T$ then prove $\|A\|_2 = \|u\|_2 \; \|v\|_2$

Let $u,v \in \mathbb{R}^n, A = u\cdot v^T$ then prove $\|A\|_2 = \|u\|_2 \; \|v\|_2$ How can I do this? I'm kinda stuck with this 2-norm of the matrix. If it would be $\|A\|_{\text{frob}}$ then ...
3
votes
1answer
57 views

A question on proving the uniqueness of a mathematical object

When proving that there is a unique mathematical object that satisfies a particular condition, e.g., the inverse of an element of a group, is the intuition behind it the following? You assume that ...
1
vote
2answers
42 views

Prove identity related to nths root of unity

If $1=z_0,z_1,...,z_{n-1}$ are nth roots of unity, prove that $$(z-z_1)(z-z_2)...(z-z_{n-1})=1+z+z^2+...+z^{n-1}$$ I don't know what is meant by the condition given. If I substitute ...
1
vote
2answers
91 views

If $f:\mathbb{R} \to \mathbb{R}$ has two derivatives such that $f(0) =0$ and $ f'(x) \leq f(x), \forall x,$ then $f\equiv 0 \ ?$

Suppose $f:\mathbb{R} \to \mathbb{R}$ has two derivatives such that $f(0) =0$ and $ f'(x) \leq f(x), \forall x.$ Could anyone advise me how to prove/disprove that $f \equiv 0 \ ?$ Thank you.
1
vote
1answer
77 views

Prove that every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex.

I need to prove/disprove the following statement -- If every minimal edge cut in a simple connected graph $G(V,E)$ is even, then $G(V,E)$ has no odd degree vertex. I am a bit confused about one of ...
0
votes
1answer
31 views

why does $\varphi'(N)=0$ in this proof?

Fulton's book on page 105 defines $N$: Afterwards Fulton writes this solution for this lemma: I didn't understand why $\varphi'(N)=0$ Thanks
1
vote
1answer
45 views

Any advantage when proving linear algebra statements without using bases?

I always felt that proofs in linear algebra that do not assume the existence of bases seem more elegant but is there also something mathematically more valuable about these proofs? I know that the ...
0
votes
4answers
69 views

In the Collatz function, why does $2^k-1$ reach $3^k-1$ after $2k$ steps, and could it be used to find divergent trajectories?

If you start calculating the Collatz function from an integer of the form $2^k-1$, you will reach $3^k-1$ after $2k$ steps. So, it is possible to pick a starting value that continuously zig-zags ...
1
vote
1answer
95 views

A question regarding a small calculation in the proof of a theorem.

I understand the theorem overall, and that the $\epsilon$ values are arbitrary. Notice how the values $\epsilon_1=\frac\epsilon{2M}$ and $\epsilon_2=\frac\epsilon{2(|t| + 1)}$ are just assumed, and ...
1
vote
1answer
61 views

Two rows or two columns with the same number of plusses

I have tried drawn numerous tables in attempt to explain this and understand that the number of cells must be even however, I am not sure how to create this proof. I appreciate your support. Each ...
3
votes
1answer
29 views

Show that $\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}$ where $|x| < 1$ is not uniformly convergent

Show that $\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}$ where $|x| < 1$ is not uniformly convergent My professor's proof is as follows: So we know that the radius of convergence is $R = 1$. Now ...
0
votes
1answer
52 views

Show that $\sup \{f(x) + g(x) : x \in\ X\} \leq \sup \{f(x) : x \in\ X\} + \sup \{g(x) : x \in\ X\}$

Let $X$ be a nonempty set, and let $f$ and $g$ be defined on $X$ and ave bounded ranges in $\mathbb{R}$. Show that: $$\sup \{f(x) + g(x) : x \in\ X\} \leq \sup \{f(x) : x \in\ X\} + \sup \{g(x) : x ...
3
votes
2answers
122 views

Understanding how to prove limit theorems for sequences.

How do you know what arbitrary value to choose for epsilon as in this document, and when should the triangle inequality be considered when writing your proof?
1
vote
1answer
55 views

Uniform convergence of $\sum_{k=1}^{\infty}\frac{2^{k-1} x^{2^{k-1}-1}}{1+x^{2^{k-1}}}$

Does $\sum_{k=1}^{\infty}\frac{2^{k-1} x^{2^{k-1}-1}}{1+x^{2^{k-1}}}$ converges uniformly. $-1<x<1$ I have tried to bound it by Weierstrass M-Test but haven't been successful. I have also tried ...
1
vote
0answers
14 views

Finding specific functions $g_i$ in $f(x)= \sum_{i=1}^{n} x^{i}g_i $

Let $f: \mathbb{R}^{n} \to \mathbb{R}$ be differentiable (may be not in $C^{1}$) and $f(0)=0$, show that there exists $g_{i} : \mathbb{R}^{n} \to \mathbb{R}$ such that: $$f(x)= \sum_{i=1}^{n} ...
1
vote
1answer
20 views

Proof through contradiction

My textbook says: To prove $A\Rightarrow B$ we have to lead $A \wedge \neg B$ to a contradiction. Does it imply, that $B\Rightarrow A$ would also be true? As far as I know $\wedge$ is commutative.
1
vote
1answer
45 views

Proving that a function that calculates the cardinality of a given set is surjective on specified domain and codomain.

Define the set $A \subseteq\mathcal P(\mathbb N)$ as $$A = \{E \in\mathcal P(\mathbb N)\,:\, E\ \text{has a finite amount of elements}\}$$ Define a function $f: A\rightarrow \mathbb N$: ...
3
votes
2answers
56 views

Prove that given real number $x$ there exist unique numbers $n$ and $\epsilon$ such that $x=n+\epsilon$ where $n$ is an integer and $0\leq\epsilon<1$

I wrote Since $0\leq\epsilon<1$ and $x=n+\epsilon\implies$ $\epsilon=x-n$, this shows that $n\leq x$. Since $n$ is an integer we also know that $0\leq n \geq 1$. Since $x = n + \epsilon ...
5
votes
5answers
589 views

The set of functions that are zero almost everywhere is enumerable

I have become somewhat overwhelmed with a problem I am working on I had a friend tell me that my proof was wrong. I would be grateful if someone could explain why I am wrong, and possibly offer a ...
1
vote
1answer
37 views

Induction help with final answer

Use induction to prove that for any complex number $z$ that does not equal $1$ and integer n is greater or equal to 1: $$ 1+z+z^2+...+z^n = \frac{1-z^{n+1}}{1-z} $$ So far for the base case I used ...
1
vote
1answer
45 views

Estimating distance between two functions

Let $F = {f_{n} | n ∈\Bbb N }$ be an infinite collection of functions $f_{n}(x)=e^{−n(x−n)^2} , x ∈ \Bbb R$. I am trying to prove that $F$ is closed in $BC(\Bbb R, \Bbb R)$, where $BC$ is the space of ...
2
votes
1answer
62 views

How to show that $Rank(AB)\geq Rank(A)+Rank(B)-n$

Let $A\in M_{m \times n}$ and $B\in M_{n \times k}$. Prove that $$Rank(AB)\geq Rank(A)+Rank(B)-n.$$ I have tried to use $Im(AB) \subseteq Im(B)$ but that lead me to nowhere, how should I approach ...
4
votes
0answers
53 views

Proving not equicontinuity in $\Bbb R$ but equicontinuity in any other closed subset of $\Bbb R$

Let $F = {f_{n} | n ∈\Bbb N }$ be an infinite collection of functions $f_{n}(x)=e^{−n(x−n)^2} , x ∈ \Bbb R$. Prove that $F$ is not equicontinuous on $\Bbb R$ but equicontinuous on $[−a, a]$ for any $a ...
0
votes
1answer
53 views

A decomposition of a differentiable function

this time I want to solve this problem: Let $f: \mathbb{R}^{n} \to \mathbb{R}$ be differentiable (may be not in $C^{1}$) and $f(0)=0$, show that there exists $g_{i} : \mathbb{R}^{n} \to \mathbb{R}$ ...
0
votes
2answers
72 views

Assuming $a_k + b_k = 1$ (Putnam 2003) [duplicate]

I do not understand as I wrote in a previous question: solution: I see that we can scale: $u_k$ but I do not understand why it is legal to say $a_k + b_k = 1$ what is $a_1 = 20$ and $b_1 = 1$ ...
0
votes
0answers
14 views

Proof for Scaling homogeneous inequalities. [duplicate]

Apparently, there exists a theorem, which says if a inequalities is homoegenous the terms can be multiplied by a scale $u_k$ like: $$(a_1 a_2 ... a_n)^{1/n} + (b_1 b_2 ... b_n)^{1/n} \le [(a_1 + ...