For questions about the formulation of a proof, not about the mathematics behind it.

learn more… | top users | synonyms

7
votes
5answers
562 views

Proof writing: how to write a clear induction proof?

What is an effective way to write induction proofs? Essentially, are there any good examples or templates of induction proofs that may be helpful (for beginners, non-English-native students, etc.)? ...
4
votes
3answers
843 views

How to prove that $z\gcd(a,b)=\gcd(za,zb)$

I need to prove that $z\gcd(a,b)=\gcd(za,zb)$. I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me ...
73
votes
4answers
11k views

Can an irrational number raised to an irrational power be rational?

Can an irrational number raised to an irrational power be rational? If it can be rational, how can one prove it?
202
votes
14answers
9k views

Can every proof by contradiction also be shown without contradiction?

Are there some proofs that can only be shown by contradiction or can everything that can be shown by contradiction also be shown without contradiction? What are the advantage/disadvantages of proving ...
26
votes
1answer
3k views

How would one be able to prove mathematically that $1+1 = 2$?

Is it possible to prove that $1+1 = 2$? Or rather, how would one prove this algebraically or mathematically?
9
votes
2answers
3k views

Prove that $\mathcal{P}(A)⊆ \mathcal{P}(B)$ if and only if $A⊆B$. [duplicate]

Here is my proof, I would appreciate it if someone could critique it for me: To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, ...
4
votes
2answers
3k views

Proof the inequality $n! \geq 2^n$ by induction

I'm having difficulity solving an exercise in my course. The question is: Prove that $n!\geq 2^n$. We have to do this with induction. I started like this: The lowest natural number where the ...
4
votes
4answers
3k views

Sum of cubes proof [duplicate]

Prove that for any natural number n the following equality holds: $$ (1+2+ \ldots + n)^2 = 1^3 + 2^3 + \ldots + n^3 $$ I think it has something to do with induction?
61
votes
4answers
21k views

Proof by contradiction vs Prove the contrapositive

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by ...
24
votes
7answers
7k views

how to be good at proving?

I'm starting my Discrete Math class, and I was taught proving techniques such as proof by contradiction, contrapositive proof, proof by construction, direct proof, equivalence proof etc. I know how ...
5
votes
6answers
2k views

Prove that $(a-b) \mid (a^n-b^n)$

I'm trying to prove by induction that for all $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, that $(a-b) \mid (a^n-b^n)$. The base case was trivial, so I started by assuming that $(a-b) \mid (a^n-b^n)$. ...
3
votes
2answers
3k views

Prove the integral of $f$ is positive if $f ≥ 0$, $f$ continuous at $x_0$ and $f(x_0)>0$

Prove that $\int_a^b f(x)\,dx \gt 0$ if $f \geq 0$ for all $x \in [a,b]$ and $f$ is continuous at $x_0 \in [a,b]$ and $f(x_0) \gt 0$ EDIT. Please ignore below. It is very confusing actually -.- ...
4
votes
5answers
361 views

$A \oplus B = A \oplus C$ imply $B = C$?

I don't quite yet understand how $\oplus$ (xor) works yet. I know that fundamentally in terms of truth tables it means only 1 value(p or q) can be true, but not both. But when it comes to solving ...
2
votes
5answers
5k views

Proof by induction that $ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $

I'm starting to understand how induction works (with the whole $k \to k+1$ thing), but I'm not exactly sure how summations play a role. I'm a bit confused by this question specifically: $$ ...
11
votes
8answers
1k views

Book about technical and academic writing

I'm in the process of writing my Master's Thesis on automata theory. The writing must be in English which isn't my mother tongue. So the question is, given that this is my first time long (hundred ...
16
votes
3answers
20k views

Prove: If a sequence converges, then every subsequence converges to the same limit.

I need some help understanding this proof: Prove: If a sequence converges, then every subsequence converges to the same limit. Proof: Let $s_{n_k}$ denote a subsequence of $s_n$. Note that $n_k ...
1
vote
2answers
449 views

simple binomial theorem proof

I am trying to prove this binomial statement: For $a \in \mathbb{C}$ and $k \in \mathbb{N_0}$, $\sum_{j=0}^{k} {a+j \choose j} = {a+k+1 \choose k}.$ I am stuck where and how to start. My steps ...
4
votes
5answers
541 views

H0w t0 prove that periodic decimal numbers are rational? $a_1…a_k(b_1b_2..b_l)={m \over n}$

Given $a_1...a_k(b_1b_2..b_l)={m \over n}$ how can I prove that periodic decimal numbers are rational? Where do I even begin?
8
votes
4answers
3k views

$f\geq 0$, continuous and $\int_a^b f=0$ implies $f=0$ everywhere on $[a,b]$

This is problem 6.2 from the 3rd edition of Principles of Mathematical Analysis. Problem 6.2: Suppose $f\geq 0$, f is continuous on $[a, b]$, and $\int_{a}^{b}f(x)dx = 0$. Prove that $f(x)=0$ for ...
7
votes
3answers
155 views

Stuck with proof for $\forall A\forall B(\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)\rightarrow A\subseteq B \vee B\subseteq A)$

I came to point where I suppose for case 1 that $A\subseteq B$ and conclusion is trivial. For case 2 I suppose that $A\not\subseteq B$ and try to prove $B\subseteq A$, but that gets me nowhere. Any ...
4
votes
4answers
3k views

Proving the sum of the first $n$ natural numbers by induction [duplicate]

I am currently studying proving by induction but I am faced with a problem. I need to solve by induction the following question. $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$ for all $n > 1$. Any ...
3
votes
2answers
571 views

Infinum & Supremum: An Analysis on Relatedness

$\require{color}$ Question: I need some help in proving that $\color{green}{\text{if $k\geq 0$, then $\sup (kS) = k\sup(S)$ and $\inf (kS) = k\inf (S)$}}$, and also that $\color{red}{\text{if ...
5
votes
3answers
920 views

How to prove or statements

How do I prove statements of the following types: $A \text{ or } B \implies$ C $A \implies B \text{ or } C$ I don't know how to go about proving statements like this when they have "or". Can ...
18
votes
4answers
844 views

Advice for writing good mathematics?

It's been a (far-fetched, possibly) goal of mine to some day write a math Textbook. I've been thinking about writing this question for a while, but reading an exceedingly mediocre text on Mathematical ...
8
votes
1answer
5k views

Inductive Proof for Vandermonde's Identity?

I am reading up on Vandermonde's Identity, and so far I have found proofs for the identity using combinatorics, sets, and other methods. However, I am trying to find a proof that utilizes mathematical ...
9
votes
2answers
4k views

Proof: How many digits does a number have? $\lfloor \log_{10} n \rfloor +1$

I read recently that you can find the number of digits in a number through the formula $\lfloor \log_{10} n \rfloor +1$ What's the logic behind this rather what's the proof?
2
votes
3answers
1k views

Maps - question about $f(A \cup B)=f(A) \cup f(B)$ and $ f(A \cap B)=f(A) \cap f(B)$

I am struggling to prove this map statement on sets. The statement is: Let $f:X \rightarrow Y$ be a map. i) $\forall_{A,B \subset X}: f(A \cup B)=f(A) \cup f(B)$ ii) $\forall_{A,B \subset X}: ...
7
votes
2answers
1k views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...
1
vote
3answers
4k views

Sum of $k {n \choose k}$ is $n2^{n-1}$

Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$. As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $. I tried solving this by induction but, in the ...
11
votes
5answers
1k views

$A \in B$ vs. $A \subset B$ for proofs

I have to prove a few different statements. The first is if $A \subset B$ and $B \subset C$ then prove $A \subset C$. This one is fairly straight forward, but I'm stuck on how the next one differs. ...
76
votes
14answers
5k views

Formal proof for $(-1) \times (-1) = 1$

Is there a formal proof for $(-1) \times (-1) = 1$? It's a fundamental formula not only in arithmetic but also in the whole of math. Is there a proof for it or is it just assumed?
10
votes
3answers
1k views

Intuition of Addition Formula for Sine and Cosine

The proof of two angles for sine function is derived using $$\sin(A+B)=\sin A\cos B+\sin B\cos A$$ and $$\cos(A+B)=\cos A\cos B-\sin A\sin B$$ for cosine function. I know how to derive both of the ...
10
votes
1answer
32k views

Proof for triangle inequality for vectors

Generally,the length of the sum of two vectors is not equal to the sum of their lengths. To see this consider the vectors $u$ and $v$ as shown below. By considering $u$ and $v$ as two sides of a ...
7
votes
3answers
705 views

Proof of Wolstenholme's theorem

According to the theorem, if $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{p-1} =\frac{r}{q}$$ then we have to prove that $r\equiv0 \pmod{p^2}$. (Given $p>3$, otherwise ...
14
votes
3answers
295 views

Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$

For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$. I used induction principle for the solution but cannot prove it. I took $P(k) = ...
8
votes
3answers
183 views

Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$.

Problem: Prove that $1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$ for $n \in \mathbb{N}$. My work: So I think I have to do a proof by induction and I just wanted some help editing my proof. My ...
8
votes
3answers
5k views

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number I've looked at http://math.stackexchange.com/a/19998 It is known that $2^n-1$ can only be prime if $n$ is ...
7
votes
4answers
23k views

Prove that $1^3 + 2^3 + … + n^3 = (1+ 2 + … + n)^2$ [duplicate]

This is what I've been able to do: Base case: $n = 1$ $L.H.S: 1^3 = 1$ $R.H.S: (1)^2 = 1$ Therefore it's true for $n = 1$. I.H.: Assume that, for some $k \in \Bbb N$, $1^3 + 2^3 + ... + k^3 = (1 ...
6
votes
4answers
888 views

Prove that $\cot^2{(\pi/7)} + \cot^2{(2\pi/7)} + \cot^2{(3\pi/7)} = 5$

Prove that $\cot^2{(\pi/7)} + \cot^2{(2\pi/7)} + \cot^2{(3\pi/7)} = 5$ . I am sure this is derived from using roots of unity and Euler's complex number function, but I am very uncomfortable in these ...
6
votes
2answers
5k views

A continuous function $f$ from a closed bounded interval $[a, b]$ into $\mathbb{R}$ is uniformly continuous

I am reading (as a supplement) the book Basic Real Analysis, by Anthony Knapp. Before I proceed into reading a proof, I want to be sure that the result seems obvious. Yet, I am having trouble seeing ...
6
votes
2answers
4k views

Proof of Non-Ordering of Complex Field

Let $\mathcal F$ be a field. Suppose that there is a set $P \subset \mathcal F$ which satisfies the following properties: For each $x \in \mathcal F$, exactly one of the following statements holds: ...
6
votes
2answers
3k views

help me understand a line in an “$A^TA$ is positive, semi-definite” proof

I am looking at a proof for why $A^TA$ is positive semi-definite when $A$ is $n\times n$ and it has this line. $$ v^TAA^Tv = A^Tv \cdot A^Tv ≥ 0. $$ I understand what $v^TAA^Tv$ means and the purpose ...
5
votes
4answers
583 views

Proof of $n^2 \leq 2^n$.

I am trying to prove that $n^2 \leq 2^n$ for all natural $n$ with $n \ne 3$. My steps are: induction base case: $n=0:$ $0² \leq 2⁰$ which is okay. inductive step: $n \rightarrow n+1:$ ...
2
votes
4answers
3k views

proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
7answers
821 views

Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.

Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume $\neg ...
0
votes
2answers
78 views

How to check, whether the formula is a tautology

How do we decide whether the formula in predicate logic is a tautology? Is there some universal way to decide? Let's have an example: ...
114
votes
10answers
7k views

Why do people use “it is easy to prove”?

Math is not generally what I am doing, but I have to read some literature and articles in dynamic systems and complexity theory. What I noticed is that authors tend to use (quite frequently) the ...
5
votes
2answers
479 views

Completeness proof of $\ell^p$

Say $\{x_n\}$ is Cauchy in $\ell^p$ and $x$ is its pointwise limit. To argue that $x \in \ell^p$ would the following be correct: Let $\varepsilon > 0$ and let $N$ be s.t. $n,m > N$ ...
15
votes
2answers
1k views

Prove that the multiplicative groups $\mathbb{R} - \{0\}$ and $\mathbb{C} - \{0\}$ are not isomorphic.

Is my proof correct? I have made use of the fact isomorphism preserves order of elements, which I proved couple of exercises back. I am also interested in other ways of proving it. Is there a more ...
11
votes
3answers
5k views

Why is it that when proving trig identities, one must work both sides independently?

Suppose that you have to prove the trig identity: $$\frac{\sin\theta - \sin^3\theta}{\cos^2\theta}=\sin\theta$$ I have always been told that I should manipulate the left and right sides of the ...