Questions tagged [elementary-proofs]
For questions related to 'elementary' proofs in a technical sense, which has nothing to do with the difficulty of the argument or result. A typical example would be 'elementary' proofs of the Prime Number Theorem, which avoid complex analysis. The tag is however not limited to this particular notion of 'elementary.'
209
questions
5
votes
1
answer
327
views
Conjectured primality test for specific class of $N=k \cdot 6^n+1$
Can you provide a proof or a counterexample for the claim given below?
Inspired by Theorem 5 in this paper I have formulated the following claim:
Let $N=k \cdot 6^n+1$ , $k<6^n$ and $\operatorname{...
3
votes
0
answers
336
views
How to prove there is infinite prime numbers of form $5n+3$ without Dirichlet theorem? [closed]
Is there a nice elementary way to prove there is infinite prime numbers of form $5n+3$ (also for $5n+2$) with $n\in \mathbb{N}$?
I know how to do it for primes of form $pn+1$ for any prime $p\geq 3$ ...
1
vote
3
answers
233
views
Perfect squares between certain divisors of a number
Let $n$ be a positive integer. We will call a divisor $d(<\sqrt{n})$ of $n$ special if there exists no perfect squares between $d$ and $\frac{n}{d}$. Prove that $n$ can have at-most one special ...
-2
votes
1
answer
168
views
Diophantine equation $10^n-a^3-b^3=c^2$
Consider the Diophantine equation:
$10^n-a^3-b^3=c^2$, for $a$, $b$, $c$, and $n$ positive.
Has this equation infinitely many solutions?
2
votes
2
answers
293
views
"Strengthening" the mean value theorem for the sine function
The present discussion arises from this MO question. Below, $e$ stands for Euler's number and let
$$\tau:=\arccos\left(\frac{\sin e-\sin 1}{e-1}\right)\approx 1.82\cdots.$$
An application of the Mean ...
6
votes
5
answers
889
views
Combinatorial proof of Catalan's identity
Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{...
4
votes
2
answers
429
views
Largest absolute value of a polynomial of degree $n$ on $\{0,1,\ldots,n\}$
Consider a polynomial $P_n(x)\in\mathbb{R}[x]$, of degree $n\geq1$, of the form
$$P_n(x)=c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}+x^n.$$
To illustrate the question, take $P_1(x)=c_0+x$ so that $P_1(0)=...
0
votes
1
answer
375
views
Can I get away without using Arzela-Ascoli?
I am currently thinking of function-valued random variables. In order to prove a result, I need to approximate by (function-valued) step functions. This naturally leads to the idea of chopping up the ...
0
votes
0
answers
163
views
Some questions in a paper by E. H. Neville (1949) about Farey series?
I am reading the paper
MR0029924: Neville, E. H. The structure of Farey series. Proc. London Math. Soc. (2) 51, (1949). 132–144. (Reviewer: W. H. Simons)
and by now two questions raised for me;
...
8
votes
2
answers
308
views
Area method in Lobachevskian geometry
There are many proofs in Euclidean geometry using the area method; for example, Ceva's theorem or the proof of Pythagorean theorem shown below.
Do you know such proofs in hyperbolic geometry?
I ...
1
vote
0
answers
109
views
The $p$-adic valuation of powers of consecutive integers
Let $n > 0, K > 0$ integers and, for $i \in \{1,...,n\}$, let $k_i$ and $l_i$ be integers such that $k_i + l_i = K$. Assume that for some $i,j \in \{1,...,n\}$ we have $k_i \neq k_j$.
Claim: ...
4
votes
2
answers
503
views
Squares in Lucas sequences
Good night, everyone!
According to a celebrated result by J. H. Cohn, the only perfect squares in the Fibonacci sequence are $F_{0}=0$, $F_{1}=F_{2}=1$, and $F_{12}=144$. It is also known that the ...
2
votes
0
answers
107
views
Average number of pieces of a random piecewise-linear function
Let $I$ be a (nonempty) compact interval in $\mathbb R$ and $a_1,b_1,\ldots,a_L,b_L \in \mathbb R$. Let $\varphi$ be a piecewise function with $T \ge 2$ pieces(for example $T=2$ for the choice $\...
2
votes
0
answers
211
views
Conjectured primality test for numbers of the form $N=4 \cdot 3^n-1$
This is a repost of this question.
Can you provide proof or counterexample for the claim given below?
Inspired by Lucas-Lehmer primality test I have formulated the following claim:
Let $P_m(x)=2^{...
3
votes
2
answers
468
views
Good upper bound for a certain sum
Given $\gamma \in [0, 1)$, an integer $N \ge 2$, and a decreasing null sequence of positive numbers $e_1,e_2,\ldots,e_t,\ldots$, I'm interested in estimating the sum $S_N := \sum_{t=1}^N\gamma^t e_{N-...
7
votes
2
answers
436
views
A set, product of any two elements minus one is a perfect square
The first problem of IMO 1986 asks the following:
Prove that, one can find two distinct $a,b$ in the set $\{2,5,13,d\}$ such that $ab-1$ is not a perfect square.
Note that, this proves, for the ...
2
votes
0
answers
56
views
Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$
Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...
So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
11
votes
1
answer
598
views
Diophantine equation $3^a+1=3^b+5^c$
This is not a research problem, but challenging enough that I've decided to post it in here:
Determine all triples $(a,b,c)$ of non-negative integers, satisfying
$$
1+3^a = 3^b+5^c.
$$
5
votes
1
answer
350
views
What was the first elementary proof that $\pi(x)=o(x)$?
Denote by $\pi(x)$ the number of primes $\leq x$. I'm interested in knowing who came up with the first elementary proof that $\pi(x)=o(x)$.
I know that Chebyshev demonstrated elementarily before ...
1
vote
1
answer
170
views
Formally proving that a metric is not induced by any norm in $\mathbb{R}^n$ [closed]
What is the procedure to formally prove that no norm exists in $\mathbb{R}^n$, that induces a metric $d$?
My first instinctive idea would be to show that $d$ is a metric in $\mathbb{R}^n$, but after ...
6
votes
2
answers
1k
views
Products and sum of cubes in Fibonacci
Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$.
Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
3
votes
0
answers
227
views
Reference for calculating definite integral involving sines
Recently I accidentally discovered a simple, elementary derivation of the following identity, valid for any $n,k \in \mathbb N$:
\begin{align*}
\frac1\pi \int_0^\pi {\rm d}x \left(\!\frac{\sin nx}{\...
13
votes
1
answer
1k
views
Is there an elementary proof that there are infinitely many primes that are *not* completely split in an abelian extension?
I'm currently in the middle of teaching the adelic algebraic proofs of global class field theory. One of the intermediate lemmas that one shows is the following:
Lemma: if L/K is an abelian ...
2
votes
1
answer
426
views
Partitioning the positive integers into finitely many arithmetic progressions
From Bóna's A Walk through Combinatorics:
Prove or disprove that if we partition the positive integers into finitely many arithmetic progressions then there will be at least one arithmetic ...
11
votes
3
answers
2k
views
Does anyone recognize this inequality?
In some paper the authors make use of the following inequality without further explanation: Let $x\in\mathbb{R}^n$ with $x_1\le\cdots\le x_n$ and $\alpha\in[0,1]^n$ with $\sum_{i=1}^n \alpha_i=N\in\{1,...
2
votes
1
answer
440
views
Good UPPER bounds for $\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i$ where $(p_i)_i$ is a probability vector
Let $x=(z_1,\ldots,z_n)$ be real vector and $(p_1,\ldots,p_n)$ be a probability vector.
Question
$\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i \le ???$
Observation
This paper allows us to ...
4
votes
2
answers
683
views
Is the following recursion formula for $\zeta(2n)$ known?
I have discovered (and found an elementary proof of) the following
$$\zeta(2k)=(-1)^{k-1}\dfrac{\pi^{2k}}{2^{4k}-2^{2k}}\left[k\dfrac{2^{2k}}{(2k)!}+{\displaystyle \sum_{l=1}^{k-1}(-1)^{l}\dfrac{2^{2k-...
11
votes
2
answers
376
views
Sum of squared nearest-neighbor distances between points in a square
Let $\square_2=\{(x,y): 0\leq x, y\leq1\}$ be the unit square in $\mathbb{R}^2$. Take $n>1$ points $P_1, \dots, P_n\in\square_2$.
Denote the distances $d_j=\min\{\Vert P_k-P_j\Vert: k\neq j\}$, ...
22
votes
15
answers
6k
views
Geodesics on the sphere
In a few days I will be giving a talk to (smart) high-school students on a topic which includes a brief overview on the notions of curvature and of gedesic lines. As an example, I will discuss flight ...
6
votes
2
answers
757
views
How often does the Mertens function vanish?
It is well known that the Mertens function
$$M(x)=\sum _{n\leq x}\mu(n)$$
has infinitely many zeros, and this seems to be a short proof.
Are there known results about how often the Mertens function ...
8
votes
4
answers
780
views
Different derivations of the value of $\prod_{0\leq j<k<n}(\eta^k-\eta^j)$
Let $\eta=e^{\frac{2\pi i}n}$, an $n$-th root of unity. For pedagogical reasons and inspiration, I ask to see different proofs (be it elementary, sophisticated, theoretical, etc) for the following ...
3
votes
2
answers
411
views
Prove that there exists a nonempty subset $ I$ of $ \{1,2,...,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer
Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...
9
votes
2
answers
720
views
Certain matrices of interesting determinant
Let $M_n$ be the $n\times n$ matrix with entries
$$\binom{i}{2j}+\binom{j}{2i}, \qquad \text{for $1\leq i,j\leq n$}.$$
QUESTION. Is this true? There is some evidence. The determinant $\det(M_{2n+1})...
24
votes
2
answers
3k
views
A Putnam problem with a twist
This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...
1
vote
0
answers
246
views
Supremum of an almost surely continuous random process
I was learning this proposition
and now I have a question, how to prove it for an almost surely continuous process? I would be very grateful for any tips.
12
votes
1
answer
371
views
A set of prime numbers
Consider a non-empty set $S$ of primes, with the property that, for every finite subset $S'\subset S$, all the primes dividing $\left(\prod_{k\in S'}k\right)+1$ are in $S$.
For instance, it can ...
2
votes
1
answer
82
views
On submatrices: size bound
Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$.
Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided
(a) $A$ is a $k\times k$ ...
2
votes
1
answer
401
views
Vandermonde determinant: modulo
There is a lot of fascination with the Vandermonde determinant and for many good reasons and purposes. My current quest is more of number-theoretic.
QUESTION. Let $p\equiv 3$ (mod $4$) be a prime. ...
3
votes
1
answer
321
views
Generating function for 3 -core partitions: Part II
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
8
votes
1
answer
458
views
Generating function for $3$-core partitions
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$.
We call $\lambda$ a $t$-core partition if none of ...
8
votes
2
answers
301
views
A link between hooks and contents: Part II
This is a question in the spirit of an earlier problem.
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$.
Recall also the notation for the content of a cell $...
8
votes
2
answers
264
views
A link between hooks, contents and parts of a partition
Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$.
...
17
votes
2
answers
916
views
Why are the medians of a triangle concurrent? In absolute geometry
This fact holds true in absolute geometry, and I would like to see an elementary synthetic proof not using the classification of absolute planes (Euclidean and hyperbolic planes) and specific models. ...
20
votes
1
answer
1k
views
A proof required for this identity [duplicate]
Experiments support the below identity.
Question. Is this true? Combinatorial proof preferred if possible.
$$\sum_{m=0}^n\binom{n-\frac13}m\binom{n+\frac13}{n-m}(1+6m-3n)^{2n+1}
=\left(\frac43\...
2
votes
1
answer
825
views
Primality test for generalized Fermat numbers
This question is successor of Primality test for specific class of generalized Fermat numbers .
Can you provide a proof or a counterexample for the claim given below?
Inspired by Lucas–Lehmer–Riesel ...
0
votes
1
answer
235
views
$2$-adic valuations and sum of divisor function
Consider the sum of $k^{th}$-power of divisors of $n$, denoted
$$\sigma_k(n)=\sum_{d\vert n}d^k.$$
Let $\nu_p(x)$ stand for the $p$-adic valuation of the integer $x$.
The following appears to be ...
10
votes
1
answer
676
views
Roots and relation between polynomials and their derivatives
This is probably easy but it might be interesting. Here goes $\dots$
Let $P\in\mathbb{R}[x]$ be a polynomial of degree $n>2$ and $P'=\frac{dP}{dx}$. If $x_1, x_2, \dots, x_n$ are the roots of $P(x)...
3
votes
1
answer
365
views
Primality test for specific class of $N=k \cdot b^n-1$
This question is successor of Compositeness test for specific class of $N=k \cdot b^n-1$ .
Can you provide a proof or a counterexample to the following claim :
Let $P_m(x)=2^{-m}\cdot \left(\left(...
1
vote
0
answers
191
views
Algebraic equivalence of cycles and Chow varieties
Let $p,d\geq 0$ be two integers and let $X\subseteq\mathbb{P}^N$ be acomplex projective variety. Denote the Chow variety of $X$ consisting of $p$-cycles of degree $d$ by $\mathcal{C}_{p,d}(X)$. I'm ...
10
votes
2
answers
901
views
Primality test for specific class of Proth numbers
Can you provide a proof or a counterexample for the following claim :
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)$
Let $N=k\cdot 2^n+1$ such ...