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

37
votes
20answers
8k 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 ...
23
votes
12answers
6k 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 ...
47
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 ...
65
votes
1answer
4k 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 ...
3
votes
3answers
518 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 - ...
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 ...
17
votes
7answers
4k 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 ...
30
votes
4answers
6k 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.
8
votes
2answers
1k 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)$, ...
5
votes
5answers
991 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 ...
11
votes
10answers
4k 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 ...
11
votes
6answers
3k 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. ...
4
votes
4answers
390 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 ...
54
votes
7answers
9k 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 ...
46
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
6k 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!
3
votes
3answers
321 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 ...
49
votes
3answers
10k 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
364 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 - ...
3
votes
3answers
478 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
3k 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: $$ ...
6
votes
6answers
3k 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. ...
13
votes
8answers
4k 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) = ...
4
votes
2answers
183 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, ...
5
votes
3answers
295 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 ...
4
votes
3answers
656 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 ...
3
votes
9answers
191 views
51
votes
5answers
6k 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 ...
14
votes
5answers
3k views

$\epsilon$-$\delta$ proof that $\lim\limits_{x \to 1} \frac{1}{x} = 1$.

I'm starting Spivak's Calculus and finally decided to learn how to write epsilon-delta proofs. I have been working on chapter 5, number 3(ii). The problem, in essence, asks to prove that ...
8
votes
3answers
1k 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 ...
17
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. ...
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 ...
7
votes
2answers
805 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 ...
6
votes
3answers
111 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 ...
4
votes
4answers
686 views

Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$

Prove by Mathematical Induction . . . $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$ I tried solving it, but I got stuck near the end . . . a. Basis Step: $(1)(1!) = (1+1)!-1$ $1 = ...
2
votes
2answers
221 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
680 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
6k 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
94 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 ...
19
votes
10answers
3k views

Proving $\sqrt 3$ is irrational.

There is a very simple proof by means of divisibility 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 ...
6
votes
2answers
908 views

Nested Radical of Ramanujan

I think I have sort of a proof of the following nested radical expression due to Ramanujan for $x\ge 0$. $$\large x+1=\sqrt{1+x\sqrt{1+(x+1)\sqrt{1+(x+2)\sqrt{1+\cdots}}}}$$ for $ x\ge -1$ I ...
16
votes
2answers
409 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: ...
14
votes
7answers
5k 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), ...
3
votes
1answer
275 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
330 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
619 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
198 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
380 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 ...