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
7k 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 ...
58
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 ...
3
votes
3answers
453 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 - ...
17
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 ...
8
votes
2answers
951 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)$, ...
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.
45
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!
5
votes
5answers
922 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 ...
3
votes
3answers
300 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 ...
51
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 ...
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 ...
17
votes
2answers
345 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 - ...
4
votes
3answers
291 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
414 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 ...
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: $$ ...
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 ...
9
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. ...
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. ...
4
votes
3answers
485 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 ...
49
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 ...
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
931 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
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
107 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 ...
3
votes
2answers
159 views

Sum of Stirling numbers of both kinds

Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not. My task: Prove, ...
2
votes
2answers
183 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
646 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}$$ ...
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 :)
1
vote
1answer
62 views

Properties of GCD in rings

Let $R$ be subring of integral domain $S.$ Suppose $R$ is $\text{PID}.$ Let $a\in R$ be a greatest common divisor of $r_1,r_2$ in $R$. ($r_1,r_2 \in R$, not both zero). Could anyone advise me on how ...
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 ...
16
votes
2answers
392 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
759 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
219 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
318 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
609 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
183 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
329 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 ...
1
vote
8answers
112 views

How to derive this formula? $\displaystyle n^2=\sum_{k=1}^n(2k-1).$

Welcome sir in the content of my question. How to derive this formula? $$n^2=\sum_{k=1}^n(2k-1).$$ Thank you sir.
0
votes
1answer
260 views

Proving that $C$ is a subset of $f^{-1}[f(C)]$

More homework help. Given the function $f:A \to B$. Let $C$ be a subset of $A$ and let $D$ be a subset of $B$. Prove that: $C$ is a subset of $f^{-1}[f(C)]$ So I have to show that every element ...
35
votes
2answers
6k 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 ...
18
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
843 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 ...