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

32
votes
20answers
6k views

Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?

I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$ I really ...
20
votes
9answers
3k views

Prove that $\lim \limits_{n \to \infty} \frac{x^n}{n!} = 0$, $x \in \Bbb R$.

Why is $$\lim_{n \to \infty} \frac{2^n}{n!}=0\text{ ?}$$ Can we generalize it to any exponent $x \in \Bbb R$? This is to say, is $$\lim_{n \to \infty} \frac{x^n}{n!}=0\text{ ?}$$ This is ...
44
votes
1answer
2k views

Is Lagrange's theorem the most basic result in finite group theory?

Motivated by this question, can one prove that the order of an element in a finite group divides the order of the group without using Lagrange's theorem? (Or, equivalently, that the order of the group ...
51
votes
1answer
3k views

How to determine with certainty that a function has no elementary antiderivative?

Given an expression such as $f(x) = x^x$, is it possible to provide a thorough and rigorous proof that there is no function $F(x)$ (expressible in terms of known algebraic and transcendental ...
11
votes
2answers
1k views

Proof of a formula involving Euler's totient function.

The third formula on the wikipedia page for the Totient function states that $$\varphi (mn) = \varphi (m) \varphi (n) \cdot \dfrac{d}{\varphi (d)} $$ where $d = \gcd(m,n)$. How is this claim ...
16
votes
7answers
3k 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 ...
3
votes
3answers
440 views

Finding the error in a proof

I have a "proof" that has an error in it and my goal is to figure out what this error is. The proof: If x = y, then $$ \begin{eqnarray} x^2 &=& xy \nonumber \\ x^2 - y^2 &=& xy - ...
30
votes
4answers
5k views

Prove that $i^i$ is a real number

According to WolframAlpha, $i^i=e^{-\pi/2}$ but I don't know how I can prove it.
44
votes
13answers
3k views

Pseudo Proofs that are intuitively reasonable

What are nice "proofs" of true facts that are not really rigorous but give the right answer and still make sense on some level? Personally, I consider them to be guilty pleasures. Here are examples ...
46
votes
7answers
5k views

Prove every odd integer is the difference of two squares

I know that I should use the definition of an odd integer ($2k+1$), but that's about it. Thanks in advance!
8
votes
2answers
898 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)$, ...
3
votes
3answers
294 views

Cauchy Sequence. What is this question actually telling me?

Let $(a_n)$ be a sequence such that $\lim\limits_{N\to\infty} \sum_{n=1}^n |a_n-a_{n+1}|<\infty$. Show that $(a_n)$ is Cauchy. So basically I am told that the sum of the difference isn't ...
44
votes
3answers
7k 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 ...
4
votes
3answers
287 views

Proving $f(C) \setminus f(D) \subseteq f(C \setminus D)$ and disproving equality

Let $f: A\longrightarrow B$ be a function. 1)Prove that for any two sets, $C,D\subseteq A$ , we have $f(C) \setminus f(D)\subseteq f(C\setminus D)$. 2)Give an example of a function $f$, and sets ...
3
votes
3answers
402 views

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

I need to prove that $z \cdot \text{gcd}(a,b)=\text{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 ...
49
votes
7answers
7k views

Lesser-known integration tricks

I am currently studying for the GRE math subject test, which heavily tests calculus. I've reviewed most of the basic calculus techniques (integration by parts, trig substitutions, etc.) I am now ...
16
votes
2answers
337 views

How can I prove my conjecture for the coefficients in $t(x)=\log(1+\exp(x)) $?

I'm considering the transfer-function $$ t(x) = \log(1 + \exp(x)) $$ and find the beginning of the power series (simply using Pari/GP) as $$ t(x) = \log(2) + 1/2 x + 1/8 x^2 – 1/192 x^4 + 1/2880 x^6 - ...
5
votes
6answers
2k views

Easiest and most complex proof of $\gcd (a,b) \times \operatorname{lcm} (a,b) =ab.$

I'm looking for an understandable proof of this theorem, and also a complex one involving beautiful math techniques such as analytic number theory, or something else. I hope you can help me on that. ...
5
votes
5answers
909 views

Show that $3p^2=q^2$ implies $3|p$ and $3|q$

This is a problem from "Introduction to Mathematics - Algebra and Number Systems" (specifically, exercise set 2 #9), which is one of my math texts. Please note that this isn't homework, but I would ...
4
votes
3answers
460 views

induction proof: $\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$

I encountered the following induction proof on a practice exam for calculus: $$\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$$ I have to prove this statement with induction. Can anyone please help me ...
2
votes
5answers
1k views

Proof via Induction for A Summation

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: $$ ...
48
votes
5answers
5k views

Getting better at proofs

So, I don't like proofs. To me building a proof feels like constructing a steel trap out of arguments to make true what you're trying to assert. Oftentimes the proof in the book is something that I ...
10
votes
7answers
3k views

What's the proof that the Euler totient function is multiplicative?

That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
16
votes
4answers
3k views

How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. ...
6
votes
3answers
106 views

What should I do if I don't know where to start?

Sometimes getting started on a problem seems to be the hardest part. Once you find something to sink your teeth into, everything goes smoothly. What are some good things to try when you're staring at ...
2
votes
2answers
181 views

What are the strategies I can use to prove $f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$?

$f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$ I think I have to show that the LHS is a subset of the RHS and the RHS is a subset of the LHS, but I don't know how to do this exactly.
14
votes
2answers
635 views

Where's the error in this $2=1$ fake proof? [duplicate]

I'm reading Spivak's Calculus: 2 What's wrong with the following "proof"? Let $x=y$. Then $$x^2=xy\tag{1}$$ $$x^2-y^2=xy-y^2\tag{2}$$ $$(x+y)(x-y)=y(x-y)\tag{3}$$ ...
30
votes
6answers
1k views

What is an efficient nesting of mathematical theorems?

Various mathematical areas of research evolved from a wide and diverse range of questions. Many are physical in nature or come from informatics/computer science, some are procedural or optimization ...
8
votes
3answers
913 views

Proof of a simple property of real, constant functions.

I recently came across the following theorem: $$ \forall x_1, x_2 \in \mathbb{R},\textrm{function, } f: \mathbb{R} \rightarrow \mathbb{R}, x \mapsto y; \ |f(x_1) - f(x_2)| \leq (x_1-x_2)^2 \implies ...
16
votes
2answers
391 views

Proving that $(b_n) \to b$ implies $\left(\frac{1}{b_n}\right) \to \frac{1}{b}$

In my textbook (S. Abbott. Understanding Analysis 1 ed. pp 47 Theorem 2.3.3.iv), the author proves $b_n \to b$ implies $\frac{1}{b_n} \to \frac{1}{b}$ the following way: ...
12
votes
8answers
3k views

How to prove that $\lim\limits_{n \to \infty} \frac{k^n}{n!} = 0$

It recently came to my mind, how to prove that the factorial grows faster than the exponential, or that the linear grows faster than the logarithmic, etc... I thought about writing: $$ a(n) = ...
7
votes
2answers
758 views

Prove that $\beta \rightarrow \neg \neg \beta$ is a theorem using standard axioms 1,2,3 and MP

I've proven that $\neg \neg \beta \rightarrow \beta$ is a theorem, but I can't figure out a way to do the same for $\beta \rightarrow \neg \neg \beta$. It seems the proof would use Axiom 2 and the ...
3
votes
1answer
207 views

line of mathematicians guess their own hat color out of c colors

There is a common problem in which a long line of N mathematicians are each given a hat that is either red or blue. They cannot see their own hat but can see all in front of time and can hear any ...
3
votes
4answers
315 views

Proving that there are infinite cardinal numbers >$\mathfrak{c}$

I was reading Simmons' book and he states that there are infinite cardinal numbers > $\mathfrak{c}$ where $\mathfrak{c}$ denotes the number of Real Numbers. For this, he states that we can construct ...
11
votes
3answers
1k views

Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$?

Is it true that : $\frac {n}{5} < \phi (n) < n$ for all $n > 1$ where $\phi (n)$ is Euler's totient function . Since $\phi(n)$ has maximum value when $n$ is a prime it follows that ...
7
votes
4answers
607 views

Explanation for why $1\neq 0$ is explicitly mentioned in Chapter 1 of Spivak's Calculus for properties of numbers.

During the first few pages of Spivak's Calculus (Third edition) in chapter 1 it mentions six properties about numbers. (P1) If $a,b,c$ are any numbers, then $a+(b+c)=(a+b)+c$ (P2) If $a$ is ...
5
votes
1answer
182 views

Equivalences of continuity, sequential convergence iff limit (S.A. pp 106 t4.2.3, 110 t4.3.2)

1. This post became too long, ergo I moved this here. 2. I questioned anew here. How does $\color{red}{(I) \implies (III)}$? This contradicts $a \le b \not \implies \Leftarrow a < b$. 3. ...
4
votes
3answers
319 views

How to prove floor identities?

I'm trying to prove rigorously the following: $\lfloor x/a/b \rfloor$ = $\lfloor \lfloor x/a \rfloor /b \rfloor$ for $a,b>1$ So far I haven't gotten far. It's enough to prove this instead ...
2
votes
3answers
2k views

Proof of triangle inequality

I understand intuitively that this is true, but I'm embarrassed to say I'm having a hard time constructing a rigorous proof that $|a+b| \leq |a|+|b|$. Any help would be appreciated :)
35
votes
2answers
5k views

What is the proper way to study (more advanced) math?

Here's what happens. I get stuck on some proof or some mathematical construction and I end up staring at the problem for hours, sometimes not making any progress. I do this because sometimes I think ...
16
votes
5answers
1k views

Prove that every number ending in a $3$ has a multiple which consists only of ones.

Prove that every number ending in a $3$ has a multiple which consists only of ones. Eg. $3$ has $111$, $13$ has $111111$. Also, is their any direct way (without repetitive multiplication and ...
17
votes
10answers
3k views

Proving $\sqrt 3$ is irrational.

There is a very simple proof by means of divisivility that $\sqrt 2$ is irrational. I have to prove that $\sqrt 3$ is irrational too, as a homework. I have done it as follows, ad absurdum: Suppose ...
14
votes
4answers
836 views

Is the proof of this lemma really necessary?

To prove the Cayley-Hamilton theorem in linear algebra, my professor said that a lemma was necessary: Lemma: Let $A \in M_n(\mathbb{K})$ be an $n\times n$ matrix over a field $\mathbb{K}$, let ...
13
votes
4answers
2k views

Proof by Contradiction, Circular Reasoning?

Suppose we wish to prove $P$ implies $Q$. We assume $P$. Proof by contradiction begins by assuming not $Q$, and from these two assumptions, a "contradiction" is derived. Now, sometimes that ...
27
votes
7answers
1k views

Must we use induction to prove a statement for all integers

This question is prompted by a remark from Bill Dubuque in his answer to this question on proving a particular sum without using mathematical induction. From Bill's answer: A proof that a ...
14
votes
6answers
419 views

When to use the contrapositive to prove a statment

My question tries to address the intuition or situations when using the contrapositive to prove a mathematical statement is an adequate attempt. Whenever we have a mathematical statement of the form ...
14
votes
8answers
3k views

Proof for exact differential equations shortcut?

Today in my math class, we learned about exact differential equations. During class, our teacher first taught us the accepted way to solve exact equations, but then, told us of a shortcut that one of ...
19
votes
3answers
1k views

When do I use “arbitrary” and/or “fixed” in a proof?

In many proofs I see that some variable is "fixed" and/or "arbitrary". Sometimes I see only one of them and I miss a clear guideline for it. Could somebody point me to a reliable source (best a ...
14
votes
7answers
4k views

Proof of $ f(x) = (e^x-1)/x = 1 \text{ as } x\to 0$ using epsilon-delta definition of a limit

I am in calc 1 and we have just learned the epsilon-delta definition of a limit and I (on my own) wanted to try and use this methodology in order to prove $(e^x-1)/x = 1$ (one of the equivalencies), ...
8
votes
6answers
2k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...