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.'

Filter by
Sorted by
Tagged with
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{...
Pedja's user avatar
  • 2,673
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$ ...
User2020201's user avatar
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 ...
user154024's user avatar
-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?
Enzo Creti's user avatar
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 ...
T. Amdeberhan's user avatar
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_{...
user avatar
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)=...
T. Amdeberhan's user avatar
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 ...
Daron's user avatar
  • 1,761
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; ...
asad's user avatar
  • 841
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 ...
Anton Petrunin's user avatar
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: ...
Daniel W.'s user avatar
  • 365
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 ...
Jamai-Con's user avatar
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 $\...
dohmatob's user avatar
  • 6,716
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^{...
Pedja's user avatar
  • 2,673
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-...
dohmatob's user avatar
  • 6,716
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 ...
hookah's user avatar
  • 1,096
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 ...
dohmatob's user avatar
  • 6,716
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. $$
hookah's user avatar
  • 1,096
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 ...
Q_p's user avatar
  • 824
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 ...
user avatar
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 ...
T. Amdeberhan's user avatar
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}{\...
Dierk Bormann's user avatar
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 ...
Alison Miller's user avatar
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 ...
VRS's user avatar
  • 39
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,...
Robert Rauch's user avatar
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 ...
dohmatob's user avatar
  • 6,716
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-...
user avatar
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\}$, ...
T. Amdeberhan's user avatar
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 ...
Roberto Frigerio's user avatar
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 ...
Basj's user avatar
  • 577
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 ...
T. Amdeberhan's user avatar
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 ...
color's user avatar
  • 169
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})...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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.
Staysy's user avatar
  • 21
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 ...
hookah's user avatar
  • 1,096
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$ ...
T. Amdeberhan's user avatar
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. ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 $...
T. Amdeberhan's user avatar
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)$. ...
T. Amdeberhan's user avatar
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. ...
Fedor Petrov's user avatar
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\...
T. Amdeberhan's user avatar
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 ...
Pedja's user avatar
  • 2,673
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 ...
T. Amdeberhan's user avatar
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)...
T. Amdeberhan's user avatar
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(...
Pedja's user avatar
  • 2,673
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 ...
Vincenzo Zaccaro's user avatar
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 ...
Pedja's user avatar
  • 2,673