# Thread: Extracurricular Elementary Mathematics Marathon

1. ## Re: Extracurricular Elementary Mathematics Marathon

$First, we look at the second assertion. The number of primes in the set I_n(x)=\{x+1,x+2,\ldots,x+n\} is given by g_n(x):=\pi(x+n)-\pi(x) for any non-negative integer x.\\ \\ If we look at the shifted interval I_n(x+1) instead, we might lose a prime from no longer having x+1 in our set, and we might gain a prime from adding x+n+1 to our set. \\ \\It might also be the case that both or neither of these things happen. In any case, the main point is that g_n(x+1)-g_n(x) can either be 0,-1 or 1. Ie the function g_n(x) takes steps of size at most 1. \\ \\ By the discrete intermediate value theorem, it then suffices to show that for each n, we can find an x_n with g_n(x_n)=0 (as we trivially have g(0)=\pi(n), so every integer between 0 and \pi(n) must then lie in the range of g.)\\ \\ Proving this fact also establishes the first assertion, so we can now kill these two birds with the one stone next post.$

2. ## Re: Extracurricular Elementary Mathematics Marathon

(It suffices to show that pi(x)=o(x), which is a quite weak statement about the distribution of the primes that can be proved by a completely elementary sieving process. Am just thinking of the cleanest way to write this. Will post shortly.)

3. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
$First, we look at the second assertion. The number of primes in the set I_n(x)=\{x+1,x+2,\ldots,x+n\} is given by g_n(x):=\pi(x+n)-\pi(x) for any non-negative integer x.\\ \\ If we look at the shifted interval I_n(x+1) instead, we might lose a prime from no longer having x+1 in our set, and we might gain a prime from adding x+n+1 to our set. \\ \\It might also be the case that both or neither of these things happen. In any case, the main point is that g_n(x+1)-g_n(x) can either be 0,-1 or 1. Ie the function g_n(x) takes steps of size at most 1. \\ \\ By the discrete intermediate value theorem, it then suffices to show that for each n, we can find an x_n with g_n(x_n)=0 (as we trivially have g(0)=\pi(n), so every integer between 0 and \pi(n) must then lie in the range of g.)\\ \\ Proving this fact also establishes the first assertion, so we can now kill these two birds with the one stone next post.$
Ahh yes, that was the other way to do it, but that was meant to be the second part to the problem. My intended solution was to use the fact that n! has n-1 obvious factors, and exploit that to construct an arithmetic progression strictly consisting of composite numbers, which is a lot easier to prove.

4. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
(It suffices to show that pi(x)=o(x), which is a quite weak statement about the distribution of the primes that can be proved by a completely elementary sieving process. Am just thinking of the cleanest way to write this. Will post shortly.)
$Let S_p be the set of natural numbers indivisible by p. \\ \\ It is trivial that \frac{|S_p\cap [1,n]|}{n}\rightarrow 1-\frac{1}{p} as n\rightarrow\infty.\\ \\ Moreover, since primes are pairwise coprime, we have \frac{|(\cap_{k=1}^m S_{p_k})\cap [1,n]|}{n}\rightarrow \prod_{k=1}^m \left(1-\frac{1}{p_k}\right).\\ \\ As this quantity for a given m is telling us the proportion of numbers that are indivisible by any of the first m primes, in the limit as n\rightarrow\infty this gives us an m-dependent upper bound for the proportion of primes.$

$However:\\ \\\prod_{k=1}^m \left(1-\frac{1}{p_k}\right)=\prod_{k=1}^m \left(\sum_{j=0}^\infty \frac{1}{p_k^j}\right)^{-1}=\left(\sum_n \frac{1}{n}\right)^{-1}\\ \\ where the final summation is taken over all n whose only prime factors lie in the set \{p_1,\ldots,p_m\}. By the divergence of the harmonic series, we can make this quantity arbitrarily small by taking m sufficiently large.\\ \\ In other words, the proportion of the first n positive integers that are prime must tend to zero.$

$Now if for some m, every collection of m consecutive integers contained a prime, that would imply that the proportion of primes in the first n positive integers would have to be at least 1/m in the limit n\rightarrow\infty. This is impossible by what we just proved, and hence we are done.$

5. ## Re: Extracurricular Elementary Mathematics Marathon

(And yes, this is strictly more work than one needs to do to answer your original question, where a construction using a factorial explicitly gives us prime gaps of length blah. I just did it this way because I personally wanted to see how "low-tech" I could make a proof of the fact that the primes have density zero. )

Stronger statements about prime distribution are also very much within the scope of MX2 level techniques.

One such example is Bertrand's postulate, which states that there is at least one prime strictly between n and 2n for any positive integer n greater than 1.

This will be harder for a HS student to do without guidance, but I encourage any interested student to think about it / have a crack at it.

6. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Solve completely over \mathbb{N} . \\a) y^2 = (x-2)2^{x-1}+1 \\ b) y^2 = (x-1)2^x+1$

7. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Here's a set of simpler problems, all doable with infinite descent: \\ Note: all solutions must be in \mathbb{N} \\ a^2 + b^2 = 3c^2 \\ x^3 +2y^3 = 4z^3 \\Simultaneous Equations: a^2 + 6b^2 = p^2 and b^2 + 6a^2 = q^2$

8. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Show that there exist arbitrarily long sub-intervals of the natural numbers that contain no primes.\\Hence, show that amongst the natural numbers, there will always be a sub-interval of length n containing k prime numbers for all \pi(n) \geq k \geq 0, where \pi(n) is the prime counting function, which denotes the number of primes in the interval (1,n).$
$\noindent Discrete Intermediate Value Theorem: \\ For all \{a,b\} \in \mathbb{Z}, \; azz
This wording means that the question is now valid, before you said that any subinterval of length n contained a subinterval of k primes (pi(x)>k>0), which was clearly not true and hence I was confused. I would normally post my solution, but Seanieg89 has already done so and mine was pretty similar except in the part where you had to prove that there exists a subinterval with 0 primes.

$\noindent Solve completely over \mathbb{N} . \\a) y^2 = (x-2)2^{x-1}+1 \\ b) y^2 = (x-1)2^x+1$
$Part a). Testing x =1\rightarrow5, we obtain (x,y): (2,+-1), (5,+-7) (0 isn't natural number).\\(y+1)(y-1)=y^2-1=(x-2)2^{x-1}\ So, the the RHS has two factors which differ by 2 \Rightarrow |2^ac-2^bd|=2 \ where a+b=x-1 and cd=x-2.a,b,c,d all natural. |2^{a-1}c-2^{b-1}d|=1. a,b cannot both exceed 1(RHS is odd) so we consider 2 cases. Case 1: a=1 and b\geq1. Then, |\frac{x-2}{d}-2^{x-3}d|=1 \Rightarrow \ x-2-2^{x-3}d= \pm d. \\ x-2=2^{x-3}d^2 \pm d. But for x>5, RHS \geq 2^{x-3} \pm 1>2^{x-3}-1.>x-2, contradiction. (Last inequality from calculus) Case 2: a=0, b\geq0. By following a similar method as case 1, we reach: 2^{x-1}d^2 \pm d=x-2. But for x>3 LHS> 2^{x-1}-1>x-2, contradiction. By symmetry, we've dealt with the cases where b=0 and a\geq0, or b=1 and a\geq1. Thus, no solution exists for x>5, and so our solution set is (x,y): (2,+-1), (5,+-7) \\ Part b) is part a with all the x solutions dropped by 1, so we now have (1,+-1), (4,+-7).$

9. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Here's a set of simpler problems, all doable with infinite descent: \\ Note: all solutions must be in \mathbb{N} \\ a^2 + b^2 = 3c^2 \\ x^3 +2y^3 = 4z^3 \\Simultaneous Equations: a^2 + 6b^2 = p^2 and b^2 + 6a^2 = q^2$
$a^2+b^2=3c^2. Suppose there exists a natural solution (a,b,c) to this. Since the quadratic residue mod 3 is 0 or 1, the equation can only hold if a and b are both divisible by 3 (otherwise LHS would be 1 or 2 mod 3 whilst the RHS is 0 mod 3). So, a=3k, b=3j, c=3l, 9k^2+9j^2=3(9l^2). Dividing through by 9, we find that (k,j,l) is a smaller natural solution. By Fermat's method of descent, there are no natural solutions. \\ x^3+2y^3=4z^3. Similar to first q, 2|x, and thus 2|y as 4|RHS and x^3 is even. But since the LHS is then divisible by 8, so is the RHS, so 2|z. (\frac{x}{2},\frac{y}{2}, \frac{z}{2}) is a smaller natural solution, and thus there are no natural solutions. \\ Adding both equations, 7(a^2+b^2)=p^2+q^2. Since the quadratic residue of 7 is 0,1,2,4, and the LHS is 0 mod7, 7 must divide both p and q. This implies that 7|a,b so (a/7,b/7,p/7,q/7) is a smaller natural solution, so no natural solutions exist.$

10. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by Blast1
$a^2+b^2=3c^2. Suppose there exists a natural solution (a,b,c) to this. Since the quadratic residue mod 3 is 0 or 1, the equation can only hold if a and b are both divisible by 3 (otherwise LHS would be 1 or 2 mod 3 whilst the RHS is 0 mod 3). So, a=3k, b=3j, c=3l, 9k^2+9j^2=3(9l^2). Dividing through by 9, we find that (k,j,l) is a smaller natural solution. By Fermat's method of descent, there are no natural solutions. \\ x^3+2y^3=4z^3. Similar to first q, 2|x, and thus 2|y as 4|RHS and x^3 is even. But since the LHS is then divisible by 8, so is the RHS, so 2|z. (\frac{x}{2},\frac{y}{2}, \frac{z}{2}) is a smaller natural solution, and thus there are no natural solutions. \\ Adding both equations, 7(a^2+b^2)=p^2+q^2. Since the quadratic residue of 7 is 0,1,2,4, and the LHS is 0 mod7, 7 must divide both p and q. This implies that 7|a,b so (a/7,b/7,p/7,q/7) is a smaller natural solution, so no natural solutions exist.$
You've solved a lot of problems, maybe post your own?

11. ## Re: Extracurricular Elementary Mathematics Marathon

A bit on the easier side, but just to get the ball rolling in this thread again:

A function g(n) defined on the non-negative integers satisfies:

i) g(0)=g(1)=0.

ii) g(p)=1 if p is prime.

iii) g(mn)=m*g(n)+n*g(m) for all non-negative integers m and n.

Find all n such that g(n)=n.

---------------------------------------

A somewhat harder followup question is proving that the sequence obtained by:

u(0)=63
u(n+1)=g(u(n))

tends to infinity.

12. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
A bit on the easier side, but just to get the ball rolling in this thread again:

A function g(n) defined on the non-negative integers satisfies:

i) g(0)=g(1)=0.

ii) g(p)=1 if p is prime.

iii) g(mn)=m*g(n)+n*g(m) for all non-negative integers m and n.

Find all n such that g(n)=n.

---------------------------------------

A somewhat harder followup question is proving that the sequence obtained by:

u(0)=63
u(n+1)=g(u(n))

tends to infinity.
Ahh, arithmetic derivative, I have not seen you in a while.

I'll work on this later today if I get time. Otherwise, someone else can do it.

13. ## Re: Extracurricular Elementary Mathematics Marathon

$The problem amounts to solving the infinite diophantine equation:$

$\frac{a_1}{2}+\frac{a_2}{3}+\frac{a_3}{5}+\frac{a_ 4}{7}+\frac{a_5}{11}+\frac{a_6}{13}+\frac{a_7}{17} +\frac{a_8}{19}+\cdots+\frac{a_k}{p_k}+\cdots = 1$

$Over the naturals.$

$Which I'm not sure is any easier or harder. I think it's harder.$

$A trivial class of solutions is p_k^{p_k}$

$p_k is the k^{\text{th}} prime number.$

$Anyone else got any ideas?$

14. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Suppose u_n = 2^4*k for some integer k. Applying the so-called arithmetic derivative, we have u_{n+1} =2^4(2k+k')>2^5*k. This shows that each term, is strictly at least twice as large as the previous term. u_5 is the first term to contain a fourth power of two, and hence, this sequence diverges into infinity.$

15. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Suppose u_n = 2^4*k for some integer k. Applying the so-called arithmetic derivative, we have u_{n+1} =2^4(2k+k')>2^5*k. This shows that each term, is strictly at least twice as large as the previous term. u_5 is the first term to contain a fourth power of two, and hence, this sequence diverges into infinity.$
Good, you have done the harder part of the question .

It remains to determine the exact solutions of g(x)=x but you are super close.

16. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
Good, you have done the harder part of the question .

It remains to determine the exact solutions of g(x)=x but you are super close.
And you said it was harder. :P

I don't see how I can possibly bash this question.

Trying to come up with some way to restrict the solutions but nothing I think of will work.

17. ## Re: Extracurricular Elementary Mathematics Marathon

And you said it was harder. :P

I don't see how I can possibly bash this question.

Trying to come up with some way to restrict the solutions but nothing I think of will work.
I still think it is.

18. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
I still think it is.

Well I'm not sure if my mathematical rigor is exact, but here goes.

Suppose we had a solution with more than one of the numbers not equal to zero. However, if we multiply all the denominators up onto the other side, we would have an arbitrarily large set of congruences that are all equal to zero on the right hand side, but not equal to zero on the left hand side, as each term on the left hand side is not divisible by one of the primes on the right hand side. this leads to an impossible set of residues, and we have a contradiction. Thus, the only solutions that can exist are for exactly one of the integers equal to it's denominator, and every other term equal to zero. This verifies the class of solutions I mentioned earlier, and we are done.

19. ## Re: Extracurricular Elementary Mathematics Marathon

Exactly, although worded slightly funny. The point is that the j-th term on the LHS MUST be divisible by p_j as every other term trivially is.

This means that each a_j must be a non-negative integer multiple of p_j. (Because we do not get a prime factor of p_j in this term from multiplying out the denominators.)

I.e we have a finite ordered collection of non-negative integers summing to 1. The only way for this to happen is for one of these integers to be 1 and the others to be zero.

This lets us draw the desired conclusion.

20. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent 1. \forall n \in \mathbb{N} , prove \frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n-1} \geq n (\sqrt[n]{2}-1) (AM-GMed by seanieg98)\\ 2. Prove (2n-1)!\geq n^n (inducted by Integrand) \\ 3. Prove that for every integer x, \frac{x^5}{5}+\frac{x^3}{3}+\frac{7x}{15} is also an integer. (modulo-ed by KingOfActing) \\ 4. Prove for all n >1, \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots \frac{2n-1}{2n}<\frac{1}{\sqrt{3n}} (case bashed by seanieg98)\\ 5. Find all integer pairs (x,y) that satisfy x^3+y^3 = (x+y)^2 (WLOGGED by seanieg98)\\ 6. Solve for all f(x) the following functional equation: f(f(x)+y) = x+y (Solved simultaneously by Integrand and seanieg98)\\ 7. 2(n^{2n}) > (2n)! (AM-GMed by seanieg98)$

21. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent 1. \forall n \in \mathbb{N} , prove \frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{2n-1} \geq n (\sqrt[n]{2}-1) \\ 2. Prove (2n-1)!1, \frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdots \frac{2n-1}{2n}<\frac{1}{\sqrt{3n}} \\ 5. Find all integer pairs (x,y) that satisfy x^3+y^3 = (x+y)^2 \\ 6. Solve for all f(x) the following functional equation: f(f(x)+y) = x+y$
I'm pretty new to this stuff, but I think I can do 3.

$\frac{x^5}{3} + \frac{x^3}{5} + \frac{7x}{15} being an integer is equivalent to 3x^5+5x^3+7x being divisible by 15, aka divisble by both 5 and 3. For divisibility by 3 we work mod 3. The case x \equiv 0 \mod{3} is trivial, as it is a factor of the polynomial.\\In the other case, x^2 \equiv 1 \mod{3} and hence \\3x^5 + 5x^3+7x \equiv 3x + 5x + 7x \equiv 15x \equiv 0 \mod{3} \\and so is divisble by 3. \\Now working mod 5, the case x \equiv 0 \text{ mod 5 is again trivial. Else, by Euler's theorem, } \\x^{\varphi(5)} = x^4 \equiv 1 \mod{5}\\Hence:\\3x^5 + 5x^3 + 7x \equiv 3x + 5x^3 + 7x \equiv 5(x^3+2x)\equiv 0\mod{5} \\ and hence is divisible by 5. This completes the proof.$

edit: Now that I think about it, Euler's Theorem is total overkill. Just note that x can be congruent to -2, -1, 0, 1 or 2 mod 5. After dealing with the 0 case, the +-1 cases have x^4 = 1, and the +-2 cases have x^4 = 16 which is congruent to 1 mod 5.

Also, since this is supposed to be a an elementary thread, if anyone hasn't done modular arithmetic yet, note that it is sufficient to make sure the statement holds true for x = 0,1,...,14. I don't think it can get any more elementary than that.

22. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Here's a proof by induction for 2.$

$\noindent The result is clearly true for n=1, since then, LHS =(2-1)! = 1! =1, and RHS = 1^1 = 1 = LHS.$

$\noindent Now, suppose that the result holds for some particular positive integer n, so that we have (2n-1)! \geq n^n. We need to show that (2n+1)! \geq (n+1)^{n+1}. We have$

\begin{align*}LHS &= (2n+1)(2n)(2n-1)! \\ & \geq (2n+1)(2n) n^n \quad (\text{by the inductive hypothesis}).\end{align*}

$\noindent So the claim that LHS \geq (n+1)^{n+1} will be implied by (2n+1)(2n) \geq \frac{(n+1)^{n+1}}{n^n}, which is equivalent to (2n+1)(2n) \geq \left(\frac{n+1}{n}\right)^n \cdot (n+1). But this is true, since 2n \geq n+1, and$

\begin{align*}\left(\frac{n+1}{n}\right)^n=\left (1+\frac{1}{n}\right)^n &= \sum_{k=0}^n \binom{n}{k}\frac{1}{n^k} \quad (\text{binomial theorem}) \\ &= \sum _{k=0}^n \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k!}\cdot n^k \\ &= \sum _{k=0}^n \frac{1\cdot \left(1-\frac{1}{n}\right)\cdot \left(1-\frac{2}{n}\right)\cdot \cdots \cdot \left(1-\frac{k-1}{n}\right)}{k!}\\ &< \sum _{k=0}^n \frac{1}{k!} \\ &\leq \sum _{k=0}^n 1 \quad \\ &= n+1 \\ &< 2n+1 \quad \forall n\in \mathbb{Z}^+.\end{align*}

$\noindent It follows by the principle of mathematical induction that the given inequality is true for all positive integers n, with equality iff n=1.$

23. ## Re: Extracurricular Elementary Mathematics Marathon

$1.\\ \\ LHS+n=\sum_{k=0}^{n-1} \left(1+\frac{1}{n+k}\right)\\ \\ =\sum_{k=0}^{n-1} \frac{n+k+1}{n+k}\\ \\ \leq n\left(\prod_{k=0}^{n-1} \frac{n+k+1}{n+k}\right)^{1/n} = n\cdot 2^{1/n}.$

24. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
$1.\\ \\ LHS+n=\sum_{k=0}^{n-1} \left(1+\frac{1}{n+k}\right)\\ \\ =\sum_{k=0}^{n-1} \frac{n+k+1}{n+k}\\ \\ \leq n\left(\prod_{k=0}^{n-1} \frac{n+k+1}{n+k}\right)^{1/n} = n\cdot 2^{1/n}.$
For those who have no idea what just happened, this was a case of algebraic manipulation and one application of the AM-GM Inequality.

25. ## Re: Extracurricular Elementary Mathematics Marathon

$LHS^2=\prod_{k=1}^n \left(\frac{2k-1}{2k}\right)^2 \\ \\= \frac{1}{2}\cdot\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\frac{5}{6}\cdot\frac{7}{8}\cdot\frac{7}{8}\cdot\frac{9}{10}\cdot\frac{9}{10}\cdot\frac{11}{12}\cdot \left(\frac{11}{12}\cdot\frac{13}{14}\right)\cdot\left(\frac{13}{14}\cdot\frac{15}{17}\right)\ldots \left(\frac{2n-3}{2n-2}\cdot \frac{2n-1}{2n}\right)\cdot \frac{2n-1}{2n}\\ \\ < \left(\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\frac{5}{6}\cdot\frac{7}{8}\cdot\frac{7}{8}\cdot\frac{9}{10}\cdot\frac{9}{10}\cdot\frac{11}{12}\right)\cdot \left(\frac{12}{13}\cdot\frac{13}{14}\right)\cdot\left(\frac{14}{15}\cdot\frac{15}{17}\right)\ldots \left(\frac{2n-2}{2n-1}\cdot \frac{2n-1}{2n}\right)\\ \\ < \left(\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\frac{5}{6}\cdot\frac{7}{8}\cdot\frac{7}{8}\cdot\frac{9}{10}\cdot\frac{9}{10}\cdot\frac{11}{12}\right)\cdot \frac{12}{2n}$

$=\frac{43659}{131072n}<\frac{1}{3n}.$

This establishes the claim for all n larger than 6.

Verifying the inequality for the five values of n between 2 and 6 with a calculator or by hand completes the proof.

Page 2 of 4 First 1234 Last

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•