The proof-strategy tag has no wiki summary.
22
votes
15answers
3k 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 ...
33
votes
1answer
1k 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 ...
14
votes
7answers
915 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 ...
5
votes
2answers
647 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 ...
40
votes
13answers
2k 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 ...
4
votes
5answers
677 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 ...
33
votes
5answers
3k 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 ...
39
votes
1answer
1k 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 ...
8
votes
7answers
796 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
166 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 - ...
2
votes
5answers
123 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:
$$
...
8
votes
3answers
511 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 ...
11
votes
8answers
992 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
646 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 ...
16
votes
5answers
990 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 ...
38
votes
4answers
2k 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!
14
votes
4answers
756 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
1k 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 ...
25
votes
7answers
926 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 ...
10
votes
10answers
1k 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
...
23
votes
4answers
2k 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.
9
votes
3answers
761 views
$\frac {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 ...
4
votes
4answers
145 views
Proving the stabilizer is a subgroup of the group to prove the Orbit-Stabiliser theorem
I have to prove the OS theorem. The OS theorem states that for some group $G$, acting on some set $X$, we get
$$
|G| = |\mathrm{Orb}(x)| \cdot |G_x| $$
To prove this, I said that this can be written ...
3
votes
4answers
146 views
Quantifies, predicates, logical equivalence
I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent. I dont think they are but how will I prove it. Am I supposed to use either ...
1
vote
2answers
64 views
Catalan number interpretation
I have a $2 \times n$ chessboard where numbers are increasing from left to right and top to bottom. I want to show that the number of arrangements is the $nth$ catalan number.
for example one such ...
8
votes
2answers
170 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)$, ...
6
votes
4answers
436 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 ...
4
votes
2answers
152 views
Short proof for the non-Hamiltonicity of the Petersen Graph
It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either.
Is there a simple (short) argument that the ...
4
votes
5answers
637 views
If $a|b$ and $c|d$, then $ac|bd$
I just need to check the reasoning in my proof is correct, I think it is valid although I'm not totally convinced because I can't follow the logic; does proving that $x$ is an integer prove that ...
2
votes
3answers
212 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 - ...
2
votes
3answers
476 views
Prove algorithm correctness
I'm wondering if there exists any rule/scheme of proceeding with proving algorithm correctness? For example we have a function $F$ defined on the natural numbers and defined below:
...
1
vote
3answers
181 views
Cauchy Sequence. What is this question actually telling me?
So basically I am told that the sum of the difference isn't infinite. I know that to show the sequence is Cauchy, the difference between the sums must be very small ($\epsilon$). So what exactly do ...
1
vote
3answers
183 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 ...
0
votes
2answers
112 views
What are common methods/techniques can be used to prove that limit of an infinite sequence exists?
I would like to know what are common methods can be used to show that an infinite sequence converges. From what I know so far,
If a sequence is bounded and monotonic increasing/decreasing then it ...
21
votes
2answers
1k 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 ...
24
votes
2answers
829 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 proofs by ...
14
votes
8answers
970 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
3answers
609 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 ...
4
votes
1answer
87 views
Combinatorial reasoning for linear binomial identity
I have the following equation:
\begin{equation}
m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}
\end{equation}
I iteratively took $m=1$ to $m=4$ to solve for the coefficients. I got ...
3
votes
2answers
887 views
Strong Induction proofs done with Weak Induction
I've been told that strong induction and weak induction are equivalent. However, in all of the proofs I've seen, I've only seen the proof done with the easier method in that case. I've never seen a ...
1
vote
1answer
143 views
Infinitely many primes of the $\sum_{i=0}^{a} n^{i}+m\cdot\sum_{i=0}^{b} n^{i}$ form?
How to show that there is infinitely many prime numbers of the form:
$p=\sum_{i=0}^{a} n^{i}+m\cdot\sum_{i=0}^{b} n^{i}$
where: $m\in \mathbb{Z}^{*}$ , $a,b,n\in \mathbb{N}$ , $\gcd(a+1,b+1)=1$
For ...
10
votes
4answers
1k views
Proof by contradiction: $r - \frac{1}{r} =5\Longrightarrow r$ is irrational?
Prove that any positive real number $r$ satisfying:
$r - \frac{1}{r} = 5$ must be irrational.
Using the contradiction that the equation must be rational, we set $r= a/b$, where a,b are positive ...
6
votes
2answers
488 views
Mathematical Telescoping
Bill Dubuque has answered several questions by indicating that some form of "telescoping" is taking place. See this post and the links provided by Bill for more information.
I have never heard of ...
4
votes
2answers
256 views
Induction without integers (aka Structural Induction)
While composing the following question, I had an "ah-ha" moment. I still want to post the question along with my answer to show what I have learned. Any comments or additional answers will be greatly ...
3
votes
2answers
980 views
Proof of $\gcd(a,b)=ax+by$
Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs?
$a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
3
votes
2answers
181 views
Did I underestimate the limit proof?
This is the problem:
Prove that if $a_n \le b_n$ for $n \ge 1, L = \lim_{n \to \infty} a_n$
and $M = \lim_{n \to \infty} b_n$, then $L \le M$
EDIT: Progress
Proof
Assume $L >M$ ...
3
votes
1answer
338 views
Improve my proof about this $C^\infty$ function
Here's the problem (from little Spivak):
Define $f:\mathbb{R}\rightarrow\mathbb{R}$ by
$$f(x)=\begin{cases}
e^{-x^{-2}} & x\ne 0 \\
0 & x=0
\end{cases}$$
Show that $f$ is a $C^\infty$ ...
2
votes
4answers
208 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 ...
1
vote
2answers
62 views
Prove the following ceiling and floor identities?
Could someone help me prove these identities? I'm completely lost:
$$\begin{align*}
&(1)\quad \left\lceil \frac{\left\lceil \frac{x}{a} \right\rceil} {b}\right\rceil = \left\lceil ...
7
votes
5answers
443 views
Constructive proof of boundedness of continuous functions
Consider the theorem for the continuous function:
Let $a<b$ be real numbers, and let $f:[a,b]\to{\bf R}$ be a function continuous on $[a,b]$. Then $f$ is a bounded function.
The proof in the ...
