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

1
vote
2answers
57 views

Help with a proof I can't quite

Let $(F_j)^\infty_{j=1}$ be the sequence of Fibonacci numbers. For all $n \in \mathbb{N}$, $\sum\limits_{k=1}^{2n-1}F_kF_{k+1}=(F_{2n})^2$. I handled the base case quite well but couldn't go very ...
0
votes
2answers
29 views

Using Direct Proof Technique prove that x*y is odd

I need help proving this statement. I'm studying for my final and I can't figure out how to finish it. P(x,y): If x and y are odd integers, then the product of x*d must also be odd. I know that $ x ...
3
votes
2answers
88 views

Law of excluded middle. Do we need it in proofs?

Quite often when I am making a natural deduction proof, and I have no fixed idea on how to continue. I find myself thinking: "lets start with some form of the law of the excluded middle (LEM) and ...
4
votes
5answers
191 views

Non-inductive, not combinatorial proof of $\sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

I've seen the identity $\displaystyle \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$ used here recently. I checked for proofs here ...
0
votes
2answers
45 views

Using Euclid's Algorithm prove..

Using Euclid's Algorithm prove that the fraction $\frac{24n+5}{18n+4}$ is in lowest terms. Is this solution going to be correct as a proof? Thanks for help!
0
votes
1answer
37 views

Question about the Least squares method

We have $n$ dots: $(x_1,y_1)\cdots (x_n,y_n)$. We know that if we use the Least squares method we will get a line $y=mx+b$ that giving the minimal value for the function $w=\sum_{i=1}^n ...
0
votes
0answers
13 views

Proof of update rule for perceptrons

$$w = \sum_n \tau^n\phi^nt^n$$ $$t^n = -1\text{ or }+1.$$ $\phi^n$ is a vector. $\tau^n$ is the number of times each vector $\phi^n$ has been presented and misclassified. It can be shown that ...
0
votes
1answer
28 views

Euler's Formula v-e+f=2

Assuming G is a planar graph with k components, I need to determine an equation relating vertices, edges, faces and components. It is given that when k=1, v-e+f=2. So from this I have gotten: ...
6
votes
2answers
216 views

Proof of continuity - (ε-δ) definition - Can anyone check this?

I've been trying to get my head around this problem for quite some time by now. I want to prove that $$f(x) := \left|\frac{x-1}{x^2+1}\right|$$ is continuous for $$x_0 = -1$$ Now, in order to prove ...
2
votes
1answer
17 views

Need help proving that $ fRg \Leftrightarrow fg = f $ on $ B^{n} $ to $ B $ if and only if $ f(b_1,…,b_n) \leq g(b_1,…,b_n) $

I'm trying to gather my thoughts for proving the following claim: For $ fRg \Leftrightarrow fg = f$ on $B^{n}$ to $B$, show that $ fRg $ if and only if for any input values $ b_1,...,b_n $, we ...
1
vote
1answer
32 views

Proof: If $F^3 = F$ then F is diagonalisable

let $V$ be a $\mathbb{R}$-vectorspace with $dim V < \infty$ and $F$ an endomorphism of V with $F^3 = F$. Show: F is diagonalisable. $F^3 = F$ is equivalent to $F^3 - F = 0$. Now I know that ...
0
votes
0answers
39 views

Mathematical logic and proofs involving absolute values

Is the following proof correct? Let ($\forall$ x, y $\in $$\Bbb R)$ $|x-y| \le |x| +|y|$ case#1: Suppose x and y $\ge0$. We want to show that $|x-y| \le |x| + |y|$. Since $|x|\ge x$ and $|y|\ge y$, ...
1
vote
2answers
24 views

Heuristics for Lipschitz equivalence

I'm studying for my finals in general topology and when I look at the definition of the Lipschitz equivalence of two metrics as: Let $d(x,y)$ and $d'(x,y)$ be metrics on a non-empty set $X$. We ...
1
vote
1answer
32 views

Inductive step assumption for all numbers up to $n$

I know that the inductive step should be "for all $n$ (if $P(n)$ then $P(n+1)$)" and NOT "if (for all $n$ $(P(n)$)) then (for all $n$ ($P(n+1)$))" - see this answer. But can it be like "if (for all ...
0
votes
1answer
33 views

Are these proofs correct?

I haven't formally learn how to do proofs, but I attempted some of these. It'd be great if you guys can check them and give me some pointers. Thanks!
1
vote
2answers
60 views

Ground Plan - Prove Fermat-Euclid's Totient Theorem with Lagrange's Theorem

If $\gcd(a,n) = 1$, then $a^{\phi(n)}\equiv 1\pmod n$. Here's a three-step proof. An integer a is invertible means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \pmod n$. By cause of Jones p84 ...
4
votes
2answers
164 views

Fermat's Little Theorem fails for composite instead of prime numbers.

I know Fermat's Little Theorem = Fermat-Euler's Totient Theorem when $n$ is prime. Elementary Number Theory, Jones, p83 writes if we simply replace p with a composite integer n, then the ...
2
votes
1answer
59 views

Backward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

(1) How can you preconceive to prove by contradiction? Prove by contradiction. Suppose $n$ is composite. This means there exists a divisor $d|n$ such that $1<d<n$. We are given that ...
1
vote
3answers
34 views

Question about the non-hausdorffness of the cofinite topology

I'm reading a proof about that disproves that the cofinite set $$O_c= \{\emptyset,X\}\cup\{S\subset X|\quad X-S\quad \text{is finite }\}$$ is hausdorff. It goes as follows : Let $U,V \subset X$ ...
1
vote
2answers
38 views

Ground Plan – Forward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p) $.

Lemma 5.3 - I omit proof here - Let p be prime. Then $x^2 \equiv 1 \, (mod p) \iff x \equiv \pm 1 \; (mod p)$ First we establish the result for the first two primes 2, 3. Then prove the result for ...
3
votes
1answer
87 views

Ground plan of Forward direction - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Prove by contradiction. Thence suppose NOT $p\equiv 1 \; (mod 4)$. Thence 3 possibilities remain: $4|p, 4|(p - 2), 4|(p - 3)$. But $p > 2$ is prime, thence $4 \not | p$. (1) How can you ...
0
votes
1answer
18 views

Help proving a theorem in my textbook

If $r \in \mathbb{N}$ is not a perfect square, then $\sqrt{r}$ is irrational. For reference, an integer $n$ is a perfect square if $n=m^2$ for some $m \in \mathbb{Z}$. Any help proving this ...
2
votes
2answers
45 views

Help with a proof my professor gave my class

Let $x,y \in \mathbb{R}$ with $x<y$. There exists an irrational number $z$ such that $x<z<y$. My proof so far: Let $x,y \in \mathbb{R}$ and assume $x<y$. Then, by Theorem 11.8 (in ...
3
votes
1answer
169 views

Ground plan of Backward direction (<=) - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

Apply the identity $p-i \equiv -i \mod p$ for $i=1, \ldots$ to the pink factors $ \begin{align} \color{seagreen}{ (p-1)! } = 1\times 2\times\cdots\times \dfrac{p-1}{2} & \times \quad ...
5
votes
2answers
209 views

$\binom{n}{k}\binom{n}{n - k}$ vs $\binom{n}{k}$ - Differences? Similarities?

So the # of ways to choose an $n$ set with $k$ kiwis is $\binom{n}{k}\binom{n}{n - k} = \binom{n}{k}^2$. AlexR wrote No, picking exactly $k$ kiwis means you discount the $n-k$ remaining ...
12
votes
3answers
1k views

Show that the product of two consecutive natural numbers is never a square.

I'd like to have my proof verified and if possible, to see other solutions that are interesting. Proof: Suppose $n(n+1)$ is a square. Then we write $$n(n+1) = \prod_{p} p^{c(p)}$$ where $c(p) = a(p) ...
0
votes
0answers
22 views

Defining a not surjective function to be surjective

The question asks us to define functions $f$ and $g$ from integers to integers such that $f$ is not subjective and yet $g ∘ f$ is surjective. I tried to do a piece-wise function $x+5$ where $x>= ...
0
votes
2answers
24 views

Taking the compositions of two constant functions

The questions asks to prove that the composition of g with f is not equal to f with g. However, I don't know whether you can even take the composition of constant functions or how. so if f(x)=2 and ...
0
votes
1answer
11 views

Let Cn be the largest possible number of intersection points of a family of $n$ lines in the plane. Prove that $Cn = n(n-1)/2$

(If some lines are parallel, or if three lines intersect at a single point, then the number of intersection points could be less than $Cn$.) Question for proofs homework, which will be on the ...
0
votes
1answer
17 views

Proving equivalence relation

Suppose a function f : A → B is given. Define a relation ∼ on A as follows: $a_1 ∼ a_2 ⇐⇒ f(a_1 ) = f(a_2 )$ (a) Prove that ∼ is an equivalence relation on A. I know that in order to prove this I ...
0
votes
1answer
35 views

Under what conditions on $a,b$ is $1/(a+bi)=(1/a)+(i/b)$?

Question in proofs review in the complex numbers unit. I expressed $1/(a+bi) = (a-bi)/(a^2+b^2)$ I then separated the two terms in the denominator to get $a/(a^2+b^2)-bi/(a^2+b^2)$ I then equated ...
0
votes
3answers
46 views

Define a relation on $Z$ by a~b if and only if $a=b(mod2)$ and $a=b(mod5)$. Show that ~ is an equivalence relation.

The if and only if is throwing me off. Would the first direction be to prove the two modular conditions hold if the relation is an equivalence relation? Furthermore, I'm having difficulty proving ...
0
votes
2answers
28 views

Let A, B and C be sets. Prove that $A \cap (B-C) = (A \cap B) - (A \cap C)$

Someone please edit so the & symbol is the intersect (reverse of U). This is a recent question on proofs homework. From what I understand, intersect and minus symbols used in equations for sets ...
3
votes
4answers
56 views

Solve $85x \equiv 34 \pmod{153}$

I'm not exactly sure how to solve these modular problems involving a variable. Can someone solve this (trivial) example with explanation? I found the answer (4) by trial and error, however, I'm sure ...
5
votes
3answers
114 views

Is there a simple way to illustrate that Fermat's Last Theorem is plausible?

A first step in proving a theorem is true could be to show that it is plausible, so at least you then would have a general idea that it could be true and have something to start with in proving it. ...
2
votes
3answers
124 views

Prove the distributive law $a(b+c)=ab+ac$ for real numbers?

I have always taken these kinds of things for granted. Well of course $a(b+c)=ab+ac$! But why? The thought randomly popped in my head, and I realized that I could not prove it. Perhaps we should take ...
0
votes
1answer
56 views

Prove that weak convergence does not necessarily imply strong convergence without counterexample.

Here is the set of original problems. Let $\{x_n\}$ be a sequence in a normed linear space $X$. Prove that: Strong convergence implies weak convergence with the same limit. The converse ...
1
vote
2answers
34 views

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = hcf(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

Proofs homework question. We know that if $a|c$ and $b|c$ then $a\cdot b\cdot s=c$ (for some positive integer $s$). $(ab|c)$ Then doesn't $ab|dc$ since $ab|c$? I feel like I'm misunderstanding my ...
0
votes
1answer
17 views

Let $a$ and $b$ be coprime positive integers. Prove that, for any integer $n$, there exist integers $s$ and $t$ such that $sa + tb = n$

I always sort of took this fact for (well..) fact. Can someone help me with the proof? Does this question have something to do with modulus? Since $a$ and $b$ are coprime ($gcd$ = 1), multiplying ...
4
votes
2answers
81 views

Prove that if $a$ is a rational number and $a^2$ is an integer then $a$ is an integer.

Question on a proof's review: Proof by contradiction: Suppose $a$ is not an integer. Then $a=p/q$ where $p$ and $q$ are coprime, $q$ is not 0, and $q$ is not 1. Then $a^2 = p^2/q^2$. This is ...
1
vote
3answers
62 views

Help: Proof via Induction homework problem.

(b) Prove that for every integer $n \ge 1$, $$1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$$ This is the second part of a two part question. Part (a) was the following: ...
0
votes
3answers
57 views

Help with 2 questions my professor gave us

I was wondering how to solve these two proofs my professor put on the blackboard today. He said they were pretty easy but i'm still unsure how to prove them. ANy help would be greatly appreciated! ...
4
votes
2answers
58 views

Which Cross Product for the Desired Orientation of a Hyperboloid ? [Stewart P1103 16.9.8]

P1103 16.9.$8.$ Evaluate the surface integral $\iint_S \mathbf{F} \cdot d\mathbf{S}$. $\mathbf{F} = (x^3y,-x^2y^2,-x^2yz)$ and $S$ is the surface of the solid bounded by the hyperboloid $x^2 + ...
3
votes
4answers
56 views

Proof of $e^x - 1 \geq x$ for ${x: -1 \leq x < 0}$ [duplicate]

Is this valid, and how can i prove that it holds. Proof of $$e^x - 1 \geq x \text{ for } {x:-1 \leq x < 0}$$
2
votes
2answers
71 views

Proving that repeating decimals can be rewritten as fractions without using infinite series

I'm being asked to prove that all repeating decimals can be written as fractions. The catch is that I'm not allowed to use infinite series, so that excludes most if not all methods I've seen so far. ...
2
votes
2answers
29 views

Two sequences are equivalent. Prove that one is Cauchy iff the other is Cauchy.

This question has already been asked and answered here Let $ϵ>0$ be given. With loss of generality, we may assume $ϵ$ is rational. Suppose $a_n$ is a Cauchy sequence and $b_n, a_n$ are ...
2
votes
0answers
46 views

Continuity of the right-hand derivative of a Convex function (help with the proof)

Hi everyone I have some trouble with one point in the following proof. Let $f$ be a convex function (strict convex function) on a real interval. If $f'_-(a)=f'_+(a)$ where $f'_-$ and $f'_+$ are ...
0
votes
0answers
43 views

ideals in rings

Let $M$ be the ideal generated by $x^2+2$ in the ring $\ \Bbb Z/3\ \ [x]$. What are the distinct congruence classes in $\ \Bbb Z/3\ \ [x]/I$, is I a prime ideal,a maximal ideal, and is $\ \Bbb Z/3\ \ ...
0
votes
2answers
56 views

Prove that for every integer $n \ge 1$, $1 + \frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+ … +\frac{1}{\sqrt{n}}\le 2\sqrt{n}$

I understand that this is an induction question. I start with the base case (n=1): $$1 < 2 \tag{That works!}$$ Induction step: Assume the statement works for all $n = k$, Prove for all $n = ...
-1
votes
1answer
44 views

Countability of Different Sets [duplicate]

(a) Prove that $N \times N$ is a countable set (b) Let T be the set of two element subsets of N. Prove that T is countable. This is a question in my exam review package. I missed the lesson on ...