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

proof detail concerning bijection between a set and its power set

Theorem: If $X$ is a set, then $X$ is not equivalent to its power set. Proof: suppose for a contradiction that $f:X\to P(X)$ is a bijection. Define $B:=\{x \in X, x\not\in f(x)\}$. Because $f$ is ...
1
vote
1answer
22 views

Wheel Graphs and Dimension of Embeddings

I'd like to preface this by saying this is the tip of the iceberg for an optional question for a summer REU program application, so if you think asking this question is in bad taste, let me know and I ...
2
votes
3answers
841 views

Proof that a $n$-hypercube is $n$-vertex-connected

I'm new to graph theory, I'm finding it hard to get upon proofs. To prove: An $n$-hypercube is $n$-vertex connected. Approaches I thought: It holds true for $n=2$, so assume it holds true for ...
3
votes
3answers
127 views

Proving that for any odd integer: $\lceil \frac{N^2}{4} \rceil = \frac{N^2 + 3}{4}$

I'm trying to construct a proof that for any odd integer: the ceiling of $\large \lceil \frac{N^2}{4} \rceil = \frac{N^2 + 3}{4}$. Anyone have a second to show me how this is done? Thanks!
6
votes
4answers
849 views

Prove by induction: $2^n + 3^n -5^n$ is divisible by $3$

Let $P(n) = 2^n + 3^n - 5^n $. I want to prove that $P(n)$ is divisible by $3$ for all integers $n\geq 1$. The basis step for this proof is easy enough: $P(1)$ is divisible by $3$. For the ...
2
votes
2answers
46 views

Induction Proof without Explictly Using The Induction Hypothesis?

I have encountered several problems where one can prove the desired result without actually needing the induction hypothesis. More specifically, you basically just pick $n \in \mathbb{N}$ and run ...
0
votes
1answer
41 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
1
vote
0answers
20 views

Proving with a given definition that if $|A|=|B|$ then $A,B$ are equivalent (with induction but without using the induction hypothesis)

Let $A,B$ be finite sets, we'll say the sets are equivalent if $|A\setminus B|=|B\setminus A|$. Prove with the above definition that if $|A|=|B|$ then $A,B$ are equivalent. Suppose ...
4
votes
1answer
60 views

Proving $\sqrt{100,001}-\sqrt{100,000} < \frac{1}{2\sqrt{100,000}}$

Proving $\sqrt{100,001}-\sqrt{100,000} < \frac{1}{2\sqrt{100,000}}$ I squared both sides of the equation to get $100,001 + 100,000+-200\sqrt{10}\sqrt{100,001} < \frac{1}{400,000}$. I am just ...
1
vote
1answer
25 views

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.

Prove that if $p > 3$ is a prime then $2(p-3)! \pmod{p} =-1 \pmod{p}$.. I am totally lost; at first I thought this could be done by induction, but unfortunately this is not possible (at least I ...
0
votes
3answers
31 views

Proving if $p|ab$ then $p|a\vee p|b$, then $p$ is prime

Let $1\neq p\in \mathbb N$ such that $\forall a,b \in \mathbb N$ if $p|ab$ then $p|a\vee p|b$. Prove that $p$ is prime. My attempt, proof by contradiction: Suppose $p$ isn't prime, then ...
0
votes
0answers
20 views

About Mellin transform and harmonic series

Let $\mathfrak{M}\left(*\right)$ the Mellin transform. We know that holds this identity$$\mathfrak{M}\left(\underset{k\geq1}{\sum}\lambda_{k}g\left(\mu_{k}x\right),\, ...
0
votes
1answer
17 views

Proof of floor function identity.

Let $f(x) = \lfloor x \rfloor$ and let $l$ be the greatest integer $\le x$ How do I prove $l + 1 > x$ I see that: $x \ge \lfloor x \rfloor = l$ No complete answers, just hints
4
votes
2answers
105 views

Need to prove that “If $x+y \ge 1$ then $x \ge \frac 12$ or $y \ge \frac 12$”

So I have this one homework assignment where I have to prove the following clause "If $x+y \ge 1$ then $x \ge \frac 12$ or $y \ge \frac 12$". I thought that if I assign $x=y$ and put it like "$2x \ge ...
1
vote
4answers
3k views

Is this correct method to prove that $a^2 + b^2 + c^2 ≥ ab + bc + ac$, when $a,b,c \geq 0$?

Can I prove it like this: Let's say that $a=b=c$ so we get "If $a \geq 0$ then $3a^2 ≥ 3a^2$" Now I take the negation of that statement and get "If $a \geq 0$ then $3a^2 < 3a^2$" The anti-thesis is ...
7
votes
0answers
196 views

Proof of the conjecture that the kernel is of dimension 2, extended

Pursuing my research, I am now looking for a proof of an extension of the problem proposed here and answered. It's an extension in the sense that I'm now considering two different $t_1$ and $t_2$. The ...
1
vote
2answers
33 views

Proving Pascal's identity

So I came across Pascal's identity: Prove that for any fixed $r\geq 1$, and all $n\geq r$, $$ \binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1}. $$ I know you can use basic algebra or even an inductive ...
3
votes
4answers
439 views

How can I prove this integral is equal to f(0)?

Given that $f$ continuous over $[-1,1]$, how can I show $\lim_{x \to 0}\frac{1}{x}\int_0^xf(t)dt = f(0)$? I know the limit of $\frac{1}{X}$ doesn't exist at 0, and it's negative infinity from the ...
2
votes
3answers
53 views

Prove that $0 < 1$. Prove that $ab = 0 \implies a = 0$ or $b = 0$.

Proof: There exists $a = 0$ (For every $b$, an element of the set of positive numbers, such that: $b > a$) $$a + b > 0 \implies b > 0 \implies a < b.$$ Thus, we have shown that $0 < ...
3
votes
1answer
14 views

Boolean Algebra: Converting $xy'z + wxy'z' + wxy + w'x'y'z' + w'x'yz' = w'x'z' + xy'z + wx$

Notation w,x,y,z are all just primary statements "+" is the OR logical operator what looks like two or more statements being multiplied is actually the AND operator The complement or prime ...
2
votes
2answers
44 views

Geometric interpretation or solution of an induction problem

Problem: Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile, ...
2
votes
1answer
22 views

Finding a specific term in a repeating sequence.

Let $f(x) = \frac1{1-x}$, and define the function $f^r$ by $$f^r(x):=\underbrace{f(f(f(...f(f}_{r\text{ times}}(x))))).$$ I am asked to find to find $f^{653} (56)$. I know that there are only $3$ ...
0
votes
2answers
26 views

Binomial coefficient identity $\sum_{k=1}^n k {n \choose k } = n\cdot 2^{n-1}$ [duplicate]

I'm having a bit of problems proving the following: $$\sum_{k=1}^n k {n \choose k } = n\cdot 2^{n-1}$$ I always seem to get to the line: $2^{n-1} + 1 = 2^n$ which I know is untrue. Could anyone ...
6
votes
3answers
70 views

Show $7!^{1/7} < 8!^{1/8}$

Show $7!^{1/7} < 8!^{1/8}$ So I know that the first step is to remove the radicals. So would I raise both sides to the power of 8 to get $({7!}^{1/7})^8 < 8!$. I am not sure where to go from ...
2
votes
2answers
54 views

Show that $a^2 + b^2 + c^2 \geq ab + bc + ca$ for all positive integers $a$, $b$, and $c$ [duplicate]

Show that $a^2 + b^2 + c^2 \geq ab + bc + ca$ for all positive integers $a$, $b$, and $c$. I am not sure how to approach this problem. Should I divide this problem into multiple cases based on ...
3
votes
2answers
41 views

What is the modus ponens of a tautology?

In the statement $P$ and $Q$, please show that $\; (P \land (P \Rightarrow Q))\Rightarrow Q \;$ is a tauntology. The state the $\;(P \land (P \Rightarrow Q))\Rightarrow Q\;$ in words. I know I need ...
2
votes
3answers
26 views

Prove that $\sqrt x$ is Lipschitz on $[1, \infty)$

Prove that $\sqrt x$ is Lipschitz on $[1, \infty)$ I want to show that $|f(x) - f(y)| \leq L |x - y|$ So $|\sqrt x - \sqrt y| = \frac{|x - y|}{\sqrt x + \sqrt y} \leq \frac{1}{2}|x - y|$. I can ...
13
votes
3answers
778 views

Any ideas on how I can prove this expression?

I don't have a lot of places to turn because i am still in high school. So please bear with me as i had to create some notation. In order to understand my notation you must observe this identity for ...
2
votes
2answers
1k views

Solve the recurrence of $T(n)= 3T(n-1)+1$ with$ T(0)=2$ by iteration of the recurrence

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction) I googled "iteration of the recurrence." I did not ...
1
vote
2answers
25 views

Proving if $A$ or $B$ are symmetric then $AB$ is symmetric

Prove if $A$ or $B$ are symmetric then $AB$ is symmetric. Symmetric set definition: $A$ is symmetric if for every $a\in A$ there's $-a\in A$ Product set definition: $AB=\{ab\mid a\in A, ...
0
votes
2answers
48 views

If $\gcd (x,4) = 2$ and $\gcd(y,4) = 2$ then $\gcd(x+y,4) = 4$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $(x, 4) = 2$ and $(y, 4) =2$, then $(x + y, 4) = 4$, where $(a,b)$ denotes the ...
2
votes
2answers
57 views

Is there another way to prove $(x-n)^2 = (n-x)^2$

Let's say $n$ is $4$. So, I came up with the solution below. $(x-4)^2 = (x-4)(x-4) = x^2 - 8x + 16$ $(4-x)^2 = (4-x)(4-x) = 16 - 8x + x^2 = x^2 - 8x + 16$ I was wondering if there is another way ...
0
votes
1answer
27 views

Rectangles in one dimension

I have to prove the following proposition : Show that the intesection of two rectangles in $\mathbb{R}^{n}$ is either the vaccum or is another rectangle. My attempt: I one is embeded in the other ...
1
vote
2answers
43 views

Proving if $|A|\ge 4 \vee |A|\le 2$ then $|A+A|\neq 4$ with direct, contradiction and contraposition

Prove if $|A|\ge 4 \vee |A|\le 2$ then $|A+A|\neq 4$. $A$ is some set and we define $A+B=\{a+b|a\in A, b\in B\}$, $A$ is some subset of the reals. In a direct proof and proof by contradiction I'd ...
0
votes
1answer
33 views

Prove tautology without truth using a truth table. [duplicate]

I am struggling to prove, without using truth tables, that the statement is a tautology. [(p→q)∧(q→r)]→(p→r) My work so far... ¬[(¬p∨q)∧(¬q∨r)]∨(¬p∨r) ...
1
vote
1answer
35 views

Using induction to show associativity on $x_1+\dots + x_n$

I want to use induction to show that the sum $x_1 + \dots + x_n$ of real numbers is defined independently of parentheses to specify order of addition. I know how to apply induction(base, assumption, ...
0
votes
4answers
50 views

GCD : Why does the GCD of two numbers divides their difference?

I was working my way through some number theoretic proofs and being a newbie am stuck on this proof : Why does the gcd of two numbers , say (a,b) - also divides their difference : a-b My ...
0
votes
3answers
36 views

Next step to take in this proof by contradiction?

This is a problem from Discrete Mathematics and its Applications Here is my work so far It's similar to this other question I had Next step to take to reach the contradiction?. I am assuming ...
1
vote
2answers
52 views

How to get to $5^3 \geq n^3$ in the proof by contradiction?

This is the same problem asked here. - Next step to take to reach the contradiction? Here is it again. I understand the solution - how you want to get to the fact 100 divides n^2 and then go ...
0
votes
1answer
45 views
+100

Conditional independence given elementary events implies conditional independence given $\sigma $-algebra

Proposition: Let $X$ be a continuous markov chain with discrete state space $S$. Let $Z$ be the corresponding jump chain and $\left\{ {{W_i},i \in \mathbb{N}} \right\}$ its holding times. Let ...
0
votes
0answers
27 views

How to prove that the integral of a positive, continuous function is positive?

Obviously intuitively the area under something that is above the x-axis is always positive, but how can I show this with a proof?
2
votes
2answers
49 views

Proving with induction $(1-x)^n<\frac 1 {1+nx}$

Prove using induction that $\forall n\in\mathbb N, \forall x\in \mathbb R: 0<x<1: (1-x)^n<\frac 1 {1+nx}$ My attempt: Base: for $n=1: 1-x<\frac 1 {1+x}\iff 1-x^2<1$, true since ...
2
votes
3answers
63 views

Can someone verify my direct proof that if $A$ is a subset of $B$, $A\cup B = B$?

This is a problem from Discrete Mathematics and its Applications I am trying to use a direct proof to do this problem. Here is my book's explanation/section on direct proof Here is my work so ...
0
votes
5answers
49 views

Number theory proof [on hold]

$(i)$ Prove that for every natural number $n \geq 2$, one has $(n + 1)|(n^3 + 1)$; $(ii)$ Suppose that $n$ is a natural number exceeding $1$. Prove that $(n^2-1)|(n^3+1)$ if and only if $n = 2$.
0
votes
1answer
30 views

prove that $p^2-1$ is divisible by $24$ if $p$ is a prime greater than $3$ [duplicate]

How to prove that $p^2-1$ is divisible by $24$ if $p$ is a prime number greater than $3$?
0
votes
1answer
30 views

Using set theory to prove a function problem

I begin with: $$A = \{a \le x < x_0 | f(x) = 0 \}$$ $$B = \{x_0 < x \le b | f(x) = 0 \}$$ Let $c = \sup A$ and let $d = \sup B$ First to prove $f(x) > 0$ for $x \in (c, d)$ I will ...
0
votes
2answers
72 views

Proof of a point's existence in an open interval

Well let us begin consider a set $A$ $$A = \{a \le x \le b \space | \space f(x) > 0 \}$$ Lets take $\alpha = \sup A$ and $\beta = \inf A$ What we must do is prove that $\alpha = d$ and ...
11
votes
8answers
250 views

What are the theorems in mathematics, proved using completely different ideas?

I know this question can have many answers. But I would like to know about theorems which can give completely different proofs. For example: I read from the book "Proof from the Book," there ...
2
votes
2answers
24 views

Homology groups of orientable surfaces.

I am trying to show that the second (simplicial) homology group or an orientable surface is ismormophic to $\mathbb Z$. I can show that this group is non-trivial by triangulating the surface, and ...