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

13
votes
5answers
763 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}$?
2
votes
4answers
304 views

Prove that $\log_9 15$ is irrational

Im having trouble with the following proof... Ill post what I have completed so far.. Prove that $\log_915$ is irrational. Ill attempt by contradiction assuming $\log_915$ is rational. So, ...
-2
votes
0answers
30 views

How to prove that you cannot solve for x

I want to prove that $x$ cannot be solved for (besides the zero solution) in the equation $x^2=\sin(x)$.
1
vote
3answers
52 views

How am I to interpret this result?

Prove of give counter example: Let A and B be sets. $$ A \backslash ( A \backslash B) = B \backslash ( B \backslash A) $$ An attempt at a proof: If $ x \in A \backslash ( A \backslash B)$ then $x ...
5
votes
4answers
1k views

On a topological proof of the infinitude of prime numbers.

There is a proof of the infiniteness of prime numbers using Topology. I was only informed of the existence of this proof. They say it's very elegant. One could show how this proof?
5
votes
1answer
262 views

Conjectured compositeness tests for $N=k\cdot 2^n \pm 1$ and $N=k\cdot 2^n \pm 3$

How to prove these conjectures ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ~\text{are ...
2
votes
2answers
39 views

$\{a_n\} \to a$ iff $\limsup_{n \to \infty} \{a_n\} = \liminf_{n \to \infty} \{a_n\}$

It is clear that if $$\limsup_{n \to \infty} \{a_n\} = \liminf_{\to \infty} \{a_n\},$$ then $\{a_n\} \to a$, since we can just squeeze the terms in the middle. I understand that to prove the ...
1
vote
5answers
219 views

Proof by induction for “sum-of”

Prove that for all $n \ge 1$: $$\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$$ What I have done currently: Proved that theorem holds for the base case where n=1. Then: Assume that $P(n)$ is ...
3
votes
1answer
46 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
-1
votes
1answer
25 views

Use induction to prove that n! ≥ 2^(n−1) for for all integers n ≥ 1. [on hold]

Use induction to prove that n! ≥ 2^(n-1) for for all integers n ≥ 1. Hello everyone, I'm stuck on this problem right here $(k+1)! = 2^{(k+1)-1}$
3
votes
3answers
34 views

Help with partitions, equivalence classes, equivalence relations.

The following definitions and results are from my textbook. A partition $\mathcal{P}$ of a set $X$ is a collection of nonempty sets $X_1, X_2, \dots$ such that $X_1 \cap X_j = \emptyset$ for $i ...
1
vote
0answers
34 views

Possible proof strategy for Sendov conjecture?

Sendov's conjecture says that if all roots of a polynomial lie within the unit disk, then for every root, there exists a critical point at a distance at most one from the root. I read that Sendov ...
9
votes
4answers
18k 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 :)
3
votes
1answer
23 views

All closed rational rays measurable implies $f$ measurable

Is the following proof correct? Let $f: X \to \mathbb{R}$ where $X$ is a measurable space. Suppose $\{x: f(x) \geq r\}$ is measurable for each $r \in \mathbb{Q}$. Then, $f$ is measurable. Proof: ...
1
vote
0answers
26 views

Proving the Leibniz Rule for Lie Derivatives of tensor fields.

I am learning some Differential Geometry on my own in preparation for a course I'm starting in October, and one of the exercises in the notes I'm using is to check that the Lie Derivative satisfies ...
3
votes
3answers
46 views

Proving $[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R$ is a tautology without using a truth table?

$$[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R\tag{1}$$ How can I prove that $(1)$ is a tautology without using a truth table? I used the identity $$(P\to R)\land(Q\to R)\equiv(P\lor Q)\to R$$ but ...
0
votes
1answer
48 views

Proof for linearity on tensor products

Theorem: Let $U$ and $V$ be vector spaces. Let $\mathbf{u}^* \in U^*$. Define $\mathbf{f} : U \otimes V \to V$: $$\mathbf{f}\left(\sum_{r} \mathbf{u}_r \otimes \mathbf{v}_r\right) = \sum_{r} ...
25
votes
7answers
1k views

We all use mathematical induction to prove results, but is there a proof of mathematical induction itself?

I just realized something interesting. At schools and universities you get taught mathematical induction. Usually you jump right into using it to prove something like $$1+2+3+\cdots+n = ...
3
votes
1answer
220 views

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
6answers
130 views

Prove the existence of the square root of $2$.

I am trying to prove the existence of the square root of $2$. I have some steps with a very vague explanation and I would like to clarify. The proof: Let $$S=\{x\in\mathbb R\mid x\geqslant 0 \text{ ...
2
votes
3answers
848 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 ...
0
votes
0answers
21 views

Property of nth root

I'm trying to prove the following result: "Let $x,y \geq 0$ be non-negative reals, an let $n,m \geq 1$ be positive integers. If $y=x^{1/n}$ then $y^n=x$." $x^{1/n}:=sup \{y \in \mathbb{R}: y \geq 0, ...
1
vote
1answer
19 views

Every collection of periodic sets $A_n \subset \Bbb{N}$ (minus a common point), that avoids…

Let $\{A_n\}$ be a set of subsets of $\Bbb{N}$ each of which are periodic except for a common point. That is to say, there exists one and only one $x_0$, such that for each $n$, if $x \in A_n, x \neq ...
0
votes
0answers
14 views

Proof of optimal substructure for the “plus sign game”

First of all, I think there's no "plus sign game", I have just invented the name to describe the problem faster. Another thing: I thought to ask the question in these stack exchange's website because ...
7
votes
3answers
225 views

Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

How to prove that these conjectures are true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ...
1
vote
1answer
31 views

Deriving the inverse Fourier transform without knowledge of the form it will take

I've run by several proofs of the Fourier inversion theorem. However, every proof I have come across starts by assuming the form that the inverse transform will take. For example, Ron Gordon's ...
1
vote
1answer
30 views

Validity of my proof by contradiction of converse of Pythagorean Theorem.

So in, $\triangle ABC$ it is given that $AB^2=AC^2+BC^2$. Let us assume that $\angle C\neq{90}^{\circ}$. And let us make a perpendicular $AD$ to $BC$. Now, by the Pythagorean Theorem, in $\triangle ...
0
votes
1answer
42 views

Let $A, B$ and $X$ be sets. Prove that if $A ∪ B ⊆ X$ then $A ⊆ X$.

I have just started learning set theory and I've been trying to learn how to do proofs, however I really can't figure out I've been trying to answer a simple one: Let $A, B$ and $X$ be sets. Prove ...
30
votes
12answers
747 views

What are the theorems in mathematics which can be proved using completely different ideas?

I would like to know about theorems which can give different proofs using completely different techniques. Motivation: When I read from the book Proof from the Book, I saw there were many ...
4
votes
1answer
38 views

How to formulate the requirements that a counterexample must satisfy?

Let $p_1, p_2$ and $p_3$ be three statements. Suppose now we know that if $p_1$ is true, then $p_2$ and $p_3$ are equivalent. That is, if $p_1$ and $p_2$ are true, then $p_3$ is true, and if $p_1$ ...
0
votes
1answer
11 views

Which Function is Big-O of the Other

Given $f(n)=nlog(n)$ and $g(n)=10^{-6}n^2$, I am asked to find whether $f\in O(g)$ or $g \in O(f)$. The book claims that $f \in O(g)$, but I do not see how that is true. If it is true, there exists ...
1
vote
1answer
21 views

Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one.

Let $X,Y$ be nonempty sets and $f:X\to Y$ be a function. Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one. My approach is by ...
3
votes
3answers
68 views

If a set is countable and infinite, there is a bijection between the set and $\mathbb{N}$

I'm trying to show that if a set $S$ is infinite and countable then there is a bijection $\varphi : S\to \mathbb{N}$. Since $S$ is countable, we know that there is an injection $f: S\to \mathbb{N}$. ...
4
votes
1answer
23 views

Basic question on equivalence relations.

Show that the following relation is an equivalence relation on the given set. $m \sim n$ in $\mathbb{Z}$ if $m \equiv n\,(\text{mod}\,6)$.
2
votes
2answers
39 views

Prove function space is linearly independent.

Let $V$ the space of all funcions $f:Ŗ\rightarrow R$. Prove that the ten functions defined by $x\rightarrow |x-1|$,$x\rightarrow |x-2|$,....,$x\rightarrow |x-10|$ are linearly independent. I need ...
28
votes
6answers
2k views

When has one sufficiently mastered an area of mathematics?

This is a rather soft question regarding the mastery of various mathematical subjects, such as undergraduate subjects. In particular, say, when has one mastered undergraduate analysis? Is it ...
0
votes
2answers
73 views

Proving the Ideal Generated by the Coefficients of $f(X)\cdot g(X)\in R[X]$ is $R$.

Let $R$ be a commutative ring with unity, and let $f(X),g(X)\in R[X]$. Assume the ideals generated by the coefficients of $f(X),g(X)$ are both $R$. Prove that the ideal generated by the ...
1
vote
0answers
22 views

Showing polynomials as products of roots

How do I show rigorously that any polynomial $a_nx^n+a_{n-1}x^{n-1}+...a_1x+a_0$ can be written as $a_n(x-b_1)(x-b_2)...(x-b_n)$ for real $a_i$ and real or complex $b_i$
2
votes
1answer
117 views

Polynomial tending to infinity

Take any polynomial $(x-a_1)(x-a_2)\ldots(x-a_n)$ with roots $a_1, a_2,\ldots,a_n$ where we order them so that $a_{i+1}>a_i$ is increasing so $a_n$ is the biggest root. It doesn't matter whether ...
1
vote
1answer
73 views

Is this a valid proof of this math challenge problem?

From a fixed point P not in a given plane, three mutually perpendicular line segments are drawn terminating in the plane. Let a, b, c denote the lengths of the three segments. Show that ...
0
votes
1answer
584 views

Equivalent systems of Linear equation

I've just begun to re-learn linear algebra because is so important, the book that I chose is naturally the Hoffman's for a lot of reason. Well, In the first chapter I'm stuck with the following, ...
0
votes
1answer
33 views

Straight line through $(a,b)$ with slope $m$ is the graph of the function $f(x) = m(x-a) + b$

Spivak's Calculus Chapter 3 Problem 6 says: Show that the straight line through $(a,b)$ with slope $m$ is the graph of the function $f(x) = m(x-a) + b$. Since the slope in a graph of a line is ...
0
votes
2answers
46 views

Weird question about natural numbers. Obvious or not?

Given any subset $A,C \subset \Bbb{N}$, there exists a maximal subset $B \subset \Bbb{N}$ such that for all $b \in B, a \in A, \ |b - a| \in C$. For instance $A = \{3,5\}$, $C = \{2,4\}$, then ...
1
vote
3answers
112 views

how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+1})$

we can say that if all $i$ s in the sum were equal to $n$ then the answer to the summation would be $n\cdot n^k$. So $n^{k+1}$ is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$ For ...
3
votes
4answers
120 views

Proving $\frac{n^n}{3^n} < n!$ for $n\ge6$ by induction

How would I prove this using mathematical induction: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$. Here is what I have tried: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$ Base case: ...
4
votes
0answers
120 views

Infinite Chain of Implication Statements - Can it have a Conclusion?

First, does an infinite string of implication statements have a conclusion? If so, is there a such thing as a "closure" of such a beast, giving a conclusion? I am also trying to determine if the ...
12
votes
0answers
280 views
+100

Cauchy induction: are there examples of cases where choosing an integer other than $2$ is a better strategy?

Cauchy induction, sometimes called backwards induction, works as follows: show that $p(1)$ is true show that $p(n)$ implies $p(2n)$ (which inductively implies $p(2^n)$ is true) show that $p(n)$ ...
0
votes
1answer
30 views

Show that (c,a)=(c,b)

In my book I have the implication: If $gcd(a,b)=1$ and $c|(a+b)$, then $gcd(c,a)=gcd(c,b)=1$. It gives me a hint that begins by supposing that $gcd(a,c)=gcd(b,c)=d$. But in my opinion, I do not ...
1
vote
2answers
38 views

Prove that $B = \bigcup\{A_\alpha \mid \alpha \in[1,2]\}$

I am working this question: Set $B = \{(x, y)\mid 1 \le x^2 + y^2 \le 4\}$, $A_\alpha = \{(x, y)\mid x^2 + y^2 = α^2\}$. Prove that $\bigcup\{A_\alpha\mid \alpha \in [1, 2]\} = B$. because this ...
1
vote
1answer
33 views

Find all primes $p$ for which $x^2+2x+4\equiv 0 \pmod p$ is solvable. Am I correct?

Getting ready for an exam, I would like to focus on the correctness of my solution, final results and assumptions, and would appreciate any comment regarding it or even additional ...