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

learn more… | top users | synonyms

36
votes
11answers
6k views

How can you prove that the square root of two is irrational?

I have read a few proofs that $\sqrt{2}$ is irrational. I have never, however, been able to really grasp what they were talking about. Is there a simplified proof that $\sqrt{2}$ is irrational?
8
votes
5answers
742 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.)? ...
79
votes
4answers
12k 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?
6
votes
2answers
4k views

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

I'm having difficulty solving an exercise in my course. The question is: Prove that $n!\geq 2^n$. We have to do this by induction. I started like this: The lowest natural number where the ...
221
votes
15answers
10k 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 ...
67
votes
4answers
24k 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 ...
25
votes
7answers
9k 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 ...
10
votes
2answers
4k 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)$, ...
27
votes
2answers
4k 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?
4
votes
4answers
4k 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?
2
votes
4answers
6k 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: $$ \sum_{i=1}^...
5
votes
5answers
409 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 ...
11
votes
2answers
5k 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?
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 ...
6
votes
6answers
3k 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
599 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?
9
votes
2answers
3k 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 ...
7
votes
4answers
1k 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 ...
8
votes
3answers
167 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 ...
3
votes
2answers
582 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 $k<...
5
votes
3answers
1k 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 ...
1
vote
2answers
456 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 ...
19
votes
3answers
23k 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 \...
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
5answers
887 views

Fibonacci number identity.

How do I see that $f_{n+1}f_{n-1} = f_n^2 + (-1)^n$, $n \ge 2$, where $f_1 = 1$, $f_2 = 1$, and $f_{n+2} = f_{n+1} + f_n$ for $n \in \mathbb{N}$?
12
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 ...
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 ...
2
votes
3answers
2k 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}: f(...
3
votes
3answers
182 views

Prove $A = (A \setminus B) \cup (A \cap B)$

Prove $A = (A \setminus B) \cup (A \cap B)$ Logically, this is clearly true. I can explain why: start with $A$, remove all elements in $B$ and then add in any elements in both $A$ and $B$, which ...
2
votes
3answers
5k 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 ...
3
votes
2answers
785 views

how to prove $f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)$

I am given this equation: $f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)$ I want to prove it: what i did is I take any $a \in f^{-1}(B_1 \cap B_2)$, then there is $b \in (B_1 \cap B_2)$ so ...
10
votes
1answer
36k 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 ...
8
votes
3answers
196 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 attempt:...
2
votes
4answers
5k 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 $$\...
5
votes
4answers
716 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:$ $(n+1)²\...
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 ...
1
vote
7answers
948 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 P\...
0
votes
2answers
103 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: ...
2
votes
4answers
843 views

Show that for all real numbers $a$ and $b$, $\,\, ab \le (1/2)(a^2+b^2)$ [duplicate]

so as in the title, I have the following theorem to prove. Theorem Show that for all $a$, $b\in \mathbb R$, that the following inequality holds, $\begin{equation} ab \leq \frac{1}{2}(a^2 + b^2) \...
118
votes
9answers
8k 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 ...
78
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?
5
votes
2answers
551 views

How do I prove the completeness 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$ $\Rightarrow$...
16
votes
3answers
316 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) = 1^k+2^k+\dots+...
15
votes
3answers
1k views

Prove $\sqrt{a} + \sqrt{b} + \sqrt{c} \ge ab + bc + ca$

Let $a,b,c$ are non-negative numbers, such that $a+b+c = 3$. Prove that $\sqrt{a} + \sqrt{b} + \sqrt{c} \ge ab + bc + ca$ Here's my idea: $\sqrt{a} + \sqrt{b} + \sqrt{c} \ge ab + bc + ca$ $2(\...
7
votes
4answers
27k 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 +...
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 ...
12
votes
5answers
6k 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 ...
11
votes
1answer
603 views

Proof that $1729$ is the smallest taxicab number

For homework I have to produce the proof (algebraic or otherwise) to show that $1729$ HAS to be the smallest taxi cab number. A taxicab number means that it is the sum of two different cubes and can ...
8
votes
3answers
6k 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 prime....