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

2
votes
2answers
246 views

how to prove that the following is not a regular language?

the language we want to disprove is : $$ L = \{ 0^i1^j| gcd(i,j)=1 \} $$ my attempt : i used the pumping lemma this way: consider the set of strings of the form $0^p1^q$ such that $n <=p$ and ...
4
votes
2answers
94 views

How much does Proof writing improve over the years?

This is a very soft question. Just a bit of background: I'm a junior in high school taking Analysis I and II out of Baby Rudin at a very well-recognized university. I find quite a few of his ...
1
vote
0answers
22 views

Let A= [0,1] - {1/n │n ∈ N}. Find sup(A), inf(A), min(A), max(A).

My idea of this question is to claim sup(A) and inf(A) exists (and equals a value) and prove by contradiction that min(A),max(A) exists afterwards (and equals sup(A),inf(A)). The issue that I have is ...
2
votes
2answers
72 views

Prove $f(x)=g(x)$ for all $x \in\mathbb{R}$

If $$f(x)=\sum_{n=0}^\infty\frac{x^n}{n!}, x\in\mathbb{R}$$ and $$ g(x) = 1 + \int_0^x f(t) \,dt $$ prove that $g(x)=f(x)$ for all $x\in\mathbb{R}$ and prove that $f$ is differentiable on ...
0
votes
1answer
69 views

How to prove that the matrix $A^k$ approaches $0$ as $k$ approaches infinity

First of all, what does it mean to say an eigenvalue is "less than unity"? I'm not exactly sure what this means. Secondly, how do I show that $\lim_{k\to\infty} A^k=0$ given that all eigenvalues of ...
0
votes
1answer
32 views

Prove that if $\lim_{x\to c} f(x)=L$ then $\lim_{x\to c} 7f(x)=7L$

Prove that if $\displaystyle\lim_{x\to c} f(x)=L$ then $\displaystyle\lim_{x\to c} 7f(x)=7L$ I've never worked with limits, yet am trying to figure out how to prove this.
0
votes
1answer
71 views

Show that $4^\frac{1}{3}$ is an algebraic number?

How do you show that $4^\frac{1}{3}$ is an algebraic number? I don't understand the question nor how to begin on describing the proof to show what the question is asking.
3
votes
0answers
145 views

An argument for “Brocard's problem has finite solution”

Brocard's problem is a problem in mathematics that asks to find integer values of n for which $$x^{2}-1=n!$$ http://en.wikipedia.org/wiki/Brocard%27s_problem. According to Brocard's problem ...
0
votes
2answers
150 views

Proving $x^{2}+1 \neq n! $,using Gaussian Integer.

I want to show that $$x^{2}+1 \neq n! $$ for $n>3$ where $x,n$ are both integers. Since $$x^{2}+1=(x+i)(x-i) $$ it follows that $x^{2}+1$ has only prime factors on the form ($4k+1$), whereas $n!$ ...
-1
votes
2answers
68 views

Proving by induction $2^k - 1 = 1+\cdots +2^{k-1}$

How can I show: $$2^k - 1 + 2^{(k+1)-1} = 2^{k+1} - 1$$ I am trying to prove this by induction: $$2^k - 1 = 1+\cdots +2^{k-1}$$ and proved the base case: $2^2-1 = 1+2^1$ as $2^2-1=3$ and ...
3
votes
3answers
57 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
3answers
32 views

How to prove that $G(x)=ax+b$ is a one-to-one correspondence where $a\neq0$ and $a,b\in\mathbb{R}$.

$G(x) = ax + b$ where $a$ is not equal to $0$ and $b$ are real numbers. Prove $G$ is a one-to-one correspondence. I understand that for every $a$ there is a corresponding $b$-value that does not ...
3
votes
2answers
72 views

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. Is this valid?

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. I would say that this is false since the weather isn't directly influencing John's health. Am I right or wrong? Should I use ...
3
votes
3answers
67 views

How can I prove if $A\subseteq B$, then $A\cup B=B$?

I need to prove that $$A\subseteq B \implies A\cup B=B$$ I defined the subset relation as the statement $x\in A\Rightarrow x\in B$. I tried to convert the claim into a logic statement, then proceeded ...
5
votes
4answers
81 views

Prove $2015$ divides $1^{2015}+2^{2015}+3^{2015}+\cdots+2015^{2015}$.

How to prove that the number $$1^{2015}+2^{2015}+3^{2015}+\cdots+2015^{2015}$$ is divisible by $2015$.
0
votes
1answer
69 views

$3 \times 3$ matrices are similar if and only if they have the same characteristic and minimal polynomial

I want to prove: $B$ is similar to $A \Leftrightarrow m_A(x) = m_B(x)$ and $P_A(x) = P_B(x)$, where $m,P$ are the minimal and characteristic polynomial, respectively. "$\Rightarrow$" Let $A$ to ...
5
votes
1answer
53 views

$\mathbb{Z}[\sqrt{2}]/(3-\sqrt{2})$ is ring isomorphic to $\mathbb{Z}_n$.

what would be an $n$ such that $\mathbb{Z}[\sqrt{2}]/(3-\sqrt{2})$ is ring isomorphic to $\mathbb{Z}_n$? This problem was on a qualification test. Here's how I solved it, but I'm not satisfied ...
0
votes
5answers
60 views

Prove that if $m$ and $n$ are integers and $mn$ is even, then $m$ is even or $n$ is even.

I have this assignment: Prove that if $m$ and $n$ are integers and $mn$ is even, then $m$ is even or $n$ is even. How should I begin?
0
votes
2answers
25 views

quick function proof

If $$f(x)$$ is a function with unit area, show that the scaled and strectehd function $$\frac{1}{a}f(\frac{x}{a}) $$ also has unit area. Before you give an answer I would still like to try to ...
3
votes
1answer
61 views

Introduction to proofs: proving a set is a partition.

I've been really trying to understand how some of these proofs work; I've spent a majority of my time studying the material for this class, but I'm still performing poorly in it. It doesn't help that ...
1
vote
4answers
81 views

Prove that if $k \in \mathbb{N}$, then $k^4+2k^3+k^2$ is divisble by $4$

I am trying to solve by induction and have established the base case (that the statement holds for $k=1$). For the inductive step, I tried showing that the statement holds for $k+1$ by expanding ...
1
vote
2answers
24 views

Using the binomial theorem to generate a geometric proof of the derivative.

According to wikipedia, if we wanted to prove $$(x^n)'=nx^{n-1}$$ geometrically by creating an $n$-dimensional hypercube $$(x+\Delta x)^n$$ and setting $a=x$ and $b=\Delta x$, we could expand using ...
-2
votes
0answers
27 views

Algebra , indexed family of sets, Set theory. [closed]

i have this problem on the notion of indexed family of sets that i am trying to solve . Any contribution will be very much appreciated . Many thanks. Questions Let $A_n=[1/n,2-1/n]$ and ...
0
votes
0answers
29 views

If $x\in S$ and $x\notin S'$, then $x\in bd S$

If $x\in S$ and $x\notin S'$, then $x\in bd S$. From $x\in S$, I know that for all nbd $N$ of $x$ , $N\cap S\neq \emptyset$. From $x\notin S', $ I know that there exists a nbd $N$ of $x$ such that ...
2
votes
3answers
70 views

Prove irrationality of $\sqrt{2+\sqrt{2}}$ and $\sqrt{2}+\sqrt{3}$ [duplicate]

I am trying to prove the irrationality of the above two numbers, but I don't know how. What would be a general strategy for problems like these? My current strategy is trying to reach a contradiction ...
1
vote
1answer
30 views

Finding a natural number $k>1$ such that $k$ divides $(26+35n)$ and $(3+7n)$

I am trying to find a natural number $k>1$ such that $k$ divides $(26+35n)$ and $k$ divides $(3+7n)$ for some integer $n$. I know that $(ka)=(26+35n)$ for some $a \in Z$ and $(kb)=(3+7n)$ for some ...
1
vote
1answer
21 views

Is there exist $n_p\in\mathbb{N}$ such that $p+1\equiv 0 \mod (4n_p-p)$ for prime $p(\ge 5)$?

I am looking a proof for, Existence of a positive integer $n_p$ such that $$p+1\equiv 0 \mod (4n_p-p) $$ for each prime $p\ge 5.$ But I have no idea to get an attempt to this problem in general. ...
0
votes
0answers
18 views

Proving if languages are regular [closed]

I want to prove that for any regular language R over the alphabet {0, 1}, the language P(R) over {0, 1,(,)} is also regular and P(R) = {(s) | s ∈ R}. I am a little new to proofs and I was wondering ...
0
votes
1answer
51 views

Dedekind Cuts and Real Numbers

A Dedekind cut L is a nonempty proper subset of the rational numbers that: (1) Has no maximal element (2) for all a,b in the rational numbers a is in L and b < a implies that b is in L. If $D$ is ...
4
votes
4answers
52 views

Showing $k^2-1$ is divisible by 8 when $k$ is an odd natural number

Prove that $k^2-1$ is divisible by $8$ when $k$ is an odd natural number. I am trying to prove this using induction. Initial case: Let $k\in N$ such that $k=1$ Then $k^2-1=1^1-1=0$. ...
1
vote
2answers
24 views

R={(x,y)∈ℤ×ℤ:3∣(x+y)}. Is R reflexive? Is R symmetric? Is R transitive?

First, reflexivity? Could (1,1) be a counter example, because 3∤(1+1)? As for symmetry, addition is commutative, so if 3∣(x+y), then 3∣(y+x) because x+y=y+x. Transitivity, I can't come up with a ...
0
votes
3answers
30 views

Let $f:\mathbb N\to\mathbb N$, be $f(n)=\left\lfloor\frac{2n+2}3\right\rfloor$

Let $f:\mathbb N\to\mathbb N$, be $f(n)=\left\lfloor\frac{2n+2}3\right\rfloor$. Is f one-to-one? Is f onto? I found it quite easy to find a counter-example for f not being one-to-one. ...
0
votes
1answer
24 views

Evaluating $\lim _{h\to 0^+}f(x-y)g(x/h)/h^n$

Let $f$ be locally integrable in $\mathbb{R}^n$ and let $g:\mathbb{R}^n\to \mathbb{R}$ be a bounded (Lebesgue) measurable function that vanishes outside of a compact set. I am trying to show that ...
0
votes
2answers
38 views

Prove there no integers $x,y$ such that $x+y=100$ and $\gcd(x,y)=3$

I have not encountered a problem like this before.I was thinking that there are 2 methods to solve this. 1. Assume $x+y=100$ and then prove that $\gcd(x,100-x)\neq 3$. 2. Assume that $\gcd(x,y)=3$, ...
1
vote
3answers
44 views

Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$.

Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$. So I have to show that $(A\cap B) \cup (A\cap \overline{B})\subseteq A$ and that $A \subseteq(A\cap B) \cup (A\cap ...
2
votes
4answers
45 views

Finding growth bounds on Fibonacci Sequence

I've been working on this following problem: Find a constant $c< 1$ such that $F_n \leq 2^{cn}$ for all $n \geq 0$. I honestly have no idea where to begin on this. I've done plenty of proofs ...
3
votes
1answer
47 views

Prove that $R$ is an equivalence on $\mathscr P(A)$. Is this correct?

Suppose $B\subseteq A$, and define a relation R on $\mathscr{P}(A)$ as follows: $$R=\{(X,Y)\in\mathscr{P}(A) \times \mathscr{P}(A)\mid(X\mathrel{\triangle} Y)\subseteq B\}$$ Prove that $R$ is an ...
1
vote
4answers
76 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
1
vote
2answers
45 views

prove P ∧ Q → P ⇔ R ∨ ¬R in natural deduction

I am a beginner in Natural Deduction currently reading the book "Logic in Computer Science" and got stuck at proving: $$ P\land Q\to P\Leftrightarrow R\lor\lnot R$$ The latter formula is clearly a ...
0
votes
2answers
21 views

Proving the summation of a function as big theta of another function

Show that $\sum^n_i i^4\log^2i$ = $\Theta(n^5\log^2n)$ I am completely lost on how to solve this problem. I understand that $\Theta$ deals with the upper and lower bounds, so do we prove both big-oh ...
0
votes
0answers
17 views

Deeply confused while trying to understand the derivation of infinite product representation of gamma function

I am trying to understand how in the world Euler figured out the infinite product representation of Gamma function. $$\Gamma (z)=\lim_{n\rightarrow \infty }\frac{n!n^{z}}{z(z+1)\cdots(z+n)}$$ Of ...
5
votes
1answer
36 views

Function on a Power Set

Let $f\colon \mathcal{P}(A)\mapsto \mathcal{P}(A)$ be a function such that $U \subseteq V$ implies $f(U) \subseteq f(V)$ for every $U, V \in \mathcal{P}(A)$. Show there exists a $W \in \mathcal{P}(A)$ ...
1
vote
0answers
27 views

Regularity of Special Measures

(1) Show that the counting measure on $\Bbb Z$ with the induced metric from $\Bbb R$ is regular. (2) Show that the delta measure with respect to a point $x_0$ on any metric space is regular. What I ...
1
vote
1answer
22 views

Relative Primes and Congruence

Suppose that $a$ and $n$ are relatively prime. Prove that there is an integer $b$ such that $ab\equiv 1\pmod n$ .
0
votes
0answers
91 views

Squeeze theorem and $\frac{\sin x}{x}$

I've been going over old calculus books to refresh my memory and have mainly been focusing on proofs. One of the things I found interesting was the squeeze theorem, even though since basic calculus i ...
1
vote
2answers
59 views

Finding an operation on $G^S$ that yields a group

Problem: Assume $S$ is a nonempty set and $G$ is a group. Let $G^S$ denote the set of all mappings from $S$ to $G$. Find an operation on $G^S$ that will yield a group. Update (full attempted ...
3
votes
1answer
25 views

Prove: R∩R−1 is symmetric.

The problem that I'm having is proving it - obviously. The only context that I am provided with is: "Prove: R∩R−1 is symmetric." If (x,y) ∈ R then (y,x) ∈ R−1, and since it's the intersection, ...
2
votes
2answers
63 views

Proving a Simple Fact about Slopes of Lines

The following problem is a detail from a proof I wrote recently -- a detail that I left unproven, and would like to prove. Let there be three points $a$, $b$, and $c = \frac{a+b}{2}$, with $a<b$. ...
0
votes
2answers
44 views

Prime Factorization

Let $n\ge0$. What is the power of $2$ in the prime factorization of $(2^n)!\,$? Prove that the value is correct. So far I've conjectured the value to be $2^n - 1$. This is true for $n=0,1,2,3,4$. ...
0
votes
1answer
20 views

generalised eigenspace is invariant proof

let $T \in \text{End}(V)$ where $V$ is a finite dimension vector space. We define $V_j(\lambda) = \ker ((\lambda I - T)^j))$ as the generalised eigenspace. I am trying to prove that this space of is ...