# Tagged Questions

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.

8 views

### l’Hôpital’s rule to prove that $f \in \omega(g)$

Can anyone give me a hint on how to start this please? For $n \in R >1$ let $f(n) = n^{4/3}$ and $g(n) = n · (log$5$n)^2$. Use l’Hôpital’s rule to prove that $f \in \omega(g)$.
4 views

### Algorithm Proof - $(n!/(\lceil n/2\rceil) \in w(2^{n/2})$

I need to either proof or give a counter example to the followings: 1) $(n!/(\lceil n/2\rceil) \in w(2^{n/2})$ 2) if $g(n) \in Θ(f(n))$ then $f(n)^2 \in Θ(g(n)^2)$ 3) if $f(n) \in O(g(n))$ then ...
23 views

### How to prove prime power factorization is square free

The question is as follows: "Show every positive integer is the product of a square (possibly 1) and a square free integer" We begin by writing a positive integer n in its refined prime power ...
19 views

### Are there any other elegant but obscure techniques like forward-backward mathematical induction? M

I was just recently reading about Cauchy's proof of the AM-GM inequality by forward backward induction and was simply blown away by it's elegance. However, I have never seen forward backward induction ...
117 views

### How to show this cover of $\mathbb{Q}$ doesn't cover $\mathbb{R}$?

Let $\{q_n : n \in \mathbb{N}\}$ be an enumeration of $\mathbb{Q}$ and define $\mathcal{O} = \{I_n : n \in \mathbb{N}\}$ being $$I_n = \left(q_n - \frac{1}{2^n}, q_n + \frac{1}{2^n}\right).$$ It is ...
279 views

### How to explain to a layman why Fermat's Last Theorem involves non-trivial math?

Fermat's Last Theorem states, given$$x^n + y^n = z^n$$ no three integers $x,y,z$ will satisfy the equation given integer value of $n$ greater than two. On the surface this seems like something that ...
23 views

### If the set of all polynomials is infinite-dimensional, then why is the set of all functions on [a,b] also infinite-dimensional?

So it's known that the set of all polynomials is infinite-dimensional. However, if $U[a,b]$ is the set of all functions defined on [a,b], then how would I show that U[a,b] is also ...
23 views

22 views

### Proofs involving triangles and rectangles

The figure below represents a rectangle ACLK with an inscribed right triangle ABC. The lower case letters represent lengths of segments (ex. x=|KB|, etc. a.) prove that triangle ABC is similar to ...
29 views

### proof the triangle similarity

The figure below represents arbitrary triangle ABC. The points K,L,M are the midpoints of its sides. a) Show that triangle CLK ~ triangle CAB (and similarly for the other two corner triangles) How ...
24 views

### To prove that the mean of one number and its absolute value is less than the absolute value this number

We have $\frac{x+|x|}{2}$ is superior or equal to 0 but inferior or equal to $|x|$ where the x is part of the reals. I must prove this by the method of proof by case. I have no idea one how to begin ...
20 views

### Find a definition for n choose k and prove…

Find a definition for $\binom{n}{k}$ when n < 0. Use this to prove: $$\binom{-1/2}{n} = \frac{\binom{2n}{n}}{(-4)^n}$$ -Not sure how to approach this problem or what to use to prove it, with ...
9 views

### What is a simple example showing that local optimal requires $\nabla^2 F(x^*) > 0$ but not $\nabla^2 F(x^*) \geq 0$

Claim: Suppose $F(x) \in C^2$, then if $\nabla F(x^*) = 0, \nabla^2 F(x^*) > 0$ then $x^*$ is a local optima I am trying to look for a simple example showing that strict inequality must hold for ...
39 views

### Proof by Contradiction - How do I prove that something can't be both even and odd?

I am having some trouble with a homework problem. The problem says use "proof by contradiction" to explain why no integer can be both odd and even. So, far I think that I need to start with a ...
25 views

### How to show a natural number $p$ is prime

Suppose that a natural number $p > 1$ has the property that for all nonzero integers $a$ and $b$, if $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. Show that $p$ is prime. I can't seem ...
8 views

### Proving an equation using cartesian equation

I could really use some help with the following question: The point C has coordinates (a, 0), and the point D has coordinates (b, 0). The variable point Q moves on a path such that $QC=k \times QD$, ...
51 views

### Prove $5 \mid (3^{4n} - 1)$ by induction

I need to prove by induction that $5 \mid 3^{4n} - 1$ for $n \ge 1$. Base case is true, so now I have to prove that $5 \mid 3^{4(n+1)} - 1$. I did $$= 3^{4n+4} -1$$ $$= 3^{4n} 3^{4}-1$$ I guess I ...
31 views

### Show that XY is parallel to CD

AB is parallel to CD. CD is not a diameter. I want to show that $\triangle ZCD$ is similar to $\triangle ZXY$ but I don't know how to get there. The only thing I had in mind was using the arcs, but ...
431 views

### A simple way to obtain $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s}$

Let $p_1 <p_2 <\ldots <p_k <\ldots$ the increasing list in set $\mathbb{P}$ of all prime numbers . By sum of infinite geometric series $\sum_{k=0}^\infty r^k = \frac{1}{1-r}$ for ...
18 views

### Proving trig identity with Euler cosine/sine fomulae

I am attempting to prove: $\cos(a+b)=\cos(a)\cos(b)-\sin(a)\sin(b)$ using Euler's formula. I used the formulae for cosine and sine and got the following equality: ...
47 views

### Proofs: Induction on Handshakes

Here is the problem: Suppose $n$ people are at a party, and some number of them shake hands. At the end of the party, each guest $G_i$, $1 \leq i \leq n$ shares that they shook hands $x_i$ times. ...
105 views

### On the proof that if a set is open and arc-connected then it's connected by broken lines.

Let $(X,d)$ be a metric space, and $\gamma : [a,b] \rightarrow X$ be a continuous function then $\gamma([a,b])$ is called a continuous arc. I want to prove that if a set $C$ is open and arc-connected ...
56 views

### Can you use proof by contradiction inside simple induction?

During a proof using simple induction, I assumed P(k) is true. Now in order to show P(k+1) is true using P(k), can I do a proof by contradiction on P(k+1) and say P(k) would be wrong if P(k+1) is ...
60 views

### Proving $\sum_{i=1}^ni(i+1)=n(n+1)(n+2)/3$ for $n\geq 1$ by induction

I'm trying to prove this by induction: $$1*2 + 2*3 + 3*4 + \cdots + n(n+1) = (n(n+1)(n+2))/3.$$ I have done this so far: Base Case: $n = 1$, works for both. Induction Hypothesis: Let $n = k$, ...
24 views

### Number Theory: Complete set of residues modulo $n$

I have this problem assigned for homework and I'm struggling with the proof of it: If $a_1,a_2,\dotsc,a_n$ is a complete set of residues modulo $n$ and $\gcd(a,n)=1$, prove that ...
1k views

17 views

### Need Help In Proving Exact Power of Prime Divides Product Of Factorials

I am trying to solve the following question: Prove that if a and b are positive integers, p is prime, and a + b = 2p - 1 then p || a!b!. Where || means that no higher power of p will divide a!b!. ...
173 views

### Number Theory: Which numbers 101010…0101 are prime

I have this problem assigned for homework and I'm having some trouble with it. I'm in elementary number theory. Set $M(k)=100^{k-1}+\dotsc +100+1$. Note that $M(k)$ has exactly $k$ ones. For which ...