# Extracurricular Elementary Mathematics Marathon (1 Viewer)

##### -insert title here-
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.

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.

#### seanieg89

##### Well-Known Member
And you said it was harder.

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.

##### -insert title here-
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.

#### seanieg89

##### Well-Known Member
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.

##### -insert title here-
$\bg_white \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)$

Last edited:

#### KingOfActing

##### Well-Known Member
$\bg_white \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.

$\bg_white \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.

Last edited:

#### InteGrand

##### Well-Known Member
$\bg_white \noindent Here's a proof by induction for 2.$

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

$\bg_white \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$

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

$\bg_white \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$

\bg_white \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*}

$\bg_white \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.$

Last edited:

#### seanieg89

##### Well-Known Member
$\bg_white 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}.$

##### -insert title here-
$\bg_white 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.

#### seanieg89

##### Well-Known Member
$\bg_white 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}$

$\bg_white =\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.

##### -insert title here-
$\bg_white 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}$

$\bg_white =\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.
Wow... you're so bothered to type up all that ... My solution consisted of creating an intermediate inequality and inducting on that.

#### seanieg89

##### Well-Known Member
Wow... you're so bothered to type up all that ... My solution consisted of creating an intermediate inequality and inducting on that.
Just went with the immediate idea that popped into my head, didn't take long to tex/compute.

If you want a weaker constant than 1/sqrt(3) (like 1/sqrt(2) for instance) then the same method as above gets you immediate results without needing to go several terms into the product before doing the telescoping.

##### -insert title here-
Just went with the immediate idea that popped into my head, didn't take long to tex/compute.

If you want a weaker constant than 1/sqrt(3) (like 1/sqrt(2) for instance) then the same method as above gets you immediate results without needing to go several terms into the product before doing the telescoping.
The intermediate inequality you induct on is placing 1/sqrt(3n+1) between the two. It may seem arbitrary but the problem is that the right hand side doesn't shrink fast enough for an inductive proof to be able to compare the two sides.

#### seanieg89

##### Well-Known Member
$\bg_white 5. It is clear that x=-y is a solution for any integer y. We now assume x+y\neq 0 and so we can divide by this to reduce our equation to x^2+y^2-xy=x+y. \\ \\ The reason this is promising is that for x and y large, the LHS should grow a lot faster than the RHS and equality should be impossible.\\ \\ Indeed: LHS\geq x^2+y^2-\frac{x^2+y^2}{2}=\frac{x^2+y^2}{2}.\\ \\ Now if |t|>2, then t^2/2>t, so we cannot have both |x| and |y| larger than 2. \\ \\ As the equation is symmetric, we might as well assume without loss of generality that |y|\leq |x| (keeping in mind that we need to symmetrise the solution set we end up with after this assumption).\\ \\ We now need to simply find the solution set for the 5 possible values of y.\\ \\ y=0 \Rightarrow x^3=x^2 \Rightarrow x=1.\\ \\ y=1 \Rightarrow x^2=x+2 \Rightarrow x=-2,2\\ \\y=-1\Rightarrow (x^2+2)(x-1)=x^3-x^2+2x-2=0 \Rightarrow x=1\\ \\ y=2 \Rightarrow (x-2)(x+2)(x-1)=x^3-x^2-4x+4=0 \Rightarrow x=\pm 2$

$\bg_white y=-2 \Rightarrow (x^2+4)(x-1)=0 \quad \textrm{(no solutions)}.\\ \\ Symmetrising this solution set completes the problem.$

#### seanieg89

##### Well-Known Member
$\bg_white 7. \\ \\(2n)!^2=4n^2 \prod_{k=1}^{2k-1} k(2n-k)\\ \\ \leq 4n^2 \prod_{k=1}^{2n-1} n^2=4n^{4n}.\\ \\ where the inequality came from applying AM-GM to each factor in the product.\\ \\ Taking square roots of both sides completes the proof.$

#### seanieg89

##### Well-Known Member
You should probably specify the domain of the functional equation you posted Paradoxica. It it the reals?

Assuming this is the case (and in fact this working is also valid if the domain is the integers, rationals or complex numbers), then:

6/

Let x=0 and let y=-f(0)+z, so

f(z)=f(f(0)+y)=y=-f(0)+z.

This implies that all solutions are of the form f(z)=z+c for some constant c.

However, if we apply this formula to our original functional equation, we get:

x+y+2c=x+y.

Hence c must be zero, and the only solution to the functional equation is the identity function f(x)=x.

Last edited:

#### InteGrand

##### Well-Known Member
$\bg_white \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) (done by seanieg98)\\ 2. Prove (2n-1)!\geq n^n (done by Integrand) \\ 3. Prove that for every integer x, \frac{x^5}{5}+\frac{x^3}{3}+\frac{7x}{15} is also an integer. (done 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 \\ 6. Solve for all f(x) the following functional equation: f(f(x)+y) = x+y \\ 7. 2(n^{2n}) > (2n)!$
$\bg_white \noindent 6. Bit rushed since I need to go for a bit but I hope it's right. We have f:\mathbb{R}\to \mathbb{R}, with f(f(x)+y) = x+y, for all x,y\in \mathbb{R}.$

$\bg_white \noindent Let y=0, then f(f(x)) =x for all real x. Hence f is an involution from \mathbb{R}\to \mathbb{R}. In other words, it is a bijection with f=f^{-1}. Now, applying f=f^{-1} to both sides of f(f(x)+y) = x+y gives f(x) + y = f(x+y). Now, for x,t\in \mathbb{R}, let y\equiv t-x, so x+y = t. Then f(x) + (t-x) = f(t) for all x,t\in \mathbb{R}. So f(x)-f(t)=x-t for all t,x\in \mathbb{R}. Let t=0, then f(x)-f(0) = x \Rightarrow f(x)=x+f(0). Since we have an involution, we must have f(0) = 0. So f(x) = x for all x\in \mathbb{R}. (It is easy to check this does also satisfy the equation.)$

Edit: done above

#### seanieg89

##### Well-Known Member
Lols, mega procrastination on my behalf. Am supposed to be brushing up on something for a supervisor meeting. These questions are fun though.

##### -insert title here-
$\bg_white \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)$
And we are done!

someone else post next, I've had my due run for the time being.

#### seanieg89

##### Well-Known Member
1. Does there exist a non-constant polynomial P(x) with integer coefficients such that P(k) is prime for every positive integer k?