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
1
vote
0answers
74 views

Primality test for specific class of $N=8kp^n-1$

My following question is related to my question here 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+\...
5
votes
1answer
206 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 $\...
4
votes
0answers
216 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
3answers
167 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
1answer
138 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
2answers
252 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 ...
5
votes
4answers
469 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
2answers
279 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
0answers
47 views

Exponential sums involving completely multiplicative functions

It is well-known that exponential sums is used as a tool from the analytic number theory to optimize or to compute asymptotic formulas. My question is the following: Given a completely multiplicative ...
0
votes
1answer
217 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
0answers
211 views

Number of distinct terms in the dRRS for n

For OEIS sequence A061498, the "Number of distinct terms in the first difference sequence of reduced residue system[=dRRS] for n", I am wondering if there is a simple proof that this sequence is ...
0
votes
0answers
142 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
2answers
229 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
0answers
86 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: ...
3
votes
1answer
146 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
0answers
85 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
0answers
179 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
2answers
366 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
2answers
348 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
0answers
50 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
1answer
542 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
1answer
316 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
1answer
98 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
2answers
815 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
0answers
202 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}{\...
11
votes
1answer
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
1answer
337 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 ...
12
votes
3answers
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,...
1
vote
1answer
66 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
2answers
458 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-...
10
votes
2answers
254 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
15answers
4k 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
2answers
445 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 ...
7
votes
4answers
733 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 ...
2
votes
2answers
314 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
2answers
612 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})...
21
votes
2answers
2k 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
0answers
94 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.
10
votes
1answer
295 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
1answer
77 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
1answer
318 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
1answer
254 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
1answer
219 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 ...
7
votes
2answers
197 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 $...
6
votes
2answers
159 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)$. ...
16
votes
2answers
472 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. ...
21
votes
1answer
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\...
1
vote
1answer
640 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
1answer
172 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 ...
9
votes
1answer
595 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)...