Some weeks ago the idea of making a daily math challenge thread gained popularity and then a guy started doing it, first with a problem about circles and then a problem about an integral with circles. Unfortunately he stopped, but I am here to save it.
Here is Today's problem:
Suppose that a sequence [math] a_1 , a_2 , a_3 , ... [/math] of positive real numbers satisfies:
[math] a_{k+1} \geq \frac{k a_k}{ (a_k)^2 + k - 1} [/math] for every positive integer [math] k [/math].
Prove that [math] a_1 + a_2 + ... + a_n \geq n [/math] for every [math] n \geq 2 [/math]
RULES: 1) If you have a proof, show full work. This means that: 2) The method of proof of leaving it as an exercise for the reader is invalid, for even the most trivial detail of your proof. 3) Everyone welcome, which means 4) You may tackle this problem in any way you see fit. The most elementary and the most complex methods will be praised equally. 5) When you post your solution, also tell us your major. Just for fun. 6) If you do not understand any detail of the problem, feel free to ask questions 7)Latex is encouraged but pictures of handwriting are also okay.
You didnt give a0? Or am I such a brainlet that I can't see that it's unnecessary to know?
Kevin Reyes
clever homework thread, but do it yourself
Brayden Morales
Great first equation.
First, there is no a0, our first term is a1. But that is not important.
Regarding the heart of your question, to solve this problem you do not need to know the first term. The "hard" part of the statement is that you need to prove that for ANY arbitrary first term, the theorem holds.
So for your proof you will have to assume an arbitrary a1 and prove it like that.
Hudson Wood
And obviously an induction proof is best applicable here.
Owen Hughes
Not a homework thread. This is a problem right from the international math olympiad. Not gonna tell you what year tho. I don't want anyone going to copy paste the solution given on the website.
Benjamin Diaz
Shit nigga IMOs pretty hard, maybe start with USAMO
Ethan Perry
But here we supposedly have university students from freshman to senior. And even some masters and PhDs students.
And the point is for it to be a challenge... and I've never heard of USAMO before.
Brody Foster
A sketchy answer [eqn] \frac{k}{a_k+ \frac{k-1}{a_k}} > \frac{ka_k}{k-1} > a_k [/eqn]If [math]a_1 \geq 1 [/math], we're done.[eqn] a_2 \geq \frac{1}{a_1}[/eqn]By AM-GM, [math]a_2+a_1 \geq 2[/math]. If [math]a_1 < 1[/math], [math]a_2 >1[/math], so [math] a_k > 1 [/math] for k >1 and so we're done
James Russell
We have retarded university students, that's the problem. To be fair though, I suppose IMOs do get harder every year
Andrew Williams
I just noticed that the first line is true only if k > 1 lol, but the reasoning still seems to hold
Aiden Wright
>If [math]a_1 \geq 1 [/math] , we're done.
Sure but that is the trivial case.
Remember that the first term is arbitrary and the only constraint is that it is a positive real number. So the first term could be 0.5 or 0.1111 or 0.0009
So either also prove that a first term smaller than 1 would contradict the theorem and therefore should not be considered or make an alternative proof for numbers smaller than 1 but larger than 0.
Jacob Myers
>make an alternative proof for numbers smaller than 1 but larger than 0 Aren't the last 2 lines proving that?
Brandon Edwards
Then something in your proof is wrong.
I know because I am computing the form that the ak have and if I consider the first term to be 0.5
Then a_3 is larger than or equal to 0.90909090...
So a_3 could be smaller than 1, considering a sequence where a_3 = 0.91 or 0.90909090,,,
Kevin Moore
Ah! Got something really interesting a(k+1)+a(k) is always greater or equal than 2 of a(k) is greater than 1.
Wyatt Turner
Oh wait, I haven't considered the case a_1 >= 1 properly
If a_1 = 0.5, that would imply that a_2 >= 1.5. a_3 is obviously > a_2 so how are you getting 0.91?
Brody Gray
Well, fuck it all. The first inequality is supposed to be in the other direction. Disregard my post
Thomas Young
Proof:
First consider the second term, given an arbitrary [math]a_1[/math], [math] a_2 = \frac{1}{a_1} + c [/math] where non-negative real number. However, for my proof I will assume c=0 and then if it works for c=0, it should work for all c larger than 0.
So we fix [math] a_1 + a_2 = a_1 + \frac{1}{a_1} [/math] and to prove the base case for an induction argument, consider:
Given any positive [math]a_1[/math], [math] a_1 + \frac{1}{a_1} \geq 2 [/math]
Which we can prove by multiplying both sides by [math]a_1[/math] and assuming it is positive (which means the order is preserved) you get the relation [math] (a_1 - 1)^2 \geq 0 [/math]
Which is true for ALL [math]a_1[/math], and because of our assumption, at least only for positive [math] a_1 [/math] which is all we need.
Then, through a lot of writing I found that if [math]S_n[/math] is the sum of all the terms from 1 to n then
[math] a_n \geq \frac{n-1}{S_{n-1}} [/math]
So now I can tackle the induction step.
Suppose that it is true that [math]S_n \geq n[/math]
and then fix [math] a_{n+1} \geq \frac{n}{S_n} [/math]
which implies [math] S_{n+1} \geq S_n + \frac{n}{S_n} [/math]
At the IMO you have approximately 90 mins to do each problem, right? If so, you did bretty gud timewise. Haven't read your shit, so it still might be wrong, though.
Someone post that legendarily hard IMO problem that appeared in Numberphile.
Zachary Perry
Quick question : is a1 positive ? The condition doesn't really seems to work if a1 is not > 0.
Robert Myers
By the description of the problem, our arbitrary sequence is strictly a sequence of positive real numbers. Therefore, the first term must be positive.
Alexander Parker
Btw OP I'm an psychology major. Sorry phone poster
Kayden Thomas
>probably always true
Good try but actually there are counterexamples.
The sequence
{0.5,2,0.8,0.91,238.055,...) is one that does contradicts this for the third and fourth term and is a valid sequence, given the problem's constraints.
Let [math]a[/math] and [math]b[/math] be positive integers such that [math]ab + 1[/math] divides [math]a^2 + b^2[/math] . Show that [math]\frac{a^2 + b^2}{ab+1}[/math] is the square of an integer.
Lincoln Sanchez
Okay just pretend I extended the base case to n =4
Ryder Gutierrez
>Okay just pretend I extended the base case to n =4
Then take the sequence
(0.9,1.2,0.99,0.997,0.9985,...)
Now the first, third, fourth and fifth term are smaller than 0.
Ayden Butler
Fuck, I tried a proof by induction and I'm fucked beyond belief
Luke Ortiz
You handwaved the most important part. You need the inductive assumption to get to
[math]a_n \geq \frac{n-1}{S_{n-1}}[/math]
Here:
[math]\frac{k a_k}{(a_k)^2+k-1} \geq 0[/math]
[math]k \geq a_k + \frac{k-1}{a_k}[/math]
Assume for induction that the sum of the sequence [math]S_k \geq k[/math]
[math]S_k \geq k \geq a_k + \frac{k-1}{a_k}[/math]
I feel, you. It is just that how I found that out was too long for latex. That said, I proved it like in the picture.
And that is nothing, really. To first notice the pattern I actually computed by hand the form of a6 in terms of a1 and then I was like oooooohhhhhhhhhhhhhhhh the pattern is so obvious.
Ayden Reed
Alright, I tried my hand at it and it seems I'm just a brainlet.
Basically I tried to prove that [math]a_{n+1} > 1[/math] but then concluded it was impossible if you don't use a trivial sequence (a1 = 1).
I'm also a bit sad because even I do find out, my proof will likely be a poor copypaste of those already posted.
Kevin Anderson
Don't be sad. This is an international math olympiad. Not being able to solve an IMO problem does not make you a brainlet.
That said, this problem was technically made for highschoolers. And not solving a highschool tier problem does make you a brainlet ;^)
Joseph Powell
>High-schoolers I want to know how many of them actually did it, though. And stop with that, I'm frustrated enough already.
Carter Gutierrez
>I want to know how many of them actually did it, though.
I took it from the 2015th math olympiad problems, the first one.
So a lot.
What is funny is that I also checked the answer provided by the website and it is completely different from my answer I found an alternative expression for the nth term of the sequence and then prove it like that.
They made like a list of inequalities and did some induction magic. I actually don't really understand their proof... but it is right.
Lucas Watson
Alright, I refuse to believe any high-schooler that wasn't spoonfed math all day actually did it. It's a nightmare to do.
Damn you Veeky Forums.
Liam Cook
The only person who participated in the IMO who I know things about is Terence Tao and if you read his life story it is literally the story of a kid who got spoonfed math since he was a child.
There is even a picture of himself when he looks like 5 and his tutor going over some textbook.
That guy proved his first conjecture before he popped his first boner. Which is good because if you haven't found your lifelong hobby before you get your first boner, odds are you are going to pick "getting rid of boners" as your lifelong hobby.
Tyler Gray
I don't consider that an healthy lifestyle at all, tb'h. It's frustrating, no matter what year I take, no matter what problem it is, I don't have the creativity to solve it. I need steps.
Fuck me, right ?
Gabriel Moore
How the fuck do they even come up with these problems
Charles Robinson
The problem is that you have no training.
What separates IMO participants from average students is the fact that they get logic training beforehand. Typical high school students do not get taught logical in a mathematics classroom. They get taught formulas.
IMO participants get tutors to teach them logic and then they also have a kind of "IMO summercamp" where they take you and teach you logic.
I heard that in China they take their kids and teach them a super complex method that can solve any geometry problem if you just put in variables such as distance of the points, angles, etc. so that then they can bruteforce geometry problems in the olympiad which they cannot solve traditionally.
These people basically get math steroids.
If you do not know logic (in mathematics, not some philosophy garbage) then you pretty much cannot deal with problems made to test the limits of your knowledge.
I can solve it now... because I already took logic in university. Could I have solved it in high school? Probably not.
So if you want to get "creative" then learn that creativity is a meme and go read any book about mathematical logic.
Grayson Fisher
>If you do not know logic (in mathematics, not some philosophy garbage) Both have their merits. I've always been interested by both math and philosophy/humanities.
So, it's about formal logic, like (grossly simplifying) p -> q and the rest ? I'm trying to read a book about it. It's really austere.
Bentley Wood
They may both have their merits, but logic outside of mathematics doesn't really have applications. At least not for solving problems.
>So, it's about formal logic, like (grossly simplifying) p -> q and the rest ? I'm trying to read a book about it. It's really austere.
Pretty much. Logic is important. I don't know if you've been following this thread but if you see this answer you'll see there are a lot of "if and only if" signs ([math] \iff [/math]) and those look good but they also show how the person is untrained. "If and only if" signs are not to be thrown around mindlessly and most of those signs are not only unjustified, but also completely wrong. Clearly the person, despite knowing the usual notation and having a fine grasp on how to use it, does not truly understand the logic behind the argument he himself is trying to construct, and that is why in the end he was wrong. As was pointed out by some counter examples.
I don't mean this to bash the guy, but that is usually the difference between IMO participants and normal students. Those people would not dare write down a single "if and only if" without two lines of justification. And those who do it know that those signs are wrong and do not belong there, but they do it in hopes of bluffing. I've done it quite a few times in tests and I always get marked down.
Thanks, I corrected myself. I feel kinda shameful about I proved that the function needed to be linear. I used a taylor series and showed that for the series to exist, it would need to have f''(x) = 0 for any x, f'''(x) = 0 for any x, etc...
Dominic Sanchez
Damn, I forgot (as usual) to do actual computation of small terms to find a nicer relation. Going the typical, naive route, I could at best show the relation holds so long as a_k was between 1 and k-1 for all k > 2, which wasn't helpful at all.
I have a good Indian friend who participated in IMOs while in high school (he also did the physics ones). He won some gold and silver medals there, but I've surpassed him in some regards when it comes to math since he went on to study other things. Don't let these sort of things get you down - competition math is very different from research math. If you want to study competition math then you should pick up a textbook on it (e.g. Putnam and Beyond, Problem Solving through Problems) but understand that it will be tough to work through them on your own without previously training.
Christopher King
Oh, and with regards to Terence Tao: He is a real outlier, and a real genius. If he was spoonfed math, then he was holding the spoon. There is a document somewhere that details his growth (apparently there are people who keep records of child prodigies) and you should read it; I wouldn't consider his lifestyle unhealthy whatsoever. I would also be hesitant to say that those who study for competition math have unhealthy lifestyles - they generally pursue it to such a high competition level because they enjoy it.
Haha, I think "logic" is quite an unrelated course for solving that problem.
Zachary Hall
>Haha, I think "logic" is quite an unrelated course for solving that problem.
Obviously not full logic but the "basics". What you would see in an introductory course about logic and proofs. What does an implication mean, what does an equivalency mean. How you can tell an argument is correct, etc.
You can get the best typica algebra student in the world. The guy who whenever has to find the roots of a polynomial, applies the formula perfectly. The guy who memorized 500 algebra identities for his tests. And ask him to do this problem, and he would not be able to.
This is a proof, this is a theorem. A kid like that would not in a million years be able to construct a logical argument that is sound. And much less could he spot his own logical mistakes whenever he makes one. So whenever he makes an unfounded assumption, he wouldn't be able to tell and he would go on. He would present an argument so full of holes and so badly connected that one could barely call it an argument.
James Murphy
The sort of logic you're speaking of is typically covered in a discrete math course or one's first upper division math course. (If you decided to compete, you probably learned it sooner). That logic is obviously essential, and I think anyone who even wants to try and understand the statement of this problem possesses that logic "training." What's necessary for these sorts of problems is heuristics.
Ryan Howard
>The sort of logic you're speaking of is typically covered in a discrete math course or one's first upper division math course.
And they definitely do not teach in that high school classrooms. Hell, they didn't even teach it to me. I learned all that in uni like a sucker.
And lets also be real in saying that most people who go through these courses would still not be able to solve this problem. This is why I stressed the tutors and the special training they give to the selected children go to participate. It is on another level.
You do not learn elementary logic and then prove this, you learn elementary logic and then get your tutor to ass rape you with problems until you can write proofs while drunk and then MAYBE you can give IMO problems a shot.
