DAILY MATHS CHALLENGE #2

Previous threads:
I've prepared one Calculus and one Number Theory problems for now. If they are both solved I'll post others.
Starting from tomorrow I think I'll try and do one hard problem a day with the field of study depending on the weekday like some user suggested. Other problems are very much welcome. It would be cool if during the weekend we could have one roundup thread where no one posted any more problems but we attempted all unsolved questions from that week and someone archived the whole thing.

Other urls found in this thread:

en.wikipedia.org/wiki/Distributive_property#Definition
mathworld.wolfram.com/Distributive.html
twitter.com/NSFWRedditVideo

And the NT problem.

For the calc one:
For each n >= 1, [math]x_{n+1}^3 = x_n^3 + 1 + \frac{1}{3x_n^3} + \frac{1}{27x_n^6}[/math]. Hence, we can write [math]x_n^3 \ge n + \sum_{j=1}^{n-1}\frac{1}{3x_j^3}[/math].
To complete the proof, we need only prove that [math]\sum_{j=1}^{n-1}\frac{1}{x_j^3}[/math] is unbounded. But we have [math]x_{n+1}^3 \le x_n^3 + 3[/math], hence [math]\forall n \ge 1, x_n^3 \le 3n[/math].
Finally, we get [math]\sum_{j=1}^{n-1}\frac{1}{x_j^3} \ge \sum_{j=1}^{n-1} \frac{1}{3j}[/math], which concludes.

Good initiative. I'll gladly ponder both problems. Too few people in this board value problem-solving over memes

different insight (which is overkill but meh)
The sequence is trivially increasing and unbounded (boundedness would yield convergence to 0, which is a contradiction),
hence [math]\frac{1}{x_n} [/math] converges to 0.
Note that [eqn] \begin{align} x_{n+1}^3 &= \left(x_n + \frac{1}{3 x_n^2} \right)^3\\
&=x_n^3\left( 1+\frac{1}{3x_n^3}\right)^3\\
&=x_n^3 \left(1 + \frac{1}{x_n^3}+o\left(\frac{1}{x_n^3}\right) \right)\\
&=x_n^3+1+o(1)
\end{align}[/eqn]
Hence [math] x_{n+1}^3-x_n^3[/math] converges to 1 and Cesaro mean theorem yields [math]x_n^3 = n+o(n)[/math].

Since [math] x_{n+1}^3 = x_n^3 + 1 + \frac{1}{3x_n^3} + \frac{1}{27x_n^6} [/math], [math]x_{n+1}^3 = n+1 + \frac 13 \sum_{k=1}^n \left( \frac 1{x_k^3} + \frac 1{3x_k^6}\right) [/math]
and it suffices to prove that [math] \sum_{k=1}^n \left( \frac 1{x_k^3} + \frac 1{3x_k^6}\right)[/math] is unbounded which is clear since [math]\frac 1{x_n^3} = \frac{1}{n} + o\left( \frac{1}{n} \right) [/math]

Its only true for all even Numbers M. We can write a(k) for a generall M as a(0) for another M'=M^(2k), so we only have to look at the first iteration. Wich only gets integer if M is even

wrong, for example with [math]M=9[/math], [math]a_4 = 2789204756584545 [/math]

Ok, its not completely correct, but the general idea should be right, ill write the Tex when i get home

This is true for M equal to all numbers in the union of the following sets:

S[1] = {2, 4, 6, 8, ...}
S[2] = {3, 7, 11, 15, ...}
S[3] = {5, 13, 21, 29, ...}
S[4] = {9, 25, 41, 57, ...}
...
S[n] = 2S[n-1] - 1
...

Which might be the entire set of natural numbers excluding 1, but I don't know for sure.

I've proved there's an integer term for any M which is not [math] 1 \pmod 4[/math], but I'm stumped dealing with the case [math] 1 \pmod 4[/math] ...

That's where I am too, I'm guessing you have to separate the case M = 1 mod 8 and M = 5 mod 8.
Presumably the M=5 mod 8 case will be easy to prove directly and then we have to look mod 16 for the M=1 mod 8, etc.

I hope you understand you're not working with infinite series.

That's because it works for all integers not [math] \equiv_{4} 1 [/math]. Consider some [math] x \in \mathbb{Z} [/math] such that [math] x \equiv_{4} 1 [/math]. So [math] x = 4k+1,k\in \mathbb{Z} [/math]. This implies [math] a_0 = \frac{8k+3}{2} [/math]. ... I was going somewhere with this, but I can't quite put it into words that other people would be able to follow. The idea is to show that the floor term is always 1 modulo 4, so the numerator will always remain 3 modulo 8, preventing the floor from ever being even, which produces the integer term of the sequence.

samefag, that'll work.
We'll prove by induction that for each [math]k \ge 1[/math], if [math]M \equiv 2^{k-1} + 1 \mod 2^k[/math], then (a_n) has an integer term.
Case k=1: We write [math]M = 2q[/math]. Then, [math]a_1 = \frac{2q+1}{2}[/math] and [math]a_2 = q(2q+1) \in \mathbb N[/math].

Now, assume it's true for some [math]k \ge 1[/math] and let [math]M = 2^{k+1}q+2^k+1[/math]:
We write [math]a_2 = \frac{(2^{k+2}q+2^{k+1}+3)(2^{k+1}q+2^k+1)}{2} = \frac{2N+1}{2}[/math], where the numerator satisfies [math]2N+1 \equiv 3(2^k +1) \equiv 2^k+3 \mod 2^{k+1}[/math], and thus [math]N \equiv 2^{k-1}+1 \mod 2^k[/math]. Hence, by induction hypothesis, the sequence [math](a_{k+1})_{k \ge 1}[/math] contains an integer term.
But each integer M greater than 1 satisfies [math]M \equiv 2^{k-1}+1 \mod 2^k[/math] for some [math]k \ge 1[/math].
Indeed, if [math]k = \min\{k \ge 1, M \not \equiv 1 \mod 2^k\}[/math], then since [math]M \equiv 1 \mod 2^{k-1}[/math] by definition, we can write [math] M = 2^{k-1}q + 1[/math].
Then, since [math]M \not \equiv 1 \mod 2^k[/math], we have [math]2 \not | q[/math]. Hence we can write [math] q = 2 q'+1[/math] and finally [math]M = 2^kq' + 2^{k-1} + 1[/math].
Hence, for each integer M > 1, the sequence (a_n) with a_1 = (2M+1)/2 has an integer term.
It doesn't for M=1 since it is constant with value 3/2.

I do, but I'm not sure I understand where you're going with this

would anyone suggest a basic book on proofs to me?

I would love to learn how to solve stuff like this.

Here's a calc problem since both previous problems have been solved:
Let [math]f: [a,b] \to \mathbb C[/math] a piecewise continuously differentiable function. Assume [math]f(a) = f(b) = 0[/math] and [math]|f'(x)| \le M[/math] wherever it makes sense.
Prove that [math]\displaystyle \left|\int_a^b f(t)dt\right| \le M\frac{(b-a)^2}{4}[/math].
What's the equality case ?

does it involve the taylor expansion?

i think the equality case would be a triangle-shaped piecewise linear function.

Yes, also I wanted to clarify what I mean by piecewise continuously differentiable: by that I mean a continuous function that is an antiderivative of a piecewise continuous function

that's right ! got a proof ?

Provide a bijection of (0, 1) into [0, 1].

It's possible.

Let
[math] N=\{ \frac{1-3^{-k}}{2}, 3^{-k}+\frac{1-3^{-k}}{2} \mid k\in \mathbb{N}\cup \{0\} \} [/math]
[math] M=[0,1]-N [/math]

and so we get the bijection
[math] \varphi: [0,1] \to (0,1)[/math] defined by
[math] \varphi(x)= \begin{cases} (x+1)/3 & x \in N \\ x & x \in M \end{cases} [/math]

Send 0 to 1/2, 1 to 1/3, 1/n to 1/(n+2) for each n >= 2 and leave everyone else fixed. That gives you a bijection from [0,1] to (0,1).
An interesting follow-up question might be to prove that you can't find a continuous bijection, one way or the other

How did you come up with such a convoluted formulas? Did you know the answer already?

>How did you come up with such a convoluted formulas?
an algorithmic proof of Cantor–Schröder–Bernstein

>Did you know the answer already?
yes i posted the same bijection a week or so ago

its not really that convoluted, you just contract the endpoints along an infinite sequence similarly to the way did and leave the rest fixed

What's a continuous bijection?
> an algorithmic proof of Cantor–Schröder–Bernstein
So basically picrel?

Well a bijection [math]f: [0,1] \to (0,1)[/math] (or the other way around) that is also a continuous function in the usual sense

yes basically

1 to 0.9 to 0.99 to 0.99 etc
0 to 0.1 to 0.11 to 0.11 etc
Everything else the same

Easy.

Let [math] K [/math] be an algebraic system with two binary operations (one written additively, the other multiplicatively), satisfying:

(1) [math] K [/math] is an abelian group under addition,
(2) [math] K - \{0\} [/math] is a group under multiplication, and
(3) [math] x(y+z) = xy + xz [/math] for all [math] x, y, z \in K [/math] .

Suppose that for some [math] n [/math] , [math] 0 = 1 + 1 + ... + 1 [/math] ( [math] n [/math] times). Prove that, for all [math] x \in K [/math] , [math] (-1)x = -x [/math] .

Suppose such an function f exists. If f mapped [0,1] to (0,1) this would imply (0,1) is compact. Similarly if f mapped (0,1) to [0,1] it would imply that the inverse image of [0,1] under f is closed, which it clearly is not.

In fact you only need that f is a surjection, injection is unnescessary.

>Similarly if f mapped (0,1) to [0,1] it would imply that the inverse image of [0,1] under f is closed, which it clearly is not.
It's closed in (0,1), there's no contradiction. You need more.

Injection is unnecessary for the [0,1] -> (0,1) case, but it's necessary for the (0,1) -> [0,1] case (you can find continuous surjections from (0,1) to [0,1])

Ok so if the bijection from (0,1) to [0,1] was continuous then it would imply the inverse is continuous which is not.

yup

needs fresher material, not old kacysnski papers posted so recently

You get a cookie for identifying the provenance. :^)

I notice, however, that you also have not proffered a solution.

its more fun doing questions youve never seen before

Assuming the function is continuously differentiable, and [math]0\leq a\leq b[/math],
integration by parts yields [eqn]\left|\int_a^b f(t)dt\right| = \left|\int_a^b tf'(t)dt\right|\leq M\frac{b^2-a^2}2 [/eqn] which is not as sharp as what's required (because of my additional assumptions on f)

That's not the reason it wasn't as sharp as what's required, you just went a wee bit too fast ;)
Also, don't worry, you can integrate by parts under the weaker hypothesis I put, but there's a way of finding this identity that does not require you to integrate by parts

yes, my estimate can be sharpened with a variational method. Since [math]\int_a^b f'(t)dt =0[/math], for any [math]\alpha[/math] we have
[eqn]\left|\int_a^b f(t)dt\right| = \left|\int_a^b (t-\alpha)f'(t)dt\right|\leq M \int_a^b |t-\alpha| dt [/eqn]
Some calculus or educated guess shows that [math]\alpha=\frac{a+b}2[/math] minimizes [math]\int_a^b |t-\alpha| dt [/math] and plugging in [math]\alpha=\frac{a+b}2[/math] yields the result

Very nice, quite different from my solution but I like yours better because it puts the problem in a larger context.
Mine was a collection of tricks:
Using Fubini and the fundamental theorem of calculus, we rewrite:
[math]\displaystyle \int_a^b f(t)dt = \int_a^b \int_a^t f'(u) du dt = \int_a^b (b-u)f'(u)[/math]
[math]\displaystyle \int_a^b f(t)dt = - \int_a^b \int_t^b f'(u) du = \int_a^b (a-u)f'(u)du[/math]
And hence:
[math]\displaystyle \int_a^b f(t) dt = \int_a^b \left(\frac{a+b}{2}-u\right) f'(u)du [/math]
And then [math]\displaystyle \left|\int_a^b f(t) dt \right| \le \int_a^b |f'(u)| \left| \frac{a+b}{2}-u\right| du \le M \frac{(b-a)^2}{4}[/math]
The equality case in the second inequality is when |f'| is equal to M, and the equality case in the first inequality is exactly when f' and a+b/2-u have opposite signs, which tells us that a function that satisfies the equality case must be symmetric relative to a+b/2 and triangle shaped

Alright, my turn to suggest a problem

This one is from the latest issue of the College Mathematics Journal. You can submit your solution until February iirc

1 is gonna become 1 after continuum worth of being functioned. So no. Retarded piece of shit.

You've misused Fubini's Theorem in lines 1 and 2, and your integral in the fourth line converges to 0. The inequality is still valid however.

The Fourth line actually converges to ab, which may or may not be greater than or equal to the upper bound presented In the problem.

I meant -ab. Without the constraint that both a and b are greater than or equal to 0, the inequality doesn't necessarily hold.

>You've misused Fubini's Theorem in lines 1 and 2
How ? [math]\displaystyle \int_a^b \left(\int_a^t f'(u)du\right)dt = \int_a^b \left(\int_u^b f'(u)dt\right) du[/math]

>The Fourth line actually converges to ab
what ?

Hmm I can't make it till the end...

Fubini's Theorem doesn't permit you to integrate dt over the domain of du. dt strictly corresponds to the domain a to b and du from a to t.

> The Fourth line ...
Do the integral.

Nevermind about the fourth line; I'm retarded.

hint for a compsci person whose never taken algebra?

what additional structure would you normally need to prove (-1)*x=-x without that strange identity 0 = 1+....+1?

It's not "the domain of dt" (or I'm not understanding you right). Let's see it with an extra step:
[eqn]\int_a^b \left(\int_a^t f'(u)du\right) dt = \int_a^b \left(\int_a^b 1_{u \le t}f'(u) du \right) dt \underset{Fubini}{=} \int_a^b \left(\int_a^b 1_{u \le t}f'(u) dt \right) du = \int_a^b \left(\int_u^b f'(u) dt \right) du[/eqn]

You normally use left-distributivity, ie. (x+y)z = xz + yz. Here all you have is right-distributivity

What you normally use is that:
>Assotiativity of addition
>Existence of a neutral element of addition
>Existence of additive inverses of all elements
>Existence of a neutral element of multiplication
>Right distributivity
For all x in K we have
x + (-1)*x
= 1*x + (-1)*x
= (1 + (-1))*x
= 0*x
= 0*x + 0
= 0*x + (0*x + (-(0*x)))
= (0*x + 0*x) + (-(0*x))
= (0+0)*x + (-(0*x))
= 0*x + (-(0*x))
= 0.
Analogously (-1)*x + x = 0.
Therefore (-1)*x = -x.

Pardon me, but you have confused left-distributivity with right-distributivity. Kaczynski's problem only gives you an instance of left-distributivity, and not right-distributivity as you just stated.

en.wikipedia.org/wiki/Distributive_property#Definition

mathworld.wolfram.com/Distributive.html

in each case, it is the /thing outside the parentheses/ which can informally be said to "distribute" across the two-term expression contained inside. That thing's position is where these two names come from, not the position of the two-term thing inside. After all, the thing inside the parentheses has not more than one term to "distribute" to, in the primitive case of the definitions!

i had done it this way:

(1+-1)x = x + -x
x + (-1)x = x + -x
(-1)x = -x

...

autism

i guess the obvious thing that follows from 0=1+...+1 is that any element, combined n times with itself using + is zero, so you have

-x+....+-x = (-1)x + .... + (-1)x

but i can't figure how to make the extra terms go away.

this is tough. any way that you use 0 = 1+....+1 you end up with a mess of extra terms that are hard to deal with.

how long is the proof?